Linked lists: singly and doubly

What this chapter covers

The array wins by keeping its elements together in memory. The linked list makes the opposite bet: let every element sit wherever, and connect them with pointers. That single decision flips the whole cost profile. You lose O(1) access by index — there's no address to compute, so reaching the k-th element means following k pointers — and in exchange you win O(1) insertion and deletion anywhere you're already standing, with nothing else moving. This chapter builds both the singly linked list and its doubly linked cousin, and races them against the array-backed list to show, concretely, which operation each structure is built to win.

A bit of history

Linked lists are one of the oldest ideas in computing that wasn't just a machine instruction. They came out of early artificial-intelligence work: Allen Newell, Cliff Shaw, and Herbert Simon built them into IPL, the Information Processing Language, around 1955 and 1956, to represent structures that grew and reshaped themselves as a program ran — something fixed arrays couldn't do gracefully. The idea spread fast because it solved a real problem of the era: memory was scarce and precious, and a linked list lets you grow a collection one node at a time out of whatever free memory you have, instead of reserving a big contiguous block up front. That founding trade — flexibility of layout in exchange for giving up random access — is exactly the one you still weigh today.

The intuition

A node is a value plus a pointer to the next node. The list itself is just a reference to the first node, the head; you find everything else by following pointers from there. The last node points at nothing, which is how you know you've reached the end.

Because the nodes aren't in a row, there's no arithmetic that jumps you to element k. To read the fifth element you start at the head and follow the next pointer five times. That's the price. What you buy is that inserting or deleting doesn't shift anything: to insert after a node you already hold, you make your new node point where that node was pointing, then point that node at your new node. Two assignments, done, no matter how long the list is. Compare that to the array, where inserting in the middle drags every later element over by one.

The doubly linked list adds a second pointer in each node, back to the previous one. It costs a little memory and a little bookkeeping, and it buys two things the singly linked list can't do cheaply: delete a node when all you have is the node itself, and walk backward from the tail.

Complexity: how it scales

The linked list's costs are almost the mirror image of the array's:

• Access by index, and search by value: $O(n)$. You walk from the head.
• Insert or delete at a node you already hold: $O(1)$. Rewire the pointers.
• Push to the front, or append with a tail pointer: $O(1)$.

There's no recurrence to unfold here — the analysis is just counting pointer hops. The one thing worth saying precisely is why access is genuinely $O(n)$ and not hiding a cheaper path: the only entry points into the list are the head and (if you keep one) the tail, and from an endpoint the k-th element is k hops away, with no shortcut, because the nodes carry no position information.

The chart below is the access cost, measured. It reads every element of a linked list by index and times it against doing the same to an array-backed list. The linked line curves upward hard — reading all n elements by index is n separate walks, an $O(n^2)$ job — while the array line hugs the floor:

At n = 4000 the numbers are stark: reading every element by index took about 81 ms through the linked list and 0.06 ms through the array — the array was roughly thirteen hundred times faster. That is not a constant-factor gap; it's a complexity-class gap, $O(n^2)$ against $O(n)$, and it's the array's whole reason for existing.

What it's good at, what it isn't

Reach for a linked list when your work is at the ends or at positions you already hold a reference to, and you rarely need to jump to an arbitrary index. Queues, deques, the eviction list inside an LRU cache, adjacency lists in a graph — these are natural linked structures because the operations are all splice-here, pop-there, never "give me element 5000." The list also grows one node at a time with no resize and no copy, so there are no amortized spikes and no moment where it needs the data twice over in memory.

The costs are real and often decisive. Every node is a separate allocation with pointer overhead, so a linked list uses more memory than an array holding the same values, and — this matters more than the memory — the nodes are scattered, so walking the list thrashes the cache. An array walk streams through contiguous memory the CPU prefetches; a linked walk chases pointers to random addresses, paying a cache miss at each hop. In practice this makes arrays beat linked lists at iteration even though both are $O(n)$, and it's why the advice "use an array unless you have a specific reason not to" is usually right.

The data, or the inputs

The inputs are small sequences of integers again — the values don't matter, the structure does. The interesting thing to watch is what "access" actually means when there's no index arithmetic: the physical act of walking from the head, following one pointer at a time.

Build it, one function at a time

Pushing to the front is the operation the linked list makes trivial — a new node points at the old head, and the head moves:

def push_front(self, value):
    """O(1): the new node points at the old head, then head moves to it.
    No traversal, no shifting — this is where the linked list shines."""
    self.head = Node(value, self.head)
    if self.tail is None:
        self.tail = self.head
    self._n += 1

Appending is just as cheap as long as you keep a tail pointer, so you don't have to walk to the end to find it:

def append(self, value):
    """O(1): a tail pointer lets us link onto the end without walking there."""
    node = Node(value)
    if self.tail is None:
        self.head = self.tail = node
    else:
        self.tail.next = node
        self.tail = node
    self._n += 1

Now the cost side. Getting element index has no shortcut — you start at the head and take index hops. The optional probe records the value at each hop, which is what drives the animation:

def get(self, index, probe=None):
    """O(n): the cost the array doesn't have. There is no formula for the
    address of element `index`; you start at the head and follow one `next`
    pointer at a time until you've taken `index` hops."""
    if not 0 <= index < self._n:
        raise IndexError(index)
    node = self.head
    for _ in range(index):
        if probe is not None:
            probe.append(node.value)
        node = node.next
    if probe is not None:
        probe.append(node.value)
    return node.value

And here's the payoff that justifies the access cost: inserting after a node you already hold is two pointer assignments, independent of the list's length:

def insert_after(self, node, value):
    """O(1): rewire two pointers. Nothing else moves — the whole reason to
    pay the access cost above is to buy insertions this cheap."""
    node.next = Node(value, node.next)
    if node is self.tail:
        self.tail = node.next
    self._n += 1

The doubly linked list earns its extra pointer on deletion. Given just a node, it can splice itself out in O(1) by touching its neighbors — a singly linked list would first have to find the previous node by walking from the head:

def delete(self, node):
    """O(1): unlink a node given only the node itself — impossible in a
    singly linked list, which would first have to find the predecessor by
    walking from the head (O(n))."""
    if node.prev is not None:
        node.prev.next = node.next
    else:
        self.head = node.next
    if node.next is not None:
        node.next.prev = node.prev
    else:
        self.tail = node.prev
    self._n -= 1

Watch it work

This is what O(n) access looks like from the inside. We're searching an eleven-node list for the value 5, which sits near the end. Each frame is one hop: orange is the node we're looking at, faded nodes are ones we've already walked past, green is the hit. There's no jumping ahead — the only way forward is to follow the next pointer to the neighbor. It took nine hops to reach the value. An array would have gone straight to it:

The complete code

Both versions in one place — flip between them. The from-scratch tab holds both lists: the singly linked list with its O(1) ends and O(n) access, and the doubly linked list whose prev pointer makes deletion O(1). The library tab is the linked structure you actually use in Python — collections.deque, a doubly linked list of small blocks with O(1) work at both ends.

"""Singly and doubly linked lists, from scratch.

A linked list gives up the array's one trick — O(1) access by index — to win a
different one: O(1) insertion and deletion at a position you already hold,
without moving any other element. There is no address arithmetic here; the only
way to reach the k-th element is to start at the head and follow k pointers.
"""


class Node:
    """A singly linked node: a value and a pointer to the next node."""
    __slots__ = ("value", "next")

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


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

    # region: push_front
    def push_front(self, value):
        """O(1): the new node points at the old head, then head moves to it.
        No traversal, no shifting — this is where the linked list shines."""
        self.head = Node(value, self.head)
        if self.tail is None:
            self.tail = self.head
        self._n += 1
    # endregion

    # region: append
    def append(self, value):
        """O(1): a tail pointer lets us link onto the end without walking there."""
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self._n += 1
    # endregion

    # region: get
    def get(self, index, probe=None):
        """O(n): the cost the array doesn't have. There is no formula for the
        address of element `index`; you start at the head and follow one `next`
        pointer at a time until you've taken `index` hops."""
        if not 0 <= index < self._n:
            raise IndexError(index)
        node = self.head
        for _ in range(index):
            if probe is not None:
                probe.append(node.value)
            node = node.next
        if probe is not None:
            probe.append(node.value)
        return node.value
    # endregion

    # region: insert_after
    def insert_after(self, node, value):
        """O(1): rewire two pointers. Nothing else moves — the whole reason to
        pay the access cost above is to buy insertions this cheap."""
        node.next = Node(value, node.next)
        if node is self.tail:
            self.tail = node.next
        self._n += 1
    # endregion

    # region: find
    def find(self, value, probe=None):
        """O(n): follow `next` pointers from the head until the value shows up."""
        node = self.head
        idx = 0
        while node is not None:
            if probe is not None:
                probe.append(node.value)
            if node.value == value:
                return idx
            node = node.next
            idx += 1
        return -1
    # endregion

    def __len__(self):
        return self._n

    def to_list(self):
        out, node = [], self.head
        while node is not None:
            out.append(node.value)
            node = node.next
        return out


class DNode:
    """A doubly linked node: a value plus pointers BOTH ways."""
    __slots__ = ("value", "prev", "next")

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


class DoublyLinkedList:
    """The prev pointer costs one extra link per node and buys two things a
    singly linked list can't do in O(1): delete a node you hold, and pop from
    the back. It's the structure behind most real deques and LRU caches."""

    def __init__(self):
        self.head = None
        self.tail = None
        self._n = 0

    # region: dpush_back
    def push_back(self, value):
        """O(1): link a node on at the tail, wiring both directions."""
        node = DNode(value)
        node.prev = self.tail
        if self.tail is not None:
            self.tail.next = node
        else:
            self.head = node
        self.tail = node
        self._n += 1
        return node
    # endregion

    # region: ddelete
    def delete(self, node):
        """O(1): unlink a node given only the node itself — impossible in a
        singly linked list, which would first have to find the predecessor by
        walking from the head (O(n))."""
        if node.prev is not None:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next is not None:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        self._n -= 1
    # endregion

    def __len__(self):
        return self._n

    def to_list(self):
        out, node = [], self.head
        while node is not None:
            out.append(node.value)
            node = node.next
        return out

"""The library counterpart is collections.deque — a doubly linked list of small
blocks in CPython. It's what you actually reach for when you need O(1) work at
both ends of a sequence.

Two comparisons make the chapter's point:
  1. At the FRONT, the linked structures (our list, deque) are O(1) while the
     array-backed list.insert(0, x) is O(n) — the linked list wins.
  2. By INDEX, the array-backed list is O(1) while walking a linked structure is
     O(n) — the array wins.
Different structures win different operations; that's the whole trade.
"""
from collections import deque


# region: deque_front
def push_front_with_deque(values):
    """O(1) per appendleft — deque is doubly linked, so the front is as cheap
    as the back."""
    dq = deque()
    for value in values:
        dq.appendleft(value)
    return dq
# endregion


# region: list_front
def push_front_with_list(values):
    """O(n) per insert(0, x) — the array-backed list must shift everything right
    each time, so this is O(n^2) overall. Shown as the anti-pattern."""
    out = []
    for value in values:
        out.insert(0, value)
    return out
# endregion


# region: list_index
def sum_by_index_list(seq):
    """O(1) per index into an array-backed list — the operation the linked list
    can't match."""
    total = 0
    for i in range(len(seq)):
        total += seq[i]
    return total
# endregion

Scratch vs library

This face-off is the clearest statement of the chapter's whole point: different structures win different operations. The left panel inserts at the front n times — our linked list and the deque stay cheap (O(1) each, so linear overall) while the array-backed list climbs steeply, because list.insert(0, x) shifts everything right every time. The right panel reads every element by index, and it's the exact reverse: the array is flat and the linked list explodes.

At n = 16000, inserting at the front took about 2.4 ms through our linked list and 0.23 ms through the deque, but 19 ms through the array-backed list — the array loses the front by an order of magnitude. Flip to access and the array wins by three orders. Notice the deque beats even our linked list on the front: same Big-O, but it's a tuned C structure that links blocks of elements rather than one node per value, which cuts both the per-node overhead and the cache misses. When you genuinely need a linked structure in Python, that's the one to use — not a hand-built chain of nodes.

Where you'll actually meet it

You rarely type out a linked list by hand, but you use them constantly through other structures. A deque is one. The ready and blocked queues inside an operating system's scheduler are linked lists of processes. The LRU cache in the advanced chapters is a hash map pointing into a doubly linked list, so it can move a node to the front in O(1) on every access. Graph adjacency lists are linked lists of neighbors. And any time you've been told "appending to a list is fine but inserting at the front in a loop is a performance bug," that advice exists because someone confused the array-backed list's cost model with a linked list's.

Takeaways

A linked list trades the array's O(1) indexed access for O(1) insertion and deletion at a held position, by scattering its elements and connecting them with pointers. Access and search become O(n) walks; splicing becomes two or four pointer assignments. The doubly linked variant spends one extra pointer per node to make deletion-by-node and backward traversal O(1), which is why it, not the singly linked list, underlies real deques and caches.

Weigh it against the array by asking where your operations happen. At arbitrary indices, or iterating hot loops where cache matters, the array wins — usually decisively, because contiguous memory is a constant-factor advantage that Big-O doesn't show. At the ends, or at positions you already hold, the linked list wins. Most of the time the array is the right default and deque covers the cases where it isn't. The next two chapters take this structure and clamp its operations down to just the cheap ends, which is exactly what a stack and a queue are.