# Linked lists

> Computer Science · CIE A-Level 9618
> Source: https://www.owlsprep.com/study/cie-9618-u10-linked-lists/

This module covers the structure, common operations, advantages/disadvantages, and time complexity of linked lists, a core dynamic linear data structure frequently tested in both CIE A-Level Computer Science papers.

**Prerequisites:** [Arrays and static data structures](https://www.owlsprep.com/study/cie-9618-u10-arrays/); [Pointers and memory addressing](https://www.owlsprep.com/study/cie-9618-u04-memory-management/)

## Learning objectives

- Describe the structure of singly and doubly linked lists
- Implement common operations (insert, delete, traverse) on linked lists
- Compare performance of linked lists with static arrays
- Explain advantages and disadvantages of linked lists for different use cases
- State the time complexity of common linked list operations

## Structure of a Linked List

A linked list is a dynamic linear data structure where each element (called a **node**) contains both data and a pointer to the next node in the sequence. Unlike arrays, nodes are not stored in contiguous memory locations, so the size of the list can grow or shrink dynamically at runtime.

**Node** — The fundamental unit of a linked list, storing the data value and a reference (pointer) to the next node in the list.

*Notation:* Node { data, next_pointer }

*Example:* A node storing an integer `42` will have `data = 42` and `next` pointing to the next node, or `null` if it is the last node.

> **info**
>
> A singly linked list only has pointers to the next node, so you can only traverse forward. A doubly linked list has both next and previous pointers for bidirectional traversal, but uses extra memory for the additional pointer.

**Worked example:** Draw and describe the structure of a singly linked list containing values `[10, 20, 30]` with a head pointer.

1. Create three separate nodes, each storing their respective data value: Node 1 = 10, Node 2 = 20, Node 3 = 30
2. Set the next pointer of Node 1 to point to Node 2
3. Set the next pointer of Node 2 to point to Node 3
4. Set the next pointer of Node 3 to `null` to mark the end of the list
5. Set the head pointer to point to Node 1, the first node in the sequence

## Common Linked List Operations

The four core operations for linked lists are traverse, search, insert, and delete. Each operation follows pointer manipulation rules to maintain the structure of the list.

- **Traversal**: Start at the head, move from node to node via next pointers until you reach `null`
- **Search**: Traverse the list to find a node with the target data value
- **Insertion**: Add a new node at the start, middle, or end of the list
- **Deletion**: Remove an existing node from any position in the list

**Worked example:** Insert a new node with value 15 after the node containing 10 in the list `[10, 20, 30]`.

1. Create a new node and set its data value to 15
2. Traverse from head to find the node with data 10, call this `current`
3. Set the new node's next pointer equal to `current.next` (this saves the reference to 20)
4. Update `current.next` to point to the new node
5. The new list is now `[10, 15, 20, 30]`

**Worked example:** Delete the node with value 20 from the list `[10, 20, 30]`.

1. Start at head, traverse the list while tracking both current and previous nodes
2. Stop traversal when the current node's data equals 20; previous node is 10 here
3. Set the previous node's next pointer equal to current node's next pointer (which points to 30)
4. Remove the current node from memory to avoid memory leaks
5. The updated list is now `[10, 30]`

> **Exam tip:** Always update the new node's pointer before changing the existing node's pointer. This avoids losing the reference to the rest of the list.

## Linked Lists vs Static Arrays

Linked lists and arrays are both linear data structures, but have very different performance characteristics for common operations. The table below summarises key differences:

| Operation | Linked List | Static Array |
| --- | --- | --- |
| Random Access | O(n) | O(1) |
| Insert/Delete at start | O(1) | O(n) |
| Insert/Delete at middle | O(n) | O(n) |
| Maximum Size | Dynamic, no fixed limit | Fixed at allocation |
| Memory Overhead | Extra space for pointers | No extra overhead |

Linked lists are preferred when frequent insertions/deletions are required and the size of the collection is unknown in advance. Arrays are better when random access to elements is a core requirement.

**Worked example:** Explain why a linked list is preferred over a static array for implementing a dynamic queue.

1. A queue requires two core operations: add to the end, and remove from the front
2. For a static array, removing from the front requires shifting all elements, which is O(n) time, and the array can run out of space
3. A linked list with head and tail pointers allows O(1) time for both add to end and remove from front, and grows dynamically as needed
4. Therefore, a linked list is a more efficient choice for a dynamic queue

## Time Complexity of Operations

CIE 9618 regularly asks you to state and explain the time complexity of common linked list operations. Time complexity describes how operation time scales with the number of nodes `n` in the list.

- Traversal / Search: O(n) worst case
- Insert / Delete at head: O(1) always
- Insert / Delete at tail: O(1) with tail pointer, O(n) without
- Insert / Delete in middle: O(n) worst case

**Worked example:** What is the worst case time complexity of searching for a value in an unsorted singly linked list? Explain your answer.

1. In the worst case, the target value is not present in the list, or is stored as the last node
2. To find the target, you must start at the head and traverse every node in the list until you reach the null end pointer
3. The number of nodes visited equals `n`, the total number of elements in the list
4. Therefore, the worst case time complexity is $O(n)$

> **Exam tip:** Always specify if the complexity is worst or average case, and explain your reasoning to get full marks.

## Common pitfalls

- **Wrong:** Updating the existing node's next pointer before setting the new node's next
  - Why it fails: This loses the reference to the rest of the list, breaking the entire data structure
  - Correct: Always set the new node's next pointer first, then update the existing node's next pointer
- **Wrong:** Forgetting to update the head pointer when inserting or deleting the first node
  - Why it fails: The head pointer is the only entry point to the list, so it must be updated when modifying the first node
  - Correct: Always check if the operation affects the head node first, and update the head pointer if required
- **Wrong:** Claiming linked list insertion is always O(1)
  - Why it fails: Insertion is only O(1) if you already have a pointer to the insertion point. Finding the insertion point takes O(n) time for most positions
  - Correct: State that insertion is O(1) only at the head (or tail with a tail pointer), O(n) for arbitrary positions
- **Wrong:** Leaving the previous node's next pointer pointing to a deleted node
  - Why it fails: This creates a dangling pointer and leaves the deleted node still reachable, breaking the list structure
  - Correct: Always update the previous node's next pointer to point to the deleted node's next before removing the node
- **Wrong:** Assuming linked list nodes are stored in contiguous memory
  - Why it fails: This leads to incorrect assumptions that random access is possible like in arrays
  - Correct: Remember nodes can be stored anywhere in memory, you can only access nodes by traversing from the head via pointers

## Cheatsheet

| Property | Singly Linked List |
| --- | --- |
| Core structure | Node = data + next pointer |
| Entry point | Head pointer points to first node |
| Traversal direction | Forward only |
| Random access | Not supported, O(n) |
| Insert at head | O(1) |
| Delete at head | O(1) |
| Insert/delete at middle | O(n) |
| Search for value | O(n) |
| Size | Dynamic, no fixed limit |
| Key advantage | Fast insert/delete, dynamic size |
| Key disadvantage | Extra memory for pointers, no random access |

## What's next

Linked lists are a foundational dynamic data structure that form the basis for more complex data structures like stacks, queues, graphs, and hash tables, all of which are tested in CIE 9618. Understanding pointer manipulation for linked lists also prepares you for more advanced topics like tree and graph traversal in later units. Frequent exam questions ask you to compare linked lists with other dynamic structures like arrays, and to write pseudocode for common insert and delete operations.

- [Stacks](https://www.owlsprep.com/study/cie-9618-u10-stacks/)
- [Queues](https://www.owlsprep.com/study/cie-9618-u10-queues/)
- [Trees](https://www.owlsprep.com/study/cie-9618-u10-trees/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u10-linked-lists/