Learn
B4.1.2 | EVALUATE LINKED LISTS (HL ONLY)
01 | WHY LINK VALUES TOGETHER?
Imagine a playlist that changes while you work. You insert a new track between two existing tracks and remove an old one. One possible representation keeps values in numbered array positions. Another stores each value in a small node that remembers how to reach the next node.
A linked list is a sequence represented by connected nodes. The sequence order comes from the links, rather than a requirement that the node objects sit next to one another in memory. This gives different advantages and costs from array-based storage.
To evaluate linked lists, ask where an operation happens and what references are already known. Insertion after a known node is a different task from searching for a value and then inserting after it.
02 | A NODE CONTAINS DATA AND A LINK
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
value stores the data. next stores a reference to another Node, or None if there is no successor in a linear list. Assigning next connects objects; it does not copy the successor into the current node.
Use symbolic labels such as A, B and C in diagrams to distinguish node identity from stored values. Two different nodes can contain equal values. The label B means a particular node, not necessarily index 1 or a literal memory address.
03 | THE HEAD IS YOUR ENTRY POINT
head refers to the first node. To reach value 30, start at head, follow its next reference to the second node, then follow next again. The final node has next = None in this non-circular list.
An empty list has head = None. A one-node linear list has head referring to that node and its next equal to None. If you overwrite the only route to the first node without preserving the chain, later nodes can become unreachable from the list.
04 | SINGLY LINKED LISTS
A singly linked node has one forward link. From a known node you can reach its successor directly, but you cannot immediately follow a previous reference because that field does not exist. Finding a predecessor may require a traversal from the head.
This smaller link structure uses less per-node reference storage than a comparable doubly linked design. It suits forward processing and operations near a known head. The cost is limited backward navigation and extra work for some deletions.
A tail reference can be added to identify the final node, but it is separate metadata. A singly linked list does not automatically maintain a tail just because the diagram has a last node.
05 | DOUBLY LINKED LISTS
Each node stores next and prev references. You can move both forwards and backwards. In a linear doubly linked list, the first node has prev = None and the last has next = None.
Backward navigation is useful for a history cursor or moving in both directions through a sequence. However, every node needs an extra link, and updates must keep both directions consistent. For adjacent nodes A and B, A.next = B should agree with B.prev = A.
The arrows are shown on separate lines to make the two directions readable. They represent links between the same node objects.
06 | CIRCULAR LINKED LISTS
In a non-empty circular singly linked list, the last node’s next refers back to the first node rather than None. A circular doubly linked list can also connect head.prev to the tail and tail.next to the head.
Circularity and link direction are separate choices: a list can be singly circular or doubly circular. A one-node circular singly linked list points back to itself. An empty circular list still needs a defined representation, such as head = None.
This design suits repeated rotation through items, such as turn allocation. A traversal must recognise when it has returned to the start; waiting for None on a valid non-empty circle would never finish.
07 | TRAVERSAL MEANS VISITING THE CHAIN
def traverse(head):
values = []
current = head
while current is not None:
values.append(current.value)
current = current.next
return values
This function is for a linear singly linked chain. current is a temporary traversal reference. Moving current to current.next leaves head unchanged, so the list keeps its entry point.
For 10, 20, 30, it visits three nodes in that order and then reaches None. The full traversal takes O(n) node visits for n nodes. The returned values list uses O(n) additional space; a traversal that only prints or accumulates a fixed-size result can use O(1) auxiliary state.
08 | SEARCH: FOLLOW LINKS UNTIL FOUND OR FINISHED
To search an unsorted linked list, compare the current node’s value with the target. If they differ, follow next. Stop at the first match or at the end. A target in the first node needs one comparison; an absent target may require all n nodes.
| Search for 30 | Comparison | Next action |
|---|---|---|
| Node A | 10 is not 30 | Follow A.next |
| Node B | 20 is not 30 | Follow B.next |
| Node C | 30 matches | Return C’s reference |
Searching by value is O(n) in the worst case. Even if values are sorted, a basic linked list does not provide O(1) access to the middle by index, so array-style binary search does not automatically give O(log n) total access time.
09 | INSERT AT THE HEAD
# With Node defined and head referring to an existing linear chain:
new_node = Node(5)
new_node.next = head
head = new_node
First make the new node point to the old first node. Then move head to the new node. No existing elements are shifted to different numbered slots. The link work is O(1), including when the old head is None.
The order matters. If you replace head first and then try to recover the old head through that same name, you may lose the route to the original chain or accidentally create a self-link. Preserve the successor before changing the entry point.
10 | INSERT BETWEEN TWO KNOWN NODES
| Stage | A.next | X.next | What is reachable from A |
|---|---|---|---|
| Before insertion | B | X not created | A, B, C |
| Create X with value 15 | B | None | A, B, C |
| Set X.next = A.next | B | B | A, B, C |
| Set A.next = X | X | B | A, X, B, C |
X is connected to the successor before A is redirected. The final sequence is 10, 15, 20, 30. The existing nodes keep their identity and their values; the links determine the new order.
With a valid reference to A already available, the splice uses O(1) link updates. If the task first has to find A by value or position, include that O(n) search in the total operation.
11 | DELETE A NODE BY BYPASSING IT
| Stage | A.next | B.next | Reachable sequence |
|---|---|---|---|
| Before removing B | B | C | A, B, C |
| Set A.next = B.next | C | C | A, C |
Bypassing B removes it from the list’s chain. It does not move C’s value into B. If B was the head, update head instead of a predecessor link. If it was the tail, update any maintained tail reference too.
In a singly linked list, deleting an arbitrary node generally needs its predecessor. Knowing only the target node is not enough for general constant-time unlinking, especially at the tail. Do not use a special copy-successor trick as a universal identity-preserving deletion rule.
A removed node may still be reachable through another reference. Unlinking it and the runtime reclaiming its memory are separate events.
12 | DOUBLY LINKED UPDATES NEED BOTH DIRECTIONS
| Insert X between A and B | Purpose |
|---|---|
| X.prev = A | Connect X backwards |
| X.next = B | Connect X forwards |
| A.next = X | Make A reach X |
| B.prev = X | Make B reach X backwards |
For deleting a known internal B, reconnect A.next to C and C.prev to A. At the first or last node, update head or tail and handle the absent neighbour. A sentinel-node implementation can reduce some boundary branches, but its convention must be stated.
When the target node is already known in a doubly linked list, its prev reference supplies the predecessor, so unlinking can use O(1) link work. Searching for that node by value is still a separate cost.
13 | STEP THROUGH INSERTION, DELETION AND SEARCH
Choose an operation and predict the next reference change. Each example starts from the same fresh chain A(10), B(20), C(30). The diagram shows the nodes reachable from head; the table also shows detached nodes so you can see that a link change is different from immediate object destruction.
14 | CIRCULAR TRAVERSAL NEEDS A DIFFERENT STOP
def circular_values(head):
if head is None:
return []
result = []
current = head
while True:
result.append(current.value)
current = current.next
if current is head:
break
return result
The empty check prevents an invalid dereference. For a valid non-empty circle, each node is processed once before current returns to the starting node. is checks node identity, so duplicate stored values do not cause early termination.
The function assumes a valid circle returning to head. A corrupted structure containing a different cycle needs separate validation. A maintained size can provide another bounded traversal convention, but only if that size is correct.
15 | A COMPLETE PYTHON SINGLY LINKED EXAMPLE
Save these definitions as linked_list_demo.py. This intentionally small implementation supports prepending, traversal, first-match search, insertion after the first matching value and deletion of the first matching value. The next lesson develops construction across all three list forms.
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
class SinglyList:
def __init__(self):
self.head = None
def prepend(self, value):
self.head = Node(value, self.head)
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 insert_after(self, after_value, value):
previous = self.find(after_value)
if previous is None:
return False
new_node = Node(value, previous.next)
previous.next = new_node
return True
def delete_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
return True
previous = current
current = current.next
return False
items = SinglyList()
for value in (30, 20, 10):
items.prepend(value)
print(items.values())
print(items.insert_after(10, 15))
print(items.values())
print(items.delete_first(20))
print(items.values())
Output: [10, 20, 30], True, [10, 15, 20, 30], True, [10, 15, 30]. Notice that prepend reverses the order of the supplied construction values. insert_after includes a search, so this method is O(n) in the worst case even though the final splice is constant-size.
16 | JAVA: REFERENCES AND NULL
Java uses null for an absent reference. The example below builds the same initial linear sequence, searches for 20 and removes that value. Save it as LinkedListExample.java and run main.
class Node {
int value;
Node next;
Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
class SinglyList {
private Node head;
public void prepend(int value) {
head = new Node(value, head);
}
public boolean contains(int value) {
Node current = head;
while (current != null) {
if (current.value == value) return true;
current = current.next;
}
return false;
}
public boolean deleteFirst(int value) {
Node previous = null;
Node current = head;
while (current != null) {
if (current.value == value) {
if (previous == null) head = current.next;
else previous.next = current.next;
return true;
}
previous = current;
current = current.next;
}
return false;
}
public String values() {
StringBuilder result = new StringBuilder();
for (Node current = head; current != null; current = current.next) {
if (result.length() > 0) result.append(", ");
result.append(current.value);
}
return result.toString();
}
}
public class LinkedListExample {
public static void main(String[] args) {
SinglyList items = new SinglyList();
items.prepend(30);
items.prepend(20);
items.prepend(10);
System.out.println(items.values());
System.out.println(items.contains(20));
System.out.println(items.deleteFirst(20));
System.out.println(items.values());
}
}
The output is 10, 20, 30; true; true; then 10, 30 on separate lines. The field next refers to another Node; assigning it changes connectivity rather than copying the entire successor object.
Python None and Java null serve a similar absent-reference role in these examples, but each language has its own syntax and runtime error types.
17 | ARRAYS AND LINKS STORE SEQUENCES DIFFERENTLY
An array stores a sequence in indexed slots. Under the standard array model, locating a slot by index takes O(1). In Python list and Java ArrayList, the contiguous backing storage holds references; the referenced objects themselves need not be adjacent.
A linked representation stores references within nodes. Nodes need not occupy adjacent locations. To access position i in a basic singly linked list, start at head and follow i links, so arbitrary access is O(n) in the worst case.
Do not confuse abstract sequence order with physical memory placement. Array indexing and following next references are different routes to the same logical position.
18 | COMPARE TIME COSTS WITH THE ASSUMPTIONS SHOWN
| Operation | Resizable array sequence | Singly linked, head only | Doubly linked, head and tail |
|---|---|---|---|
| Access arbitrary index | O(1) | O(n) | O(n) worst case |
| Search unsorted by value | O(n) | O(n) | O(n) |
| Insert at front | O(n) shifting | O(1) | O(1) |
| Append | Amortized O(1) | O(n) | O(1) |
| Remove final element | Amortized O(1); possible resize cost | O(n) to find predecessor | O(1) |
| Insert/unlink at known internal location | O(n) shifting in general | O(1) if required predecessor is known | O(1) if node/neighbours are known |
These are standard asymptotic costs with unit-cost reference operations and ordinary allocation assumptions. A singly linked list with a maintained tail can append in O(1), but still cannot generally remove its tail in O(1) without a predecessor route.
The doubly linked list can start an index traversal from the nearer end, which may reduce actual steps; arbitrary indexed access still has O(n) worst-case growth. Circularity alone does not remove the need to locate a predecessor.
19 | MEMORY USE IS A TRADE-OFF
| Representation | Structural storage considerations |
|---|---|
| Fixed array | Allocated slots may be unused; a full array needs a capacity policy |
| Resizable array | Can reserve spare slots and occasionally allocate a larger backing array |
| Singly linked nodes | One next reference per node, plus node/object and allocation overhead |
| Doubly linked nodes | An additional prev reference per node and metadata to maintain |
| Circular form | Reuses an end link to return to the start; may also keep head/tail metadata |
Linked structures can grow one node at a time without shifting a whole array prefix. That does not mean they always use less memory: node objects, links, alignment and allocator overhead can outweigh an array’s spare capacity.
An illustrative count of link fields is not an exact byte measurement. The runtime, representation and element types determine actual memory use.
20 | LOCALITY AND PRACTICAL PERFORMANCE
Array-backed reference slots are contiguous, which often supports efficient sequential access to those slots. Linked traversal may chase references to nodes in different locations, with more memory accesses and less predictable locality.
Big O helps describe growth but does not capture every practical timing cost. A linked insertion can have constant link work while allocation or finding the insertion point dominates measured time. A small array may perform well despite shifting.
State the workload and measure relevant operations when performance matters. “Linked lists are faster” is not a complete evaluation.
21 | WHEN EACH FORM FITS
| Scenario | Possible choice | Reason and limitation |
|---|---|---|
| Forward-only work near the head | Singly linked list | One link per node; backward navigation is awkward |
| Move a cursor both forwards and backwards | Doubly linked list | Direct neighbour routes; extra storage and updates |
| Repeated round-robin turns | Circular list | Natural wraparound; traversal needs explicit stopping rules |
| Frequent arbitrary indexed reads | Array-backed sequence | Direct indexing; middle insertion may shift elements |
| Mostly append and scan a compact sequence | Resizable array may fit | Good indexed access/locality; occasional resizing |
Real systems can use other structures too. A deque or ring buffer may serve a queue efficiently without a linked list. Evaluate the alternatives that meet the same behavioural requirement rather than forcing one representation.
22 | EVALUATE THE WHOLE OPERATION
A playlist editor may already hold a reference to the selected item. In a doubly linked representation, insertion or deletion near that cursor can use constant-size link changes, so frequent local edits may justify the additional references.
If instead the interface supplies a track title, the program must first search for it. That makes a simple linked-list edit O(n) overall in the worst case. If it supplies an index repeatedly, an array-backed sequence may provide a better balance.
A strong evaluation separates locating the position from editing the links, considers memory and navigation, and reaches a conclusion tied to the actual workload.
23 | BOUNDARIES AND LINK INVARIANTS
Test empty, one-node and multi-node lists. Insert and remove at the head, in the middle and at the tail. Include an absent target and duplicate values, and state whether an operation handles the first occurrence or all occurrences.
For a linear list, traversal should reach None without an unintended cycle. If a tail is stored, it must identify the final node. For a doubly linked list, adjacent forward and backward links must agree. For a circular list, following the valid chain should return to the chosen start after visiting each node once.
These properties help identify mistakes that a single successful printout could miss. Insertion that works in the middle can still fail on an empty list or at a maintained tail.
24 | COMMON ERRORS
| Error | Why it matters | Repair |
|---|---|---|
| Change the predecessor before preserving its successor | Can lose the old chain or create a self-link | Connect the new node to the old successor first |
| Move head during ordinary traversal | Loses the original entry route | Move a temporary current reference |
| Update only one side of a doubly linked splice | Backward and forward paths disagree | Maintain both neighbour links |
| Wait for None in a valid circle | The traversal never reaches None | Stop on return to the starting identity |
| Call all linked deletion O(1) | Finding predecessor or target can dominate | State the references already known |
| Treat unlinking as immediate destruction | Other references may remain | Separate list membership and memory reclamation |
25 | WRITE A BALANCED EVALUATION
For example: a doubly linked list suits frequent edits around a known cursor because both neighbour references are available, so items can be reconnected without shifting the remainder. However, extra links increase per-node storage and arbitrary indexed access still needs traversal. Therefore it fits a cursor-based editor better than a workload dominated by random indexed reads.
For circular lists, connect wraparound to a scenario and include the stopping-rule cost. For arrays, acknowledge shifting and resizing as well as indexing and locality. Make each strength or limitation explain a consequence rather than simply listing adjectives.
The command evaluate requires a supported judgement. There is no single best representation for every sequence.
26 | YOUR DESIGN DECISION
Compare two systems: a photo browser repeatedly jumps to a numbered position, while a turn manager repeatedly moves to the next player and occasionally removes the current player. Identify suitable representations, explain operation costs and discuss memory and boundary cases.
For the turn manager, specify which references are retained. A circular doubly linked list offers direct neighbours, while a circular singly linked list may need a predecessor reference for removal. A ring-buffer or indexed design may also be valid if its trade-offs fit the requirements.
In the next lesson, you will construct and apply singly, doubly and circular lists in more detail. Keep the sketches and ownership of each link clear before writing the updates.