Python Built-in Data Structures

Python's built-in data structures provide fundamental container abstractions essential for organizing data in programming. They support ordered sequences, unique collections, and key-value associations. The primary built-in structures include lists, tuples, ranges, sets, frozensets, and dictionaries. Each differs in semantics regarding ordering, mutability, uniqueness, indexing, membership, hashing, and access. Understanding these differences is crucial for selecting the appropriate structure for a given task.

Foundations of Python Built-in Data Structures

Python's built-in data structures conceptually fall into three principal families: sequences, sets, and mappings. Each family models a distinct kind of relationship among contained objects.

• Sequences represent ordered collections where position matters. Elements can be accessed by zero-based indices, supporting slicing and iteration that respects order. Lists, tuples, and ranges belong here.
• Sets represent unordered collections of unique elements. They emphasize membership testing and mathematical set operations like union and intersection. Sets and frozensets are members of this family.
• Mappings represent key-to-value associations, where keys uniquely identify values without positional indexing. Dictionaries are the primary built-in mapping type.

Choosing a data structure depends on the semantic relationship you need to represent: positional order (sequences), uniqueness without order (sets), or key-value associations (mappings).

These data structures vary independently along several properties:

• Mutability: Whether elements or the container can be changed after creation.
• Ordering: Whether the container preserves element order.
• Membership testing: How efficiently and by what semantics membership is tested.
• Indexing: Whether elements can be accessed by position or key.
• Iteration: The order and method of traversing contained elements.
• Hashability: Whether the container or its elements can be used as keys or set elements.

Python containers hold references to objects rather than copies. This has important consequences:

• Aliasing: Multiple containers or variables can reference the same object, so changes to mutable objects affect all references.
• Nested mutable structures: Containers can nest mutable objects, making shallow copies share referenced objects and mutations observable across aliases.
• Shallow vs. deep copying: Copying a container copies references but not the nested objects themselves.

The following table compares core Python built-in container types across these dimensions:

# Creating representative instances
lst = [1, 2, 3, 2]
tpl = (1, 2, 3, 2)
rng = range(1, 4)
st = {1, 2, 3, 2}
frz = frozenset([1, 2, 3, 2])
dct = {'a': 1, 'b': 2, 'c': 3}

containers = [lst, tpl, rng, st, frz, dct]

for c in containers:
    print(f"Type: {type(c).__name__}")
    print(f"Length: {len(c)}")
    print(f"Elements: ", end="")
    for e in c:
        print(e, end=" ")
    print()
    print(f"Membership test for 2: {2 in c}")
    print("-" * 30)

Python Built-in Sequence Types

Sequences in Python are collections of ordered elements that support zero-based indexing, negative indexing (counting from the end), slicing, iteration, membership testing, and length retrieval. Each element's position is meaningful, and sequences preserve insertion order.

Individual sequence types differ primarily in mutability and supported operations:

• Lists are mutable sequences supporting element assignment, insertion, and deletion.
• Tuples are immutable sequences that cannot be changed after creation.
• Ranges represent immutable sequences of integers defined by arithmetic progressions, optimized for memory efficiency.

Sequence Slicing

Slicing extracts a subsequence from a sequence using start, stop, and step values:

• start is inclusive (default 0).
• stop is exclusive (default sequence length).
• step defines the increment (default 1).

Omitted bounds default to sequence start or end. Negative indices count from the sequence end, and negative steps reverse iteration direction. Empty slices result when start and stop do not define a valid traversal.

Slicing returns a new sequence of the same type (or a closely related type), distinct from selecting a single element by index.

Common Sequence Operations

Sequences support several common operations:

• Concatenation (+) joins two sequences.
• Repetition (*) duplicates a sequence multiple times.
• Membership (in) tests for element presence.
• Minimum/maximum retrieve smallest or largest elements (where meaningful).
• Counting (count) returns the number of occurrences of a value.
• Index discovery (index) returns the first position of a value.

Support and complexity of these operations can vary across sequence types.

Sequence Packing and Unpacking

Packing collects multiple values into a sequence, while unpacking distributes sequence elements into multiple variables, respecting order. Starred unpacking can capture multiple elements into a single target.

lst = [10, 20, 30, 40, 50]
tpl = (10, 20, 30, 40, 50)
rng = range(10, 60, 10)

print(f"lst[0]: {lst[0]}")            # Indexing
print(f"tpl[-1]: {tpl[-1]}")          # Negative indexing
print(f"rng[1:4]: {list(rng[1:4])}")  # Slicing

print(f"20 in lst? {'20' in lst if isinstance(lst[0], str) else 20 in lst}")  
print(f"30 in tpl? {30 in tpl}")
print(f"40 in rng? {40 in rng}")

print("Iterating over list:")
for x in lst:
    print(x, end=" ")
print()

# Unpacking
a, b, *rest = lst
print(f"a={a}, b={b}, rest={rest}")

Python List Type

Python lists are mutable ordered sequences of references to objects. They can contain heterogeneous elements, repeated references, nested structures, and their size can change dynamically.

List Construction

Lists can be created by:

• Literals: [1, 2, 3]
• Iterable conversion: list(iterable)
• Derived patterns: list comprehensions, slicing, or concatenation produce new lists.

Assigning a list to a new variable creates another name (alias) for the same list; to create a new list, a copy must be made.

Indexing, Slicing, and Assignment

Lists support accessing elements by index and slices. Elements or slices can be replaced by assignment:

• Single element assignment replaces one item.
• Slice assignment can replace, insert, or remove multiple elements depending on the slice bounds and right-hand iterable length.

Adding Elements

• append(obj) adds one element at the end.
• extend(iterable) adds each element from an iterable individually.
• insert(index, obj) inserts one element at a specified position.

Removing Elements

• remove(value) removes the first occurrence of a value.
• pop(index) removes and returns element at index (default last).
• clear() removes all elements.
• del statement can remove elements or slices.

Reordering and Copying

• reverse() reverses the list in place.
• sort() sorts the list in place.
• sorted(list) returns a new sorted list.
• Slicing with [:] creates shallow copies.
• copy() returns a shallow copy.

Sorting supports keys and reverse ordering, and it is stable.

Aliasing and Nested Mutability

Multiple variables can reference the same list (aliasing). Nested mutable objects inside lists can be shared, so mutations affect all references.

lst = [3, 1, 4, 1, 5]
print("Original list:", lst)

lst[1] = 9
print("After index assignment:", lst)

lst[2:4] = [2, 6]
print("After slice assignment:", lst)

lst.append(7)
print("After append:", lst)

lst.extend([8, 9])
print("After extend:", lst)

lst.insert(0, 0)
print("After insert:", lst)

lst.remove(9)
print("After remove:", lst)

popped = lst.pop()
print("After pop:", lst, "; popped:", popped)

lst.reverse()
print("After reverse:", lst)

lst.sort()
print("After sort:", lst)

# Aliasing and shallow copying
a = [1, 2, [3, 4]]
b = a           # alias
c = a.copy()    # shallow copy

b[0] = 10
print("a after b[0]=10:", a)

c[2].append(5)
print("a after c[2].append(5):", a)
print("c:", c)

Python Tuple Type

Tuples are immutable ordered sequences. They are constructed primarily by comma-separated expressions; parentheses are optional except for empty or single-element tuples.

• One-element tuple syntax requires a trailing comma: (1,).
• Parentheses often group expressions but do not always define tuples.

Immutability

Tuple elements cannot be replaced, inserted, or removed after creation. However, tuples may contain references to mutable objects whose state can change.

Packing and Unpacking

Tuples support packing multiple values into one tuple and unpacking into variables. Nested and starred unpacking are supported.

Tuples are commonly used for:

• Fixed-position records.
• Returning multiple values from functions.

Operations

Tuples support indexing, slicing, concatenation, repetition, and comparison. They are hashable only if all elements are hashable.

empty = ()
one = (42,)
multi = (1, 2, 3)

print("Empty tuple:", empty)
print("One-element tuple:", one)
print("Multi-element tuple:", multi)

print("Indexing multi[1]:", multi[1])
print("Slicing multi[1:]:", multi[1:])

packed = 1, 2, 3
print("Packed tuple:", packed)

a, b, c = packed
print("Unpacked:", a, b, c)

nested = (1, [2, 3], 4)
nested[1].append(5)
print("Tuple with mutable element:", nested)

# Using tuple as dictionary key
key = (1, 'a')
d = {key: "value"}
print("Dictionary lookup with tuple key:", d[key])

Choosing tuples or lists depends on:

• Whether mutability is needed.
• Whether hashability is required (tuples can be keys).
• Semantic meaning: tuples represent fixed collections, lists mutable sequences.

Python Range Type

range represents an immutable sequence of integers defined by start, stop, and step parameters. It does not materialize all elements but generates values on demand, offering memory efficiency.

Construction

• One argument: range(stop) creates 0 to stop-1.
• Two arguments: range(start, stop) creates from start to stop-1.
• Three arguments: range(start, stop, step) with step positive or negative.
• Stop is exclusive.
• Step cannot be zero.
• Empty ranges occur if progression cannot advance.

Operations

Ranges support indexing (including negative), slicing (resulting in another range), membership, length, and iteration.

Equality

Two ranges compare equal if they represent the same integer sequence, even if constructed differently.

r1 = range(1, 5)
r2 = range(1, 6, 1)
r3 = range(5, 0, -1)
r4 = range(5, 1, -1)

print("r1:", list(r1))
print("r2:", list(r2))
print("r3:", list(r3))
print("r4:", list(r4))

print("r1 == range(1,5):", r1 == range(1, 5))
print("r1 == r2:", r1 == r2)

print("Indexing r1[2]:", r1[2])
print("Negative indexing r1[-1]:", r1[-1])

print("Slicing r4[1:3]:", list(r4[1:3]))

print("3 in r1:", 3 in r1)
print("10 in r3:", 10 in r3)

Ranges are preferable when representing arithmetic sequences without needing full materialization. Use lists when mutability or full random access is required.

Python Built-in Set Types

Python provides unordered collections of unique hashable elements called sets, designed for membership testing and mathematical set operations rather than positional access.

Hashability Requirements

Set elements must be hashable, meaning they have stable hash values and consistent equality semantics. Mutable types like lists are not allowed as elements.

Mutable vs Immutable Sets

• set: mutable, supports element addition, removal, and in-place set operations.
• frozenset: immutable, supports membership and set algebra but no mutation methods; can be hashable and used as dictionary keys or set elements.

s = {1, 2, 3, 3, 2}
fs = frozenset([1, 2, 2, 3])

print("Set with duplicates removed:", s)
print("Frozenset with duplicates removed:", fs)

print("Membership 2 in set:", 2 in s)
print("Membership 4 in frozenset:", 4 in fs)

print("Iterating set:")
for e in s:
    print(e, end=" ")
print()

print("Iterating frozenset:")
for e in fs:
    print(e, end=" ")
print()

Python Set Type

Sets are constructed by:

• Literals: {1, 2, 3}
• Iterable conversion: set(iterable)

Empty sets require set() because {} creates an empty dictionary.

Mutation Methods

• add(elem): inserts one element.
• update(iterable): inserts elements from an iterable.

Removal Methods

• remove(elem): removes element, raises KeyError if missing.
• discard(elem): removes element if present, no error if missing.
• pop(): removes and returns an arbitrary element.
• clear(): removes all elements.

Set Operations

• Union: set1 | set2 or set1.union(set2)
• Intersection: set1 & set2 or set1.intersection(set2)
• Difference: set1 - set2 or set1.difference(set2)
• Symmetric difference: set1 ^ set2 or set1.symmetric_difference(set2)

Subset and Superset Tests

• issubset, issuperset methods and operators.
• Proper subset/superset distinctions.
• Equality and disjointness testing.

In-place Updates

• Intersection update: set1 &= set2
• Difference update: set1 -= set2
• Symmetric difference update: set1 ^= set2
• update() can add elements.

s = {1, 2, 3}
s.add(4)
print("After add:", s)

s.update([5, 6])
print("After update:", s)

s.remove(6)
print("After remove:", s)

s.discard(10)  # no error if missing
print("After discard missing element:", s)

elem = s.pop()
print(f"Popped element: {elem}")
print("Set after pop:", s)

s.clear()
print("After clear:", s)

a = {1, 2, 3}
b = {2, 3, 4}

print("Union:", a | b)
print("Intersection:", a & b)
print("Difference:", a - b)
print("Symmetric difference:", a ^ b)

print("a is subset of b?", a <= b)
print("a is superset of b?", a >= b)
print("a is disjoint with b?", a.isdisjoint(b))

Sets are useful for deduplication, membership tracking, and relational algebra but should not be used for positional or ordered data access.

Python Frozenset Type

frozenset is the immutable counterpart to set. It is constructed from an iterable and supports membership testing and non-mutating set operations.

Because it is hashable (if its elements are hashable), frozensets can be used as dictionary keys or elements of other sets.

Set algebra operations with frozensets return the most appropriate type; mixing mutable and immutable sets requires care to understand result types.

fs1 = frozenset([1, 2, 3])
fs2 = frozenset([2, 3, 4])

print("frozenset 1:", fs1)
print("frozenset 2:", fs2)

print("Union:", fs1 | fs2)
print("Intersection:", fs1 & fs2)
print("Difference:", fs1 - fs2)
print("Symmetric difference:", fs1 ^ fs2)

# Using frozenset as dictionary key
d = {fs1: "set1", fs2: "set2"}
print("Dictionary with frozenset keys:", d)

try:
    fs1.add(5)
except AttributeError as e:
    print("Mutation attempt error:", e)

# Creating new frozenset rather than mutating
fs3 = fs1 | frozenset([5])
print("New frozenset after union:", fs3)

Immutable sets are useful for fixed unordered collections, nested set-like structures, cache keys, and contexts requiring hashability.

Python Dictionary Type

Dictionaries are mutable mappings from unique hashable keys to arbitrary object values. Keys identify associations rather than positions, and values need not be unique or hashable.

Construction

Dictionaries can be created by:

• Literals: {'a': 1, 'b': 2}
• dict() constructor: with iterable key-value pairs or keyword arguments.
• Comprehensions: {k: v for ...}

Ordering

Dictionaries preserve insertion order for iteration and views, but this is not a sorted order or positional indexing.

Operations

• Length, key membership, and iteration (over keys).
• Equality and copying.
• Nested dictionaries as values.
• Aliasing and shallow copying share mutable values.

Merging and Updating

• update() method and |= operators mutate.
• | operator creates a new dictionary merging two mappings.

d1 = {'a': 1, 'b': 2}
d2 = dict(c=3, d=4)
d3 = dict([('e', 5), ('f', 6)])

print("d1:", d1)
print("d2:", d2)
print("d3:", d3)

for key in d1:
    print(f"Key: {key}, Value: {d1[key]}")

print("Is 'a' in d1?", 'a' in d1)

# Copying and nested values
nested = {'x': [1, 2]}
d4 = {'nested': nested}
d5 = d4.copy()
d5['nested'].append(3)
print("Original nested list after append:", nested)

# Merging dictionaries
d6 = d1.copy()
d6.update(d2)
print("Merged dictionary:", d6)

Dictionary Key Semantics in Python

Dictionary keys must be hashable: their hash and equality semantics define key identity. Lookup combines hashing with equality testing to find associated values.

• Objects that compare equal must have compatible hash values to maintain consistent dictionary behavior.
• Immutable built-in types such as strings, numbers, tuples (with hashable elements), and frozensets can serve as keys.
• Mutable containers like lists, sets, and dictionaries cannot be keys because their hashability is not stable.

Distinct-looking numeric keys that compare equal and share hashes identify the same dictionary entry. For example, integer 1 and Boolean True compare equal and share a hash, referring to the same key.

Hash collisions occur when different keys share a hash value but remain distinct if they compare unequal, preserving dictionary correctness.

d = {}

# Valid keys
d["key"] = "value"
d[42] = "answer"
d[(1, 2)] = "tuple key"
d[frozenset({3, 4})] = "frozenset key"

print("Dictionary:", d)

# Unhashable key attempt
try:
    d[[1, 2, 3]] = "list key"
except TypeError as e:
    print("Error adding list key:", e)

# Numeric keys equal
d[True] = "bool key"
d[1] = "int key"
print("Value for True key:", d[True])
print("Value for 1 key:", d[1])

# Distinct keys with same hash
class Key:
    def __init__(self, x):
        self.x = x
    def __hash__(self):
        return 42
    def __eq__(self, other):
        return False

k1 = Key(1)
k2 = Key(2)
d[k1] = "k1"
d[k2] = "k2"
print("Distinct keys with same hash:", d[k1], d[k2])

Dictionary Access and Mutation in Python

Lookup

• d[key] retrieves value or raises KeyError if key is missing.
• d.get(key, default) returns value or default if key missing, without inserting.

Insertion and Replacement

• d[key] = value inserts or replaces an association.
• Assigning to an existing key updates the value.

setdefault

• d.setdefault(key, default) returns existing value if present; otherwise inserts default and returns it.
• Mutating: inserts new key-value if missing.

Updating

• d.update(other) merges another mapping or iterable of pairs.
• d |= other operator merges in-place.

Deletion and Extraction

• del d[key] removes key, raises if missing.
• d.pop(key[, default]) removes and returns value, raises or returns default.
• d.popitem() removes and returns last inserted key-value pair.
• d.clear() removes all items.

Value Mutation

Mutating an object stored as a dictionary value does not replace the key association. Aliases to the value observe the mutation.

d = {'x': 1, 'y': 2}

print("Lookup d['x']:", d['x'])
print("Get d.get('z', 0):", d.get('z', 0))

d['z'] = 3
print("After insertion:", d)

d['x'] = 10
print("After replacement:", d)

value = d.setdefault('w', 4)
print("After setdefault:", d, "; returned:", value)

d.update({'y': 20, 'v': 5})
print("After update:", d)

popped = d.pop('v')
print("After pop 'v':", d, "; popped:", popped)

key, val = d.popitem()
print(f"After popitem: removed ({key}, {val}), dict now:", d)

del d['y']
print("After del 'y':", d)

d.clear()
print("After clear:", d)

# Value mutation vs replacement
d = {'numbers': [1, 2, 3]}
alias = d['numbers']

alias.append(4)
print("After alias mutation:", d)

d['numbers'] = [10, 20]
print("After value replacement:", d)
print("Alias still references old list:", alias)

Python Dictionary Views

Dictionaries provide dynamic view objects:

• d.keys() exposes keys.
• d.values() exposes values.
• d.items() exposes key-value pairs as tuples.

These views reflect the dictionary's current state and change dynamically as the dictionary mutates.

Iteration and Mutation Hazards

Views preserve insertion order. Iterating over a live view while mutating the dictionary's key structure can cause runtime errors. Mutating values does not affect iteration safety.

Set-like Behavior

Key views and item views support set operations like union, intersection, difference, and subset tests if elements are hashable.

d = {'a': 1, 'b': 2, 'c': 3}
keys = d.keys()
values = d.values()
items = d.items()

print("Keys:", list(keys))
print("Values:", list(values))
print("Items:", list(items))

d['d'] = 4
print("After adding key 'd':")
print("Keys:", list(keys))
print("Items:", list(items))

# Set-like operations on keys
k1 = {'a', 'b'}
print("Keys intersection:", keys & k1)

# Items view set operation example
i1 = {('a', 1), ('b', 2)}
print("Items intersection:", items & i1)

Solved Python Data Structure Exercises

Exercise 1: Aggregate Sales by Category

Given a list of sales records, each represented as a tuple (category, item, quantity), produce a report mapping each unique category to the total quantity sold, preserving the order of first occurrence of categories.

records = [
    ('fruit', 'apple', 10),
    ('vegetable', 'carrot', 5),
    ('fruit', 'banana', 7),
    ('dairy', 'milk', 3),
    ('vegetable', 'lettuce', 2),
    ('fruit', 'apple', 4),
]

unique_categories = []
seen = set()

for category, _, _ in records:
    if category not in seen:
        unique_categories.append(category)
        seen.add(category)

totals = {}
for category, _, quantity in records:
    totals[category] = totals.get(category, 0) + quantity

report = [(cat, totals[cat]) for cat in unique_categories]

for category, total in report:
    print(f"{category}: {total}")

Explanation

• List of records: input data as tuples.
• Set tracks seen categories for uniqueness.
• List preserves insertion order of categories.
• Dictionary accumulates totals per category.
• Tuple stores category-total pairs in the report.
• Iteration over records builds set and dictionary.
• Final report uses list order to produce deterministic output.

Exercise 2: Dictionary with Composite Keys and Dynamic Views

Given transactions keyed by (user_id, item_id) tuples, track quantities purchased. Use frozensets as keys for unordered pairs and demonstrate mutation effects on dictionary values and views.

transactions = {
    ('alice', 'item1'): 3,
    ('bob', 'item2'): 1,
}

view = transactions.items()

# Update a tuple-keyed entry
transactions[('alice', 'item1')] += 2

# Add a new entry with frozenset key (unordered pair)
transactions[frozenset(['charlie', 'item3'])] = 5

print("Transactions:", transactions)
print("View items after mutations:", list(view))

# Demonstrate unhashable key error
try:
    transactions[['dave', 'item4']] = 1
except TypeError as e:
    print("Error with unhashable key:", e)

Explanation

• Composite keys use tuples (ordered) and frozensets (unordered).
• Dictionary values are mutable (integers here incremented).
• The items() view updates dynamically after mutations.
• Attempting to use a list (unhashable) as key raises TypeError.
• Demonstrates hashability, key equality, and dynamic views.

This completes a foundational overview and detailed treatment of Python's built-in data structures.