How a list lives in memory

The last chapter left a mystery. Checking x in set takes as long on a million items as on ten, while x in list goes through the whole million. Where does the difference come from? A set is a cunning piece of engineering, and its turn comes in Chapter 16. First we’ll work out a simpler structure, one we have used in every other line since Chapter 6. What is inside a list?

The interpreter’s source code is open, and the answer could be read there. We’ll take another route, that of a naturalist who has been brought an unfamiliar animal. First we watch how it behaves, then we weigh it, put forward hypotheses and test them by experiment, derive a law, and only at the end pick up the scalpel. We have three instruments: the stopwatch timeit from Chapter 13, the scale sys.getsizeof and, toward the end, a microscope that looks straight into memory. All the experiments run on the course’s server, on a live CPython 3.13 interpreter, and every number below comes from it.

Field observations

We start with behavior. Take a list of a million numbers and ask it for an item.

A list holds a million numbers. Which is faster: reading a[0] or a[999_999]?

a[0]: it’s closer a[999_999] Neither

Neither: check it below. This is the first property of the list we’ll have to explain. It doesn’t walk to an item from the start; somehow it knows at once where the item is.

Next, three experiments at once. For lists of ten thousand, a hundred thousand and a million items, we time three actions: reading the last item, appending an item at the end and inserting an item at the front. Each action is repeated a thousand times and the total divided by a thousand, which gives the time of one.

Into the field log it goes. Reading takes a few tens of nanoseconds, and it doesn’t care how many items the list holds. append also costs tens of nanoseconds at any length. But insert(0, x) takes about two microseconds on ten thousand items, about twenty on a hundred thousand and close to two hundred on a million: ten times the items, ten times as long to insert. In the language of the last chapter, reading and append cost $O(1)$, and inserting at the front costs $O(n)$.

The log raises three questions. How does the list know where its millionth item lies without walking past the others? Why is appending at the end cheap and inserting at the front expensive, when either way it is a single item? And what happens when the list grows? The new items must find room somewhere.

Weighing

The second instrument is the scale. The function sys.getsizeof tells you how many bytes an object takes up. We weigh an empty list and lists of zeros of different lengths.

An empty list weighs 56 bytes, and every item adds 8: one zero makes 64, two make 72, a thousand $56 + 8 \cdot 1000 = 8056$. The first hypothesis suggests itself: the list has a 56-byte header, followed by the items in a row, 8 bytes each.

But the number 0 in Python is an object, and it weighs more than 8 bytes. Time to put something heavier into the list: a good hypothesis should survive attempts to knock it down.

One such string weighs about seven and a half kilobytes, yet the list of a thousand different strings weighs the same 8,056 bytes as the list of zeros. The scale leaves no doubt: the items don’t lie inside the list. Inside lies something that is the same size for a zero and for War and Peace, 8 bytes per item.

You already know what it is. In Chapter 2 a name was a label tied to an object. A list works the same way: it is a row of labels, each tied to its own object, while the objects themselves live anywhere in memory. This also explains the trap from Chapter 6, where [[0] * 4] * 3 gave three labels on one row of the table. What is left is to find out what a label is made of, since it weighs 8 bytes. The microscope will show us that; for now, on to the third question, how a list grows.

Experiment: the list grows

When we call append, the list gets longer. If the item labels lie in a row, every addition needs another 8 bytes of room somewhere. How does the list find them?

A list grows one item at a time through append. How do you think it reserves room?

Each time, room for the new item and no more When it runs out of room, it doubles it Each time it adds ten places Some other way

Some other way; the experiment below shows which. Textbooks usually talk about doubling, and up to 16 items CPython does look like a doubler. Beyond that, the law is different.

Here is the experiment. We append numbers to an empty list one at a time and weigh the list after each append, printing only when the weight changes. The weight tells us how many 8-byte places are reserved for items at the moment: subtract the header and divide by eight.

There it is: after each append the weight either stays put or jumps. The first item got four places at once, the fifth eight, the ninth sixteen. So far it looks like doubling. But then come 24, 32, 40, 52, 64, 76, 92, 108: places are added, but nowhere near twice as many. A list has a capacity, the number of places reserved, and a length, the number of places taken. The capacity is never less than the length, and when the length catches up, the capacity jumps.

The experiment has rejected the doubling hypothesis. What law takes its place? Small numbers won’t show it: rounding gets in the way too much. A naturalist in this position enlarges the sample. We grow the list to a million items and see by what factor, and by how much, the capacity grows at the last few jumps.

A million appends took only 86 jumps, and each one raises the capacity 1.125 times, by an eighth. More accurately, by an eighth and a few places more: an increase of 73,260 where an eighth would be 73,254. This gives the law

$$\text{new capacity} \approx n + \frac{n}{8} + \text{a little},$$

where $n$ is the length of the list at the moment of the jump. That “little” is why small lists grow almost twofold: at $n = 8$ an eighth is one place, and most of the increase comes from the extra. You will derive the exact formula CPython uses, down to the last place, in the task at the end of the chapter, and test it on the live interpreter on lengths up to a million.

The dissection

The behavior is described and the law is found; time for the scalpel. But first, a few words about memory.

A computer’s memory is a very long street of numbered little houses, each one a byte. On the machine our server runs on there are billions of them. A byte’s number is called its address. It is an unusual street: the processor can read the byte at any address in a single access, without passing the others. That is why this memory is called RAM, random access memory. How it is built out of gates, and how it manages this, is the subject of Chapter 31.

In CPython the function id(), which we have known since Chapter 2, returns an object’s address in memory: an object’s “number” is the number of its first byte. And the ctypes module can read memory at any address. Ordinary programs never do this, because one wrong address and the interpreter crashes. But we need a microscope for one experiment. We read the first forty bytes of the list object, five fields of 8 bytes each.

Five fields of the header, five finds. At offset 0 lies the number of labels hanging on the list: one at the moment, a. Add b = a and run it again, and it becomes two; when the number drops to zero, Python frees the object’s memory. At offset 8 is the address of the list object: that is how the list knows its type. At offset 16, the length, which len hands back without counting anything. At offset 32, the capacity we used to work out from the weight: five items, eight places. Another 16 of the 56 bytes are a service record for the garbage collector, which sits right before the object’s address.

The most interesting field is at offset 24. It holds the address of another place in memory: a separate block where the items are kept. We look in there, reading 8 bytes at a time from that address on.

Cell number $i$ holds id(a[i]), the address of the item. The label from Chapter 2 has turned out to be a number: a reference to an object is its address, and it weighs 8 bytes because addresses on a 64-bit machine are eight bytes long. The list doesn’t keep the numbers 10, 20 and 30; it keeps the addresses of the places where those numbers live. That is why a string from War and Peace and a zero need the same room in a list.

And the references themselves lie side by side, one after another: the cell addresses in the output differ by 8. A block of identical cells lying in a row in memory is called an array, and in an array the address of any cell is given by one formula:

$$\text{address}(i) = \text{start} + 8 \cdot i.$$

It also clears up the mystery of the last chapter. An array answers the question “what lies in cell number $i$?” instantly. To the question “is there a 30 anywhere?” it has no answer at all: a thirty can lie in any cell, and in opens them one at a time. If the cell number could be computed from the value itself, searching would be as instant as reading by index. That is how a set works; Chapter 16 has the details.

Moving house

This explains why the capacity grows in jumps. The item block is an array, and an array lies in memory in one piece. A cell can be added to its end only if the memory right after it is free. So the list takes room in advance, and when the spare room runs out, it asks the system for a bigger block. If the memory right after the old block is free, the block is extended in place. If someone already lives there, the list has to find free space at the other end of the street, move all its references there and free the old block. A list that grows this way, with spare room and moves, is called a dynamic array.

Only the item block moves. The list object with its header stays where it is; one field changes, the address at offset 24. That is why id(a) stays the same however much the list grows, and every label tied to it remains valid.

Now the same under the microscope, on live CPython. We append items one at a time and, after each resize, check whether the block’s address has changed. The experiment runs twice: in roomy memory, where hardly anything appears besides our list, and in crowded memory, where after every tenth append the program creates another small list, a neighbor.

In roomy memory about half the resizes happen in place: the block lies at the edge of the memory in use, and the space after it is free. In crowded memory nearly every resize is a move. The numbers change from run to run, because this is the behavior of the memory allocator, and it depends on everything the program did before. A naturalist knows the feeling: an animal behaves one way in a cage and another in the wild.

Coins

A move is expensive: every reference has to be carried over, and there may be a million of them. And yet in our measurements append always cost tens of nanoseconds, because moves are rare, and the bigger the list, the rarer they are. To see this clearly, we put the stopwatch aside and count the work: how many times a reference has to be carried from one place to another while the list grows to $n$ items. And we compare CPython’s law with other ways of reserving room.

The table splits the strategies into two worlds. Add a fixed number of places, one or a hundred, and the work per append grows with $n$: at a million items it comes to half a million copies per append with one spare place, and five thousand with a hundred. The whole list of $n$ items is built in $O(n^2)$, like the quadratic programs of the last chapter. Add a fraction instead, an eighth or as many again as there were, and the work per append stays put: seven to nine copies for CPython, about one for doubling, however many items there are.

Why a fraction saves the day is best explained with coins. Imagine that every append pays its own way in coins: one for writing its reference, and the rest go into a piggy bank. When a move comes, the piggy bank pays for it, one coin for every item carried over. The question is how many coins each append must put in so that the piggy bank never goes negative.

Take doubling. Right after a move the list has $m$ items and $2m$ places, and the piggy bank is empty. The next move comes after $m$ appends, and then $2m$ items will have to be carried over. If each of those $m$ appends puts two coins in the bank, there will be $2m$ of them by the time of the move, which is enough. So three coins per append will do forever: one for the write, two for the bank. CPython keeps an eighth in reserve, so there are only $m/8$ appends before the next move and $9m/8$ items to carry: each append has to save nine coins, ten in all. That is more, but it is still a constant. With a reserve of a hundred places, on the other hand, there are a hundred appends before a move, all $m$ items have to be carried, and each append has to save $m/100$, a number that grows with the list. No fixed fee can ever be enough.

A cost like this is called amortized, from the accountants’ word for spreading a large expense over many years. A single append sometimes costs $O(n)$, when a move falls on it. But averaged over any long sequence of appends, it costs $O(1)$. This is a guarantee, with no luck involved: the piggy bank proves it for every $n$. Arguments of this kind, the coins among them, were turned into a general method by Robert Tarjan in his 1985 paper “Amortized Computational Complexity.”

Still, CPython doesn’t double, because doubling has its own price. Right after a move half the places stand empty, while with CPython only a ninth do. It is a trade of memory for time, and different languages choose differently: Java’s ArrayList grows by half again, and std::vector in the library of the GCC compiler doubles. With any constant factor greater than one, append stays $O(1)$ amortized; only the number of coins changes.

Why inserting at the front is expensive

The coins won’t help with the third observation. To insert an item at the front of an array, cell 0 has to be freed, so all the other references must shift one cell to the right. You have to start from the end, or else every reference would overwrite one that hasn’t moved yet. We can draw this straight from Python: each call of show_list adds a frame, and a picture with a slider appears under the cell.

Five shifts for one insertion. In a list of a million items it takes a million shifts, and no reserve can help: the reserve is at the end, and the room is needed at the front. pop(0) costs as much (everyone shifts left), and so does inserting or deleting in the middle (half the list shifts). The shifting is done by fast C code rather than a Python loop, which is why you don’t see it on small lists. But it is $O(n)$ all the same, and on big lists it shows, as it did in our first experiment.

Here is what the dissection found. A Python list is a dynamic array of references. Reading and writing by index are $O(1)$: the address comes from a formula. append and pop() at the end are $O(1)$ amortized: the spare room takes care of them. Inserting and deleting at the front or in the middle are $O(n)$: everything has to shift. Searching with in is $O(n)$: nothing tells you where a value lives. If you want fast insertion at the front, you need an animal of another species.

Another species: the linked list

The picture you are about to see, boxes joined by arrows, was first printed by Newell and Shaw in February 1957, in their paper on how Logic Theorist was programmed, “Programming the Logic Theory Machine.” Linked lists have been drawn that way ever since. And in 1975 Newell and Simon received the Turing Award, with “list processing” named in the citation among their contributions. A couple of years after IPL, John McCarthy took up the idea in the language Lisp, whose name stands for LISt Processor.

In Python a linked list is built from the objects we learned to write in Chapter 12. Each item is a node: an object with two attributes, a value and a reference to the next node. The last node has no next one, and None sits there instead. The list itself is a reference to the first node, called the head, head.

Press “Steps”: node hops along the arrows from node to node. There is no other way to reach an item: the nodes don’t lie in a row, and there is no address formula for them. Such a chain is called a linked list.

The new species has mirror-image properties. To reach item number $i$ you have to follow $i$ arrows: $O(n)$ instead of the array’s $O(1)$. But inserting a node at the front takes three actions: create the node, give it a reference to the old head, and declare it the new head. Nothing shifts anywhere, however many nodes the chain has. Inserting or deleting a node right after the one you are standing on is equally cheap: change a couple of arrows. There is no spare room and there are no moves at all: every node lives wherever it happens to land, and the arrows keep the order.

Compare “push front” and “push back” in the kit. The first takes three steps at any length. The second walks the whole chain to find the last node: the longer the list, the longer it takes. If you need that often, keep a second reference next to the head, one to the tail, and appending at the end becomes $O(1)$ too. That will come in handy in one of the tasks.

Comparative anatomy

We gather the observations into a table, the way zoologists do when they compare the skeletons of related species. The last column is collections.deque, a hybrid we’ll come to shortly.

* Amortized. ** If you keep a reference to the tail.

A table is a hypothesis. We test it with a race. Three contestants (the list, deque and our linked list built on the class Node) perform the same operation on the server. After every five thousand operations the server reports what one of them cost, and the graph is drawn as the measurements come in.

The race also shows something the table doesn’t. In “insert at the front” our linked list is flat, as $O(1)$ should be, but it runs several times slower than deque: every node is a Python object, and creating an object costs far more than writing a reference into a ready cell. Asymptotics tell you how the time grows, not where it starts from. The last row of the table deserves a check too.

The tracemalloc module counts all the memory a program has taken from the system. A node of our linked list costs 88 bytes, an array cell 8: an elevenfold difference, and that is before counting the values themselves. There is a third reason why arrays nearly always beat home-made linked lists. The processor reads memory in chunks, so neighboring cells of an array come almost for free, while nodes are scattered through memory, and each one has to be fetched separately. How that works is explained in Chapter 34.

A hybrid: deque

Python’s standard library has a structure that takes the best of both species. It is deque from the collections module; the name is pronounced “deck” and stands for double-ended queue. Inside it is a linked list, except that each node is an array block of 64 references, and each node has two arrows, one to the next block and one to the previous. A chain with arrows in both directions is called a doubly linked list.

Adding or taking an item at either end is $O(1)$: the end block either has a free cell, or a new block is clipped onto the chain, and nobody has to shift. The memory per item is almost the same as for an array, since the overhead is a pair of arrows per 64 items. Reading from the middle, though, is $O(n)$: you have to walk the blocks from the nearer end, even if each step jumps 64 items at once. You can see it in the race, on the “read the middle” tab.

The last lines show a handy little feature: deque(maxlen=3) remembers only the three most recent items and pushes the old ones out at the other end by itself. That is how you keep “the last 100 lines of the log” or “the last ten actions.” Where else a double-ended queue is needed, and why list.pop(0) inside a loop is a hazard, is the subject of the next chapter.

Tasks

Four tasks: in two of them you build species of your own, one hides a catch about depth, and in one you have to derive the law we found, down to the last place.

A list is full: n items take up all n places. We call append. Write a function grow(n) that returns the new capacity, the number of places there will be. You may not use sys.getsizeof, only arithmetic: you are deriving the law, not measuring it. The tests compare your answer with CPython 3.13 for every n from 0 to 3000 and for a hundred random n up to a million. [None] * n gives you a full list of n items; you can experiment on it in a separate cell.

Collect data first. In a separate cell, for a few dozen values of n, run a = [None] * n, a.append(None) and print (sys.getsizeof(a) - 56) // 8. Compare with n + n // 8: how far off is it?

All the capacities are divisible by 4. So something at the end is rounded to a multiple of four, but up or down? Try rounding down an expression of the form m + m // 8 + c, where m is the new length, n + 1, and c is a small constant.

Rounding down to a multiple of four: x // 4 * 4.

In CPython’s source code (the file Objects/listobject.c, the function list_resize) this formula reads new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3. The shift >> 3 is integer division by 8, and & ~3 clears the two lowest bits, which rounds down to a multiple of four; bits and masks are in Chapter 28. Next to it in the source there is a comment with the sequence we measured: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76…

Write a class DynArray, a dynamic array like CPython’s. Keep the items in the attribute data, a list of fixed length that plays the part of a memory block: create it as [None] * capacity and never change its length (no append, insert or pop on it). When there isn’t enough room, create a bigger block and carry the items over. You need:

• DynArray(), an empty array; the attribute capacity says how many places the block has (it equals len(data));
• append(x), which adds at the end in amortized $O(1)$;
• pop(), which removes the last item and returns it; on an empty array, IndexError;
• arr[i] and len(arr), the methods __getitem__ and __len__; for i outside 0…len-1, IndexError.

The tests append 200,000 items and make sure there are no more than ten copies per item.

The move: new = [None] * new_capacity, then a loop that copies self.data[i] into new[i] for every occupied i, then self.data = new and self.capacity = new_capacity.

Make the new capacity a constant number of times bigger than the old one, say twice as big. Adding a constant number of places, a hundred for instance, won’t pass the test on the number of copies.

In pop, remember to write None into the freed cell. Otherwise the array keeps a label on an object that no longer belongs to it, and that memory is never freed.

A Python list can also shrink: if after a pop fewer than half the places are in use, CPython asks the system for a smaller block. Shrinking at exactly half would be a mistake: then alternating append and pop at the boundary would cause a move on every step. Think about why.

Write a class LinkedList built on Node nodes (the node class is already in the starter). The methods:

• push_front(x) and push_back(x) add at the front and at the end, both in $O(1)$;
• pop_front() removes the first item and returns its value; on an empty list, IndexError;
• len(lst) works in $O(1)$, that is, without walking the nodes;
• to_list() returns an ordinary list of the values from head to tail.

The tests add a hundred thousand items at the end and ask for the length a hundred thousand times, with a time limit.

The starter is correct but slow in two places: push_back and __len__ walk the whole chain. What could the object keep so that it doesn’t have to walk?

Keep self.tail, a reference to the last node, and self.size. Every operation has to keep them up to date. The special cases: adding to an empty list (head and tail are the same node) and removing the last node (the tail becomes None again).

A tail reference and a counter are the classic trade: a little memory, and care in every method, so that two operations drop from $O(n)$ to $O(1)$. The most common mistake is forgetting to reset tail when the last node is taken: the next push_back then hooks the new node onto a node that is no longer in the list.

Write a function reverse(head) that reverses a linked list in place and returns the new head: 1 → 2 → 3 becomes 3 → 2 → 1. Don’t create new nodes; re-point the arrows of the old ones. An empty list is None. The tests also try a chain of two hundred thousand nodes.

The starter is correct and short, but on a long chain it will crash. Remember Chapter 9: how deep does this recursion go?

Walk the chain with a loop, holding two references: prev, the head of the part already reversed (None at first), and cur, the first node not yet reversed. At each step one arrow has to be turned around, the one from cur. Try the “reverse” button in the construction kit above.

Before you re-point cur.next, save it: nxt = cur.next. Otherwise the rest of the chain is lost.

One pass, three references, $O(n)$ time and $O(1)$ extra memory. The recursive version is also $O(n)$ in time, but it keeps $n$ frames on the call stack and on two hundred thousand nodes runs into the depth limit. This task is a regular at job interviews: it shows whether a person can re-point arrows without losing a piece of the chain.

What next

Adding to the end of a list and taking from the end cost $O(1)$; at the front, $O(n)$. If you touch only the end, a list becomes a ready-made store for things you need back in reverse order: the last thing put in is the first to come out. This order turns up more often than you might think. The browser’s “Back” button returns you to the last page you opened. Ctrl+Z undoes the last action, then the one before it. The functions of Chapter 9 return in the reverse order of their calls. What this structure is, why the first scientific pocket calculator, which had no “=” button, ran on it, and how to use it to teach a program to understand parentheses: all in the next chapter.