Linked Lists

The arrays wing forced the librarian to copy the entire collection across the street whenever the shelves filled up. There is another way to run a library. Stop building shelves at all. Let every book sit wherever there is space, tuck a small index card inside the cover, and write on each card the location of the next book in the sequence. Adding a book costs nothing — find any open spot, write a card, slide the previous book's card to point at the new one. The librarian no longer chases capacity. She walks the chain.

This was the move John McCarthy made at MIT in 1958 when he was inventing LISP. He needed to represent symbolic expressions — math formulas, nested lists, programs that could be passed around as data. Fixed-size arrays could not stretch the way symbolic logic needed to stretch. McCarthy invented the cons cell: a tiny two-slot record holding one value and a pointer to the next cell. Every list in LISP was a chain of these cells. Every list in every functional language since has inherited the idea. The cost is that walking from the front to position 47 takes 47 hops instead of one jump, but for problems where you mostly add and remove from the ends, the chain wins.

Build the chain yourself in linked.py. The Node class is the index card. The LinkedList class is the librarian who knows where the chain starts.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        cursor = self.head
        while cursor.next is not None:
            cursor = cursor.next
        cursor.next = new_node
 
    def prepend(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
 
    def insert_after(self, target_value, value):
        cursor = self.head
        while cursor is not None and cursor.value != target_value:
            cursor = cursor.next
        if cursor is None:
            raise ValueError(f"{target_value} not in list")
        new_node = Node(value)
        new_node.next = cursor.next
        cursor.next = new_node
 
    def delete(self, value):
        if self.head is None:
            return
        if self.head.value == value:
            self.head = self.head.next
            return
        cursor = self.head
        while cursor.next is not None and cursor.next.value != value:
            cursor = cursor.next
        if cursor.next is None:
            return
        cursor.next = cursor.next.next
 
    def show(self):
        parts = []
        cursor = self.head
        while cursor is not None:
            parts.append(str(cursor.value))
            cursor = cursor.next
        print(" -> ".join(parts) if parts else "(empty)")

The head is the only entry point. Everything else is reached by following next from one card to the next. Run the chain through every operation and watch the order shift after each one.

ll = LinkedList()
ll.show()
 
ll.append("A"); ll.show()
ll.append("B"); ll.show()
ll.append("C"); ll.show()
 
ll.prepend("Z"); ll.show()
 
ll.insert_after("B", "B2"); ll.show()
 
ll.delete("A"); ll.show()
ll.delete("Z"); ll.show()

The trace prints each mutation as a fresh chain.

(empty)
A
A -> B
A -> B -> C
Z -> A -> B -> C
Z -> A -> B -> B2 -> C
Z -> B -> B2 -> C
B -> B2 -> C

The interesting move is the middle insertion. When you insert B2 after B, no other book moves. The librarian walks from the head, finds B, scribbles a new card for B2 that points to whatever B used to point at, then changes B's card to point at B2. Two card edits. That is the whole operation. An array would have had to shove every book after B one shelf to the right.

The chain pays for that flexibility. To find B2, you walk from the head, hop to A, hop to B, hop to B2. Every visit is one hop. Indexing is no longer instant. There is also a memory tax: each Node carries an extra pointer slot, so a list of a million ints in linked-list form weighs more than an array of a million ints. Pick the shape that matches the workload. If you mostly append and read by index, take the array. If you mostly insert in the middle and never index, take the chain.

The doubly linked variant adds a prev pointer to each Node so the chain can be walked backward as well. That is the structure inside Python's collections.deque, which is the production-grade chain you reach for when you want fast adds and removes from both ends. Type this.

from collections import deque
 
dq = deque()
print(dq)
dq.append("A"); print(dq)
dq.append("B"); print(dq)
dq.appendleft("Z"); print(dq)
dq.pop(); print(dq)
dq.popleft(); print(dq)

Output:

deque([])
deque(['A'])
deque(['A', 'B'])
deque(['Z', 'A', 'B'])
deque(['Z', 'A'])
deque(['A'])

The deque hides the Node class and the pointer rewiring. Under the hood it is a doubly linked list of fixed-size blocks, written in C. The same chain shape that McCarthy invented in 1958 is sitting one import away, faster than anything you could write in pure Python, with the same operations exposed as append, appendleft, pop, popleft. Keep the LinkedList class you wrote. The next page builds two new shapes on top of it.

Question: between the array and the linked list, which one would you pick for storing a player's chat history in a multiplayer game, where new messages always arrive at the bottom and old messages scroll off the top after 100?

Answer: the linked list — specifically the doubly-linked deque. Adds at one end and removes from the other are both single-pointer rewires. An array would have to shift every remaining message down by one slot every time the oldest message scrolled off.

The linked list lets you add a book anywhere in the chain. That freedom is the thing that lets you start placing rules on it: what if the librarian only allowed you to take the most recently added book, or only the oldest one still waiting? Constraints turn the chain into something with new uses.