IB COMPUTER SCIENCE | B4.1.2 Linked Lists (HL)

Lesson objective

Evaluate singly, doubly and circular linked lists, trace basic operations diagrammatically and compare memory and performance with array-based structures.

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

Singly linked list with three nodes head Node A value 10 next Node B value 20 next Node C value 30 None
Singly linked list with three nodes. Arrows are references; box spacing is illustrative, not a physical memory map.

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

Doubly linked linear list head Node A value 10 next prev Node B value 20 next prev Node C value 30 None First.prev = None; last.next = None
Doubly linked linear list. Arrows are references; box spacing is illustrative, not a physical memory map.

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

Circular singly linked list head Node A value 10 next Node B value 20 next Node C value 30 last.next refers to head
Circular singly linked list. Arrows are references; box spacing is illustrative, not a physical memory map.

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.

MATCH THE LINKED-LIST IDEA

Terminology

Terminology

Linked list

A sequence represented by nodes connected through references.

Node

A component holding a value and one or more links.

Reference

A value through which code reaches an object.

Head

The reference identifying the first node or chosen entry node.

Tail

The final node of a linear list, or a maintained reference to it.

Successor

The next node in the logical sequence.

Predecessor

The node immediately before another in the sequence.

Singly linked list

A linked sequence whose nodes carry a next reference.

Doubly linked list

A linked sequence whose nodes carry next and prev references.

Circular linked list

A non-empty linked list whose end links back to its start.

Linear linked list

A non-circular chain with an absent-reference end marker.

Traversal

Visiting nodes by following links.

Search

Locating a node with a required value or property.

Insertion

Adding a node and connecting it into the sequence.

Splice

A local change reconnecting nodes during insertion or removal.

Deletion from a list

Removing a node from the reachable sequence by updating links.

None / null

Absent-reference markers in Python and Java respectively.

Current reference

A temporary reference used to move through a chain.

Known-node operation

An operation starting with the relevant node reference already available.

Random indexed access

Reaching an arbitrary position directly by index.

Array-backed sequence

An indexed sequence stored using a backing array of slots.

Link overhead

Storage needed for references in addition to the stored values.

Locality

How closely accessed storage locations are grouped, affecting practical memory access.

Invariant

A property that valid operations maintain.

Sentinel node

An extra boundary node used by some implementations to simplify updates.

Object identity

Whether references reach the same node rather than merely equal data.

Unreachable node

A node no longer accessible through live reference routes.

Round robin

Repeatedly cycling through a sequence of participants or tasks.

Amortized cost

Average cost over an operation sequence that includes occasional expensive work.

Evaluation

A reasoned judgement weighing strengths and limitations for a stated context.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which describe a singly linked list?
2. Which fit a doubly linked list?
3. Which describe a valid non-empty circular singly linked list?
4. For insertion of X after known A, which order is safe?
5. Which deletion statements are correct?
6. Which cost statements are accurate?
7. Which favour an array-backed sequence?
8. Which memory evaluations are sound?
9. Which circular-traversal choices are appropriate?
10. Which tests are useful?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Define a linked list.

2. Distinguish singly and doubly linked lists.

3. Explain a circular linked list and its traversal stopping rule.

4. Describe how to insert X between A and B in a singly linked list.

5. Explain how a singly linked list deletes B between A and C.

6. Evaluate the claim that linked-list insertion is always O(1).

7. Compare array-based and linked indexed access.

8. Evaluate linked-list memory use compared with resizable arrays.

9. Suggest a representation for repeated next-player turns and explain a limitation.

10. Explain why a tail reference does not make every singly linked tail operation O(1).

11. Construct a test plan for linked-list operations.

12. Evaluate a doubly linked list for a cursor-based editor.

EVALUATE | A CURSOR-BASED PLAYLIST

Evaluate a singly linked, doubly linked and array-backed representation for a playlist editor. The editor holds a reference to the currently selected item, frequently inserts or deletes nearby items, moves backwards and forwards, and only rarely jumps to a numbered position.

Reveal a supported judgement

A doubly linked list fits the frequent local edits and two-way navigation because the current node exposes both neighbours, so the link changes can be constant-size without shifting a suffix. A singly linked form uses fewer link fields but needs a predecessor route for general deletion and backward movement. An array-backed sequence offers direct index access and useful locality but usually shifts elements for middle edits.

Given this workload, doubly linked storage is reasonable if the extra references and update complexity are acceptable. Check empty, one-node and endpoint cases. The conclusion could change if random index jumps dominated or if measured overhead made a compact array more effective.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B4.1.2 Linked Lists (HL) is coming soon. Complete the matching task and written questions in your exercise book.