Arrays and Dynamic Arrays
An array is n equal-sized slots laid side by side in memory, so the address of slot i is the start address plus i times the slot size. That is one multiplication, one addition and one memory read, whatever n is. The arithmetic is why indexing is O(1), and why a scan over an array is the fastest loop a machine can run (Chapter 4).
Its price is that nothing can go into the middle without moving everything after it. A Python list is this structure plus a rule for growing, and it holds pointers rather than values. Both facts decide what a list costs, and most of this chapter builds on them.
Contiguous Memory
An array's slots are all the same size, with no gaps and no bookkeeping per element. The index is not a search key; it is an offset. With 8-byte slots starting at address 1000, slot 5 sits at 1000 plus 5 times 8, which is address 1040. Element one million costs the same to reach as element zero.
Contiguity is also what makes a scan fast. Consecutive elements share cache lines, eight 8-byte slots to a 64-byte line, and the addresses advance by a steady step that the prefetcher recognizes and fetches ahead of. A scan over an array runs at the memory's bandwidth rather than its latency, which no other layout manages.
The Price of the Middle
Inserting at position i shifts the n minus i elements after it one slot to the right, and deleting shifts them one slot left. At the end that is nothing. At the front it is all n elements. The shift is a single block move that the hardware does quickly, but it is still proportional to the tail.
Built one front insert at a time, a list of 100,000 items moves about 100,000 squared over 2 elements in total, five billion. On CPython 3.15 that loop took 0.9 seconds, where appending the same 100,000 items to the end took about 2 milliseconds. Both loops look like one line of code each.
Growing Without Knowing n
A dynamic array keeps a capacity larger than its length. When an append finds no room, it allocates a larger block, copies every element into it and frees the old one. Growing by a constant factor, rather than by a constant amount, makes those copies average out to O(1) per append, the amortized arithmetic of Chapter 1.
The factor is a trade between wasted room and repeated copying. Doubling, the textbook rule, copies each element about once over the list's life but can leave half the block empty. Java's ArrayList grows by half again, 1.5 times, which wastes less and copies each element about twice. CPython grows a list by about an eighth plus a few slots, the leanest of the three, and pays with about eight copies per element.
capacity: 0 → 4 → 8 → 16 → 24 → 32 → 40 → 52 → 64 → 76 → 92 → 108 → 128 ... rule: new capacity ≈ needed + needed / 8 + 6, rounded down to a multiple of 4
The listing shows the capacities an empty CPython 3.15 list passes through as items are appended one at a time. The first steps look like doubling, because the constant six dominates small sizes. From a few dozen slots onward each step adds about an eighth: 64 slots become 76, 76 become 92. Measured over a million appends, the three rules copied each element about 1.05, 2.4 and 8.4 times on average for doubling, half again and CPython's eighth.
What a Python List Really Is
A Python list is an array of 8-byte pointers to objects that live elsewhere on the heap (Chapter 4). That is how one list can hold an integer, a string and another list side by side: every slot is the same size because every slot holds an address. The objects themselves are wherever the allocator put them.
The indirection has a price in memory. A float object takes 24 bytes on 64-bit CPython 3.15 and a small integer 28. A million floats in a list cost 8 megabytes of pointers plus 24 megabytes of float objects, 32 in all, which matches what CPython 3.15 measured. The same million values as packed 8-byte numbers, in the standard library's array module or in NumPy, cost 8 megabytes and sit contiguously.
Arrays Underneath Everything
Strings, bytes, a dictionary's entry table (see Hash Tables), a heap (Chapter 6), a ring buffer (see Stacks, Queues and Ring Buffers) and a B-tree page (Chapter 6) are all arrays with a rule on top. Most structures in this book start life as an array, because contiguity is the one property that every rung of the memory hierarchy rewards.
Strings are the instructive case. CPython stores every character of one string at the same width, 1, 2 or 4 bytes chosen by the widest character in it, precisely so that finding character i stays array arithmetic. A string of a hundred ASCII letters takes 141 bytes on CPython 3.15, and a string of a hundred emoji takes 460. UTF-8, where characters take 1 to 4 bytes each, cannot offer that: reaching character i means walking from the start (Chapter 2).
The structures that are not arrays, linked lists and pointer-based trees, give up contiguity to gain something else, usually cheap insertion in the middle. The next topic weighs that trade on real hardware.
The Cost in a Script You Run
The append that triggers growth copies the whole block, a pause proportional to the list's size, unless the allocator manages to extend the block where it stands. On CPython 3.15 on macOS, the appends that grew the block while building a list of 30 million items took up to about a millisecond each, tens of thousands of times a normal append. A loop that inserts at the front or pops from the front is quadratic without looking it (see Stacks, Queues and Ring Buffers).
Memory is the other bill. Ten million measurements kept as Python floats in a list cost about 330 megabytes, measured on CPython 3.15, where a packed array of the same values costs 80. For a script that holds numbers, the container is often a bigger choice than the algorithm.
- "Append sometimes copies everything, so append is O(n)." One append can. Across n appends the copying adds up to a constant multiple of n, about n with doubling and about 8n with CPython's leaner rule, so each append is O(1) amortized (Chapter 1).
- "A Python list stores its numbers." It stores 8-byte pointers. Each number is a separate object of 24 to 28 bytes elsewhere, so a list of numbers costs four to five times their packed size.
- "Popping from the front costs the same as popping from the end." Taking from the front shifts every remaining element. Draining a list of 100,000 items from the front moves about five billion pointers, and took 0.86 seconds on CPython 3.15.
- "Python lists double when they grow." CPython over-allocates by about an eighth. Doubling is the textbook's rule, and the amortized argument works for any constant factor above one.
- Add and remove at the end of a list, and use a deque when the front moves (see Stacks, Queues and Ring Buffers). The end is free and the front costs the whole list.
- Build a list once and read it many times, rather than inserting into its middle. Every middle insert moves the tail.
- Store large numeric data in a packed array. It takes a quarter of the memory, and its values are ones the cache can stream.
- Look things up by position only when position means something, and by key in a dictionary otherwise (see Hash Tables). An index lookup is O(1) only if you already know the index.
Knowledge Check
Over n appends, roughly how many element copies does a dynamic array make if it grows by a factor of 2, of 1.5 and of 1.125?
- About n each time, because every element is copied exactly once
- About n log n for all three, because the copies happen at doublings
- About n, 2n and 8n: the total is n divided by the factor minus one
- About n², because every growth copies all the elements again
How much memory do a million floats take in a Python list, compared with a packed array of 8-byte values?
- About 8 MB in both, since a float is 8 bytes
- About 32 MB in the list and 8 MB in the array
- About 16 MB in the list and 8 MB in the array
- About 8 MB in the list and 32 MB in the array
A script builds a list of 100,000 items by inserting each new item at index 0. Why is it slow?
- Each insert allocates a new list from scratch, and allocation dominates
- Index 0 is a special case that the interpreter handles through a slow path
- Each insert shifts every element already there, about n²/2 moves in all
- Inserting at index 0 reverses the list, and reversing costs n log n
Why does reaching element 1,000,000 of an array cost the same as reaching element 0?
- The array keeps an index of every millionth position for fast jumps
- The processor caches every element, so all of them are equally close
- The interpreter walks the array in large blocks rather than one by one
- Its address is the start plus the index times the slot size
What does a dynamic array's growth factor trade?
- Unused capacity against the number of times elements get copied
- Lookup speed against insertion speed at the front of the array
- Memory safety against speed, since large blocks are easier to overflow
- Sorted order against insertion order, since growth reorders elements
You got correct