Linked list

Put the cursor at the very start of Part One of War and Peace and type a letter. If the text is stored as an array, all 244,500 characters after the cursor move one cell to the right. If as a linked list, the new letter takes its place between two neighbours, and four links change. Below is Part One of Volume One in three forms at once: an array, a doubly linked list and a gap buffer, the structure Emacs is built on. The novel is in the original Russian. Type, move the cursor, put cursors after every «Пьер» (Pierre), and watch who does how much work.

A letter at the start of the text costs the array 244,500 shifts and the list four links, and the same for every following letter. The gap buffer pays as much as the array for the first letter: the gap, an empty space inside the array, starts at the end of the text and has to move to the cursor. But after that letters drop straight into the gap and cost nothing. Now tap the text somewhere in the middle. For the array this is free: a position is just a number. The buffer pays nothing right away either and moves the gap to the new place on the first edit. The list, though, knows no numbers and walks to the new place on foot, node by node, from the nearest of the three places it remembers: the start, the cursor and the end.

The idea

The elements lie wherever they happen to be in memory, and each holds a link to the next one, and in a doubly linked list to the previous one too. The order is set by the links, not by addresses. So inserting an element next to a node you already have in hand, or taking such a node out, means rewriting two to four links, however many elements the list has. The price is that an element’s number says nothing about where it is: reaching the k-th takes k steps.

The whole article is about the proviso “already in hand”. If the node first has to be found by index or by value, the list goes through O(n) nodes, and its fast insertion no longer changes anything. How to build a list out of Python objects, why it was invented for the first artificial intelligence program, and how it differs from list and deque is told in the course chapter on lists. Here is what you need to use one seriously: sentinels and rings, an honest comparison with an array, and loops.

Four links and a sentinel

Inserting a letter before the node at where the cursor stands is, in a doubly linked list, four assignments. The new node gets a link back, to the left neighbour, and forward, to at; the left neighbour now looks forward to the new node, and at looks back to it. Deleting the letter to the left of the cursor is two assignments: the neighbours of the erased node start looking at each other, and the node itself drops out of the chain, although the links inside it still lead somewhere.

Trouble starts at the edges. The first node has no left neighbour, the last no right one, an empty list has nobody, and every operation grows checks for “what if this is the start”. They are removed by one empty node that holds no data, a sentinel. The list closes into a ring through it: the sentinel’s right neighbour is the first node, its left the last, and in an empty list the sentinel looks at itself. Now every node always has both neighbours, and inserting at the start is no different from inserting in the middle. This is how container/list in Go is built (the source says it plainly: internally the list is implemented as a ring, with the root node as a sentinel), as is OrderedDict in the version written in Python itself (a comment says the sentinel is never deleted, which simplifies the algorithm), and the Linux kernel lists.

In the editor in the scene the cursor is a link to the node it stands before, and a cursor before the sentinel means the end of the text. So the “to the start” and “to the end” keys are free: the sentinel’s right neighbour and the sentinel itself are always known. But going to the middle costs as many steps as it takes to get there.

Where a list wins

There is one condition: the node is already in hand, and something constant has to be done with it: insert a neighbour, take it out, move it elsewhere.

Many cursors. Press “A cursor after every «Пьер»” in the scene and type a couple of letters. Each letter is inserted at every cursor, and on every insertion the array shifts its whole tail. In the last edit of the novel listing the cursors stand after all 36 occurrences of «князь Василий» (Prince Vasily), and « Курагин» (Kuragin) is typed: the array shifts 33,864,016 characters, the gap buffer moves 1,456,970, because on every letter the gap travels round all the cursors, and the list rewrites 1152 links, four for each of the 288 letters inserted.

An LRU cache. A cache of limited size, once full, throws out the entry that has gone longest without being accessed. A dictionary finds an entry by key in O(1), and a doubly linked list keeps the entries in order of access. On a hit the node is taken out of its place and put at the end, four links, with no search at all, because the dictionary hands over the node itself. This is how functools.lru_cache in CPython works: in its source every entry has prev and next fields, and a hit cuts the entry out and appends it before the sentinel. The details are in the article on the LRU cache.

A ring. When a sequence has neither start nor end, its natural form is a circular list: a queue of tasks to which the processor hands out time in turn, players at a table, free blocks of memory. The memory allocator in Kernighan and Ritchie’s book “The C Programming Language” keeps the free blocks exactly this way, as a circular list. Go has a separate package for it, container/ring.

A node inside the object. In the Linux kernel the links prev and next are a field struct list_head inside the structure itself, a process for instance, and not a separate node pointing to it. Such an intrusive list spends no memory on extra nodes, an object with several such fields sits in several lists at once, and it can be taken out of any of them in O(1) with only the object itself in hand. The list_entry macro recovers the address of the structure from the address of the field embedded in it.

There is a quiet advantage too: a node never moves. An element of a dynamic array is copied to a new block when the array grows, and a reference to the old place becomes invalid; a reference to a list node stays valid whatever is inserted and deleted around it.

Where it loses: memory and the cache

Each link is eight bytes on a 64-bit machine. A node of a doubly linked list of letters in Go is a letter and two links, 24 bytes instead of four for an element of []rune and less than two on average for Russian text in UTF-8. In Python a node with __slots__ takes 56 bytes, plus the object of the letter itself, and on Part One of the novel it comes to about a hundred bytes per character.

Worse than the memory is the order of traversal. The processor reads memory in cache lines of 64 bytes and can fetch the next ones in advance if the addresses go in a row. That is how it reads an array. A list cannot be read like that: the address of the next node becomes known only once the current one is read. Below is the summing of n numbers: from a slice, from a list whose nodes were allocated in a row, and from the same list with its links shuffled, as after a long life of insertions and deletions in different places.

In Go a slice spends about half a nanosecond per number at any n. A list with nodes in a row, about one and a half: each step waits until the previous one is read, but the nodes lie close together and are already in the cache. A shuffled list with a thousand nodes is hardly different from an unshuffled one, with ten thousand it is already four times slower, and once it stops fitting in the cache, each step becomes a trip to main memory: with two million nodes it is 146 nanoseconds per number, more than two hundred times longer than a slice. In Python all three lines are higher because of the interpreter, but with 300 thousand shuffled nodes the picture is the same: 385 nanoseconds against 71 for a Python list.

Now an honest test on the list’s favourite operation, insertion in the middle. Bjarne Stroustrup showed this problem in 2012 at the GoingNative conference and says it was devised by Jon Bentley: insert random numbers so that the sequence stays sorted. The place for a number is found by scanning from the start in both cases; after that the array shifts its tail and the list changes one link.

In Go the array is no worse than the list at any n: with a thousand numbers they are level, with twenty thousand the array is seven times faster. Both structures spend O(n) finding the place, but the array scans it in a row, and shifting the tail is one fast memory copy. The list pays a cache miss for every step of the search, and its gain on the insertion itself drowns in the search. In Python the lines almost merge: a step of the interpreter’s loop costs more than both a cache miss and a shift. Stroustrup drew a rule from this: by default use vector, store data compactly and access memory predictably. A linked list is justified where no searching is needed.

Code

The editor from the scene in miniature: a doubly linked list of letters with a sentinel and a cursor, and next to it the same editor on an array. The keys are as in the article’s first problem: < and > move the cursor, [ and ] send it to the start and the end, # erases the letter on the left. Both editors get the same keystrokes, and the program prints the text with the cursor, how many links the list rewrote and how many characters the array shifted.

A dash at the start of the line cost the array 62 shifts: two characters, and each shifted all 31 characters of the text. The list, eight links, four per character, like any other insertion. For real work Go has the ready-made container/list built the same way; here the list is written by hand so that all four links can be seen.

Now the whole of Part One of the novel, in three forms at once. The program reads War and Peace from the server where the code runs, cuts out Part One of Volume One and makes four edits, the same as the button in the scene.

edit                          array shifts  list hops   links   gap moves
start: Война и мир. Том...       6,112,500          0     100     244,500
end: Конец первой части.                 0          0      76     244,500
first Наташа: + Ростова          1,303,816     81,567      32     162,977
36 x князь Василий: + Курагин   33,864,016          0   1,152   1,456,970
total                           41,280,332     81,567   1,360   2,108,947

The third line is the list’s weak spot: to add the surname «Ростова» (Rostova) after the first «Наташа» (Natasha), it had to walk 81,567 nodes from the start of the text. The array, though, shifted 162,977 characters for each of the eight letters. In absolute terms all these shifts are cheap: shifting 244,500 characters of []rune in Go is a copy of a megabyte of memory, about 15 microseconds on the Mac where the examples were checked, and a person at the keyboard will not notice it. The count changes with files of hundreds of megabytes and with dozens of cursors: then every keystroke shifts gigabytes.

A loop in the chain: the tortoise and the hare

A list can close into a loop, by mistake, when a link pointed back, or because that is how the data is arranged. Take the generator of “random” numbers that John von Neumann proposed in 1949: square a four-digit number, pad it with zeros on the left to eight digits and take the middle four. 0540 gives 2916, then 5030, then 3009, and 0540 again. Each number determines the next uniquely, so the sequence is a linked list where the link to the next node is not stored but computed. There are finitely many numbers, so the chain is bound to loop. First comes a tail of μ numbers that will never occur again, then a cycle of length λ spins for ever, and the whole picture looks like the Greek letter ρ.

μ and λ can be found by remembering all the numbers in a dictionary until one of them repeats. But that takes μ + λ cells of memory, and if a node is a program state of a megabyte, that is unaffordable. The algorithm attributed to Robert Floyd makes do with two pointers. The tortoise moves one number at a time, the hare two.

In the scene the drawing knows the shape in advance, but the pointers do not: they have only two numbers. Start with 0156: a tail of eight numbers, a cycle of four, 6100 → 2100 → 4100 → 8100. The number 1234 slides down to zero in 56 steps and stays there for ever: a cycle of length one. For the eight-digit 80770865 the tail stretches over 16,279 steps and also ends at zero. Von Neumann himself knew that his method quickly degenerates and considered this a virtue: degeneration is easy to notice. He is also the author of the remark that anyone who produces random digits by arithmetic is in a state of sin.

In 1980 Richard Brent proposed a faster variant: the tortoise stands still and jumps to the hare when the hare’s step count reaches the next power of two. By Brent’s own estimate it is on average about 36% faster than Floyd’s method. The program below finds μ and λ in three ways, by Floyd, by Brent and with a dictionary, and counts how many times each evaluated the formula.

digits      seed     mu  lam  cycle entry  floyd calls  brent calls  remembered
     4       540      0    4          540           16           11           4
     4      6100      0    4         6100           16           11           4
     4      5546    101    4         4100          518          337         105
     6    857729    689  210       119585         4108         2821         899
     8  80770865  16279    1            0        81396        48943       16280

The dictionary evaluates the formula least of all, exactly μ + λ times, but keeps all 16,280 numbers in memory. Floyd and Brent compute more, but remember two or three numbers whatever the length of the chain. The same trick underlies Pollard’s rho method, which factors numbers: there the loop is sought in a sequence of remainders modulo a divisor not yet known, and remembering it is impossible in principle. And with random number generators the cycle is the first thing checked: the length of the period is a measure of quality; more on it in the article on generators.

What it costs

Asymptotics say less than usual here. A list and an array both go through n elements in O(n), but the measurement above shows a difference of hundreds of times: the array gets eight numbers with each cache line, while the shuffled list waits for a new line from memory at every step. Binary search on a list does not work either: the middle has to be walked to, and that is already O(n). The way along a list can be sped up by adding links that skip several nodes; that is how a skip list is built.

History

The linked list was invented in 1955–1956 by Allen Newell, Cliff Shaw and Herbert Simon: their language IPL and the Logic Theorist program written in it rested on it. The familiar picture of boxes joined by arrows first appeared in Newell and Shaw’s 1957 paper “Programming the Logic Theory Machine”. As early as 1953 Hans Peter Luhn of IBM had proposed chaining together the records that land on the same number in a hash table. In 1958 John McCarthy began Lisp, where the list became the main structure, and in 1975 Newell and Simon received the Turing Award, whose citation names list processing. This history is told in detail in the course chapter.

Donald Knuth attributed the tortoise and hare algorithm to Floyd in 1969, in the second volume of “The Art of Computer Programming”. It does not appear in Floyd’s published work, so the authorship is in question; the name has stuck all the same.

Problems

In the first problem a document has to be restored from a log of keystrokes, and the well-known two-stack solution is too slow there: the “to the start” and “to the end” keys make it move the whole text across. In the second, find the tail and cycle of von Neumann’s generator for many seeds.