Built-in Data Structures Deep Dive

Choosing the right data structure is half of solving an algorithm problem. Python ships with four workhorse structures plus one from the standard library. This page covers what each does, when to reach for it, and the Big-O cost of common operations. Pair it with the Big-O cheat sheet for the full picture.

list: the ordered, resizable array#

A list stores items in order and can grow or shrink. It is your default sequence.

1nums = [3, 1, 4, 1, 5]
2nums.append(9)          # add to end: O(1) amortized
3nums.insert(0, 0)       # insert at front: O(n), shifts everything
4last = nums.pop()       # remove from end: O(1)
5first = nums.pop(0)     # remove from front: O(n)
6print(nums[2])          # index access: O(1)
7print(4 in nums)        # membership scan: O(n)

Lists are mutable, so you can change them in place. Access by index is instant, but searching for a value or inserting at the front is linear because elements must shift. Slicing copies a subrange.

1data = [10, 20, 30, 40, 50]
2print(data[1:4])        # [20, 30, 40], O(k) copy
3print(data[::-1])       # [50, 40, 30, 20, 10] reversed copy
4data.sort()             # in place, O(n log n)

Use a list when order matters, when you push and pop from the end (a stack), or when you index into positions.

dict: the hash map#

A dict maps keys to values with average O(1) lookup, insert, and delete. Keys must be hashable (immutable types like strings, numbers, and tuples).

 1counts = {}
 2for ch in "banana":
 3    counts[ch] = counts.get(ch, 0) + 1
 4print(counts)                 # {'b': 1, 'a': 3, 'n': 2}
 5
 6print("a" in counts)          # O(1) key membership
 7print(counts.get("z", 0))     # 0, safe default
 8del counts["b"]               # O(1) removal
 9for key, value in counts.items():
10    print(key, value)

Dicts preserve insertion order (guaranteed since Python 3.7). Reach for a dict whenever you need to look something up by a key: frequency counts, caches, adjacency lists for graphs, and memoization tables all use dicts.

set: fast membership and uniqueness#

A set is an unordered collection of unique, hashable items with average O(1) membership tests.

 1seen = set()
 2nums = [1, 2, 2, 3, 3, 3]
 3for n in nums:
 4    seen.add(n)
 5print(seen)                   # {1, 2, 3}
 6print(2 in seen)              # O(1), much faster than list scan
 7
 8a = {1, 2, 3}
 9b = {3, 4, 5}
10print(a & b)                  # intersection {3}
11print(a | b)                  # union {1, 2, 3, 4, 5}
12print(a - b)                  # difference {1, 2}

Use a set to deduplicate, to check “have I seen this before” in linear time overall, or for set algebra. Sets are mutable; if you need an immutable, hashable version (for example as a dict key), use frozenset.

tuple: the immutable record#

A tuple is like a list but cannot be changed after creation. Because it is immutable, it is hashable and can serve as a dict key or set member.

1point = (3, 4)
2x, y = point                  # unpacking
3print(x, y)                   # 3 4
4
5# tuples as dict keys for grid coordinates
6grid = {}
7grid[(0, 0)] = "start"
8grid[(1, 2)] = "wall"
9print(grid[(0, 0)])           # start

Use tuples for fixed-size records (a coordinate, an RGB color) and anywhere you need a hashable composite key. Trying to mutate one raises an error, which protects your data.

1t = (1, 2, 3)
2try:
3    t[0] = 99
4except TypeError as e:
5    print("cannot mutate:", e)

collections.deque: the double-ended queue#

A list is slow at the front. When you need fast pushes and pops on both ends (queues, breadth-first search, sliding windows), use deque from the collections module.

1from collections import deque
2
3q = deque([1, 2, 3])
4q.append(4)        # push right: O(1)
5q.appendleft(0)    # push left:  O(1)
6print(q)           # deque([0, 1, 2, 3, 4])
7q.popleft()        # pop left:   O(1)
8q.pop()            # pop right:  O(1)
9print(q)           # deque([1, 2, 3])

Random indexing into the middle of a deque is O(n), so if you need frequent middle access, stick with a list.

Quick reference: mutability and Big-O#

Pick the structure that makes your hot operation O(1). That single choice often decides whether your solution passes. Apply these directly in the algorithm lessons and the 60-day curriculum.