The big idea: Two things make a linked list: a Node that holds a value and a reference, and a head reference that points at the first node.
Lose the head: Lose the head and the whole list is unreachable. Nothing else points at the first node.
class Node:
def __init__(self, value):
self.value = value
self.next = None # nothing after it yet
head = Node("A")
head.next = Node("B")
head.next.next = Node("C")
# head -> A -> B -> C -> Noneclass Node {
String value;
Node next; // nothing after it yet
Node(String value) {
this.value = value;
this.next = null;
}
}
Node head = new Node("A");
head.next = new Node("B");
head.next.next = new Node("C");
// head -> A -> B -> C -> nullNone marks the end: The last node's next is None. That is the only thing distinguishing the end of the list from the middle of it — which is why every traversal tests for it.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
Traverse
Start at the head, do the work, move on. Stop when the reference runs out — when it is None.
Insert at the front
The cheapest operation there is — no traversal at all. Point the new node forwards first, then move the head onto it.
Insert after a node
Point the new node at prev's successor first, then repoint prev. Doing those two in the other order loses every node after prev.
Delete
Nothing is erased — the node is simply routed around. Once nothing references the target, it is unreachable.
# 1. Traverse
current = head
while current is not None:
print(current.value)
current = current.next
# 2. Insert at the front
new_node = Node("Z")
new_node.next = head # point at the old first
head = new_node # the new node IS the head
# 3. Insert after a node
new_node.next = prev.next # point forwards FIRST
prev.next = new_node # then repoint prev
# 4. Delete — route around the target
prev.next = target.nextTraverse
Start at the head, do the work, move on. Stop when the reference runs out — when it is null.
Insert at the front
The cheapest operation there is — no traversal at all. Point the new node forwards first, then move the head onto it.
Insert after a node
Point the new node at prev's successor first, then repoint prev. Doing those two in the other order loses every node after prev.
Delete
Nothing is erased — the node is simply routed around. Once nothing references the target, it is unreachable.
// 1. Traverse
Node current = head;
while (current != null) {
System.out.println(current.value);
current = current.next;
}
// 2. Insert at the front
Node newNode = new Node("Z");
newNode.next = head; // point at the old first
head = newNode; // the new node IS the head
// 3. Insert after a node
newNode.next = prev.next; // point forwards FIRST
prev.next = newNode; // then repoint prev
// 4. Delete — route around the target
prev.next = target.next;Deleting the first node is the special case: There is no prev for the head. Deleting it means moving the head itself — head ← head.next.
An answer that handles only the middle case is incomplete, and this is the case examiners choose.
Feeling unprepared for exams?
Get a clear study plan, practice with real questions, and know exactly where you stand before exam day. No more guessing.
| Doubly linked | Circular | |
|---|---|---|
| Node holds | value, next, prev | value, next |
| End of list | next is None | next points at the head |
| Traversal stops when | current is None | current is back at the head |
| Insertion updates | Four references | Two |
| Deleting needs | Only the node itself | The node before it |
| Doubly linked | Circular | |
|---|---|---|
| Node holds | value, next, prev | value, next |
| End of list | next is null | next points at the head |
| Traversal stops when | current is null | current is back at the head |
| Insertion updates | Four references | Two |
| Deleting needs | Only the node itself | The node before it |
Four references, not two: Inserting into a doubly linked list updates the new node's next AND prev, the previous node's next, and the following node's prev.
Miss one and traversal works in one direction and breaks in the other — a bug that hides until something walks backwards.
A circular list never reaches None — the last node points back at the head — so the loop needs a different stop test:
current = head
while True:
print(current.value)
current = current.next
if current is head:
breakCircular traversal: The stop test is identity with the head, not None. Say that explicitly.
A circular list never reaches null — the last node points back at the head — so the loop needs a different stop test:
Node current = head;
while (true) {
System.out.println(current.value);
current = current.next;
if (current == head) {
break;
}
}Circular traversal: The stop test is identity with the head, not null. Say that explicitly.
How this is tested — you must write or trace the reference assignments in the right ORDER, and handle the head as a special case. It comes up two ways:
Paper 2 — working with code
- Construct code for an operation, 4-6 marks
- Trace what a list looks like after operations
- Sketch the list as boxes and arrows
Paper 2 — the algorithmic-thinking question
- Explain why an order of assignment matters
- Identify the case an implementation fails on
The classic trap: Assigning prev.next ← new before new.next ← prev.next. The first assignment overwrites the only reference to the rest of the list, and everything after it is lost.
Write a Python function that deletes the first node whose value equals a target from a singly linked list, handling the case where it is the head.
Model answer plan
See the answer broken into clear points, with guidance on how each point earns marks.