Linked lists

An array keeps a sequence in one block of memory, which makes every position one arithmetic step away and every insertion in the middle a shift of everything behind it. A linked list makes the opposite trade: each item lives in its own node, and each node points to the next one, so inserting or removing an item next to a node you already hold rewrites at most four pointers whatever the length, while reaching position i means following i pointers from the front. That trade is behind queues and stacks that never move their items, the chains of a hash table, adjacency lists, editor buffers, undo histories, operating system run queues and the least recently used cache in front of almost every slow store. This page defines the list as an abstract sequence and builds it in every common shape: singly linked with a head and a tail, with a sentinel node, doubly linked, circular, and circular doubly linked with a header. It traces every insertion and deletion pointer by pointer, shows why the order of the pointer writes decides whether the list survives, reverses a list, finds a cycle with Floyd's tortoise and hare, merges sorted lists, builds an LRU cache from a dictionary and a doubly linked list, and measures all of it against Python's list, collections.deque, OrderedDict and functools.lru_cache in counted hops, pointer writes and element moves. Afterwards you will be able to write any list operation without losing a node, trace it by hand, and tell when a linked list beats an array and when it does not. It builds on Asymptotic analysis and pairs with Arrays and dynamic arrays.

The structures need only the standard library; to run the plots, the sample project and the notebook install the base group.

Intuition

Picture a treasure hunt. Each clue tells you where the next clue is hidden, and nothing else: there is no map of all the hiding places. To reach the fifth clue you must find the first four. In exchange, the hunt is easy to change. To add a clue between the second and the third, you hide the new clue, write on it where the third one is, and then change the second clue to point at the new one. Nothing else moves. To drop a clue, you change the clue before it to point past it.

Now picture the same clues pinned in a row on a long board, in order. Anyone can walk straight to the fifth one, because its place on the board says where it is. But to add a clue between the second and the third, every clue from the third onwards has to be unpinned and moved along one place.

The first picture is a linked list and the second an array. The whole topic is about the first picture's two promises and its one danger. Changing the list next to a clue you hold costs a fixed handful of pointer writes. Finding a clue by its position costs a walk. And the instructions must be followed in the right order: if you change the second clue before writing the third clue's location on the new one, nobody knows any more where the third clue is.

The diagram shows the abstract data type at the top and the three ways Python programs usually implement it below. The outlined linked list is the only implementation with no element moves at all.

The linked list comes in the five variants on the left, which this page builds one by one, and the filled boxes on the right are the jobs each does in this handbook and elsewhere.

How it works

The list as an abstract sequence

A sequence holds items in an order that the user decides, not one derived from the items. Its operations are:

• len, and iterating over the items in order.
• get(i), the item at position i, counting from 0.
• find(x), the first position or node holding x.
• insert at the front, at the back, at position i, or next to an item already found.
• remove at the front, at the back, at position i, the first item equal to x, or an item already found.

Python's list, collections.deque and every linked list in this package implement this contract with the same results; they differ only in what each operation costs. LinkedSequence in sequence.py holds the parts every linked variant shares: walking, indexing and searching only need to know where the first node is.

Nodes and pointers

A node is a small object with a value and one pointer, next, to the following node, or null (None) after the last one. A doubly linked node has a second pointer, prev, to the node before it. In Python both are classes with __slots__, which store the fields in fixed slots instead of a per-object dictionary and make each node several times smaller (see the memory section below).

Everything a linked-list operation does is made of three primitive actions, and pointers.py implements exactly these three, each counting itself and recording a trace step:

• link: write a pointer field, such as node.next = other or head = node. Counted as links.
• hop: follow a pointer, such as cur = cur.next. Counted as hops.
• matches: compare a stored value with the one searched for. Counted as comparisons.

Every cost on this page is a count of these three, plus, for Python's list and deque, element moves: one element written into an array slot.

A singly linked list with head and tail

SinglyLinkedList keeps two pointers of its own: head, the first node, and tail, the last node, both null when the list is empty, and a size. Its invariant is that following next from head visits exactly size nodes, the last of which is tail, whose next is null. The tail pointer is optional; it makes appending cheap, and in exchange every operation that changes the last node must update it. The validity check check_linked_list walks the list with a bounded walk and names the first broken part, so a list whose pointers loop by mistake fails the check instead of hanging it.

Inserting

There are five places to insert, and they reduce to two patterns.

• At the front: the new node's next takes the old head, then head takes the new node. Two links. If the list was empty, tail takes the new node too.
• At the back: the old last node's next takes the new node, then tail moves to it. Two links, thanks to the tail pointer; without one, finding the last node would cost n − 1 hops. If the list was empty, head takes the new node instead of a last node.
• After a node you hold: the new node's next takes node.next, then node.next takes the new node. Two links, plus a tail update when node was the last node.
• Before a node you hold: a singly linked node does not know its predecessor, so predecessor walks from the head until prev.next is the node, and the insertion becomes an insertion after prev. At the head there is no predecessor and it becomes an insertion at the front.
• At position i: position 0 is the front and position n is the back; any other position needs the node at i − 1, reached in i − 1 hops, followed by an insertion after it.

The pattern for the middle is worth stating as code, because the two lines may not be swapped:

self.link(new, "next", node.next, trace)
self.link(node, "next", new, trace)

Deleting and searching

Removal mirrors insertion. Removing the first node moves head to head.next, one link, and clears tail too when that empties the list. Removing the node after prev makes prev.next skip it, one link, and moves tail back to prev when the removed node was the last. Removing the last node needs the second-last node, so even with a tail pointer it walks n − 2 hops: the tail pointer helps to append but not to remove. Removing at position i walks to node i − 1 and removes the node after it. Removing by value walks two pointers, prev one node behind cur, because unlinking cur means writing prev.next; the walk compares each value with the one searched for.

A removed node is simply no longer reachable. Python's garbage collector frees it once nothing refers to it; a language with manual memory management would free it explicitly at this point, after the pointers around it have been rewritten.

Searching is a walk from the head comparing each value. A value at index i costs i + 1 comparisons and i hops, and a missing value costs n comparisons and n − 1 hops. There is no shortcut: even a sorted linked list cannot be binary searched, because reaching its middle already costs n/2 hops.

The order of pointer writes

Every insertion and deletion is a short sequence of pointer writes, and each write destroys the value the field held before. The rule that keeps a list intact is: before overwriting a pointer, make sure the node it points to is still reachable some other way. In an insertion after node, the only reference to the rest of the list is node.next. Writing it first, node.next = new, leaves nothing that points to the old successor, and the next statement, new.next = node.next, copies the new node's own address into it. The new node points to itself and the rest of the list is gone.

The two pairs show what an insertion changes and nothing else: two pointers in a singly linked list and four in a doubly linked one, drawn dashed, while every other pointer keeps its target. These pictures are written by examples/worked_example.py from the actual nodes before and after the call.

The left column is the safe order and the right column the order that loses the list: after its first write node 43 and everything after it are unreachable, with no arrow left pointing into them, and its second write closes a loop on the new node. A trace of the broken version prints the list as [18, 26, 31, 31, 31, ...], because a walk from the head never reaches null again; the package's bounded walks stop and mark the cut with an ellipsis. The same rule decides the order in every other operation on this page: in a doubly linked insertion the new node's own two pointers go first, because writing them only reads the list, and node.next goes last, because it is the way to the successor.

Sentinel nodes

Most of the special cases above exist because the first node has no predecessor: inserting at the front writes head instead of a next field, and removing the first node does the same. A sentinel, or dummy, node removes them. SentinelList keeps a node that holds no value and sits before the first real node forever; dummy.next is the first real node, and tail is the dummy itself when the list is empty. Now every real node has a node before it, so there is one insertion routine, insert_after(prev), and one removal routine, remove_after(prev), and the front, the middle and the back all use them: the front is insert_after(dummy) and the back insert_after(tail). The search for removal by value looks one node ahead, comparing prev.next.value, so it stops on exactly the node the removal needs.

The sentinel costs one node of memory and makes the walk to position i one hop longer, and in exchange the code has no branch for the empty list or the front. The same trick appears as the dummy node at the start of a merge, and as the header of the circular doubly linked list below, where it removes every special case.

Doubly linked lists

A doubly linked node also points back to its predecessor. The invariant gains a mirror condition:

With it, a node can be removed in O(1) given only the node: its predecessor's next takes its successor and its successor's prev takes its predecessor, two links, with head or tail standing in for a missing neighbour at the ends. Insertion before a node is as cheap as insertion after it, because node.prev is the predecessor a singly linked list has to search for; each insertion writes four pointers. The last node can be removed in O(1) too, so a doubly linked list with a tail pointer is a deque. Walking can start from either end, so node_at(i) walks from the nearer end and never needs more than about n/2 hops. The price is one more pointer per node and twice the pointer writes per change, and every one of those writes must keep the mirror condition, which makes doubly linked code the place where a forgotten back pointer silently breaks backward walks.

Circular lists

In a circular list the last node points back to the first, so no next is ever null. CircularLinkedList keeps a single pointer, tail, to the last node: the first node is then tail.next, one hop away, and both ends are O(1) to insert at. Inserting at the front places the new node between the last node and the first; inserting at the back does the same and then moves tail one step forward onto the new node, because in a ring the node after the last is the first. A one-node ring is a node whose next is itself, and the empty ring has no tail at all.

Because no pointer is null, every walk must stop on returning to where it began, or after size steps; the package bounds every walk by the size, which is also what makes searching for a missing value terminate. Two rings can be spliced into one in O(1) with three pointer writes (concatenate), and advancing tail by one rotates the ring, the round-robin turn of a scheduler. Removing the last node still needs its predecessor and so still walks n − 2 hops.

Circular doubly linked lists

A circular doubly linked list (CircularDoublyLinkedList) closes the ring in both directions: the first node's prev is the last node and the last node's next is the first. A single pointer to the first node then reaches both ends in one hop, and both ends are O(1) for insertion and removal. Only the empty list needs a case of its own; a one-node ring is a node that is its own neighbour on both sides.

Adding a sentinel to the ring removes that last case. In HeaderList a header node closes the ring between the last node and the first: header.next is the first node, header.prev the last, and the empty list is the header pointing to itself both ways. Every insertion is the same four writes (splice_in) and every removal the same two (splice_out), with no test for an end or for emptiness anywhere. This is the list the LRU cache below is built on, and the shape of the list type inside operating system kernels.

The left column shows each variant with the same three values and the right column its smallest case, where the special cases live. Between two doubly linked nodes the next pointer runs above the prev pointer, each from node to node; pointers that turn back run in loops below the row. These states are drawn by examples/variants_and_sentinels.py from the real structures, which also run the same random operations as a Python list and check every invariant after every operation.

Reversing a list

Reversing a singly linked list in place turns every next pointer around. The iterative method keeps three pointers: previous, the head of the part already reversed; current, the head of the part not yet touched; and following, saved in each round before current.next is overwritten, because nothing else refers to the rest of the list. Each round does following = current.next, current.next = previous, previous = current and current = following. The loop invariant is that the two parts together hold every node exactly once, the first reversed and the second untouched; when current reaches null, previous heads the reversed list.

Each frame lays the two parts out side by side, as two separate lists, which is exactly what they are between rounds. The recursive version reverses everything after the head and then hangs the head behind its old successor. It is shorter, but it needs a stack frame per node, so its depth is the length of the list; Python's default recursion limit of about 1000 frames means a list of 2000 nodes raises RecursionError, while the iterative loop reverses 100000 nodes without trouble. That is why reverse_chain is the one the lists use, and why recursion on lists belongs only where the depth is known to be small (see Recursion). A doubly linked list reverses by swapping each node's two pointers and then head and tail.

Detecting a cycle

A chain of nodes that should end in null may instead loop back into itself, through a bug or by design. Its shape is then a rho: a tail of μ nodes leading into a cycle of λ nodes. Walking it naively never ends. Remembering every node visited in a set finds the loop in μ + λ hops, at the cost of memory for every node.

Floyd's tortoise and hare does it with two pointers. The tortoise moves one node per round and the hare two. If the chain ends, the hare reaches null first. Otherwise both enter the cycle, where the hare gains one node per round, so it catches the tortoise. Number the positions along the rho from 0 at the head; position p ≥ μ lies on the cycle, and two positions name the same node only if they are equal or both on the cycle and congruent modulo λ. The tortoise is at position t after t rounds and the hare at 2t, so:

The second phase finds where the cycle starts. The meeting point is a whole number of laps from the head, t = kλ, so moving one pointer back to the head and stepping both pointers one node at a time brings them together at the start:

The number of single steps taken in the second phase is μ itself, and one more lap from the start counts λ. floyd returns all four facts in a CycleReport, and remove_cycle uses them to cut the pointer that closes the loop.

The loop below the row is the pointer from 79 back to 31. The worked example below traces every round.

Merging two sorted lists

Two sorted lists merge into one by relinking their nodes: no node is copied and nothing is allocated except one dummy node that stands before the result, so appending the first node is no different from appending any other. In each round the smaller of the two front values is unlinked from its list and linked after the last node of the result. On equal values the node from the first list is taken, which makes the merge stable: equal values leave in the order they arrived, the property merge sort relies on (see Merge sort). When one list runs out, the rest of the other is already sorted and is attached with a single pointer write, however long it is. That last step is the advantage of merging linked lists over merging arrays, where the rest must be copied.

An LRU cache

A cache keeps the results of slow requests so repeated requests are fast, and when it is full it must evict something. The least recently used policy evicts the entry whose last use is oldest, betting that what was used recently will be used again soon. It needs three things in O(1): find an entry by key, mark an entry as just used, and find the least recently used entry. A dictionary alone finds entries but keeps no order of use; a list alone keeps the order but must search for an entry. Together they do it all: LRUCache keeps a dictionary from each key to its node in a HeaderList, which holds the entries from the most recently used at the front to the least recently used at the back.

• A hit looks up the node in the dictionary, splices it out of the list and splices it in after the header: six pointer writes, or none when it is already at the front.
• A miss loads the value, and if the cache is full it first removes the node before the header, the least recently used one, from the list and its key from the dictionary; then it puts a new node at the front. Four pointer writes, plus two for an eviction.

Every request therefore costs one dictionary operation or two and at most six pointer writes, whatever the capacity. The doubly linked list is essential: removing a node from the middle of the list needs its predecessor, which only a prev pointer gives in O(1).

The dictionary never changes on a hit; only the list does, so after p moves each key's arrow still reaches the same node, now at another place in the row. The worked example traces all nine requests.

Cost

Every operation

For a list of n items, with i the position of the item involved:

• Insert or remove next to a node you hold: O(1), two links for a singly linked insertion after the node, one for a removal after it, four and two in a doubly linked list. This is the operation linked lists exist for.
• Insert at the front: O(1) in every variant. Insert at the back: O(1) with a tail pointer, in a circular list kept by its tail, and in every doubly linked ring; O(n) in a singly linked list without a tail.
• Remove at the front: O(1) everywhere. Remove at the back: O(1) in the doubly linked variants; n − 2 hops in the singly linked and circular singly linked ones, tail pointer or not.
• Insert or remove at position i, get(i): about i hops in a singly linked list, about min(i, n − 1 − i) in a doubly linked one, then O(1).
• Insert before a node you hold: O(1) in a doubly linked list, a walk to the predecessor in a singly linked one.
• Search for a value: Θ(n) comparisons in the worst case.
• Reverse: n hops and n links, O(1) extra memory. Splice two circular lists: O(1). Merge two sorted lists of m and n items: at most m + n − 1 comparisons and m + n links at most.
• Detect a cycle: at most 5n hops with Floyd's method and O(1) memory, or n hops and memory for n nodes with a set.

All of these are worst-case bounds; no operation is amortized and no operation moves an element, which is why linked lists suit real-time code: every single operation finishes within its bound, unlike a dynamic array's append, which is O(1) only on average over a sequence (see Amortized analysis).

Reaching a position

Search is a scan: a value at index i is found after i + 1 comparisons and i hops, and a missing value costs a full scan.

If the value searched for is equally likely to be at any index, the expected number of comparisons of a successful search is the average of i + 1:

Reaching a position without comparing anything costs the same walk. A doubly linked list can walk from either end and takes the shorter way, which halves the worst case and the average:

This is the cost an array does not have: a Python list reaches position i with one multiplication and one addition, whatever i is. Any code that indexes a linked list in a loop, for i in range(len(lst)): lst[i], pays the walk on every access and makes n(n − 1)/2 hops in total.

Against Python's list and deque

Python's list is a dynamic array of pointers. It reaches any index in O(1), but inserting at index i shifts the n − i items behind it one slot right and then stores the new one, and removing shifts n − i − 1 items left:

collections.deque is a doubly linked list of blocks of 64 slots. Both ends are O(1), but an insertion or deletion in the middle is done by rotating the deque until position i is at the front, working there and rotating back, and CPython rotates the shorter way round:

Both containers are written in C, so their moves cannot be counted from Python. builtin_costs.py wraps a real list and a real deque, performs each call on them, and adds the moves that CPython's source makes for that call; the results always come from the real containers. The example operation_costs.py measures one insertion at each position of a container of n = 1000 items:

The left panel is the honest comparison when the position is only known as a number: a singly linked list pays i hops to get there, almost exactly what the list pays in moves on the other side, and the doubly linked list's walk from the nearer end costs about half the deque's rotation at the middle, 503 against 1001. The right panel shows the case linked lists are made for: when the code already holds the node, as an iterator, a cursor or a dictionary entry does, the cost is 2 or 4 pointer writes anywhere, while the arrays still shift.

Three workloads

The example also runs three workloads for n from 256 to 16384. A queue appends n items and then removes them all from the front. Python's list pays for every removal at the front with a shift of everything behind it, while the deque moves nothing and the linked lists write a few pointers per operation:

Edits at a wandering cursor imitate an editor: 2000 edits, 40 percent of them moving the cursor up to three places either way, 30 percent inserting right after it and 30 percent deleting the item under it. The arrays shift about half the items on every insertion or deletion near the middle; the doubly linked list holds the cursor's node and pays a few hops and links per edit:

The third workload reads 1000 random positions, the linked list's weak spot.

At n = 16384 the list as a queue makes 134225920 moves against 49153 links for the singly linked list and 16384 moves for the deque. At the cursor, the list makes 9876824 moves and the deque 19587674, against 4938 hops and links for the doubly linked list, which does not depend on n at all. Reading 1000 random positions costs the singly linked list 8091703 hops, the doubly linked list 4161405 and the deque only 64527 block hops, while the Python list needs none. Each structure wins exactly one panel, which is the summary of this section: a deque for queues, a linked list for edits at positions you hold, an array for positions you compute.

Reversal, cycles and merging

The iterative reversal follows each pointer once and writes each pointer once; the recursive one makes the same changes from the other end and needs a frame per node:

Floyd's method costs three hops per round of the first phase, two per step of the second and one lap to measure the cycle. Since t ≤ μ + λ, the total is at most five hops per node:

The example pointer_algorithms.py counts the hops on chains of four shapes for n from 8 to 4096 and checks every count against the formula:

The worst shape is a long tail ending in a self-loop: the hare reaches the loop early and spins there until the tortoise arrives, 4.9990 hops per node at n = 4096. A tail just longer than the cycle makes the first phase take two laps, 4.4988 hops per node; half tail and half cycle gives exactly 3.0000, and a pure cycle 4.0000. The dictionary method needs one hop per node but memory for every node; Floyd's needs between three and five times the hops and two pointers of memory.

A merge compares once per node it takes, until one list runs out, so it makes at least min(m, n) comparisons, when every value of the shorter list comes first, and at most m + n − 1, when the lists interleave to the very end:

For random inputs, where every interleaving is equally likely, the expected count follows from counting what is left over when one list runs out. A value of the first list is still waiting at that moment exactly when it comes after every value of the second list, which happens with probability 1/(n + 1):

The tests check this expectation exactly by enumerating every interleaving of small lists, and the example measures it on larger ones:

Merging one value into a sorted list of 1000 costs about 500 comparisons on average, the linear insertion it is, 485.8450 over 200 trials against the expected 500.9990; merging two lists of 1000 costs 1998.0750 against the expected 1998.0020, almost the maximum, because random lists interleave to the end.

Memory per element

Every node is a separate Python object. On 64-bit CPython 3.12 an object with k slot fields takes 16 bytes of links for the cyclic garbage collector, a 16-byte header with the reference count and the type, and 8 bytes per field:

An array of pointers needs one pointer per element. A list keeps some spare capacity to make appending amortized O(1); a deque wastes two link pointers per block of 64:

The example measures the same with tracemalloc on 100000 elements, not counting the elements themselves, which every container shares: 8.00 bytes per element for a list, 48.00 for SinglyLinkedList and 56.00 for DoublyLinkedList, six and seven times as much. A node class written without __slots__ measured 80.03 bytes. In C a node is just its value and its pointers, but the ratio stays: a linked list of 8-byte values spends at least half its memory on pointers.

Cache locality

Counting hops treats every hop as equal, and on real hardware they are not. An array's elements sit next to each other, so reading one brings its neighbours into the processor's cache and the hardware prefetches the next ones. A list's nodes sit wherever the allocator put them, and each hop may be a cache miss of a hundred cycles or more. The example walks 300000 nodes twice: once linked in the order they were allocated, which places neighbours close in memory, and once relinked in a shuffled order. Even in Python, where interpreting the loop dominates, the shuffled walk took three to five times as long on the machine that wrote this page, and sum over a Python list of the same numbers was six to seven times faster than either walk. Wall-clock times differ between machines, which is why they are printed and never plotted. In compiled languages the gap is larger, and it is the main reason production code prefers arrays and deques even where a linked list wins on counted operations.

Worked example

Every step below is printed by examples/worked_example.py and asserted by tests/test_worked_example.py.

Building and inserting

The singly linked list starts as 18, 26, 43, 57, built by appending, with head on 18 and tail on 57.

• push_front(12): node 12.next = node 18, then head = node 12. Two links, no hops: [12, 18, 26, 43, 57].
• push_back(64): node 57.next = node 64, then tail = node 64. Two links: [12, 18, 26, 43, 57, 64].
• insert_after(node 26, 31): node 31.next = node 43, while the list still reads [12, 18, 26, 43, 57, 64], then node 26.next = node 31. Two links: [12, 18, 26, 31, 43, 57, 64].
• insert_before(node 43, 39): the predecessor walk moves prev from 12 to 18, to 26 and to 31, whose next is 43; then node 39.next = node 43 and node 31.next = node 39. Three hops and two links: [12, 18, 26, 31, 39, 43, 57, 64].
• insert_at(2, 22): one hop from 12 to 18, the node at position 1, then node 22.next = node 26 and node 18.next = node 22: [12, 18, 22, 26, 31, 39, 43, 57, 64].

Deleting and searching

• remove_at(5): four hops reach 31, the node at position 4, and node 31.next = node 43 unlinks 39. One link: [12, 18, 22, 26, 31, 43, 57, 64].
• remove(64): eight comparisons, 64 against 12, 18, 22, 26, 31, 43, 57 and 64, with seven hops of cur and prev one node behind. The match is the last node, so node 57.next = null and tail = node 57. Two links: [12, 18, 22, 26, 31, 43, 57].
• find(31): five comparisons and four hops, found at index 4.
• find(50): seven comparisons and six hops, not found.

The final list is [12, 18, 22, 26, 31, 43, 57], with head on 12 and tail on 57.

Pointer order, right and wrong

Take the insertion of 31 after 26 again, in the list 18, 26, 43, 57 and on. The right order writes new.next = node.next, so 31 points to 43 while 26 still does too, and then node.next = new; the list stays whole at every moment. The wrong order writes node.next = new first: from that moment 26 leads to 31 and 31 to null, and 43, 57 and everything after them are unreachable. Its second write, new.next = node.next, reads the field just overwritten and makes 31 point to itself. The pointer-order diagram above shows both sequences frame by frame, and examples/common_mistakes.py prints the broken list as [18, 26, 31, 31, 31, 31, 31, ...].

A doubly linked list

The doubly linked list starts as 15, 29, 46, 63.

• insert_before(node 46, 38): node 38.next = node 46, node 38.prev = node 29, node 29.next = node 38, node 46.prev = node 38. Four links, no hops: [15, 29, 38, 46, 63]. The predecessor came from node 46.prev.
• remove_node(node 29): node 15.next = node 38 and node 38.prev = node 15. Two links: [15, 38, 46, 63].
• pop_back(): node 46.next = null and tail = node 46. Two links, no walk: [15, 38, 46], which reads [46, 38, 15] backwards.

Circular lists

The ring holds 21, 34, 58 with tail on 58.

• push_back(66): node 66.next = node 21 and node 58.next = node 66, after which the ring read from tail.next is [66, 21, 34, 58], so 66 is the first node; then tail = node 66 makes it the last: [21, 34, 58, 66]. Three links.
• pop_back(): two hops, from 21 to 34 to 58, find the predecessor of the last node; node 58.next = node 21 and tail = node 58. Two links: [21, 34, 58].
• concatenate with the ring 81, 93: the second ring is spliced in behind 58 and the tail moves to its last node, a constant three links however long either ring is: [21, 34, 58, 81, 93], and the second ring is left empty.
• rotate(1): one hop and tail = node 21: [34, 58, 81, 93, 21].

Reversing

Reversing 13, 28, 41, 69 takes four rounds of one hop and one link each:

• Round 1: following moves to 28 and node 13.next = null. Reversed [13], rest [28, 41, 69].
• Round 2: following moves to 41 and node 28.next = node 13. Reversed [28, 13], rest [41, 69].
• Round 3: following moves to 69 and node 41.next = node 28. Reversed [41, 28, 13], rest [69].
• Round 4: following moves to null and node 69.next = node 41. Reversed [69, 41, 28, 13], rest empty.

Finding a cycle

The chain 8, 17, 23, 31, 44, 52, 65, 79 ends with a pointer from 79 back to 31, so μ = 3 and λ = 5.

• Phase one: after round 1 the tortoise is on 17 and the hare on 23; after round 2 on 23 and 44; after round 3 on 31 and 65; after round 4 on 44 and 31; after round 5 both are on 52. Five rounds, as t = 5·max(1, ⌈3/5⌉) = 5 predicts, and 15 hops.
• Phase two: the tortoise restarts at 8. Single steps take it to 17, 23 and 31, and the hare from 52 to 65, 79 and 31. They meet at 31 after 3 steps, so μ = 3, with 6 hops.
• Phase three: a lap from 31 through 44, 52, 65 and 79 back to 31 counts λ = 5 with 5 hops.

In all 26 hops, which equals 3·5 + 2·3 + 5.

Merging

Merging 11, 24, 38, 52 with 17, 24, 30, 61, 75:

• 11 against 17: take 11 from the first list.
• 24 against 17: take 17 from the second.
• 24 against 24: a tie, take 24 from the first list, which keeps the merge stable.
• 38 against 24: take 24 from the second.
• 38 against 30: take 30 from the second.
• 38 against 61: take 38 from the first.
• 52 against 61: take 52 from the first, which empties the first list.

Then one link attaches 61 and 75. Seven comparisons, within the bounds 4 and 8, and eight links: [11, 17, 24, 24, 30, 38, 52, 61, 75].

An LRU cache of three entries

The cache holds three entries; the requests are p q p r s p q r p, and the list is shown from the most recently used.

• p: miss, [p], 4 links.
• q: miss, [q, p], 4 links.
• p: hit, [p, q], 6 links.
• r: miss, [r, p, q], 4 links.
• s: miss, evict q, [s, r, p], 6 links.
• p: hit, [p, s, r], 6 links.
• q: miss, evict r, [q, p, s], 6 links.
• r: miss, evict s, [r, q, p], 6 links.
• p: hit, [p, r, q], 6 links.

Three hits, six misses and three evictions. The LRU diagram above shows the state after s and the next two requests.

The code

The package linked_lists is plain Python, one idea per module. Importing it needs only the standard library; Matplotlib is imported by plotting.py alone.

• nodes.py holds Node, DoublyNode, the sentinel markers, chain and rho_chain that build bare chains, and the bounded walk and values_from.
• counting.py holds OperationCounter with the fields comparisons, hops, links and moves, and CountedKey, which counts the comparisons library code makes.
• trace.py holds the Step record, record, describe, format_trace and link_statements, which prints the pointer writes of a trace as statements.
• pointers.py holds the three primitive actions link, hop and matches, which count themselves and record their steps.
• sequence.py holds LinkedSequence, the abstract sequence with the walking, indexing and searching every variant shares.
• singly.py, sentinel.py, doubly.py, circular.py, circular_doubly.py and header.py hold the six lists: SinglyLinkedList, SentinelList, DoublyLinkedList, CircularLinkedList, CircularDoublyLinkedList and HeaderList.
• reversal.py, cycles.py and merging.py hold the algorithms on bare chains; lru.py holds LRUCache.
• invariants.py holds linked_list_violation, is_linked_list and check_linked_list for every variant and the cache.
• builtin_costs.py holds ListModel and DequeModel, Python's list and deque with their element moves counted, and the memory measurements.
• comparisons.py holds the operations applied to any list and to a Python list side by side, OrderedDictLRU, and the hit counts of functools.lru_cache.
• workloads.py holds the worked example's values and seeded random inputs: operation sequences, requests and cursor edits.
• snapshots.py turns real nodes into frames, cells.py says how a node's cells, a null box and a pointer look in each role, routing.py decides where each node, pointer and label of a frame goes, drawing.py writes the DOT text and scenes.py builds the frames of this page's diagrams.
• pitfalls.py holds deliberately broken versions for the pitfalls below, and plotting.py draws every figure in the handbook's colours.

Counting and tracing never change what the code does. The two writes of an insertion after a node are two calls:

def insert_after(self, node: Node, value: Any, trace: list[Step] | None = None) -> Node:
    new = allocated(Node(value), trace)
    self.link(new, "next", node.next, trace)
    self.link(node, "next", new, trace)
    if node is self.tail:
        self.link(self, "tail", new, trace)
    self.size += 1
    return new

The examples run in a few seconds each from the repository root:

• examples/worked_example.py prints every step of the worked example and writes five generated diagram sources.
• examples/variants_and_sentinels.py builds every variant, prints its smallest cases, shows the sentinel's single insertion routine and runs every variant against a Python list; it writes the variants diagram.
• examples/operation_costs.py counts insertions at every position and the three workloads against list and deque, and prints the memory and locality measurements.
• examples/pointer_algorithms.py runs the reversals, Floyd's method on chains of every shape and the merge experiment.
• examples/common_mistakes.py runs every broken version from pitfalls.py next to the correct code.
• examples/compare_with_builtins.py checks the package against list.index, deque, OrderedDict, functools.lru_cache, heapq.merge and sorted.
• examples/practice.py prints fresh exercises with their solutions; --seed gives a new set.

python linear-structures/linked-lists/examples/worked_example.py
python linear-structures/linked-lists/examples/variants_and_sentinels.py
python linear-structures/linked-lists/examples/operation_costs.py
python linear-structures/linked-lists/examples/pointer_algorithms.py
python linear-structures/linked-lists/examples/common_mistakes.py
python linear-structures/linked-lists/examples/compare_with_builtins.py
python linear-structures/linked-lists/examples/practice.py --seed 7

The sample project, project/cache_simulation.py with its helper project/request_streams.py, puts an LRUCache in front of a slow store and serves it a seeded stream of 200000 requests for 10000 items whose popularity follows Zipf's law, the shape of web, file and database traffic: the item of rank i is requested with probability proportional to 1/i^s.

For every capacity it reports the hit rate, checks that functools.lru_cache and an OrderedDict cache score exactly the same hits on the same stream, counts the pointer writes per request, and compares the hit rate with Che's approximation, which treats each item as staying in the cache for a characteristic time T after its last request:

Options --requests, --items, --skews, --capacities, --focus and --seed change the setup, and --figures writes the PNGs elsewhere; the default run takes about 10 seconds.

python linear-structures/linked-lists/project/cache_simulation.py
python linear-structures/linked-lists/project/cache_simulation.py --skews 0.6,1.2 --items 50000

Che's approximation is remarkably close: at skew 0.8 and capacity 200 the cache hit 0.2217 of the requests against the predicted 0.2218, and at capacity 1600 0.5210 against 0.5223. At skew 1.0 a cache of 100 entries, one percent of the items, already serves 0.3916 of the requests. Every request cost about six pointer writes, 5.9811 per request at skew 0.8 and capacity 100, whatever the capacity, as the cost formula says. The project also compares LRU with two other policies at skew 0.8: first in first out, which is what an LRU cache becomes when it forgets to move an entry to the front on a hit, and Belady's offline optimum, which evicts the entry whose next request is furthest in the future and so needs to know the future.

LRU beats first in first out at every capacity, 0.3999 against 0.3587 at capacity 800, because it keeps popular items that keep being requested; the optimum shows how much any policy that cannot see the future leaves on the table, 0.6334 at the same capacity. LRU is not always better: on the requests a b a c b d with room for two entries, first in first out scores two hits and LRU one, a case the tests check.

The notebook linked_lists.ipynb follows this page: the worked example traced step by step, the diagrams, the cost measurements, the comparisons with the built-ins and the cache simulation on a smaller stream. The tests in tests check the worked example value by value, the invariants after every operation of long random sequences on every variant, the cost formulas on counts, and the agreement with Python's list, deque, OrderedDict, functools.lru_cache and heapq.merge, and run in a few seconds:

python -m pytest linear-structures/linked-lists

All data are synthetic, generated from seeds by workloads.py and project/request_streams.py, so nothing is downloaded and no licence is involved.

In practice

Python's list and collections.deque

Python has no general-purpose linked list in its standard library, and for good reasons that the cost section measures. A Python list is the right sequence whenever positions are computed: indexing, slicing, sorting and appending are fast, and insertions in the middle are a memmove of pointers that is quick for thousands of items even though it is O(n). collections.deque is the right queue and the right double-ended buffer: O(1) at both ends, compact blocks of 64 items, and a maxlen option for bounded buffers. The package's lists agree with both on every operation, and examples/compare_with_builtins.py shows the gap in speed: a queue of 100000 items through DoublyLinkedList took about 30 times as long as through deque, mostly the difference between Python and C, while using list.pop(0) as a queue grew quadratically, four times the items taking about 16 times as long. When to use which:

• Use a list for sequences you index, sort or scan, and for stacks.
• Use deque for queues, sliding windows and anything that grows or shrinks at both ends; never list.pop(0) or list.insert(0, x) in a loop.
• Use a linked list when the program holds references to items and inserts or removes next to them: an LRU cache, an editor buffer, a scheduler's run queue, the free list of an allocator, or splicing whole sequences in O(1).
• Use a dictionary or a set beside the list whenever items must be found by key; the list alone can only scan.

OrderedDict and functools.lru_cache

collections.OrderedDict is itself a dictionary combined with a doubly linked list of its keys, written in C: move_to_end(key) marks a key as just used and popitem(last=False) removes the oldest. An LRU cache in pure Python is usually written with it, as OrderedDictLRU in comparisons.py is. functools.lru_cache decorates a function with the same policy, implemented in C with a circular doubly linked list and a dictionary, exactly the structure of LRUCache. On 20000 uniform requests for 500 keys at five capacities, all three scored identical hits, and LRUCache kept exactly the recency order of the OrderedDict version after every one of 5000 requests; it was roughly 7 times slower than the OrderedDict version and 10 to 12 times slower than lru_cache, the gap between Python and C. Use lru_cache to memoize a function, OrderedDict to write a cache by hand, and the linked-list version to understand both. heapq.merge merges sorted iterables lazily with a heap, about two comparisons per item, 3998 for two lists of 1000 against 1999 for merge_chains, and sorted on the concatenation finds the two runs and merges them, galloping through a very short run with few comparisons.

Elsewhere

Java's LinkedList and C++'s std::list are doubly linked lists, and both are used far less than ArrayList and std::vector for the locality reasons above; C++ also has std::forward_list, singly linked, and both list types offer splice, which moves nodes between lists in O(1) without copying. Rust's standard library has a doubly linked LinkedList that its own documentation recommends against in most cases, preferring Vec and VecDeque. The Linux kernel uses intrusive circular doubly linked lists with a header, list_head, embedded inside the structures they link, so one object can sit in several lists without any allocation; that is the HeaderList of this page. Memory allocators keep free blocks in linked free lists, hash tables with separate chaining keep each bucket as a list (see Hash tables), graph libraries keep adjacency lists (see Graphs and their representations), and skip lists stack several sorted linked lists to search in expected logarithmic time (see Treaps and skip lists). Lock-free linked lists and queues, built with atomic compare-and-swap on the pointers, are a staple of concurrent programming. Caches in databases, operating systems and content delivery networks use LRU or refinements of it, such as segmented LRU, 2Q and CLOCK, a circular list with a reference bit that approximates LRU without moving nodes on every hit.

Pitfalls

• Overwriting a pointer before saving what it points to. In an insertion, the new node takes node.next first and node.next changes last; at the front, the new node takes head before head moves. In the wrong order the new node ends up pointing to itself and the rest of the list is lost: [18, 26, 31, 31, 31, ...]. examples/common_mistakes.py runs this and every following mistake.
• Calling an insertion "after" when it lands before. A search that stops with cur on the matching node and links the new node between prev and cur inserts before the match: inserting 31 "after 26" in [18, 26, 43, 57] gives [18, 31, 26, 43, 57]. Insert after a node with new.next = node.next; node.next = new, and test the first node, the last node and a missing value, where such code also crashes because prev is still null.
• Stopping one node late when removing by value. A walk that stops with prev on the match and unlinks prev.next removes the successor: removing 26 from [18, 26, 43, 57] gives [18, 26, 57]. Compare prev.next.value, or keep prev one node behind cur.
• Forgetting the end pointers. Removing the last node without moving tail, or popping the only node without clearing it, leaves tail on a detached node; the next append then links to that node and vanishes, while the size says it is there. Every operation that touches the first or last node must update head or tail; a sentinel removes most of these cases.
• Walking a circular list until null. No pointer in a ring is null, so while node is not None never ends, and neither does a search for a missing value that waits for the value to turn up. Stop on returning to the starting node, or after size steps.
• Forgetting a back pointer. A doubly linked insertion writes four pointers; forgetting the successor's prev leaves the forward walk right and the backward walk wrong: [57, 43, 26, 18] backwards for [18, 26, 31, 43, 57] forwards. Check both directions in tests, as check_linked_list does.
• Skipping equal neighbours when removing every match. After unlinking prev.next, the next candidate is the new prev.next; advancing prev as well skips it, so [5, 9, 9, 9, 2, 9] loses only some of its nines and ends as [5, 9, 2].
• Starting Floyd's hare one node ahead. The first phase still meets, but one step early on the cycle, and the second phase then circles one node apart forever. Start both pointers at the head, or advance the hare once more before the second phase.
• Breaking ties toward the second list when merging. Taking from the second list unless the first is strictly smaller puts equal values from the second list first, and the merge, and any merge sort built on it, is no longer stable.
• Recursing over a list. A recursive reversal, length or search uses one stack frame per node, and Python raises RecursionError at about a thousand. Write list algorithms as loops.
• Indexing a linked list in a loop. lst[i] walks from the head every time, so for i in range(len(lst)) makes n(n − 1)/2 hops, 4950 for 100 values; iterate over the list instead.
• Forgetting to move an entry on a hit. An LRU cache that only evicts from the back but never moves hits to the front is a first-in first-out cache, with fewer hits: 2 instead of 3 on the worked example's requests.
• Choosing a linked list for speed. Counted operations favour linked lists only when the program holds the nodes; for indexing, scanning and queues, a list or a deque wins on counts, on memory (six to seven times less) and on cache locality.

Further reading

• D. E. Knuth, The Art of Computer Programming, volume 1, Fundamental Algorithms, third edition, sections 2.2.3 to 2.2.5, Addison-Wesley, 1997. Linked allocation, circular and doubly linked lists, and the header node.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, fourth edition, section 10.2, MIT Press, 2022. Linked lists with sentinels.
• R. Sedgewick and K. Wayne, Algorithms, fourth edition, section 1.3, Addison-Wesley, 2011. Bags, queues and stacks on linked lists.
• D. E. Knuth, The Art of Computer Programming, volume 2, Seminumerical Algorithms, third edition, section 3.1, exercise 6, Addison-Wesley, 1997. The cycle-finding method, credited there to R. W. Floyd.
• R. P. Brent, "An improved Monte Carlo factorization algorithm", BIT 20(2), 176-184, 1980. A cycle-finding method with fewer steps than Floyd's.
• L. A. Belady, "A study of replacement algorithms for a virtual-storage computer", IBM Systems Journal 5(2), 78-101, 1966. The optimal offline replacement policy.
• H. Che, Y. Tung and Z. Wang, "Hierarchical web caching systems: modeling, design and experimental results", IEEE Journal on Selected Areas in Communications 20(7), 1305-1314, 2002. The characteristic-time approximation of LRU hit rates.
• C. Fricker, P. Robert and J. Roberts, "A versatile and accurate approximation for LRU cache performance", Proceedings of the 24th International Teletraffic Congress, 2012. Why Che's approximation works so well.
• U. Drepper, "What every programmer should know about memory", 2007. Caches, prefetching and the cost of pointer chasing.
• The Python documentation of collections.deque, collections.OrderedDict and functools.lru_cache, and the CPython source files Modules/_collectionsmodule.c, Objects/odictobject.c and Modules/_functoolsmodule.c.