Loading…
Free A-Level Computer Science guide
Extend the existing node-and-traversal resource with complete modification algorithms. Trace references in their actual assignment order, then test the edge cases that can break the chain.
Content owner: Michael Print · Written for A-Level learners · Checked against official specifications
A singly linked list keeps a head reference and a next reference in each node. Traversal follows those references until None. Insertion connects the new node to the successor before redirecting the predecessor; deletion redirects the predecessor around the removed node.
The head needs separate treatment because it has no predecessor. An empty list has head None, and deleting its only node must restore that empty state. The code below specifies that searches and value-based modifications use the first matching value.
OCR H446 · 1.4.2(b–c), 2.3.1(e): singly linked-list operations
Useful foundations
By the end, you should be able to
head → 4 → 6 → 8 → None contains separate Node objects. References link them; they are not array indexes and need not occupy adjacent memory.
Traversal copies head into a local reference, then follows next without changing head. The constructor works backwards through input values and prepends them, preserving input order in O(n) time.
An array-of-records version could store next indexes and manage a free list. That is a different storage implementation of the same chain.
Preserve the old successor before overwriting its link. Otherwise the remainder of the chain may become unreachable.
Prepending builds a node pointing to the old head, then replaces head. Empty lists work because that old head is None.
Appending traverses to a node whose next is None, then connects the new tail. For an empty list, set head instead.
Before
head → 4 → 6 → 8 → None. Create a new node containing 5.
Preserve the successor
Set new.next to the existing node containing 6. The old chain is still reachable.
Redirect the predecessor
Set 4.next to the new node containing 5.
After
head → 4 → 5 → 6 → 8 → None.
Keep current for the inspected node and previous for its predecessor. previous is None at the head. Check current exists before reading current.value.
After reconnecting, clear the removed node’s next to show it is detached. Another reference may still keep that object alive, so detaching alone does not guarantee memory release.
If search reaches None, return False without changing the list. Traversal, search and locating a target can take O(n); relinking a known predecessor takes O(1).
insert_after by value remains O(n) because it searches first. Prepend is O(1); append is O(n) here because no tail reference is stored. Each node stores a value and next reference.
previous.next = current.next, bypassing current.head = current.next. No predecessor exists.Worked example
| Line | Output |
|---|---|
| 1 | [4, 6, 8] |
| 2 | [3, 5, 6, 8, 9] |
| 3 | 8 False |
| 4 | True [] |
| 5 | False |
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
class LinkedList:
def __init__(self, values):
self.head = None
for value in reversed(values):
self.prepend(value)
def values(self):
result = []
current = self.head
while current is not None:
result.append(current.value)
current = current.next
return result
def find(self, value):
current = self.head
while current is not None:
if current.value == value:
return current
current = current.next
return None
def prepend(self, value):
self.head = Node(value, self.head)
def append(self, value):
if self.head is None:
self.prepend(value)
return
current = self.head
while current.next is not None:
current = current.next
current.next = Node(value)
def insert_after(self, target, value):
predecessor = self.find(target)
if predecessor is None:
return False
predecessor.next = Node(value, predecessor.next)
return True
def remove_first(self, value):
previous = None
current = self.head
while current is not None:
if current.value == value:
if previous is None:
self.head = current.next
else:
previous.next = current.next
current.next = None
return True
previous = current
current = current.next
return False
chain = LinkedList([4, 6, 8])
print(chain.values())
chain.insert_after(4, 5)
chain.prepend(3)
chain.append(9)
chain.remove_first(4)
print(chain.values())
print(chain.find(8).value, chain.remove_first(99))
single = LinkedList([7])
print(single.remove_first(7), single.values())
print(single.remove_first(7))Worked example
5 original questions total 22 marks. Attempt each before opening the independently written indicative marking guidance.
A list is head → 2 → 7 → 10 → None. Describe the reference updates, in order, to insert 5 after 2. Explain why that order matters.
Indicative answer
Trace remove_first(7) on [7]. Give previous, current.next, the resulting head and the returned value.
Indicative answer
Run remove_first(5) conceptually on [3, 5, 5, 8]. Give the resulting values and explain how the contract determines the answer. Then state the result of remove_first(99).
Indicative answer
A programmer removes a node by assigning current = current.next and returns True. Explain why this fails and show the required alternatives for a head and a non-head node.
Indicative answer
Compare the worst-case time for prepend, find and this implementation's append. Explain why insert_after by value cannot generally be described as O(1).
Indicative answer
This guide addresses OCR H446 1.4.2(b–c), 2.3.1(e): singly linked-list operations. Check your examination year and the complete specification for the assessment scope.
These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.
Found an error? Email a correction.
Use the free examples first, then explore one-to-one tuition if guided practice would help.