Singly linked lists
Construct and trace insertion, deletion, traversal and search using explicit Node references in Python.
Follow the reference, not an index
- sketch and interpret a singly linked list;
- construct Python node/list code without using a built-in Python list as the linked structure;
- apply insertion, deletion, traversal and search;
- trace reference changes without losing nodes.
Rapid Recall Deck
Attempt each card first. If a term is new, flip and study it, then answer it again without looking. Mark only secure recall as “Know it”.
Create a singly linked structure explicitly
class Node:
def __init__(self, value):
self.value = value
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = NoneBuild three nodes manually
Construct statements that produce head → 10 → 20 → 30 → None.
a = Node(10) b = Node(20) c = Node(30) a.next = b b.next = c linked = SinglyLinkedList() linked.head = a
Trace the references
After the structure is built, what does linked.head.next.next.value evaluate to? Explain the path.
It evaluates to 30: head refers to node 10, the first next reaches node 20, the second next reaches node 30, then value returns 30.
Insert at the front without losing the chain
def add_front(self, value):
new_node = Node(value)
new_node.next = self.head
self.head = new_nodeExplain the update order
Why must new_node.next = self.head happen before self.head = new_node?
The new node first needs a reference to the existing first node. If head were overwritten first, the code would no longer have the old head reference available through self.head, risking loss of the existing chain.
new → old_head, then move head to new.Repeatedly follow next until the structure ends
def values(self):
current = self.head
output = []
while current is not None:
output.append(current.value)
current = current.next
return outputTrace traversal
For head → 4 → 9 → 12 → None, record the value of current.value on each loop iteration and the final output.
The visited values are 4, then 9, then 12. The final list returned is [4, 9, 12].
Construct search
Construct a method contains(target) that returns True if a node stores target, otherwise False. Do not convert the linked list to a Python list.
def contains(self, target):
current = self.head
while current is not None:
if current.value == target:
return True
current = current.next
return FalseMove the head reference safely
Delete the first node
Construct remove_front(). If the list is empty, return None. Otherwise remove the first node and return its value.
def remove_front(self):
if self.head is None:
return None
removed = self.head
self.head = self.head.next
return removed.valueTrace deletion
Starting with head → 7 → 8 → 9 → None, what remains after two calls to remove_front(), and what two values are returned?
The calls return 7 and then 8. The remaining structure is head → 9 → None.
Model the logic used in the official specimen style
Paper 2-style linked-list construction
A player linked list uses nodes with name, score and next. self.head references the first node. Construct find_player(self, name) so it returns the matching score, or None if the player is absent.
def find_player(self, name):
current = self.head
while current is not None:
if current.name == name:
return current.score
current = current.next
return NoneReference order is part of correctness
Exit repair
def add_front(self, value):
new_node = Node(value)
self.head = new_node
new_node.next = self.headExplain the bug and correct the two pointer-update lines.
The original list is lost because head is changed before the new node saves the old head. Correct order:
new_node.next = self.head self.head = new_node
Finish the learning cycle
IA — main task
Continue Criterion D implementation/testing. Capture evidence for one non-trivial algorithm or data-handling feature.
Paper 2 — short practice
From a blank page, construct Node, head insertion, traversal, search and front deletion for a singly linked list.