Linked Lists

Data Structures in Practice

Chapter 5 · Linked Lists

A linked list stores items in separate small objects, each holding a value and a reference to the next one. Nothing is stored side by side, which is the opposite of the array inside a Python list (Data Structures in Practice 2). It is a classic structure that every programmer should be able to build, and understanding it also explains why it is rarely the right tool in Python.

What was run, and what was not

Every snippet below was run and the output shown is what it printed. No timings or memory sizes are quoted, because they differ between machines; costs are described as patterns.

Nodes and Pointers

Each node holds a value and a next reference. The last node's next is None. The list itself is just a reference to the first node, called the head. To visit every item you start at the head and follow next until you run out.

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

a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c

n = a
while n:
    print(n.value, end=" ")
    n = n.next
print()
    

1 2 3

The picture to hold in your head:

head
  │
  ▼
┌───┬───┐   ┌───┬───┐   ┌───┬──────┐
│ 1 │ ●─┼──▶│ 2 │ ●─┼──▶│ 3 │ None │
└───┴───┘   └───┴───┘   └───┴──────┘
    

A Small LinkedList Class

Wrapping the head in a class gives a tidy interface. This version keeps a size counter so that len() does not have to walk the chain, and an __iter__ so that list(ll) and for loops work.

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

    def push_front(self, value):
        self.head = Node(value, self.head)
        self.size += 1

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

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

    def __len__(self):
        return self.size

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

    def remove(self, value):
        prev, cur = None, self.head
        while cur:
            if cur.value == value:
                if prev:
                    prev.next = cur.next
                else:
                    self.head = cur.next
                self.size -= 1
                return True
            prev, cur = cur, cur.next
        return False

    def insert_after(self, node, value):
        node.next = Node(value, node.next)
        self.size += 1
    

ll = LinkedList()
for v in [2, 3, 4]:
    ll.append(v)
ll.push_front(1)
print(list(ll), len(ll))
ll.insert_after(ll.find(2), 99)
print(list(ll), len(ll))
print(ll.remove(99), ll.remove(1), ll.remove(42))
print(list(ll), len(ll))
    

[1, 2, 3, 4] 4
[1, 2, 99, 3, 4] 5
True True False
[2, 3, 4] 3
    

Note the two cases in remove: deleting the head means moving self.head, while deleting anywhere else means the previous node must skip over it. Tracking prev as you walk is what makes that possible, because a node cannot see backwards.

Reversing in Place

A favourite exercise, and a good test of whether you can hold several references at once. Walk the chain and flip each next to point backwards. The original next must be saved before it is overwritten.

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next      # save it before overwriting
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

ll.head = reverse(ll.head)
print(list(ll))
    

[4, 3, 2]

No new nodes were made: the same objects were relinked. The function returns the new head, so the caller must store it.

Where Linked Lists Win, on Paper

In theory the trade is simple. Once you hold a reference to a node, inserting after it or unlinking its neighbour changes one or two references, with no shifting of anything else. A list has to move every item after the position.

Operation	Python list	Linked list
Index `x[i]`	Constant	Walk i nodes
Append at the end	Amortised constant	Constant with a tail reference, otherwise a full walk
Insert or remove at the front	Shifts every item	Constant
Insert or remove next to a node you already hold	Shifts items after it	Constant
Find a value	Walk (linear)	Walk (linear)
Extra memory per item	One reference	A whole object plus one or two references
Memory layout	Contiguous references	Scattered objects

Why Python Rarely Needs One

The "constant insertion" advantage needs a node in hand. Finding that node is a linear walk, so inserting at a position you only know by index or value is linear for both structures.
Every node is a full Python object. It carries object overhead on top of the value and the reference, so a linked list uses noticeably more memory than a list of the same items.
Scattered objects are slower to walk. A list's references sit next to each other; a chain of nodes can be spread across memory, which tends to make traversal slower in practice even when the step count is equal.
Python's own list is written in C. Shifting items inside it is a tight low-level loop, while your while cur: loop runs through the interpreter one step at a time. For all but very large sizes, the "slow" list is the faster choice.
The common cases already have a tool. Fast work at both ends is a deque (Data Structures in Practice 4), which is itself built from linked blocks. Fast membership is a set or dict (Data Structures in Practice 3).

Do not assume "insert in the middle is faster"

That sentence is true of the textbook model and often false in measured Python code. If it matters for your data, measure both on realistic sizes (Data Structures in Practice 1) before building a custom structure.

Where You Still Meet Linked Structures

The idea is everywhere even when you do not build the list yourself: deque uses linked blocks internally, trees and graphs (Data Structures in Practice 7 and 8) are nodes with several references, and hash table chains, undo histories in some systems and operating-system queues are all linked. Lower-level languages use plain linked lists far more often, and technical interviews ask about them for exactly that reason.

Two Pointer Habits

Most linked-list problems rely on a few patterns.

Track prev and cur. You need the previous node to remove one (as in remove) or to flip direction (as in reverse).
Slow and fast pointers. Move one pointer a step at a time and another two steps. When the fast one finishes, the slow one is at the middle; if there is a loop, the fast one catches the slow one. Exercises 1 and 2 use this.
A dummy node. Start with a placeholder in front of the real head so the "list is empty" case needs no special code. Exercise 3 uses this.

Singly and doubly linked

This chapter's nodes only point forwards (singly linked). A doubly linked node also stores a prev reference, so you can walk backwards and unlink a node without hunting for its predecessor, at the price of one more reference per node and more links to keep consistent.

Challenges

Exercise 1

Using Node and a helper build(values) that creates a chain from a Python list, write middle(head) that returns the value of the middle node in one pass, using slow and fast pointers and no length count. Test it on 5 nodes, 4 nodes (say which middle you return), 1 node and an empty list (return None).

📄 View solution

Exercise 2

Write has_cycle(head) that returns True if following next would loop forever. Build a four-node chain, check it gives False, then make the last node point back to the second and check it gives True. Explain why you compare nodes with is rather than ==.

📄 View solution

Exercise 3

Write merge_sorted(a, b) that merges two already-sorted linked lists into one sorted chain by relinking the existing nodes (no new nodes except one dummy). Test [1, 4, 6] with [2, 3, 7, 9], an empty list with [5], and [1, 1] with [1]. Add a short to_list(head) helper to print results.

📄 View solution

Quick Reference

Node: a value plus next; the list is its head
Strengths: constant-cost insert or remove at the front or next to a node you hold
Weaknesses: no indexing, linear search, more memory, scattered layout
In Python: use list by default and deque for both ends; build a linked list to learn or when relinking nodes is the point
Patterns: prev/cur, slow/fast, dummy head
Reverse: save next first, flip, advance; return the new head
Measure before choosing a custom structure for speed

Coming next

Data Structures in Practice 6 covers heaps and priority queues: heapq, finding the top k items and simple scheduling, the answer to "the most urgent".