How are Python lists implemented, and what's the time complexity of common operations?
Quick Answer
A `list` is a dynamic array (contiguous, resizable array of object pointers), not a linked list. Indexing (`lst[i]`) and appending (`lst.append`) are **O(1) amortized**; inserting/removing at the front or middle (`lst.insert(0, x)`, `lst.pop(0)`) is **O(n)** because every following element must shift; membership testing (`x in lst`) is **O(n)** since it scans linearly.
Detailed Answer
Lists are dynamic arrays, not linked lists
CPython's list stores a contiguous array of pointers to objects, with
some extra pre-allocated capacity to amortize the cost of growth. This is
why indexing is O(1): lst[i] is just pointer arithmetic into the
underlying array, not a traversal.
lst = [1, 2, 3]
lst[1] # O(1) -- direct array index
lst.append(4) # O(1) amortized -- usually just writes into pre-allocated space
Complexity cheat sheet
| Operation | Complexity | Why |
|---|---|---|
lst[i], lst[i] = x | O(1) | direct array index |
lst.append(x) | O(1) amortized | writes to spare capacity; occasional O(n) resize, amortized away |
lst.pop() (from end) | O(1) | no shifting needed |
lst.pop(0), lst.insert(0, x) | O(n) | every remaining element shifts by one slot |
x in lst | O(n) | linear scan, no index structure |
len(lst) | O(1) | length is cached, not recomputed |
lst.sort() | O(n log n) | Timsort |
slicing lst[a:b] | O(k) | k = length of the slice, since a new list is built |
Why append is amortized O(1)
When the underlying array runs out of spare capacity, CPython allocates a larger array (roughly growing by ~1.125x plus a constant) and copies existing elements over — an O(n) operation, but one that happens increasingly rarely as the list grows, so the average cost per append across many appends works out to O(1).
Why front-insertion/removal is expensive
lst = [1, 2, 3, 4, 5]
lst.pop(0) # removes 1, then shifts 2,3,4,5 each one slot left -- O(n)
lst.insert(0, 0) # shifts every element right by one slot -- O(n)
If your workload needs frequent insert/pop from both ends, use
collections.deque instead — it's implemented as a doubly-linked list of
fixed-size blocks and supports O(1) append/pop from either end, at the
cost of O(n) random access (deque[i] is O(n) for large i, unlike
list).
Interview-ready summary: Python lists are dynamic arrays: O(1)
indexing and end-append/pop, but O(n) for inserting/removing anywhere
except the end, and O(n) membership testing. When you need efficient
operations at both ends, reach for collections.deque instead of list.