PYTHON / DATA STRUCTURES AND ALGORITHMS
Arrays and dynamic array behaviour
Explain how a Python list works as a dynamic array of object references, and predict which list operations are cheap and which are linear.
What you will learn
- Explain why indexing a list is O(1) at any position
- Show why append is amortized O(1) using geometric buffer growth
- Spot insert(0)/pop(0) loops that turn linear work into quadratic
- Choose array('i'/'d') when you need packed machine values, not references
Understanding Arrays and dynamic array behaviour
A Python list is a dynamic array: one contiguous block of memory holding pointers to objects, plus a stored length and a stored capacity. Because the block is contiguous and every slot is the same size (one pointer), the interpreter reaches lst[i] by adding i * pointer_size to the block's start address, so lst[0] and lst[999999] cost the same. The values themselves live elsewhere on the heap, which is why one list can hold an int, a str and another list at once: the slots are uniform even when the objects are not.
When you append and the block is already full, the list cannot simply extend in place, so CPython allocates a bigger block, copies every existing pointer into it, frees the old block, and then stores the new item. The new capacity is chosen with room to spare, growing roughly geometrically rather than by one slot, so the resizes happen at rapidly spreading-out lengths: 1,000,000 appends trigger only a few dozen copies, and the copied pointers sum to a small constant multiple of 1,000,000. That is what amortized O(1) means for append: individual appends occasionally do linear work, but the average over a run of appends is constant.
The same contiguity that makes indexing fast makes front operations slow. insert(0, x) has to move every existing pointer one slot to the right before writing slot 0, and pop(0) moves every remaining pointer one slot left, so both are O(n) in the number of items after the insertion point. Deleting also does not hand memory back promptly: the capacity stays reserved until the length drops well below it, so a list that once held a million items can stay large after you empty most of it.
class DynamicArray:
"""Models what CPython does under list.append, with visible resizes."""
def __init__(self):
self._slots = []
self._capacity = 0
self._size = 0
self.copies = 0
def _grow(self):
new_capacity = 4 if self._capacity == 0 else self._capacity * 2
new_slots = [None] * new_capacity
for i in range(self._size):
new_slots[i] = self._slots[i]
self.copies += 1
print(f"resize to capacity {new_capacity} after copying {self._size} items")
self._slots = new_slots
self._capacity = new_capacity
def append(self, value):
if self._size == self._capacity:
self._grow()
self._slots[self._size] = value
self._size += 1
arr = DynamicArray()
for n in range(17):
arr.append(n)
print("appends: 17 total element copies:", arr.copies)A list is a contiguous block of object references with spare capacity, so indexing and append are cheap while any operation that shifts the tail is linear.
Worked examples
Slots hold references, so repeated rows alias
Shows that list multiplication copies pointers, not the objects they point to.
grid = [[0] * 3] * 3
grid[0][0] = 9
print(grid)
print(grid[0] is grid[1])
grid2 = [[0] * 3 for _ in range(3)]
grid2[0][0] = 9
print(grid2)
print(grid2[0] is grid2[1])Example explained
Line 1[[0] * 3] * 3 fills three slots with the same pointer, so there is only one inner list.
Line 2grid[0][0] = 9 writes through that shared pointer, which every row sees.
Line 3The comprehension evaluates [0] * 3 once per iteration, producing three distinct inner lists.
Line 4grid2[0] is grid2[1] is False, confirming the rows are separate objects.
Packed storage with the array module
Contrasts a list of references with array's contiguous machine values under a fixed typecode.
from array import array
a = array('i', [1, 2, 3])
a.append(4)
print(a, a.typecode, a.itemsize)
print(len(a) * a.itemsize, "bytes of payload")
try:
a.append(1.5)
except TypeError:
print("TypeError: typecode 'i' stores C ints only")Example explained
Line 1typecode 'i' fixes every slot to one C int, so itemsize is 4 bytes instead of a pointer plus an int object.
Line 2append grows the buffer the same way a list does, so it is still amortized O(1).
Line 3The payload for four ints is 16 bytes total; the equivalent list stores four pointers plus four separate int objects.
Line 4Appending 1.5 raises TypeError because the buffer has no slot shape that can hold a float under typecode 'i'.
The list object is the buffer, names are just references
Shows that growing a list in place is visible through every name bound to it, while slicing makes a new buffer.
a = [1, 2, 3]
b = a
c = a[:]
a.append(4)
print(b)
print(c)
print(a is b, a is c)
a[:] = [9]
print(b)Example explained
Line 1b = a binds a second name to the same list object, sharing its buffer, length and capacity.
Line 2c = a[:] allocates a new buffer and copies the pointers, so later growth of a cannot reach c.
Line 3a.append(4) mutates the shared buffer, which is why printing b shows four items.
Line 4a[:] = [9] replaces the contents in place, so b changes too; a = [9] would instead rebind only a.
Front removal shifts the tail
Counts the pointer moves that pop(0) implies compared with pop() from the end.
items = ['a', 'b', 'c', 'd', 'e']
first = items.pop(0)
print(first, items, "shifted", len(items), "slots")
last = items.pop()
print(last, items, "shifted 0 slots")
read = 0
queue = ['a', 'b', 'c', 'd', 'e']
while read < len(queue):
print("served", queue[read])
read += 1Example explained
Line 1pop(0) returns slot 0, then moves the remaining four pointers left by one to keep the block contiguous.
Line 2pop() only decrements the stored length, so nothing is copied and the capacity is unchanged.
Line 3Advancing a read index consumes the items in order with zero shifting, at the cost of keeping the buffer alive.
Line 4The while condition re-reads len(queue) each pass, which is O(1) because the length is stored, not counted.
Important notes
The exact over-allocation formula (currently about one eighth extra plus a constant) is a CPython implementation detail; treat sys.getsizeof numbers as observations, not guarantees, since they differ between versions and builds.
Amortized O(1) is a statement about a run of appends, not about one call: the append that triggers a resize really does copy every existing pointer, which matters in latency-sensitive loops.
Common mistakes
Consuming a list with while lst: x = lst.pop(0) — each pop shifts every remaining pointer, so draining 200,000 items does about 20 billion pointer moves and appears to hang, while pop() from the end finishes instantly.
Building a matrix with rows = [[0] * cols] * rows_count — every row is the same list object, so rows[2][0] = 1 sets column 0 in all rows and grid logic silently produces wrong results.
Assuming del lst[:] or repeated pop() returns memory immediately — the capacity stays reserved until the length falls far below it, so a process that once held a huge list keeps a large resident footprint.
Try it yourself
Change, predict, then run
Build two lists of 20000 integers, one with append(i) and one with insert(0, i), timing each with time.perf_counter. Then repeat at 40000 and report how each timing changed, explaining the difference from the shifting each operation performs.
Open the Python workspaceCheck your understanding
You append 1,000,000 items to an empty list one at a time. Some of those appends copy the entire buffer, yet the total work stays proportional to 1,000,000. Why?
- Resizes happen at geometrically spaced lengths, so the pointers copied across all resizes add up to a small constant multiple of the final length.
- CPython performs the buffer copy on a background thread, so the copying does not count toward the total work.
- Each resize adds exactly one slot, so after the first allocation no further copying is ever needed.
- A list stores its items in a chain of nodes, so appending never has to touch items that are already stored.
Show answer
Capacity grows by a multiplicative factor, so resizes occur at lengths like 4, 8, 16, ... and the copied pointers form a geometric series bounded by a constant times n; the average per append is therefore constant. Option 3 is tempting because it correctly notes that appending should not disturb existing items, but it describes a linked structure: a list is one contiguous pointer block, which is exactly why it must sometimes be copied wholesale.