Doubly and circular linked lists
Construct and trace two required linked-list variants, paying attention to bidirectional references and circular stopping conditions.
More links create more possibilities — and more failure points
- construct and trace doubly linked nodes with
nextandprev; - construct and trace circular links;
- apply insertion, deletion, traversal and search to these variants;
- evaluate the extra memory/complexity against their behavioural advantages.
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”.
Every connection has a reverse direction too
class DNode:
def __init__(self, value):
self.value = value
self.prev = None
self.next = NoneConstruct A ⇄ B ⇄ C
Create nodes A, B and C and connect all required forward and backward references.
a = DNode("A")
b = DNode("B")
c = DNode("C")
a.next = b
b.prev = a
b.next = c
c.prev = bMaintain both directions
Insert X between A and B
Assume a.next is b and b.prev is a. Construct the four reference updates needed to insert node x between them.
x.prev = a x.next = b a.next = x b.prev = x
Delete the middle node
For A ⇄ B ⇄ C, B is being removed and you already have a reference to B. Construct the two neighbour updates that reconnect A and C.
b.prev.next = b.next b.next.prev = b.prev
The stopping condition is part of the algorithm
a = Node("A")
b = Node("B")
c = Node("C")
a.next = b
b.next = c
c.next = a
head = aTrace one cycle
Starting from head, list the values encountered during exactly one complete traversal.
A, B, C. After C, next returns to A, which signals completion of one cycle.
Construct safe traversal
Assume the circular list is non-empty. Construct a loop that prints each node exactly once.
current = head
while True:
print(current.value)
current = current.next
if current is head:
breakNever wait for None in a true cycle
Construct circular search
Assume head is either None or the first node of a singly circular linked list. Construct a function contains(head, target) that checks every node at most once.
def contains(head, target):
if head is None:
return False
current = head
while True:
if current.value == target:
return True
current = current.next
if current is head:
return FalseChoose the variant from the behaviour
Evaluate the variants
A browser history must move both backward and forward. A round-robin scheduler repeatedly cycles through active processes. For each application, choose singly, doubly or circular linked list and justify.
Browser history: doubly linked is a natural fit because the structure must move in both directions; the extra previous reference is justified. Round-robin scheduler: circular linked is natural because after the final process the traversal returns to the first; correct cycle termination/removal logic is essential. A singly non-circular list would be simpler but would not model either requirement as directly.
Structure determines the termination condition
Exit bug
A circular traversal uses while current is not None:. Explain why this can fail and state a correct stopping idea.
In a valid circular list, current never becomes None, so the loop can run forever. Stop after the reference returns to the starting node/head, or use another explicit count/sentinel that guarantees one cycle.
Finish the learning cycle
IA — main task
Continue Criterion D implementation/testing and record one bug or edge case you tested deliberately.
Paper 2 — short practice
Reconstruct doubly linked insertion/deletion and circular traversal/search from memory, then explain one memory/performance trade-off for each variant.