Linked lists
Computer ScienceΒ· Unit 10: Data types & structuresΒ· 15 min read
1. Structure of a Linked Listβ β ββββ± 4 min
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.
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.
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
nullto mark the end of the list - 5
Set the head pointer to point to Node 1, the first node in the sequence
2. Common Linked List Operationsβ β β βββ± 6 min
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
nullSearch: 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
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.nextto point to the new node - 5
The new list is now
[10, 15, 20, 30]
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.
3. Linked Lists vs Static Arraysβ β β βββ± 5 min
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.
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
4. Time Complexity of Operationsβ β β β ββ± 3 min
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
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
Exam tip:
Always specify if the complexity is worst or average case, and explain your reasoning to get full marks.
5. Common Pitfalls
Wrong move:
Updating the existing node's next pointer before setting the new node's next
Why:
This loses the reference to the rest of the list, breaking the entire data structure
Correct move:
Always set the new node's next pointer first, then update the existing node's next pointer
Wrong move:
Forgetting to update the head pointer when inserting or deleting the first node
Why:
The head pointer is the only entry point to the list, so it must be updated when modifying the first node
Correct move:
Always check if the operation affects the head node first, and update the head pointer if required
Wrong move:
Claiming linked list insertion is always O(1)
Why:
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 move:
State that insertion is O(1) only at the head (or tail with a tail pointer), O(n) for arbitrary positions
Wrong move:
Leaving the previous node's next pointer pointing to a deleted node
Why:
This creates a dangling pointer and leaves the deleted node still reachable, breaking the list structure
Correct move:
Always update the previous node's next pointer to point to the deleted node's next before removing the node
Wrong move:
Assuming linked list nodes are stored in contiguous memory
Why:
This leads to incorrect assumptions that random access is possible like in arrays
Correct move:
Remember nodes can be stored anywhere in memory, you can only access nodes by traversing from the head via pointers
6. Quick Reference 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 |
7. Frequently Asked
Do I need to learn doubly linked lists for the exam?
You need to understand their structure and differences from singly linked lists, but most implementation questions focus on singly linked lists.
Can I use pseudocode for linked list questions?
Yes, CIE accepts standard syllabus pseudocode as long as your pointer logic is clear and complete.
When this came up on past exams
AI-estimated based on syllabus patterns β cross-check with official past papers for accuracy. Use only as revision-focus signals.
- 2022 Β· 1
Linked list insertion operation
- 2023 Β· 2
Implement linked list deletion
- 2024 Β· 1
Compare arrays and linked lists
Going deeper
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.