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. This is 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).
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.