Linked Lists

This lesson covers linked lists — the archetypal dynamic data structure, in which elements live in separate nodes joined by pointers rather than in one contiguous block. Linked lists are a core A-Level topic in their own right and the conceptual foundation for trees, graphs, and the linked implementations of stacks, queues, and hash-table chains. The skill the examiner most wants to see is tracing how pointers change during insertion and deletion.

Spec Mapping

This lesson addresses AQA A-Level Computer Science (7517), section 4.2.6 (Lists / linked lists). It covers the node-and-pointer model, the head pointer and null terminator, the singly, doubly, and circular variants, the standard operations (traverse, search, insert, delete) with their complexities, and the comparison against arrays from §4.2.1. The same node-with-pointer idea recurs in §4.2.5 (trees) and the graphs topic. Wording below is original and does not reproduce AQA specification text.

---

What is a Linked List?

A linked list is a dynamic data structure consisting of a sequence of nodes. Each node contains:

1. Data — the value stored in the node.
2. A pointer (next) — a reference holding the address of the following node.

The list is reached through a single external head pointer that holds the address of the first node. The final node's next pointer is set to null (None in Python), marking the end of the list. Crucially, the nodes need not be adjacent in memory — each is allocated separately on the heap, and the next pointers thread them together.

flowchart LR
    H["HEAD"] --> N1["data: ? | next"] --> N2["data: ? | next"] --> N3["data: ? | next"] --> NUL["null"]

Example

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

This linked list stores the values 10, 20, and 30. To reach the value 30 you must start at HEAD and follow two next pointers — there is no index arithmetic and therefore no random access.

---

Types of Linked Lists

Type	Description
Singly linked list	Each node holds one pointer, to the next node. Traversal is one-directional.
Doubly linked list	Each node holds two pointers, to the next and previous nodes. Traversal is bidirectional.
Circular linked list	The last node's next points back to the first node, forming a loop with no null terminator.

Singly Linked List

flowchart LR
    H["HEAD"] --> A["A | next"] --> B["B | next"] --> C["C | next"] --> NUL["null"]

Doubly Linked List

A doubly linked list adds a prev pointer to every node, so you can walk backwards as well as forwards. This makes deleting a known node $O(1)$O(1) (you already have its predecessor via prev), at the cost of an extra pointer per node.

flowchart LR
    NUL1["null"] <--> A["prev | A | next"] <--> B["prev | B | next"] <--> C["prev | C | next"] <--> NUL2["null"]

Circular Linked List

In a circular list the tail links back to the head, which is convenient for round-robin scheduling and ring buffers because traversal never hits a null end.

flowchart LR
    H["HEAD"] --> A["A | next"] --> B["B | next"] --> C["C | next"]
    C -- "loops back" --> A

---

Implementing a Singly Linked List

Node Class

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None   # pointer to the next node; None marks the end

Linked List Class

class LinkedList:
    def __init__(self):
        self.head = None   # empty list: head points to nothing

    def is_empty(self) -> bool:
        return self.head is None

    def add_to_front(self, data):          # O(1)
        new_node = Node(data)
        new_node.next = self.head          # 1) new node points to old first
        self.head = new_node               # 2) head points to new node

    def add_to_end(self, data):            # O(n)
        new_node = Node(data)
        if self.head is None:
            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

    def display(self):
        current = self.head
        while current is not None:
            print(current.data, end=" -> ")
            current = current.next
        print("null")

    def search(self, target) -> bool:      # O(n)
        current = self.head
        while current is not None:
            if current.data == target:
                return True
            current = current.next
        return False

    def delete(self, target):              # O(n)
        if self.head is None:
            return
        if self.head.data == target:       # deleting the head is a special case
            self.head = self.head.next
            return
        current = self.head
        while current.next is not None:
            if current.next.data == target:
                current.next = current.next.next   # bypass the target node
                return
            current = current.next

---

Building a List Step by Step

Watching the head pointer evolve makes the structure concrete. Starting from an empty list and calling add_to_end with 10, then 20, then 30:

Call	Head points to	Full chain
(start)	null	(empty)
add_to_end(10)	node(10)	10 → null
add_to_end(20)	node(10)	10 → 20 → null
add_to_end(30)	node(10)	10 → 20 → 30 → null

Crucially, after the first insertion the head pointer never changes for end-insertions — each new node is attached by walking to the current last node and updating its next. This is why add_to_end is $O(n)$O(n): the walk lengthens as the list grows. Contrast it with add_to_front, where the head pointer does change every time but no walk is needed, giving $O(1)$O(1). Many implementations therefore also keep a separate tail pointer so that end-insertion becomes $O(1)$O(1) too — a small space cost for a large speed gain in queue-like usage.

---

Operations and Time Complexity

Operation	Description	Time complexity
Add to front	Re-link the head pointer	$O(1)$O(1)
Add to end	Traverse to the last node, then link	$O(n)$O(n)
Search	Traverse from head until found or null	$O(n)$O(n)
Delete	Find the predecessor, then re-link	$O(n)$O(n)
Access by index	Follow $k$k pointers from the head	$O(n)$O(n)

Exam Tip: Linked lists do not support random access. To reach the $k$kth element you must start at the head and follow $k$k pointers — that is $O(n)$O(n), unlike an array's $O(1)$O(1) index access. Stating this contrast earns marks in comparison questions.

---

Traversing and Searching — Traced

Traversal is the engine of almost every linked-list operation: you start at the head and repeatedly follow next until you reach null. Searching for 30 in HEAD -> 10 -> 20 -> 30 -> null proceeds as follows, where current is the pointer being examined:

Step	current points to	current.data	== 30?	Next action
1	node(10)	10	no	current = current.next
2	node(20)	20	no	current = current.next
3	node(30)	30	yes	return True

Three pointer dereferences were needed for a three-node list. In the worst case (target absent, or in the last node) all $n$n nodes are visited, so search is $O(n)$O(n) — the same asymptotic cost as a linear search of an array, but without the option of binary search, because a linked list cannot jump to its middle in $O(1)$O(1). The loop terminates when current becomes null, which is why the null terminator is essential: it is the signal that the list has ended.

FUNCTION search(head, target) RETURNS BOOLEAN
    current = head
    WHILE current != NULL
        IF current.data = target THEN
            RETURN TRUE
        ENDIF
        current = current.next      // advance the pointer
    ENDWHILE
    RETURN FALSE                    // reached the end without a match
ENDFUNCTION

---

Inserting a Node — Traced

Adding to the Front — O(1)

Insert 10 at the front of a list HEAD -> 20 -> 30 -> null. Only two pointer assignments are needed, regardless of list length:

1. Create the new node holding 10.
2. Set the new node's next to the current head (the node holding 20).
3. Set HEAD to the new node.

Step	HEAD points to	New node's next
Before	node(20)	—
After step 2	node(20)	node(20)
After step 3	node(10)	node(20)

flowchart TB
    subgraph Before
      HB["HEAD"] --> B20["20 | next"] --> B30["30 | next"] --> BNUL["null"]
    end
    subgraph After
      HA["HEAD"] --> A10["10 | next"] --> A20["20 | next"] --> A30["30 | next"] --> ANUL["null"]
    end

Adding After a Given Node — O(n) to find, O(1) to link

Insert 20 between 10 and 30 in HEAD -> 10 -> 30 -> null. The order of the two pointer assignments matters: link the new node forward before re-linking the predecessor, or you lose the rest of the list.

1. Create the new node holding 20.
2. Set the new node's next to node(30) — the node currently after node(10).
3. Set node(10)'s next to the new node.

flowchart TB
    subgraph Before
      HB["HEAD"] --> B10["10 | next"] --> B30["30 | next"] --> BNUL["null"]
    end
    subgraph After
      HA["HEAD"] --> A10["10 | next"] --> A20["20 | next"] --> A30["30 | next"] --> ANUL["null"]
    end

---

Deleting a Node — Traced

Delete 20 from HEAD -> 10 -> 20 -> 30 -> null:

1. Traverse to find the node before the target — here node(10), whose next is node(20).
2. Set node(10)'s next to node(30), bypassing node(20).
3. node(20) is now unreachable; in a garbage-collected language its memory is reclaimed automatically.

Step	node(10)'s next	Reachable list
Before	node(20)	10, 20, 30
After re-link	node(30)	10, 30

flowchart TB
    subgraph Before
      HB["HEAD"] --> B10["10 | next"] --> B20["20 | next"] --> B30["30 | next"] --> BNUL["null"]
    end
    subgraph After
      HA["HEAD"] --> A10["10 | next"] --> A30["30 | next"] --> ANUL["null"]
    end

Pseudocode for Deletion

PROCEDURE delete(head, target)
    IF head = NULL THEN
        RETURN
    ENDIF
    IF head.data = target THEN
        head = head.next            // deleting the first node
        RETURN
    ENDIF
    current = head
    WHILE current.next != NULL
        IF current.next.data = target THEN
            current.next = current.next.next   // bypass the target
            RETURN
        ENDIF
        current = current.next
    ENDWHILE
ENDPROCEDURE

---

Doubly Linked Lists in Depth

A doubly linked list gives each node a second pointer, prev, referencing the node before it. This costs one extra pointer per node but buys two abilities a singly linked list lacks: backward traversal and $O(1)$O(1) deletion of a node you already hold a reference to (because its predecessor is reachable through prev, with no traversal needed).

class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None    # pointer to previous node
        self.next = None    # pointer to next node

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

    def add_to_front(self, data):
        node = DNode(data)
        node.next = self.head
        if self.head is not None:
            self.head.prev = node      # old first node now points back
        self.head = node

    def delete_node(self, node):       # O(1) given the node itself
        if node.prev is not None:
            node.prev.next = node.next
        else:
            self.head = node.next      # node was the head
        if node.next is not None:
            node.next.prev = node.prev

Traced Example: Deleting a Middle Node in a Doubly Linked List

To delete node B from null <-> A <-> B <-> C <-> null, two pointers are re-wired, with no traversal because B already knows both neighbours:

Step	Pointer change	Effect
1	B.prev.next = B.next	A's next now skips to C
2	B.next.prev = B.prev	C's prev now skips back to A
Result	—	null <-> A <-> C <-> null; B is unreferenced and reclaimed

This $O(1)$O(1) deletion (given the node) is exactly why doubly linked lists back structures such as LRU caches and the navigation history of editors, where items must be unlinked quickly from the middle. The trade-off, as ever, is the extra prev pointer's memory and the need to maintain two pointers correctly on every insertion and deletion — double the opportunity for a bug.

---

Circular Linked Lists in Depth

A circular linked list removes the null terminator: the last node's next points back to the first. Traversal must therefore stop by a different rule — usually "stop when you return to the starting node" — rather than "stop at null". Circular lists suit any naturally cyclic problem: round-robin CPU scheduling (cycle endlessly through the ready processes), the players in a turn-based game, or a music player's repeat-all mode.

// Traverse a circular list exactly once, starting at head
PROCEDURE traverseCircular(head)
    IF head = NULL THEN RETURN ENDIF
    current = head
    REPEAT
        OUTPUT current.data
        current = current.next
    UNTIL current = head          // stop on return to the start
ENDPROCEDURE

A subtle danger is that a naive "while not null" loop never terminates on a circular list, because the end is never null — a common source of infinite loops in exam answers.

---

Linked Lists vs Arrays

Feature	Array	Linked list
Size	Fixed (static)	Dynamic (grows/shrinks)
Memory layout	Contiguous	Scattered (nodes on heap)
Access time	$O(1)$O(1) random access	$O(n)$O(n) sequential access
Insertion at front	$O(n)$O(n) — shift all elements	$O(1)$O(1) — re-link head
Insertion at end	$O(1)$O(1) if space available	$O(n)$O(n) — traverse to end
Deletion	$O(n)$O(n) — shift elements	$O(n)$O(n) to find, $O(1)$O(1) to re-link
Memory overhead	None	One (or two) pointers per node
Cache performance	Good (contiguous)	Poorer (scattered)