Python Built-in Data Structures#

Python ships with four core collection types — list, tuple, dict, and set — plus specialized tools in collections. In interviews you almost always use these directly rather than reimplementing from scratch. This page covers behavior, complexity, multiple usage patterns, and the nuances that cause bugs.

How to use this page

Know complexity cold and understand mutability/hashability implications. Pair with Python Language Fundamentals and Basic Built-in Functions and Libraries.

At a glance


Track	Python Basics
Sections	9 major topics
Outline	Use the right-hand TOC to jump

Topics: Quick comparison · List — dynamic array · Tuple — immutable sequence · Dictionary (dict) — hash map · Set — unique unordered collection · Choosing the right structure · Copy semantics — shallow vs deep · Sorting collections · … (+1 more)

Quick comparison
List — dynamic array
Tuple — immutable sequence
Dictionary (dict) — hash map
Set — unique unordered collection
Choosing the right structure
Copy semantics — shallow vs deep
Sorting collections
Nested structures — interview patterns

Quick comparison#

Type	Ordered	Mutable	Duplicates	Hashable*	Typical use
`list`	Yes	Yes	Yes	No	Sequences, stacks, results
`tuple`	Yes	No	Yes	Yes†	Records, dict keys, returns
`dict`	Yes‡	Yes	Keys unique	No	Maps, counts, memo, graphs
`set`	No	Yes	No	No	Membership, dedup, visited
`frozenset`	No	No	No	Yes	Immutable set as dict key

*Hashable = can be dict key / set element if contents fixed.
†Tuple hashable only if all elements hashable.
‡Insertion order preserved since Python 3.7 (language guarantee 3.7+).

List — dynamic array#

Operations and complexity#

Operation	Time	Notes
`x = a[i]`	O(1)	Index access
`a[i] = x`	O(1)
`a.append(x)`	O(1)*	Amortized
`a.pop()`	O(1)	End only
`a.pop(0)`	O(n)	Avoid in hot loops
`a.insert(i, x)`	O(n)
`a.remove(x)`	O(n)	Search + shift
`x in a`	O(n)	Linear scan
`a + b`, `a * n`	O(n)	New list
`a.sort()`	O(n log n)	In-place, stable
`sorted(a)`	O(n log n)	New list
`len(a)`	O(1)

*Amortized — occasional resize copies all elements.

nums = [1, 2, 3]
nums.append(4)
nums.extend([5, 6])      # prefer over += for clarity with non-lists
nums.insert(0, 0)        # O(n)
nums.pop()               # removes last
nums.pop(0)              # O(n)
nums.remove(2)           # removes first 2 found
nums.index(3)            # first index or ValueError
nums.count(2)
nums.reverse()           # in-place O(n)
nums.sort(key=abs)       # in-place

List as stack and queue#

# Stack — LIFO (ideal)
stack = []
stack.append(x)
stack.pop()

# Queue — FIFO (avoid pop(0))
from collections import deque
queue = deque()
queue.append(x)
queue.popleft()          # O(1)

Use deque for queue — not list.pop(0).

Slicing and copying#

a = [1, 2, 3, 4, 5]
a[1:4]       # [2, 3, 4]
a[::-1]      # reversed copy
a[:]         # shallow copy

b = a.copy()       # or list(a)
import copy
c = copy.deepcopy(nested)

Slice assignment mutates in place:

a[1:3] = [99, 100]   # replace slice
a[1:1] = [50]        # insert at index 1
del a[2:4]

List comprehensions — multiple forms#

[x * 2 for x in range(10)]
[x for x in nums if x > 0]
[(i, x) for i, x in enumerate(nums)]
[[0] * cols for _ in range(rows)]   # correct 2D init

# NOT: [[0] * cols] * rows  — shared row references

When to use list#

Need index access by position
Collecting results in order
Stack (append/pop end)
Iterating with known order

Tuple — immutable sequence#

point = (10, 20)
single = (42,)          # comma required — (42) is int!
empty = ()

x, y = point            # unpacking
a, *rest, z = (1, 2, 3, 4)  # rest = [2, 3]

coords = {(0, 0): "origin", (1, 1): "corner"}  # hashable keys

Tuple vs list — when which?#

Use tuple	Use list
Fixed-size record	Growing collection
Dict key / set element	Need append/remove
Return multiple values	Need sort in place
Protect from mutation	Same-type homogeneous sequence

Named tuples and dataclasses#

from collections import namedtuple
Point = namedtuple("Point", "x y")
p = Point(1, 2)

from dataclasses import dataclass
@dataclass(frozen=True)
class Point2:
    x: int
    y: int

frozen=True dataclass is hashable if fields are hashable.

Dictionary (`dict`) — hash map#

Operations and complexity#

Operation	Average	Worst case
`d[k]`, `d[k]=v`	O(1)	O(n)
`del d[k]`	O(1)	O(n)
`k in d`	O(1)	O(n)
`d.get(k)`	O(1)	O(n)
`len(d)`	O(1)	O(1)
Iterate all	O(n)	O(n)

Worst case rare with good hash — understand for theory; assume O(1) in interviews unless asked.

Creating dicts — five ways#

d1 = {"a": 1, "b": 2}
d2 = dict(a=1, b=2)
d3 = dict([("a", 1), ("b", 2)])
d4 = {x: x * 2 for x in range(3)}
d5 = dict.fromkeys(["a", "b"], 0)   # all keys → 0

Access patterns#

freq: dict[str, int] = {}

# Pattern 1: get with default
freq[ch] = freq.get(ch, 0) + 1

# Pattern 2: setdefault
freq.setdefault(ch, 0)
freq[ch] += 1

# Pattern 3: defaultdict
from collections import defaultdict
freq = defaultdict(int)
freq[ch] += 1

# Pattern 4: Counter
from collections import Counter
freq = Counter(text)

Pattern	Best when
`.get()`	Occasional missing keys
`setdefault`	Insert default on first access
`defaultdict`	Many grouped appends (graph)
`Counter`	Frequency counting

Iteration views#

for k in d:                    # keys
for k, v in d.items():         # key-value
for v in d.values():
list(d.keys()), list(d.values()), list(d.items())  # snapshots in 3.x

Views are dynamic — reflect dict changes.

Dict merge (3.9+)#

d = d1 | d2           # new dict
d1 |= d2              # update d1 in place
{**d1, **d2}          # older spread syntax

Hashability requirements for keys#

Keys must be hashable (immutable + correct __hash__):

valid = {(1, 2): "ok", "s": 1, frozenset({1}): 2}
# invalid: {[1, 2]: "no", {1}: "no"}

Dict for interview patterns#

# Two-sum complement lookup
seen: dict[int, int] = {}

# Graph adjacency
graph: dict[int, list[int]] = defaultdict(list)

# Memoization
memo: dict[tuple, int] = {}

# Character index map
index: dict[str, list[int]] = defaultdict(list)

See Hashing.

Set — unique unordered collection#

Operations and complexity#

Operation	Average
`add`, `remove`, `discard`	O(1)
`x in s`	O(1)
`s1 \\| s2`, `s1 & s2`	O(len(s1)+len(s2))

seen: set[int] = set()
seen.add(3)
seen.discard(3)    # no error if missing
seen.remove(3)     # KeyError-like if missing

a = {1, 2, 3}
b = {3, 4, 5}
a | b    # union
a & b    # intersection
a - b    # difference
a ^ b    # symmetric difference

Set use cases#

# Dedup
unique = list(set(nums))   # order lost — use dict.fromkeys for order preserve
unique_ordered = list(dict.fromkeys(nums))

# Membership O(1)
if node in visited:
    continue
visited.add(node)

# Set algebra
common = set(a) & set(b)
only_a = set(a) - set(b)

`frozenset`#

Immutable, hashable set — usable as dict key:

fs = frozenset([1, 2, 3])
cache = {fs: "value"}

Choosing the right structure#

Need index by position?           → list
Need key → value mapping?         → dict
Need unique elements?             → set
Need immutable sequence / key?    → tuple / frozenset
Need fast both-end queue?         → deque
Need sorted order maintained?     → list + bisect, or TreeMap concept
Need frequency counts?            → Counter or dict
Need graph?                       → dict of lists (defaultdict)

Copy semantics — shallow vs deep#

import copy

original = [[1, 2], [3, 4]]

shallow = original.copy()
shallow[0].append(99)     # original[0] also changed

deep = copy.deepcopy(original)
deep[0].append(99)        # original unchanged

Operation	Outer container	Inner objects
`a[:]` / `.copy()`	New	Shared
`list(a)`	New	Shared
`copy.deepcopy(a)`	New	Recursively copied

Critical for 2D grids and nested structures in DP/backtracking.

Sorting collections#

# List in place
nums.sort()
nums.sort(key=abs, reverse=True)

# New sorted list
sorted(nums)
sorted(words, key=str.lower)

# Sort dict by key or value
sorted(d.items())                    # by key
sorted(d.items(), key=lambda kv: kv[1])  # by value

# Sort set — convert first
sorted(my_set)

Stable sort — equal keys preserve relative order (Python's Timsort).

Nested structures — interview patterns#

2D grid#

rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]

grid[r][c] = 1
for r in range(rows):
    for c in range(cols):
        process(grid[r][c])

# Directions: up, down, left, right
DIRS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

Adjacency list (graph)#

from collections import defaultdict

graph: dict[int, list[int]] = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)   # undirected

Interview traps (quick reference)#

Trap	What goes wrong	Safe approach
`[[0]n]n` grid	Shared rows	List comprehension
`list.pop(0)` as queue	O(n²) BFS	`deque.popleft()`
Dict key is list	TypeError unhashable	Tuple key
`.get` when None valid	Can't distinguish missing	`in` check
Set loses order	Wrong order output	`dict.fromkeys` trick
Shallow copy of 2D	Shared inner lists	Deep copy or comprehension
Modify list while iterating	Skipped elements	Comprehension or copy iterate
Assume dict sorted	Insertion order ≠ sorted keys	`sorted(d)` explicitly

Mental model checklist#

What is the amortized complexity of list.append?
Why can't lists be dict keys?
When is deque better than list?
What is the difference between remove and discard on sets?
How do you count frequencies — three different ways?
What breaks when you shallow-copy a 2D list?

What's next#

Topic	Page
Interview implementations	Data Structures Overview
Hash table internals	Hashing
Both-end operations	Deque
Operators on collections	Operators
Built-in helpers	Basic Built-in Functions and Libraries

Python Built-in Data Structures#

Quick comparison#

List — dynamic array#

Operations and complexity#

List as stack and queue#

Slicing and copying#

List comprehensions — multiple forms#

When to use list#

Tuple — immutable sequence#

Tuple vs list — when which?#

Named tuples and dataclasses#

Dictionary (dict) — hash map#

Operations and complexity#

Creating dicts — five ways#

Access patterns#

Iteration views#

Dict merge (3.9+)#

Hashability requirements for keys#

Dict for interview patterns#

Set — unique unordered collection#

Operations and complexity#

Set use cases#

frozenset#

Choosing the right structure#

Copy semantics — shallow vs deep#

Sorting collections#

Nested structures — interview patterns#

2D grid#

Adjacency list (graph)#

Interview traps (quick reference)#

Mental model checklist#

What's next#

Dictionary (`dict`) — hash map#

`frozenset`#