Linked Lists

The problem: inserting at the front

A music player keeps a queue of upcoming songs. Users constantly add songs to the front ("play next"), remove songs from the middle, and reorder. With a Python list, every front insert shifts every other song one slot right: O(n). For a queue of 100,000 songs that is noticeable; for a server handling thousands of queues, it is a problem.

A linked list avoids shifting entirely. Items are not stored next to each other; instead each item sits in its own small object, a node, which records where the next node is. Inserting at the front means creating a node and updating one pointer, regardless of how long the list is.

The list column roughly quadruples per doubling (O(n²) total); the linked column roughly doubles (O(n) total). The rest of this module is about how to get that benefit safely, and what it costs.

Nodes and pointers

A node holds two things: a value and a reference (pointer) to the next node. The last node's next is None, marking the end. The list itself only needs to remember the first node, the head; it often also remembers the last node, the tail, to make appending fast.

class Node:
    __slots__ = ("value", "next")      # explained later: saves memory per node

    def __init__(self, value, next=None):
        self.value = value
        self.next = next

c = Node("C")
b = Node("B", c)
a = Node("A", b)       # a is the head: A -> B -> C -> None

In Python, a "pointer" is simply a reference: a.next is a name bound to the b object, just like any variable (M06). Following a pointer means reading an attribute. Changing a pointer means assigning one.

That loop, cur = head; while cur: ...; cur = cur.next, is the heartbeat of every linked-list algorithm. Notice what you cannot do: jump to item 2 directly. There is no address formula, so reaching index i costs i steps.

Singly linked list operations

Each operation below is a short sequence of pointer changes. The order of those changes matters: update a pointer too early and you lose the rest of the list. Use the visualizer to watch each one, then read the code.

Push front: O(1)

def push_front(self, value):
    self.head = Node(value, self.head)   # new node points at the old head
    if self.tail is None:                # list was empty: new node is also the tail
        self.tail = self.head
    self.size += 1

Append with a tail pointer: O(1)

Without a tail pointer, appending means walking to the end: O(n). Keeping a tail reference makes it O(1), at the cost of keeping it correct in every other operation.

def append(self, value):
    node = Node(value)
    if self.tail is None:        # empty list
        self.head = self.tail = node
    else:
        self.tail.next = node    # old last node points to the new one
        self.tail = node
    self.size += 1

Find: O(n)

def find(self, value):
    cur = self.head
    while cur is not None:
        if cur.value == value:
            return cur
        cur = cur.next
    return None

Delete by value: O(n) to find, O(1) to unlink

To remove a node from a singly linked list you must change the previous node's next, so you walk with two pointers: prev and cur. Then handle the edge cases: deleting the head, and deleting the tail.

def remove(self, value):
    prev, cur = None, self.head
    while cur is not None and cur.value != value:
        prev, cur = cur, cur.next
    if cur is None:
        raise ValueError(f"{value!r} not in list")
    if prev is None:              # removing the head
        self.head = cur.next
    else:
        prev.next = cur.next
    if cur is self.tail:          # removing the tail
        self.tail = prev
    self.size -= 1

Reverse in place: O(n) time, O(1) space

Reversal is the most important pointer exercise there is. Walk the list once, turning each next pointer around. You need three references: prev (the already-reversed part), cur (the node being flipped), and nxt (saved so you don't lose the rest).

def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next      # 1. save the rest
        cur.next = prev     # 2. flip this pointer
        prev = cur          # 3. advance prev
        cur = nxt           # 4. advance cur
    return prev             # prev is the new head

Making it Pythonic: dunder methods and __slots__

A linked list class should feel like a built-in container. The data model from M11 gives us the hooks:

• __iter__: write it as a generator so for loops, list(), and unpacking work.
• __len__: keep a size counter so len() is O(1) instead of a walk.
• __repr__: show the contents for debugging, e.g. LinkedList([1, 2, 3]).
• __contains__: optional, since Python falls back to __iter__ for in.
• __bool__: unnecessary when __len__ exists; an empty list is falsy automatically.

__slots__: smaller nodes

A linked list of a million items is a million node objects, so per-node overhead matters. By default each instance can grow arbitrary attributes, which needs space for an attribute dictionary (or, in modern CPython, inline value storage plus the ability to create a dict). Declaring __slots__ = ("value", "next") tells Python the complete attribute list, so each instance stores exactly two fixed reference slots and nothing else. It also makes typos like node.nxt = ... raise AttributeError instead of silently creating a new attribute.

Doubly linked lists and sentinels

A singly linked list can only move forwards, so deleting a node requires its predecessor, and removing the tail is O(n) (you must walk to find the new tail). A doubly linked list gives each node a prev pointer too. Given a reference to any node, you can unlink it in O(1), and you can walk in both directions.

Sentinels: the trick that deletes your edge cases

Most bugs in linked-list code live in the edge cases: empty list, inserting before the head, deleting the tail. A sentinel (dummy) node is a node that holds no real value and is always present. With one sentinel whose next is the first real node and whose prev is the last, the list becomes a circle and every real node always has a real neighbour on both sides. Every insertion and deletion becomes the same four-line pointer dance, with no if statements.

class DNode:
    __slots__ = ("value", "prev", "next")
    def __init__(self, value=None):
        self.value = value
        self.prev = self.next = self

class DoublyLinkedList:
    def __init__(self):
        self._sentinel = DNode()            # prev and next point to itself: empty
        self._size = 0

    def _insert_after(self, node, value):   # the only insertion routine you need
        new = DNode(value)
        new.prev, new.next = node, node.next
        node.next.prev = new
        node.next = new
        self._size += 1
        return new

    def _unlink(self, node):                # the only deletion routine you need
        node.prev.next = node.next
        node.next.prev = node.prev
        self._size -= 1
        return node.value

    def push_front(self, value): return self._insert_after(self._sentinel, value)
    def append(self, value):     return self._insert_after(self._sentinel.prev, value)
    def pop_front(self):         return self._unlink(self._sentinel.next)   # check emptiness first!
    def pop_back(self):          return self._unlink(self._sentinel.prev)

Classic linked-list problems

These five problems appear in interviews constantly because they test whether you can reason about pointers precisely. Each has a short, elegant solution.

1. Reverse a list

You did this above: three pointers, O(n) time, O(1) space. A recursive version exists but uses O(n) stack space.

2. Find the middle: slow and fast pointers

Move slow one step and fast two steps at a time. When fast reaches the end, slow has gone half as far: it is in the middle. One pass, no counting.

def middle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow     # for even lengths, the second of the two middle nodes

3. Detect a cycle: Floyd's tortoise and hare

If some node's next points back to an earlier node, a naive traversal loops forever. You could store every visited node in a set (O(n) space), but Floyd's algorithm uses O(1) space: run slow and fast pointers. If there is no cycle, fast reaches None. If there is a cycle, both pointers end up circling it, and since fast gains one node per step on slow, the gap shrinks by one each step until they meet.

def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:          # identity, not equality!
            return True
    return False

Bonus: to find where the cycle starts, once they meet, reset one pointer to the head and advance both one step at a time; they meet again at the cycle's entrance. (If the tail before the loop has length μ and the loop has length λ, the meeting point is μ steps before the entrance, going around the loop.)

4. Merge two sorted lists

Use a dummy head node so you never special-case "the result is empty". Repeatedly take the smaller front node, attach it, and advance. When one list runs out, attach the rest of the other. O(n + m) time, O(1) extra space: you re-link existing nodes rather than creating new ones. This is the merge step of merge sort.

def merge(a, b):
    dummy = tail = Node(None)
    while a and b:
        if a.value <= b.value:        # <= keeps the merge stable
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

5. Remove the nth node from the end

Move a lead pointer n steps ahead, then move lead and trail together until lead hits the end. trail is now just before the node to remove. A dummy node in front of the head handles "remove the first node" without special cases. One pass.

Arrays vs linked lists

The memory and cache rows are why, in practice, arrays win far more often than the Big-O table suggests. Every hop along a linked list is a dependent memory load: the CPU cannot fetch node 5 until it has read node 4's next. With an array, the hardware streams consecutive memory and prefetches ahead. Python adds its own overhead on top, since each cur.next is an attribute lookup executed by the interpreter.

Where linked lists are used

• LRU caches. A hash map from key to node, plus a doubly linked list ordered by recency. A hit unlinks the node and moves it to the front in O(1); eviction pops the back in O(1). This is the classic design, and the pure-Python fallback of functools.lru_cache uses exactly this idea with a circular doubly linked list.
• OrderedDict. Before regular dicts preserved insertion order (3.7), collections.OrderedDict was the way to get ordering. Its pure-Python implementation in Lib/collections/__init__.py is a dict plus a circular doubly linked list with a sentinel root, which is still why move_to_end is O(1).
• collections.deque. A doubly linked list of fixed-size blocks (64 slots each in CPython). This hybrid gets O(1) operations at both ends like a linked list while keeping most items contiguous like an array, and wastes far less memory than one node per item. See M22.
• Operating systems and allocators. Free lists of memory blocks, process scheduler queues, and the Linux kernel's intrusive list_head.
• Hash table chaining. Each bucket can be a short linked list (M23).

Pitfalls

• Losing the rest of the list by overwriting next before saving it.
• Forgetting the tail: removing the last node or reversing without updating tail leaves it pointing at a node that is no longer last.
• Off-by-one at the ends: always test empty, one node, two nodes, head, and tail.
• Using == instead of is to compare nodes. Two different nodes may hold equal values; cycle detection and "is this the tail?" need identity.
• Infinite loops from accidental cycles. A __repr__ that walks a cyclic list never returns; guard it with a step limit while debugging.
• Recursion depth: recursive algorithms on long lists hit the recursion limit around 1000 nodes. Prefer iteration.
• Exposing nodes: if callers can reach your nodes, they can corrupt your size counter and invariants. Keep nodes private (leading underscore) unless handing them out is the point.

Practice

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self, iterable=()):
        self.head = None
        self.tail = None
        self.size = 0
        for x in iterable:
            self.append(x)

    def push_front(self, value):
        self.head = Node(value, self.head)
        if self.tail is None:
            self.tail = self.head
        self.size += 1

    def append(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1

    def __iter__(self):
        cur = self.head
        while cur is not None:
            yield cur.value
            cur = cur.next

    def __len__(self):
        return self.size

    def __repr__(self):
        return f"LinkedList({list(self)!r})"

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self, iterable=()):
        self.head = self.tail = None
        self.size = 0
        for x in iterable:
            self.append(x)

    def append(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1

    def __iter__(self):
        cur = self.head
        while cur is not None:
            yield cur.value
            cur = cur.next

    def __len__(self):
        return self.size

    def find(self, value):
        cur = self.head
        while cur is not None:
            if cur.value == value:
                return cur
            cur = cur.next
        return None

    def remove(self, value):
        prev, cur = None, self.head
        while cur is not None and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            raise ValueError(f"{value!r} not in list")
        if prev is None:
            self.head = cur.next
        else:
            prev.next = cur.next
        if cur is self.tail:
            self.tail = prev
        self.size -= 1

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

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

def cycle_start(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        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

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def merge(a, b):
    dummy = tail = Node(None)
    while a is not None and b is not None:
        if a.value <= b.value:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a if a is not None else b
    return dummy.next

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def remove_nth_from_end(head, n):
    if n < 1:
        raise ValueError("n must be at least 1")
    dummy = Node(None, head)
    lead = trail = dummy
    for _ in range(n):
        lead = lead.next
        if lead is None:
            raise ValueError("n is larger than the list length")
    while lead.next is not None:
        lead = lead.next
        trail = trail.next
    trail.next = trail.next.next
    return dummy.next

Mini-project: a playlist manager

pixi init playlist
cd playlist
pixi add python=3.14 pytest
pixi run python -m pytest -q

Quiz

Recap

• A linked list is nodes holding a value and a next reference; the list keeps the head and often the tail.
• Push front, append with a tail, and unlinking a known node are O(1); indexing and search are O(n).
• Pointer code needs care: save before overwriting, and test empty, single, head, and tail cases.
• Doubly linked lists unlink any known node in O(1); a circular sentinel removes edge cases.
• Implement __iter__, __len__, and __repr__; use __slots__ for nodes.
• Classic techniques: three-pointer reversal, slow/fast pointers, dummy heads, and leading pointers.
• Arrays usually win in practice thanks to cache locality; linked lists shine for O(1) splicing (LRU caches, OrderedDict, deque blocks).

Going further

• Data model: __slots__
• collections.deque and OrderedDict
• CPython's pure-Python OrderedDict source (search for _Link).
• Next: M22 Stacks, Queues & Deques.