Algorithms Ch.2: Why Linked Lists Lose to Arrays in Real Code

0:00 Welcome to Learning Podcasts. Algorithms, chapter two: memory layout. Today we explain why two functions with the same big-O can finish ten times apart on the same machine. Picture two functions. Each one walks a million numbers and adds them up. Both are written in idiomatic code. Both are obviously O of n. You run them. The first finishes in around fifty milliseconds. The second takes ten times as long. Same algorithm. Same algorithm. Same operation count. Same complexity class. The only thing that differs is how the numbers are laid out in memory.

0:33 One walks an array. The other walks a linked list. That single choice is doing all the work. So big-O says they are equal, and the machine says one of them is destroyed. Right. This chapter is about that gap. Most data structures you use every day are built on top of two primitives. The first is the array. One contiguous block of memory holding values of the same kind, end to end. Reaching the tenth element does not involve walking past the first nine. The runtime knows where the array starts, knows the size of each element, and computes the address directly.

1:08 Constant-time random access. The second is the linked list. Many small nodes, each holding a value and a pointer to the next node. The list itself is just a reference to the first node. To reach the tenth element, you walk nine pointers. Each pointer can point anywhere in the heap. The mental model most engineers carry is that the CPU fetches a value, does some math, fetches the next one, does more math, and each fetch costs about the same. That model has been wrong for decades. A modern CPU does not fetch values.

1:40 It fetches cache lines, sixty-four byte chunks of memory. So one read pulls in a whole batch. Right. When you read a single integer, the hardware quietly loads the entire cache line that integer lives in into a small fast memory close to the core. Ask for something nearby and it is already there. The CPU is also constantly trying to predict what you will need next. When it sees you walking memory in a regular pattern, it prefetches the next cache lines ahead of the cursor, before your code even asks.

2:11 These costs are not abstract. A hit in the closest cache costs around five cycles. The next level out is around twelve. The level after that is around forty. A trip out to main memory is on the order of two hundred cycles. That is not a small constant factor. That is the difference between a function that fits in its time budget and a service that misses its deadline. So go back to the array loop. It walks straight through one contiguous block. Each cache line carries many values. Every time the CPU pulls in sixty-four bytes, it gets a batch of array entries for free.

2:44 The prefetcher sees the regular forward pattern and starts loading the next batch before the cursor gets there. Most of the reads are hot in the cache. The hardware is doing your job for you. It is. Now the linked list loop. The cursor jumps from one heap-allocated node to another. The next pointer can land anywhere. Each step is potentially a brand new cache line, possibly a brand new page. The prefetcher cannot help, because there is no pattern to predict. The cost per step stops being arithmetic and starts being a wait on memory.

3:18 Same operation count. Different physics. Now the part that surprises most engineers. The textbook line on linked lists is that they shine for insert and delete in the middle. Arrays have to shift elements; linked lists just rewire two pointers. That is true if you somehow already have a reference to the exact node you want to splice. But in real code you almost never do. You have an index. You have a key. You have a search criterion. To find the right node, you walk the list from the front. That walk is expensive in cache terms.

3:57 By the time you have located the node, you have already paid more than the cost of an array shift would have been. So the constant-time splice is real, but you cannot reach it. There is also a memory cost that is easy to forget. Every linked list node carries at least one pointer next to its value. On a sixty-four bit machine that pointer is eight bytes. If your value is a four-byte integer, the bookkeeping is twice the size of the data. And that bookkeeping is exactly what causes the cache misses.

4:30 So how does a Python list happily grow from zero to ten million elements when a real array has a fixed size? The answer is that a dynamic array is not a single array. It is a small wrapper around an array, plus a strategy for what to do when the array fills up. The strategy is to allocate a buffer that is bigger than the current contents. As long as there is room, append is just writing into the next slot. When the buffer runs out, the runtime allocates a new bigger one, copies every element across, and frees the old one.

5:04 That single resize is linear in the current size. So the question is how aggressively the buffer grows. Right. CPython grows the buffer by roughly twelve percent on each resize. Java's ArrayList grows the buffer by one and a half times its current size. C++ vectors usually grow by one and a half to two times the current size. They all share the same shape: geometric, not fixed-step. Chapter one called this pattern amortized constant time. The picture in front of you is the practical version of that idea.

5:35 Most appends are tiny. A handful are tall because they trigger a resize. The total work, summed across the whole history of the list, stays proportional to the final length. But the spikes are still real. They are. If you are running a service where any individual operation must finish under a tight latency budget, you cannot just hand-wave the spike away. Plenty of real systems pre-size their buffers exactly because they want to avoid resize jitter, even though the long-run throughput would have been the same.

6:04 After all of that, you might wonder if linked lists are simply obsolete. They are not. They are just narrow. They win in places where you genuinely have a direct reference to the node, and the operation you need is to splice that node in or out cheaply. The cleanest example is an LRU cache. It keeps the most recently used items at one end and the least recently used items at the other. Every read moves an entry to the most-recent end. Every overflow drops the entry at the least-recent end. So the question is how you find a node fast and move it without sliding everything else.

6:41 Right. The standard implementation pairs a hash map with a doubly linked list. The hash map gives you direct access to the node for a given key in expected constant time. The list lets you unlink that node from its current position and stitch it back at the front in constant time, no matter how big the cache is. An array would force you to slide entries around on every access, which would defeat the purpose. Another classic place is the free list inside a memory allocator. When the allocator hands a block back to its pool, it threads that block onto a list of available blocks.

7:15 The block itself is the linked list node, so there is no extra allocation just to track it. Pushing or popping at the head is constant time. An intrusive list. The data is the node. Right. The pattern in every case where linked lists win is the same. The list is hidden inside a structure that already gives you the right node directly. You are not searching the list. You are just splicing. So the practical version of all this comes down to a few habits. When you reach for a sequence in everyday code, default to a dynamic array unless you have a concrete reason not to.

7:50 Python lists, Java's ArrayList class, Go slices, C++ vectors. They are fast not because the language designers were lucky, but because they cooperate with the cache. Be skeptical when you see code building lists by repeatedly inserting at the front, or removing from the middle by index. Both of those operations are linear in array-backed structures, and they are linear in linked lists too once you account for finding the position. If those operations are your hot path, change the data structure.

8:20 A queue with a head and a tail. A heap. A hash set. The right structure replaces a slow operation with one that is genuinely cheap on the hardware you have. Big-O describes the slope of the road. The cache writes the constants. Two structures with the same complexity class can behave very differently because the constants are not the same constants. Next chapter we go to the data structure that everything else seems to be built on. Constant-time lookup by key. Thanks for listening to Learning Podcasts.