Linked Lists

What the representation promises

The links define logical order; allocation addresses define physical placement. Those are independent. A node at a numerically smaller address can appear later in the list, and an allocator may sometimes place nearby nodes together. “Linked” means the algorithm follows references, not that every node must be physically far apart.

Interactive: walk a chain, then splice one

The addresses are deliberately out of logical order. Step through traversal, then insert 29 after node B and notice why the new node must remember the old suffix before B's link changes.

A minimal, maintainable representation

These implementations store head, tail, and size. Tail and size are conveniences, not properties every linked list must maintain; each adds invariants that every mutation must preserve.

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


class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def prepend(self, value):
        node = Node(value, self.head)
        self.head = node
        if self.tail is None:       # empty -> one node
            self.tail = node
        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 insert_after(self, predecessor, value):
        # Precondition: predecessor is a node in this list.
        if predecessor is None:
            raise ValueError("a predecessor handle is required")
        node = Node(value, predecessor.next)  # preserve suffix first
        predecessor.next = node
        if self.tail is predecessor:
            self.tail = node
        self.size += 1
        return node

final class SinglyLinkedList<T> {
    static final class Node<T> {
        final T value;
        Node<T> next;

        Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node<T> head;
    private Node<T> tail;
    private int size;

    void prepend(T value) {
        Node<T> node = new Node<>(value, head);
        head = node;
        if (tail == null) tail = node; // empty -> one node
        size++;
    }

    void append(T value) {
        Node<T> node = new Node<>(value, null);
        if (tail == null) {
            head = tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        size++;
    }

    Node<T> insertAfter(Node<T> predecessor, T value) {
        // Precondition: predecessor is a node in this list.
        if (predecessor == null) {
            throw new IllegalArgumentException("a predecessor handle is required");
        }
        Node<T> node = new Node<>(value, predecessor.next); // preserve suffix
        predecessor.next = node;
        if (tail == predecessor) tail = node;
        size++;
        return node;
    }
}

Invariants: the mutation checklist

An invariant is true before and after every public operation. For an acyclic singly linked list with head, tail, and size, these statements form a useful executable specification.

Representation matters: a circular list intentionally violates tail.next is null; a sentinel-based list may never have a null head. State invariants for the design you actually implement.

Traversal is a small correctness proof

def find(head, target):
    current = head
    while current is not None:
        if current.value == target:
            return current       # return a handle, not an index
        current = current.next
    return None

import java.util.Objects;

final class LinkedSearch {
    static final class Node<T> {
        final T value;
        Node<T> next;

        Node(T value) { this.value = value; }
    }

    static <T> Node<T> find(Node<T> head, T target) {
        Node<T> current = head;
        while (current != null) {
            if (Objects.equals(current.value, target)) {
                return current; // return a handle, not an index
            }
            current = current.next;
        }
        return null;
    }
}

Time is Θ(k) when the algorithm examines k nodes. Worst-case search is Θ(n); extra working space is Θ(1) iteratively. A recursive traversal uses O(n) call-stack space in the worst case.

Operation costs: include the lookup

Memory reality: more than one pointer

Linked list versus dynamic array

Big-O alone misses constants and locality. For compact values and scan-heavy workloads, a dynamic array often wins even when a list advertises a better asymptotic insertion bound, especially if the list first traverses to find the position.

Ownership, identity, and aliasing

Pointer rewiring changes which nodes are reachable; it does not automatically settle who owns or may mutate them. In garbage-collected languages, references keep objects alive. In manual-memory languages, the program must define who frees a removed node and ensure no remaining reference dereferences it.

Sentinel nodes remove boundary branches

def remove_first(head, target):
    dummy = Node(None, head)
    previous = dummy

    while previous.next is not None:
        if previous.next.value == target:
            previous.next = previous.next.next
            break
        previous = previous.next

    return dummy.next  # works even when the old head was removed

import java.util.Objects;

final class RemoveFirst {
    static final class Node<T> {
        final T value;
        Node<T> next;

        Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }
    }

    static <T> Node<T> removeFirst(Node<T> head, T target) {
        Node<T> dummy = new Node<>(null, head);
        Node<T> previous = dummy;

        while (previous.next != null) {
            if (Objects.equals(previous.next.value, target)) {
                previous.next = previous.next.next;
                break;
            }
            previous = previous.next;
        }

        return dummy.next; // works even when the old head was removed
    }
}

Patterns built from the same links

def reverse(head):
    previous = None
    current = head

    while current is not None:
        following = current.next  # save the suffix
        current.next = previous   # reverse one edge
        previous = current
        current = following

    return previous

final class ReverseList {
    static final class Node<T> {
        final T value;
        Node<T> next;

        Node(T value) { this.value = value; }
    }

    static <T> Node<T> reverse(Node<T> head) {
        Node<T> previous = null;
        Node<T> current = head;

        while (current != null) {
            Node<T> following = current.next; // save the suffix
            current.next = previous;          // reverse one edge
            previous = current;
            current = following;
        }

        return previous;
    }
}

Choose the representation deliberately

Common practical compositions matter more than novelty: a queue pairs a singly linked list with head and tail; an LRU cache typically pairs a hash map with a doubly linked list; allocator free lists and intrusive lists appear in lower-level systems where object movement and lifetime are tightly controlled.

Failure modes worth rehearsing