6 — Linked lists

A linked list stores each element in its own node, and each node holds a reference to the next one. There is no index arithmetic: reaching the k-th element means following k references. In exchange, inserting or removing a node whose position is already known is O(1), whatever the list’s length, because only a couple of references change and nothing shifts.

That trade sounds balanced on paper. In practice, on modern hardware and especially in Python, arrays win most head-to-head comparisons, and linked lists earn their place in specific situations: when nodes must stay at stable addresses, when elements are spliced in and out of the middle at known positions, and when a node needs to belong to several structures at once (an LRU cache is the classic case). Linked lists are also the standard setting for a family of pointer-manipulation techniques that recur throughout this track.

Timings in this chapter were measured with Python 3.14 on one Mac. Exact numbers will differ elsewhere.

Singly, doubly and circular lists

singly:    head -> [3|*] -> [7|*] -> [1|*] -> None

doubly:    None <- [*|3|*] <-> [*|7|*] <-> [*|1|*] -> None
                   prev val next

circular:  head -> [3|*] -> [7|*] -> [1|*] --+
                     ^-----------------------+

The node used through this chapter:

class ListNode:
    __slots__ = ("val", "next")

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

__slots__ removes the per-instance __dict__, which cuts a node to 48 bytes in CPython 3.14 and makes attribute access a little faster.

The decisive row for doubly linked lists is “delete a known node”: a singly linked node cannot unlink itself without its predecessor, which may take O(n) to find. A doubly linked node knows both neighbors. This is why the LRU cache below uses a doubly linked list.

A circular list connects the tail back to the head. It has no None to stop at, so traversal stops on returning to the start. It suits round-robin scheduling and buffers that cycle, and a circular doubly linked list with one sentinel node is the cleanest general-purpose layout (the Linux kernel and Python’s OrderedDict both use it). The Josephus problem (people stand in a circle and every k-th is removed; who survives?) is a direct simulation on a circular list:

def josephus(n, k):
    head = build(range(1, n + 1))
    tail = head
    while tail.next:
        tail = tail.next
    tail.next = head                  # close the circle
    prev = tail
    while prev.next is not prev:
        for _ in range(k - 1):
            prev = prev.next
        prev.next = prev.next.next    # remove the k-th
    return prev.val

josephus(7, 3) is 4. The simulation is O(nk); the recurrence $J(1) = 0,\; J(n) = (J(n-1) + k) \bmod n$ gives the 0-based answer in O(n) without building anything.

What they cost in practice

Big-O treats “follow a pointer” and “go to the next array slot” as the same O(1) step. Hardware does not. An array’s next element is usually in the same cache line or one the prefetcher has already fetched. A linked list’s next node is wherever the allocator put it. If nodes were allocated one after another, they are often close together and the walk is fast; if they are scattered (allocated at different times, or the list was spliced and reordered), every step can be a cache miss costing on the order of 100 ns.

The measurement walks the same values four ways: a for loop over a Python list, sum over the list, a while node loop over a linked list whose nodes were allocated in list order, and the same loop over identical nodes linked in a shuffled order.

(Per element.) Three effects are visible:

• Interpreter cost. Even in the best case, following node.next in Python costs more than the list’s iterator, because each step is an attribute load and a truth test in bytecode.
• Locality. Once the list outgrows the cache, the shuffled linked list is about seven times slower than the one with the same nodes in allocation order. Same code, same number of steps.
• Built-ins. sum over a list runs entirely in C and is 50 times faster than the scattered linked walk.

Memory follows the same pattern: a list slot is an 8-byte pointer, while a ListNode with __slots__ is 48 bytes plus the pointer to its value object.

The one place the linked list clearly wins is the operation it was designed for. Building a sequence by inserting at the front:

The list is quadratic, the linked list linear. But deque is faster still: CPython implements it as a doubly linked list of 64-element blocks, which gets O(1) at both ends with most of an array’s locality. That design, linking blocks rather than single elements, is the usual production compromise. In Python, use deque for queues and stacks (see Stacks and queues) and write node classes when the problem is about the links themselves.

The dummy (sentinel) node

Most linked-list bugs are special cases at the head: deleting the first node, inserting before it, or returning a list that has become empty. A dummy node placed before the real head removes them. Every real node then has a predecessor, so “delete the node after prev” works uniformly, and the answer is always dummy.next.

Remove Linked List Elements (delete every node with a given value):

def remove_elements(head, val):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == val:
            prev.next = prev.next.next      # unlink, stay put
        else:
            prev = prev.next
    return dummy.next

Without the dummy, the code needs a separate loop to strip matching nodes from the front before the main loop, and a check for the list becoming empty. Note that prev does not advance after a deletion, so consecutive matches are handled.

The same idea in a doubly linked list is a sentinel: one permanent node that acts as both the head’s predecessor and the tail’s successor, so the list is circular and never empty. Insertion and deletion then have no branches at all; the LRU cache at the end of this chapter uses one. The build helper and the merge functions below use a dummy as the start of an output list, so appending never needs an “is this the first node?” check.

Reversal

Reverse Linked List is the core pointer manipulation. Walk the list keeping three references: the reversed part so far (prev), the current node, and the rest of the list (nxt), saved before the current node’s link is overwritten.

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next      # save the rest
        cur.next = prev     # point backward
        prev = cur          # grow the reversed part
        cur = nxt           # move on
    return prev

start:   None    1 -> 2 -> 3 -> None
         prev   cur

step 1:  None <- 1    2 -> 3 -> None
                prev cur

step 2:  None <- 1 <- 2    3 -> None
                     prev cur

step 3:  None <- 1 <- 2 <- 3    None
                          prev  cur      -> return prev (3)

O(n) time, O(1) space. Python’s tuple assignment compresses the loop body to cur.next, prev, cur = prev, cur, cur.next, which is correct because the right side is evaluated in full before any assignment; reordering the targets can break it.

Recursive reversal and the depth limit

The recursive version reverses the rest of the list first, then hooks the current node onto the end of the reversed rest. After the call, head.next is still the old second node, which is now the tail of the reversed rest:

def reverse_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head       # old second node now points back at head
    head.next = None
    return new_head

It is O(n) time and O(n) space for the call stack. In Python that space is capped: the default recursion limit is 1,000 frames.

import sys

print(sys.getrecursionlimit())
print(len(to_list(reverse_recursive(build(range(900))))))
try:
    reverse_recursive(build(range(1000)))
except RecursionError as e:
    print("RecursionError:", e)

1000
900
RecursionError: maximum recursion depth exceeded

sys.setrecursionlimit can raise the limit, but deep recursion can still exhaust the C stack, so recursive linked-list code in Python is suitable only for short lists. The iterative version has no limit. The same applies to every recursive solution in this chapter (merge sort on a list, recursive merge).

Reversing a sublist

Reverse Linked List II reverses positions left..right (1-based). With a dummy node, find the node before the sublist, then repeatedly move the node after the sublist’s first node to the front of the sublist:

def reverse_between(head, left, right):
    dummy = ListNode(0, head)
    before = dummy
    for _ in range(left - 1):
        before = before.next
    cur = before.next                   # becomes the sublist's tail
    for _ in range(right - left):
        moved = cur.next
        cur.next = moved.next
        moved.next = before.next
        before.next = moved
    return dummy.next

1 -> 2 -> 3 -> 4 -> 5, left=2, right=4
before=1, cur=2
move 3 to front:  1 -> 3 -> 2 -> 4 -> 5
move 4 to front:  1 -> 4 -> 3 -> 2 -> 5

The dummy handles left = 1 without a special case.

Fast and slow pointers

Two references traverse the list at different speeds, usually one step and two steps per iteration. Their relative position reveals structure that a single pass with one pointer cannot see without extra memory.

Middle node

When the fast pointer reaches the end, the slow one is halfway:

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

For an even length this returns the second of the two middle nodes ([1, 2, 3, 4] gives 3). Starting fast at head.next instead returns the first middle, which is what splitting a list in half for merge sort needs, so that a two-node list splits into one and one rather than two and zero.

Floyd’s cycle detection

A list has a cycle if some node’s next points back to an earlier node. Storing visited nodes in a set detects it in O(n) time and O(n) space. Floyd’s algorithm, usually attributed to Robert W. Floyd and often called the tortoise and hare, uses O(1) space.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

If there is no cycle, fast reaches the end and the loop stops. If there is one, both pointers eventually enter it, and from then on fast gains exactly one node on slow per iteration. A gap that shrinks by exactly one each step cannot skip past zero, so they meet. Compare node identity with is, not values with ==: different nodes can hold equal values.

Why they meet and where the cycle starts

Let $\mu$ be the number of steps from the head to the first node of the cycle, and $\lambda$ the cycle’s length.

head                      cycle start
 o -> o -> o -> ... -> o -> S -> o -> o
      <---- mu steps ---->  ^         |
                            |         v
                            o <- o <- o
                            <- lambda nodes ->

After $t$ iterations, slow has taken $t$ steps and fast $2t$. Once both are in the cycle ($t \ge \mu$), they are at the same node exactly when the difference in steps is a multiple of the cycle length: $2t - t = t \equiv 0 \pmod{\lambda}$. So they meet at the first multiple of $\lambda$ that is at least $\mu$, which is at most $\mu + \lambda$ iterations: O(n) time.

At the meeting point, slow has taken $t = k\lambda$ steps for some integer $k$. Now place one pointer back at the head and advance both one step at a time. After $\mu$ steps, the pointer from the head is at the cycle start, by definition. The other pointer has taken $k\lambda + \mu$ steps in total from the head, which is $\mu$ steps plus a whole number of laps, so it is also at the cycle start. They meet there for the first time, because before step $\mu$ the first pointer is still outside the cycle and the second is inside it.

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

This is Linked List Cycle II. The cycle length, if needed, is one more lap from the meeting point counting steps until returning.

The same argument works on any function iterated from a starting value, not only on node links. Find the Duplicate Number gives n + 1 integers in 1..n with one value repeated, and asks for it in O(1) extra space without modifying the array. Treat index i as a node whose next is nums[i]. Index 0 is never a target (values start at 1), so it is outside any cycle, and the duplicated value is the node with two incoming edges, the entrance to the cycle:

def find_duplicate(nums):
    slow = fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

find_duplicate([3, 1, 3, 4, 2]) is 3. Pollard’s rho factorization algorithm and the detection of cycles in pseudo-random number generators use the same idea on $x \mapsto f(x)$.

Brent’s algorithm

Richard Brent’s 1980 variant also uses O(1) space but makes fewer function evaluations (link traversals). The tortoise stays still while the hare runs ahead; whenever the hare has taken a power-of-two number of steps without meeting the tortoise, the tortoise teleports to the hare’s position and the step budget doubles. When they meet, the number of steps the hare took since the last teleport is exactly $\lambda$.

def brent(head):
    """Return (cycle length, cycle start node), or (0, None) if acyclic."""
    if head is None:
        return 0, None
    power = lam = 1
    tortoise, hare = head, head.next
    while hare is not tortoise:
        if hare is None:
            return 0, None
        if power == lam:            # budget used up: move tortoise, double budget
            tortoise = hare
            power *= 2
            lam = 0
        hare = hare.next
        lam += 1
    tortoise = hare = head          # find the start: hare goes lam steps ahead
    for _ in range(lam):
        hare = hare.next
    while tortoise is not hare:
        tortoise = tortoise.next
        hare = hare.next
    return lam, tortoise

Floyd advances three pointer steps per iteration (one for slow, two for fast); Brent advances one. Both are O(μ + λ). The second phase is simpler than Floyd’s: with the hare exactly λ steps ahead, the two meet as soon as the trailing pointer reaches the cycle start. Brent reported that it runs about 36% faster than Floyd’s method on average. For linked lists the difference rarely matters; for expensive functions such as Pollard’s rho it does.

Merging sorted lists

Merge Two Sorted Lists

Linked lists merge without allocating anything: the output is built by relinking the input nodes. A dummy node makes the first append uniform.

def merge_two(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b              # attach whichever remains, in O(1)
    return dummy.next

O(|a| + |b|) time and O(1) extra space. The <= (taking from a on ties) makes the merge stable, which is what makes merge sort stable. Attaching the remainder in one assignment, rather than copying it node by node, is one of the few places where a linked list beats an array outright.

Merge k Sorted Lists

With k lists and N nodes in total, merging them one after another into an accumulating result costs O(kN), since the accumulated list is rescanned each time. Two better options:

A min-heap of the current heads. Pop the smallest, append it, push its successor. Each of the N nodes passes through the heap once, and the heap holds at most k entries: O(N log k) time, O(k) space. See Heaps.

import heapq

def merge_k(lists):
    heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapq.heapify(heap)
    dummy = tail = ListNode()
    while heap:
        val, i, node = heap[0]
        tail.next = node
        tail = node
        if node.next:
            heapq.heapreplace(heap, (node.next.val, i, node.next))
        else:
            heapq.heappop(heap)
    return dummy.next

The list index i in each tuple is not decoration. When two values tie, Python compares the next tuple element; without i it would compare two ListNode objects and raise TypeError. Using the list index also keeps the merge stable across lists. heapreplace pops and pushes in one sift, which is cheaper than a separate pop and push.

Divide and conquer. Merge the lists in pairs, then the results in pairs, and so on. There are $\lceil \log_2 k \rceil$ rounds, each touching every node once: also O(N log k), with O(1) extra space beyond the list of lists.

def merge_k_divide(lists):
    lists = [l for l in lists if l]
    if not lists:
        return None
    while len(lists) > 1:
        lists = [merge_two(lists[i], lists[i + 1]) if i + 1 < len(lists) else lists[i]
                 for i in range(0, len(lists), 2)]
    return lists[0]

Sorting a linked list

Sort List in O(n log n) is merge sort: split at the middle with fast and slow pointers, sort both halves, merge. Merge sort suits linked lists especially well because merging needs no auxiliary array and splitting needs no copying. Quicksort, which depends on random access for good pivots and in-place partitioning, does not.

def sort_list(head):
    if head is None or head.next is None:
        return head
    slow, fast = head, head.next           # first-middle variant
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    second = slow.next
    slow.next = None
    return merge_two(sort_list(head), sort_list(second))

The recursion depth is only O(log n), so the recursion limit is not a concern here. A bottom-up version (merge runs of length 1, 2, 4, …) achieves O(1) extra space. For Python data, converting to a list, calling sorted, and relinking is faster in practice.

Intersection of Two Linked Lists

Two singly linked lists may merge at some node and share every node after it (a Y shape). Find that node, or None.

Storing one list’s nodes in a set works in O(m + n) time and O(m) space. The O(1)-space method notices that the two lists have lengths a + c and b + c, where c is the shared tail. A pointer that walks list A then list B travels a + c + b steps before reaching the shared part a second time; a pointer that walks B then A travels b + c + a. Those are equal, so if both start together they arrive at the intersection together. If there is no intersection, both reach None at the same moment after a + b steps.

def intersection(a, b):
    p, q = a, b
    while p is not q:
        p = p.next if p else b
        q = q.next if q else a
    return p

A:  a1 -> a2 ---------\
                       c1 -> c2 -> c3
B:  b1 -> b2 -> b3 ---/

p: a1 a2 c1 c2 c3 None b1 b2 b3 c1
q: b1 b2 b3 c1 c2 c3 None a1 a2 c1   -> both at c1

The comparison is by identity. Two lists with equal values in their tails do not intersect unless they share the actual nodes.

Remove Nth Node From End

Move a fast pointer n + 1 steps ahead of a slow pointer that starts at a dummy node. Then move both until fast falls off the end. slow is then directly before the node to delete.

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        fast, slow = fast.next, slow.next
    slow.next = slow.next.next
    return dummy.next

remove_nth_from_end(build([1, 2, 3, 4, 5]), 2) gives [1, 2, 3, 5]. The dummy matters when n equals the list length, which deletes the head. One pass, O(1) space. The two-pass alternative (count the length, then walk to position length − n) is equally O(n) and is a reasonable choice too.

Reorder List

Rearrange L0 → L1 → ... → Ln into L0 → Ln → L1 → Ln−1 → ... in place. This composes three earlier techniques: find the middle, reverse the second half, then interleave the two halves.

def reorder(head):
    if head is None:
        return
    slow = fast = head
    while fast.next and fast.next.next:     # slow ends at the first middle
        slow, fast = slow.next, fast.next.next
    second = reverse(slow.next)
    slow.next = None
    first = head
    while second:
        first.next, first = second, first.next
        second.next, second = first, second.next

1 -> 2 -> 3 -> 4 -> 5
split:     1 -> 2 -> 3      4 -> 5
reverse:   1 -> 2 -> 3      5 -> 4
weave:     1 -> 5 -> 2 -> 4 -> 3

O(n) time, O(1) space. Pushing all nodes onto a Python list and relinking from both ends is O(n) space and harder to get wrong; the in-place version is what the problem asks for.

Swapping pairs and reversing in k-groups

Swap Nodes in Pairs swaps every two adjacent nodes by relinking, not by swapping values (problems usually forbid changing values, and in real systems nodes carry more than a value). With a dummy, each step rewires three links:

def swap_pairs(head):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next and prev.next.next:
        a = prev.next
        b = a.next
        prev.next, a.next, b.next = b, b.next, a
        prev = a
    return dummy.next

prev -> a -> b -> rest      becomes      prev -> b -> a -> rest

[1, 2, 3, 4, 5] becomes [2, 1, 4, 3, 5].

Reverse Nodes in k-Group generalizes it: reverse each consecutive block of k nodes, leaving a final block shorter than k unchanged. For each group: check that k nodes remain (find the k-th node), reverse the group with its last node’s successor as the initial prev (so the reversed group is already connected to what follows), then connect the previous group’s tail to the new group head.

def reverse_k_group(head, k):
    dummy = ListNode(0, head)
    group_prev = dummy
    while True:
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if kth is None:
                return dummy.next             # fewer than k left: done
        group_next = kth.next
        prev, cur = group_next, group_prev.next
        while cur is not group_next:          # reverse this group
            cur.next, prev, cur = prev, cur, cur.next
        first = group_prev.next               # old first is now the group's tail
        group_prev.next = kth
        group_prev = first

With k = 3, [1, 2, 3, 4, 5, 6, 7, 8] becomes [3, 2, 1, 6, 5, 4, 7, 8]. Each node is visited twice (once to find kth, once to reverse): O(n) time, O(1) space. Starting prev at group_next rather than None is the detail that avoids a separate reconnection step at the group’s tail.

Copy List with Random Pointer

Each node has a next and also a random reference to any node in the list or None. Produce a deep copy: new nodes, with the copy’s random references pointing at copied nodes, not originals.

The difficulty is that when a node is copied, the node its random points to may not have been copied yet.

Hash map, two passes. First create a copy of every node and record original -> copy. Then set each copy’s next and random by looking up the originals’ targets. Mapping None to None removes the null checks.

class RNode:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copy_random_list_map(head):
    clone = {None: None}
    node = head
    while node:
        clone[node] = RNode(node.val)
        node = node.next
    node = head
    while node:
        clone[node].next = clone[node.next]
        clone[node].random = clone[node.random]
        node = node.next
    return clone[head]

O(n) time and O(n) extra space for the map. This is the general method for deep-copying any pointer structure, including graphs (Clone Graph); copy.deepcopy uses the same memo-dictionary idea.

Interleaving, O(1) extra space. Insert each copy directly after its original, so the map from original to copy is simply original.next. Then set each copy’s random to original.random.next, and finally unweave the two lists, restoring the original.

original:    A -> B -> C            (A.random = C, B.random = A)
interleave:  A -> A' -> B -> B' -> C -> C'
randoms:     A'.random = A.random.next = C'
             B'.random = B.random.next = A'
unweave:     A -> B -> C     and     A' -> B' -> C'

def copy_random_list_interleave(head):
    if head is None:
        return None
    node = head
    while node:                               # 1. A -> A' -> B -> B' ...
        node.next = RNode(node.val, node.next)
        node = node.next.next
    node = head
    while node:                               # 2. copy random references
        if node.random:
            node.next.random = node.random.next
        node = node.next.next
    node, new_head = head, head.next
    while node:                               # 3. separate the lists
        copy = node.next
        node.next = copy.next
        copy.next = copy.next.next if copy.next else None
        node = node.next
    return new_head

Three O(n) passes, O(1) extra space beyond the copies themselves. The input is temporarily modified, which is unacceptable if other threads may read the list concurrently (see Concurrency); the hash-map version never touches the original.

Flatten a Multilevel Doubly Linked List

Nodes have prev, next and child; a child is the head of another list, which may have children of its own. Flatten everything into one level so that each child list appears immediately after its parent, in depth-first order:

1 - 2 - 3 - 4 - 5 - 6
        |
        7 - 8 - 9 - 10
            |
            11 - 12

flattened: 1 2 3 7 8 11 12 9 10 4 5 6

Walking the top level, whenever a node has a child: find the child list’s tail, splice the child list in between the node and its next, and clear the child reference. The walk then continues into the spliced-in nodes, so deeper children are handled when it reaches them.

def flatten(head):
    node = head
    while node:
        if node.child:
            child_tail = node.child
            while child_tail.next:
                child_tail = child_tail.next
            child_tail.next = node.next
            if node.next:
                node.next.prev = child_tail
            node.next = node.child
            node.child.prev = node
            node.child = None
        node = node.next
    return head

It is O(n) time and O(1) space: each node is passed once by the main walk and at most once more by a tail search, since a tail search covers a child list that is then spliced in exactly once. A recursive version or an explicit stack (push next, then follow child) is the alternative; the recursive version can hit the recursion limit on deep nesting. Forgetting to update prev pointers and forgetting to clear child are the two common bugs. Flattening a linked list in which each node heads a sorted sub-list linked by bottom pointers is a different problem: it is a k-way merge.

Palindrome Linked List

Is the sequence of values a palindrome, in O(n) time and O(1) extra space? Copying values into a list and comparing with its reverse is O(n) space. The in-place method finds the middle, reverses the second half, compares the halves, and then reverses the second half back so the caller’s list is unchanged.

def is_palindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    second = reverse(slow)
    ok = True
    p, q = head, second
    while q:
        if p.val != q.val:
            ok = False
            break
        p, q = p.next, q.next
    reverse(second)                # restore the input
    return ok

1 -> 2 -> 3 -> 2 -> 1
middle: 3 (slow)
first half stays linked to 3:   1 -> 2 -> 3 -> None (3's next is now None)
second half reversed:           1 -> 2 -> 3
compare 1=1, 2=2, 3=3  -> True

For odd lengths the middle node ends up at the end of both halves and is compared with itself, which is harmless. Restoring the list is easy to omit and is the difference between a function that answers a question and one that silently damages its argument.

LRU cache

A least-recently-used cache holds at most capacity entries. get returns a value and marks the key as most recently used; put inserts or updates and, if the cache is full, evicts the least recently used key. Both must be O(1).

No single structure does this. A hash map gives O(1) lookup but has no notion of recency. A list ordered by recency gives the eviction candidate but needs O(n) to find and move a key. The standard design combines them:

• a hash map from key to node, for O(1) lookup, and
• a doubly linked list of nodes in recency order, for O(1) move-to-front and remove-from-back.

The list must be doubly linked because moving a node to the front means unlinking it from the middle, and only a doubly linked node can unlink itself in O(1). Each node stores its key so that eviction, which starts from the list, can delete the map entry.

map: {1: *, 3: *, 7: *}
             |    |    |
sentinel <-> [3] <-> [7] <-> [1] <-> (back to sentinel)
 most recent ^                ^ least recent: evicted next

class DNode:
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key=None, val=None):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head = DNode()                       # sentinel
        self.head.prev = self.head.next = self.head

    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)
        return node.val

    def put(self, key, val):
        node = self.map.get(key)
        if node:
            node.val = val
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) == self.capacity:
            lru = self.head.prev                  # least recent is just before the sentinel
            self._unlink(lru)
            del self.map[lru.key]
        node = DNode(key, val)
        self.map[key] = node
        self._push_front(node)

With a circular list and one sentinel, _unlink and _push_front have no conditionals: the sentinel is always there as a neighbor, even when the cache is empty. The sequence put(1,1), put(2,2), get(1) → 1, put(3,3) evicts 2 (key 1 was used more recently), so get(2) returns −1; then put(4,4) evicts 1, and get(1), get(3), get(4) return −1, 3, 4.

Python’s OrderedDict

collections.OrderedDict is this structure already. Its pure-Python reference implementation in Lib/collections/__init__.py keeps a dict mapping keys to links in a circular doubly linked list with a sentinel root, exactly as above; the C implementation that is actually used also keeps a doubly linked list of nodes alongside the hash table. move_to_end and popitem(last=False) are O(1):

from collections import OrderedDict

class LRUCacheOD:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, val):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = val
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

On 200,000 random operations against a capacity-1,000 cache, the hand-written version averaged 172 ns per operation and the OrderedDict version 112 ns, because the list manipulation happens in C. To memoize a function, functools.lru_cache is the ready-made tool; it is built on the same dict-plus-circular-doubly-linked-list design. The plain dict keeps insertion order too (guaranteed since Python 3.7), but it has no O(1) “move to end” for an existing key; deleting and reinserting works and is a common lightweight LRU in Python.

A related design, the LFU cache (evict the least frequently used, ties broken by recency), keeps a hash map from each frequency to a doubly linked list of keys with that frequency, plus the current minimum frequency, for O(1) operations.

Where linked lists are used in real systems

• The Linux kernel’s list_head. The kernel’s standard list is a circular doubly linked list with a sentinel. Rather than nodes that contain data, the data structures contain the links: a struct list_head field embedded in, say, a process descriptor, and the container_of macro recovers the enclosing structure from a pointer to its embedded link. An object can sit on several lists at once by embedding several list_head fields, and insertion and removal never allocate. This intrusive style is the main reason linked lists remain common in systems code.
• Free lists in memory allocators. An allocator that hands out fixed-size blocks keeps the free ones in a singly linked list threaded through the free blocks themselves: the first bytes of each free block hold the pointer to the next. Allocation pops the head and freeing pushes onto it, both O(1) with no extra memory. CPython’s small-object allocator (pymalloc) manages free blocks within its pools this way, and many object types keep free lists of recently released objects for reuse.
• Hash table chaining. Separate chaining stores the entries that hash to the same bucket in a short linked list (see Hashing). Java’s HashMap converts long chains to balanced trees; Python’s dict uses open addressing instead.
• Skip lists. A skip list is a sorted linked list with extra “express lane” levels of forward pointers, giving O(log n) expected search, insertion and deletion with simpler code than a balanced tree and easy concurrent variants. Redis implements sorted sets with a skip list paired with a hash table; how and why is described in Redis internals.
• LRU lists. Caches such as memcached keep their items on doubly linked recency lists. Redis instead approximates LRU by sampling a few keys and evicting the oldest, which saves the two pointers per key that an exact list would cost. PostgreSQL’s buffer manager uses a clock-sweep algorithm over a fixed array of buffers rather than a linked LRU list, for the same kind of reason: the bookkeeping on every access is cheaper.
• Undo histories, playlists, browser history, and other sequences navigated one step at a time, and the adjacency lists of graphs (see Graph traversal), which in classic presentations are linked lists and in practice are usually arrays.

The common thread is that linked lists are used where nodes are long-lived, addressed directly (by pointer, not by index), and moved between positions or collections without copying. When a sequence is mostly scanned or indexed, an array is the better choice.

Summary