Linked lists

An array keeps its items side by side, which makes indexing fast and inserting slow. A linked list makes the opposite trade. Each item lives in its own small object, called a node, and every node holds a reference to the next one. Nothing needs to be next to anything else in memory, so adding or removing an item at a known place only means changing a couple of references, while reaching the hundredth item means following a hundred links one at a time.

You will rarely write a linked list in everyday Python, because the built-in list and collections.deque cover most needs. But linked structures are everywhere under the surface, from deque's own blocks to the caches in web browsers, and writing one is the best practice there is for thinking in references. This lesson builds a singly linked list for Theo's delivery route, extends it to a doubly linked list, compares both with Python's list, and finishes with the classic interview task of reversing a linked list.

Nodes and links

A node is a tiny object with two fields: the value it stores and a reference to the next node. The last node's next reference is None, which marks the end. The list itself only needs to remember its first node, called the head; every other node is reached by following next references from there. In Python, a node is an ordinary class, and a dataclass with slots keeps it compact.

from dataclasses import dataclass

@dataclass(slots=True)
class Node:
    value: str
    next: "Node | None" = None

# Theo's delivery route: roastery -> Lakeview Cafe -> Pine St Deli
third = Node("Pine St Deli")
second = Node("Lakeview Cafe", third)
head = Node("Roastery", second)

node = head
while node is not None:
    print(node.value)
    node = node.next

Roastery
Lakeview Cafe
Pine St Deli

The while loop is the pattern behind every linked-list operation: start at the head, do something with the current node, move to node.next, and stop at None. That walk visits n nodes, so anything that must find a position by walking, such as reaching the k-th stop or searching for a value, is O(n).

A LinkedList class

Wrapping the nodes in a class keeps the details in one place. Adding at the front is the linked list's best operation: create a node whose next is the current head, then make it the new head. Two reference changes, whatever the length, so O(1). Adding at the back would mean walking to the last node, O(n), unless the list also remembers its last node, called the tail, which makes appending O(1) too.

from dataclasses import dataclass

@dataclass(slots=True)
class Node:
    value: str
    next: "Node | None" = None

class LinkedList:
    def __init__(self, values=()):
        self.head = self.tail = None
        self._size = 0
        for v in values:
            self.append(v)
    def push_front(self, value):                 # O(1)
        self.head = Node(value, self.head)
        if self.tail is None:
            self.tail = self.head
        self._size += 1
    def append(self, value):                     # O(1) thanks to the tail
        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):
        node = self.head
        while node:
            yield node.value
            node = node.next
    def __len__(self):
        return self._size
    def __repr__(self):
        return " -> ".join(self) or "(empty)"

route = LinkedList(["Lakeview Cafe", "Pine St Deli"])
route.push_front("Roastery")
route.append("Roastery")                 # back to base at the end
print(route, len(route))
print("Pine St Deli" in route)           # works through __iter__, O(n)

Roastery -> Lakeview Cafe -> Pine St Deli -> Roastery 4
True

Storing the size in a counter keeps len O(1); without it, len would have to walk the whole list. Defining __iter__ as a generator, as in PYTH-102, lets the list work with for loops, in, list() and join. The test "Pine St Deli" in route walks the nodes one by one, O(n), just as it would for an array.

Inserting and removing

Where linked lists shine is changing the middle once you already have a reference to the right node. Rosa has signed a new wholesale customer, Bayside Bakery, which sits between Lakeview Cafe and Pine St Deli on the route. With an array of stops, inserting it would shift every later stop. With a linked list, you create the new node, point it at the node after Lakeview Cafe, and point Lakeview Cafe at it. The order of those two steps matters: if Lakeview Cafe's reference changed first, the rest of the route would be lost.

Removing works the same way in reverse: to remove the node after a given node, make the given node point past it. The removed node is no longer referenced by anything, so Python reclaims its memory automatically. Removing by value first needs a walk to find the node before the one to remove, so the search is O(n) even though the unlinking itself is O(1).

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

def show(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return " -> ".join(out)

head = Node("Roastery", Node("Lakeview Cafe", Node("Pine St Deli")))

def insert_after(node, value):
    node.next = Node(value, node.next)        # new node points on first, then gets linked in

def remove_value(head, value):
    """Remove the first node holding value; return the (possibly new) head."""
    if head and head.value == value:
        return head.next
    prev = head
    while prev and prev.next:
        if prev.next.value == value:
            prev.next = prev.next.next        # skip over the node
            break
        prev = prev.next
    return head

insert_after(head.next, "Bayside Bakery")
print(show(head))
head = remove_value(head, "Pine St Deli")
print(show(head))
head = remove_value(head, "Roastery")
print(show(head))

Roastery -> Lakeview Cafe -> Bayside Bakery -> Pine St Deli
Roastery -> Lakeview Cafe -> Bayside Bakery
Lakeview Cafe -> Bayside Bakery

Removing the head is a special case, because there is no node before it; the function returns the new head so the caller can update its reference. Special cases at the ends, and at an empty list, are where most linked-list bugs live, so always test those three situations: empty, one item, and the first or last item.

def to_list(head):
    return [head.value]

def length(head):
    return 1

route = Node('Roastery', Node('Lakeview Cafe', Node('Pine St Deli')))
print(to_list(route), length(route))

Doubly linked lists

A singly linked list can only be walked forward, and removing a node requires the node before it. A doubly linked list gives every node a second reference, prev, pointing backward. Now a node can be removed in O(1) given only a reference to the node itself, because its neighbors are reachable from it, and the list can be walked in either direction. The cost is one more reference per node and more references to keep consistent on every change.

Doubly linked lists are the classic way to build a least-recently-used (LRU) cache: the most recently used items sit at one end, and when the cache is full, the item at the other end is removed. Combined with a dictionary that maps keys to nodes, every operation is O(1). Python's collections.OrderedDict provides exactly this behavior through its move_to_end and popitem methods, so you can build an LRU cache without writing the links yourself.

from collections import OrderedDict

class RecentlyViewed:
    """Keep the last `size` products a shopper viewed, most recent last."""
    def __init__(self, size=3):
        self.size, self.items = size, OrderedDict()
    def view(self, sku):
        if sku in self.items:
            self.items.move_to_end(sku)        # O(1): relink to the newest end
        else:
            self.items[sku] = True
            if len(self.items) > self.size:
                self.items.popitem(last=False) # O(1): drop the oldest
    def __repr__(self):
        return str(list(self.items))

rv = RecentlyViewed()
for sku in ["RC-101", "RC-104", "RC-102", "RC-101", "RC-106"]:
    rv.view(sku)
    print(rv)

['RC-101']
['RC-101', 'RC-104']
['RC-101', 'RC-104', 'RC-102']
['RC-104', 'RC-102', 'RC-101']
['RC-102', 'RC-101', 'RC-106']

The functools.lru_cache decorator you met in PYTH-102 uses the same structure internally. Knowing how it works explains why it is fast: looking up a cached call is a dictionary lookup, and recording a use or evicting the oldest entry is a few reference changes.

Linked lists compared with Python's list

With big O in hand, the comparison is clear. Each structure is fast where the other is slow, and the choice depends on which operations a program performs most often.

In practice, Python's list wins far more often than the table suggests. Its items sit together in memory, which modern processors read very quickly, while a linked list's nodes are scattered, and every node is a full Python object with its own overhead. Use the built-in structures first, and reach for a linked design when profiling shows that middle insertions or removals truly dominate, or when, as with an LRU cache, you need O(1) removal of a node you already hold.

Reversing a linked list

Reversing a singly linked list in place is a favorite exercise because it forces careful handling of references. Walk the list once, keeping three references: prev (the already reversed part, initially None), node (the current node) and nxt (the rest of the list, saved before it is lost). At each step, point node.next back at prev, then move all three references one step forward. When node reaches None, prev is the new head. The algorithm is O(n) time and O(1) extra space.

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

def reverse(head):
    prev, node = None, head
    while node is not None:
        nxt = node.next      # save the rest of the list
        node.next = prev     # turn this node around
        prev, node = node, nxt
    return prev

def show(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return " -> ".join(out) or "(empty)"

route = Node("Roastery", Node("Lakeview Cafe", Node("Bayside Bakery", Node("Pine St Deli"))))
print(show(route))
back = reverse(route)
print(show(back))
print(show(reverse(None)))

Roastery -> Lakeview Cafe -> Bayside Bakery -> Pine St Deli
Pine St Deli -> Bayside Bakery -> Lakeview Cafe -> Roastery
(empty)

def reverse(head):
    return head

r = reverse(Node('A', Node('B', Node('C'))))
print(r.value)