Linked Lists

A linked list is the canonical dynamic data structure: a chain of nodes scattered across memory, joined by pointers, that can grow and shrink at runtime. Where an array buys fast indexing by committing to one fixed contiguous block, a linked list buys cheap insertion and unlimited growth by giving that up. It is also the structure on which stacks, queues and the nodes of trees and graphs are built.

---

Spec Mapping

This lesson addresses the H446 1.4.2 Data Structures content on linked lists:

• Describe a linked list as a dynamic structure of nodes, each holding data and a pointer/reference to the next node, with a head pointer and a null terminator.
• Distinguish singly and doubly linked lists (and recognise the circular variant), and explain the role of pointers/references.
• Carry out and trace insertion, deletion, search and traversal, understanding how the pointers are re-linked at each step.
• Compare arrays and linked lists, justifying a choice from the trade-offs in access time, insertion/deletion cost, memory overhead and resizing.

(Phrasing here paraphrases the specification content; it is not a verbatim quote.)

---

What is a Linked List?

A linked list is a linear data structure in which each element — a node — holds two things:

1. Data — the value stored at that node.
2. A pointer (reference) — the location of the next node, or null if there is none.

Crucially, the nodes are not stored contiguously. Each node can live anywhere on the heap; the pointers are what impose order, like links joining beads into a chain. The program only ever directly knows the head (the address of the first node); to reach any other node it must follow pointers from the head. That single fact — no direct address arithmetic — is why a linked list trades away the array's $O(1)$O(1) random access.

Key Terminology

Term	Definition
Node	One element: a data field plus one (or two) pointers.
Head	A pointer to the first node; the only entry point into the list.
Tail	The last node; in a singly linked list its next is null.
Pointer / reference	A value holding the address of another node.
Null	A sentinel meaning "no node here" — marks the end of the list.

A null head means the list is empty. Every operation must handle the empty-list case first, because there is no node to dereference — a frequent source of run-time errors.

It is worth seeing a node for what it really is: a record (from the previous lesson) one of whose fields is a pointer to another record of the same type. This self-reference is the whole trick. In the arrays-and-records lesson a record's fields were plain values; here one field is the address of the next node, and that is what chains the records together without needing them to be contiguous. Recognising a node as "a record with a link field" makes two later topics fall out naturally: a tree node is just a record with two link fields (left and right children), and a graph is built from nodes with a list of links to neighbours. Linked lists are therefore not an isolated topic but the simplest member of a whole family of pointer-based structures, all resting on the same record-plus-pointer idea.

---

Singly Linked Lists

In a singly linked list each node points only to its successor, so traversal runs one way, head to tail.

flowchart LR
    H["Head"] --> N1["10 | next"] --> N2["20 | next"] --> N3["30 | next"] --> NUL["NULL"]

Declaring a node (OCR-style pseudocode)

record Node
    data : integer
    next : Node      // reference to the next node, or null
endrecord

head = null          // an empty list

Python implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None          # null pointer until linked

class SinglyLinkedList:
    def __init__(self):
        self.head = None          # empty list

    def is_empty(self):
        return self.head is None

    def insert_at_front(self, data):
        new_node = Node(data)
        new_node.next = self.head # 1) point new node at old head
        self.head = new_node      # 2) head now points at new node

    def traverse(self):
        current = self.head
        while current is not None: # stop at the null terminator
            print(current.data, end=" -> ")
            current = current.next # step along the chain
        print("NULL")

Notice what insert_at_front does not do: it never touches any node other than the new one and the old head, and it never copies the existing data. Compare this with inserting at the front of an array, where every existing element must shift one place right — an $O(n)$O(n) operation. The linked list pays for this convenience elsewhere (you cannot jump to the k-th node), but for workloads dominated by insertion and removal near a known point, the saving is decisive. This is the practical meaning of "dynamic": the structure restructures itself by re-pointing, not by re-copying.

The other half of "dynamic" is memory. When Node(data) runs, the program asks the heap for just enough memory for one node and receives back its address; when a node is deleted, that memory is released (automatically in Python, manually in languages like C). The list therefore occupies exactly as much memory as it currently holds — there is no pre-allocated capacity sitting empty, and no fixed ceiling on growth other than the total free heap. An array, by contrast, must reserve its whole capacity up front, wasting space if under-filled and requiring an $O(n)$O(n) allocate-and-copy to grow once full. Linked lists are the standard worked example of why dynamic memory allocation and pointers exist in the first place, which is why this topic threads straight into systems software.

---

Doubly Linked Lists

In a doubly linked list each node carries two pointers — next and prev — so the chain can be walked in either direction. This is the structure behind real features such as a browser's back/forward history and a music player's previous/next controls, where you genuinely need to move both ways through the sequence; a singly linked list could only ever go forward.

flowchart LR
    NUL1["NULL"] <--> N1["prev | 10 | next"] <--> N2["prev | 20 | next"] <--> N3["prev | 30 | next"] <--> NUL2["NULL"]

class DoublyNode:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_front(self, data):
        new_node = DoublyNode(data)
        new_node.next = self.head
        if self.head is not None:
            self.head.prev = new_node   # old head's prev now points back
        self.head = new_node

The second pointer is not free: every node now costs an extra reference of memory, and every insertion/deletion must keep both directions consistent. You buy backward traversal and $O(1)$O(1) deletion given a node (no need to re-find the predecessor) at the price of more memory and more pointer book-keeping. That is the central doubly-vs-singly trade-off examiners look for.

The "$O(1)$O(1) deletion given a node" advantage deserves unpacking, because it is the subtle reason doubly linked lists exist. In a singly linked list, even if a program already holds a reference to the exact node it wants to delete, it still cannot remove it efficiently: deletion requires editing the predecessor's next pointer, and from the target node alone there is no way back to its predecessor — you must restart from the head and walk $O(n)$O(n) to find it. A doubly linked list closes this gap: because each node knows its prev, the predecessor is one hop away, so the splice (node.prev.next = node.next; node.next.prev = node.prev) is $O(1)$O(1). Whenever a design needs to delete arbitrary, already-located nodes cheaply — a least-recently-used cache, for instance, evicting a node it is already pointing at — the doubly linked list earns its extra pointer. When you only ever process the list front-to-back, the singly linked list is leaner and is the right default.

---

Traced Operations

OCR routinely asks you to trace pointer surgery on a diagram or in a table. The discipline is always the same: re-link new pointers before destroying old ones, or you will lose the rest of the list.

Insert at front — $O(1)$O(1)

No traversal is needed: splice the new node in at the head.

flowchart TB
    subgraph Before
      HB["Head"] --> B10["10 | next"] --> B20["20 | next"] --> BNUL["NULL"]
    end
    subgraph After
      HA["Head"] --> A5["5 | next"] --> A10["10 | next"] --> A20["20 | next"] --> ANUL["NULL"]
    end

Step	Action	Effect
1	new.next = head	new node points at the old first node (10)
2	head = new	head now points at the new node (5)

Two pointer writes, independent of length, so insert-at-front is $O(1)$O(1). This is exactly why a stack built on a linked list pushes in constant time.

Insert at end — $O(n)$O(n)

def insert_at_end(self, data):
    new_node = Node(data)
    if self.head is None:           # empty-list case
        self.head = new_node
        return
    current = self.head
    while current.next is not None:  # walk to the last node
        current = current.next
    current.next = new_node          # link it on

You must walk all $n$n nodes to find the tail, so it is $O(n)$O(n) — unless you maintain a separate tail pointer, which makes it $O(1)$O(1) (the trick a queue uses).

Insert at a position — $O(n)$O(n)

To insert after the k-th node, walk to that node, then perform the same two-pointer splice as at the front — but in the middle of the chain.

def insert_at_position(self, data, position):
    if position == 0:
        self.insert_at_front(data)
        return
    new_node = Node(data)
    current = self.head
    for i in range(position - 1):    # walk to the node before the gap
        if current is None:
            raise IndexError("position out of range")
        current = current.next
    new_node.next = current.next     # 1) new node points at the rest
    current.next = new_node          # 2) predecessor points at new node

Trace: insert 15 at position 1 into 10 -> 20 -> 30 (i.e. after node 10).

Step	Action	List
walk	current stops at node 10	10 -> 20 -> 30
1	new.next = current.next (node 20)	new(15) -> 20 ...
2	current.next = new	10 -> 15 -> 20 -> 30

Again the splice is $O(1)$O(1), but the walk to position $k$k is $O(k)$O(k), so an arbitrary-position insertion is $O(n)$O(n) overall. The lesson that recurs across every linked-list operation is this: re-linking is cheap; reaching the place to re-link is what costs. That single sentence explains why front operations are $O(1)$O(1) while positional and end operations are $O(n)$O(n), and it is exactly the reasoning examiners want to see attached to a complexity claim.

Delete by value — $O(n)$O(n)

In a singly linked list you must reach the node before the target so you can re-route its next past the doomed node.

def delete(self, value):
    if self.head is None:
        return                       # empty: nothing to do
    if self.head.data == value:      # deleting the head is special
        self.head = self.head.next
        return
    current = self.head
    while current.next is not None:
        if current.next.data == value:
            current.next = current.next.next   # bypass the target
            return
        current = current.next

Trace: delete 20 from 10 -> 20 -> 30.

current	current.next.data	Action
node 10	20	match — set node10.next = node30
—	—	list is now 10 -> 30; node 20 is unlinked

The search for the predecessor is $O(n)$O(n); the relink itself is $O(1)$O(1). In a doubly linked list, if you already hold the node, you can delete it in $O(1)$O(1) because prev gives the predecessor directly.

Search — $O(n)$O(n)

def search(self, value):
    current = self.head
    position = 0
    while current is not None:
        if current.data == value:
            return position
        current = current.next
        position += 1
    return -1                        # not found

There is no random access, so even a sorted linked list cannot use binary search — you cannot jump to the middle in $O(1)$O(1). Searching a linked list is therefore always $O(n)$O(n), a key contrast with a sorted array's $O(\log n)$O(logn).

This deserves emphasis because it is a favourite "explain why" question. Binary search works by repeatedly inspecting the middle element of the remaining range and discarding half. To find the middle of a sorted array you compute one index, $(\text{low} + \text{high}) \div 2$(low+high)÷2, and jump there in $O(1)$O(1) — so each step halves the problem and the whole search is $O(\log n)$O(logn). To find the middle of a sorted linked list you would have to count from the head, following $n/2$n/2 pointers, which is already $O(n)$O(n) — and you would pay that on every halving step. The algorithm's whole advantage evaporates. The deeper point, and a strong evaluation mark, is that an algorithm's efficiency is not a property of the algorithm alone but of the algorithm paired with the data structure it runs on: binary search is $O(\log n)$O(logn) on an array and effectively useless on a linked list. The derivation of binary search itself belongs to the algorithms course; here it is enough to know which structures admit it and why.

Traverse — $O(n)$O(n)

Visiting every node, head to tail, is inherently $O(n)$O(n) — the loop in traverse above runs once per node, doing constant work each time, so the cost is directly proportional to the list length.

---

Circular Linked Lists

In a circular linked list the tail's pointer returns to the head rather than to null, so there is no end — traversal must stop on a count or on returning to the start.

flowchart LR
    H["Head"] --> N10["10 | next"] --> N20["20 | next"] --> N30["30 | next"]
    N30 -- "wraps back to head" --> H

This shape is ideal for anything cyclic: round-robin CPU scheduling (cycle endlessly through ready processes) and circular buffers (a fixed ring reused over and over). It links directly to the circular-queue idea in the next lesson.