IB COMPUTER SCIENCE | B4.1.3 Construct Linked Lists (HL)

Lesson objective

Construct and apply singly, doubly and circular linked lists, implementing insertion, deletion, traversal and search while maintaining their structural invariants.

Learn

B4.1.3 | CONSTRUCT AND APPLY LINKED LISTS (HL ONLY)

01 | FROM A SKETCH TO A WORKING STRUCTURE

In the previous lesson, you evaluated linked representations. Now you will build them. Each implementation must keep a usable entry point, connect new nodes safely and repair the chain when a node is removed. A diagram is a useful plan, but the code also has to handle the empty list and the final remaining node.

We will construct a singly linked linear list, a doubly linked linear list and a singly linked circular list. Each supports insertion, deletion, traversal and search. The circular implementation also provides rotation for a turn-taking application.

Use small integer values while learning the mechanics. A node’s identity is separate from its stored value, so repeated values are permitted.

02 | AGREE THE OPERATION RULES FIRST

Operation Contract in this lesson
append(value) Add a new node at the end
prepend(value) Add a new node at the beginning
find(value) Return the first matching node from head, or None
insert_after(target, value) Insert after the first matching target; return True, or False without mutation if absent
delete_first(value) Remove the first matching node; return True, or False without mutation if absent
values() Return the current forward sequence as a separate Python list
size Number of nodes currently in the list

The methods append and prepend have no useful returned result. The first-match rule makes duplicate handling predictable. find returns a live node reference for learning; do not modify its links from caller code unless an operation explicitly supports that. A production API might expose fewer internal handles.

The examples are single-threaded. Every complete method must restore the list invariants before returning, even though its individual link assignments can temporarily leave an update unfinished.

03 | UNDERSTAND THE REFERENCE FIELDS

A singly linked node has value and next. A doubly linked node also has prev. A list object stores metadata such as head, tail and size. None represents an absent node reference in Python; Java uses null.

self.head is the entry point belonging to the list instance. current is usually a local traversal reference. Changing current does not move head. Changing current.next changes the link on the node that current reaches.

Before assigning a link, identify its owner and its destination. For example, previous.next = current.next changes the predecessor’s next field to the successor reference. It does not copy the successor’s data into previous.

04 | SINGLY LINKED: INITIALIZATION AND APPEND

Linear singly linked construction model head Node A value 10 next Node B value 20 next Node C value 30 None
Linear singly linked construction model. Arrows are references; box spacing is illustrative, not a physical memory map.
# Inside SinglyList:
def append(self, value):
    node = SNode(value)
    if self.tail is None:
        self.head = node
    else:
        self.tail.next = node
    self.tail = node
    self.size += 1

Initialize head and tail to None and size to zero. For the first append, the new node becomes both head and tail. For later appends, connect the old tail to the new node before replacing tail.

Because this implementation maintains a tail reference, append does not search from head. Its link work is O(1). Every linear tail must finish with next = None.

05 | PREPEND WITHOUT LOSING THE OLD HEAD

# Inside SinglyList:
def prepend(self, value):
    node = SNode(value, self.head)
    self.head = node
    if self.tail is None:
        self.tail = node
    self.size += 1

The node constructor records the old head as the new node’s successor. Then head is redirected. If the list was empty, tail must also identify the same new node. If it was non-empty, tail stays where it was.

Do not create a shared mutable node or list as a class-level default for every instance. Each list needs its own metadata and each inserted item needs its own node object.

06 | TRAVERSE AND SEARCH WITH A LOCAL REFERENCE

# Inside SinglyList:
def find(self, value):
    current = self.head
    while current is not None:
        if current.value == value:
            return current
        current = current.next
    return None

The while condition checks whether current refers to a node before reading current.value. A match returns immediately. Only return None after the entire reachable chain has been checked; placing that return inside the non-matching branch would stop after the first node.

values follows the same progression but records every value. An absent search can take O(n) comparisons. Returning a node lets code distinguish a match from None even when a permitted stored value itself is None.

07 | INSERT AFTER THE FIRST MATCH

Step Reference effect
previous = find(target) Locate the first matching predecessor
node = SNode(value, previous.next) Preserve its old successor in the new node
previous.next = node Connect the predecessor to the new node
If previous was tail, set tail = node Keep final-node metadata correct
Increment size Count the newly inserted node

For 10, 20, 30, insert_after(10, 15) produces 10, 15, 20, 30. If target is absent, return False before creating a linked node or changing metadata.

The splice uses a fixed number of assignments after locating the target. This public method includes find, so its worst-case cost is O(n), not O(1).

08 | DELETE WITH CURRENT AND PREVIOUS

Start previous = None and current = head. Move both references together until the first matching node is reached. If previous is None at the match, current is the head, so set head = current.next. Otherwise bypass current through previous.next.

Case Required update
Delete head of several nodes head = current.next
Delete internal node previous.next = current.next
Delete tail Also tail = previous
Delete the only node Both head and tail become None
Target absent Return False with no state change

After reconnecting the live chain, set current.next = None to detach the removed node’s old outgoing route, decrement size once and return True. Detachment does not destroy an object that another reference still reaches.

09 | COMPLETE PYTHON SINGLY LINKED LIST

Save this as singly_list.py or place it in a combined practice file. SNode is the node type used only by this implementation. You can run the shared caller in section 21 after defining all three list classes.

class SNode:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

class SinglyList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def append(self, value):
        node = SNode(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def prepend(self, value):
        node = SNode(value, self.head)
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    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, target, value):
        previous = self.find(target)
        if previous is None:
            return False
        node = SNode(value, previous.next)
        previous.next = node
        if previous is self.tail:
            self.tail = node
        self.size += 1
        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
                if current is self.tail:
                    self.tail = previous
                current.next = None
                self.size -= 1
                return True
            previous = current
            current = current.next
        return False

    def values(self):
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result

Read delete_first with empty, head, tail and singleton sketches beside you. The same comparison current is self.tail checks identity rather than equal values. This matters when two different nodes store the same value.

10 | DOUBLY LINKED: MAINTAIN TWO DIRECTIONS

Doubly linked construction model 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 construction model. Arrows are references; box spacing is illustrative, not a physical memory map.

DNode adds prev. Our linear invariants require head.prev = None, tail.next = None and agreement between adjacent forward and backward references. Empty state means both endpoints are None and size is zero.

Forward traversal starts at head and follows next. Reverse traversal starts at tail and follows prev. You do not reverse the values or reconstruct the list to move backwards; the extra links already provide that route.

11 | APPEND AND PREPEND A DOUBLY LINKED NODE

Append Prepend
Set node.prev to old tail Set node.next to old head
If non-empty, old tail.next = node If non-empty, old head.prev = node
If empty, head = node If empty, tail = node
Set tail = node Set head = node
Increment size Increment size

A new DNode starts with both links equal to None. This makes the missing outer neighbour correct when adding at an endpoint. The old endpoint, when present, must point back towards the new node.

A frequent bug is a list that traverses forwards correctly but backwards incorrectly. Test both directions after every kind of insertion.

12 | INSERT IN BOTH DIRECTIONS

# After previous is found, inside DoublyList.insert_after:
node = DNode(value)
node.prev = previous
node.next = previous.next
if previous.next is None:
    self.tail = node
else:
    previous.next.prev = node
previous.next = node
self.size += 1

The new node first remembers both neighbours. If an old successor exists, redirect its prev towards the new node. Then redirect the predecessor’s next. If there was no successor, the new node becomes tail instead.

These are implementation steps inside one operation. Do not call a general traversal halfway through a splice and assume the entire public contract has already been restored.

13 | DELETE THROUGH THE NEIGHBOURS

Once the matching DNode is found, its prev and next references identify both neighbours. If prev is missing, update head; otherwise reconnect prev.next. If next is missing, update tail; otherwise reconnect next.prev.

Remove B between A and C Reason
A.next = C Forward traversal bypasses B
C.prev = A Backward traversal bypasses B
B.prev = None and B.next = None Detach the removed node’s old routes
Decrease size by one Keep metadata consistent

The endpoint branches also handle the only-node case: head and tail both become None. The unlinking is constant-size after finding the node. Searching by value remains O(n) worst case.

14 | COMPLETE PYTHON DOUBLY LINKED LIST

class DNode:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class DoublyList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def append(self, value):
        node = DNode(value)
        node.prev = self.tail
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def prepend(self, value):
        node = DNode(value)
        node.next = self.head
        if self.head is None:
            self.tail = node
        else:
            self.head.prev = node
        self.head = node
        self.size += 1

    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, target, value):
        previous = self.find(target)
        if previous is None:
            return False
        node = DNode(value)
        node.prev = previous
        node.next = previous.next
        if previous.next is None:
            self.tail = node
        else:
            previous.next.prev = node
        previous.next = node
        self.size += 1
        return True

    def delete_first(self, value):
        current = self.find(value)
        if current is None:
            return False
        if current.prev is None:
            self.head = current.next
        else:
            current.prev.next = current.next
        if current.next is None:
            self.tail = current.prev
        else:
            current.next.prev = current.prev
        current.prev = None
        current.next = None
        self.size -= 1
        return True

    def values(self):
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result

    def reverse_values(self):
        result = []
        current = self.tail
        while current is not None:
            result.append(current.value)
            current = current.prev
        return result

reverse_values is a deliberate structural test as well as a useful operation. After complete methods, its result should equal the reversed forward values. If it does not, one of the prev routes or the tail is probably wrong.

Use fresh list objects while comparing examples. A shared node attached to two independently maintained lists can break their ownership and link assumptions.

15 | CIRCULAR: STORE TAIL AND DERIVE HEAD

Circular singly linked construction model head Node A value 10 next Node B value 20 next Node C value 30 last.next refers to head
Circular singly linked construction model. Arrows are references; box spacing is illustrative, not a physical memory map.
# Inside CircularList:
@property
def head(self):
    return None if self.tail is None else self.tail.next

This representation stores tail and size. A read-only head property derives the starting node as tail.next. It avoids maintaining a second independent head field that could disagree with the circular closure.

An empty circle has tail = None and size = 0. A one-node circle has tail.next is tail. For every non-empty circle, following exactly size next links from head returns to the same head object.

16 | CIRCULAR APPEND VERSUS PREPEND

Stage Append Prepend
Empty list New node points to itself; tail becomes it The same singleton setup
Non-empty: preserve old head node.next = tail.next node.next = tail.next
Connect old tail to new node tail.next = node tail.next = node
Choose logical last node Move tail to node Keep tail at the old last node
Count the addition Increment size Increment size

Both operations splice a node between tail and head, but only append moves the tail marker. That one metadata difference determines which value is first in the resulting logical sequence.

For 10, 20, 30, appending 40 yields 10, 20, 30, 40. Prepending 5 yields 5, 10, 20, 30. Draw tail.next after each assignment rather than assuming a circular list has an absent end link.

17 | BOUNDED TRAVERSAL AND SEARCH

# Inside CircularList:
def find(self, value):
    current = self.head
    for _ in range(self.size):
        if current.value == value:
            return current
        current = current.next
    return None

The underscore is a conventional name for an unused loop counter. range(size) causes exactly size visits at most, so a valid circle cannot loop forever. On an empty list, the body executes zero times and never dereferences None.

This relies on size being correct. An alternative is to stop on returning to the starting node identity after processing it once. Neither approach should stop merely because the same data value appears again.

18 | CIRCULAR DELETION: HEAD, TAIL AND ONLY NODE

For a circular singly linked search, start previous = tail and current = head. The tail is the predecessor of the head, so the first candidate already has the route needed for bypassing. Keep both references moving for at most size visits.

Matching case Update
More than one node previous.next = current.next
The removed node is tail Also tail = previous
The removed node is head The updated tail.next now provides the new head
Only one node remains Set tail = None
After successful removal Detach current.next, decrement size, return True

Do the singleton check before applying the general bypass rule. Otherwise you can leave a tail pointing at the supposedly removed self-linked node. The method returns immediately after removal, so its precomputed loop bound does not cause extra visits.

19 | COMPLETE PYTHON CIRCULAR LIST

class CNode:
    def __init__(self, value):
        self.value = value
        self.next = None

class CircularList:
    def __init__(self):
        self.tail = None
        self.size = 0

    @property
    def head(self):
        return None if self.tail is None else self.tail.next

    def append(self, value):
        node = CNode(value)
        if self.tail is None:
            node.next = node
        else:
            node.next = self.tail.next
            self.tail.next = node
        self.tail = node
        self.size += 1

    def prepend(self, value):
        node = CNode(value)
        if self.tail is None:
            node.next = node
            self.tail = node
        else:
            node.next = self.tail.next
            self.tail.next = node
        self.size += 1

    def find(self, value):
        current = self.head
        for _ in range(self.size):
            if current.value == value:
                return current
            current = current.next
        return None

    def insert_after(self, target, value):
        previous = self.find(target)
        if previous is None:
            return False
        node = CNode(value)
        node.next = previous.next
        previous.next = node
        if previous is self.tail:
            self.tail = node
        self.size += 1
        return True

    def delete_first(self, value):
        previous = self.tail
        current = self.head
        for _ in range(self.size):
            if current.value == value:
                if self.size == 1:
                    self.tail = None
                else:
                    previous.next = current.next
                    if current is self.tail:
                        self.tail = previous
                current.next = None
                self.size -= 1
                return True
            previous = current
            current = current.next
        return False

    def values(self):
        result = []
        current = self.head
        for _ in range(self.size):
            result.append(current.value)
            current = current.next
        return result

    def rotate(self):
        if self.tail is not None:
            self.tail = self.tail.next

rotate moves the logical start one place by advancing tail to its successor. The node links themselves do not change: the same ring is viewed from a new starting point. Rotation of an empty or one-node circle leaves the visible sequence unchanged.

This is a singly linked circle. A doubly linked circular version would also maintain prev, including reciprocal links at the closure. The three implementations here make the specified singly, doubly and circular construction choices explicit.

20 | STEP THROUGH ALL THREE IMPLEMENTATIONS

Choose a representation. Each scenario starts empty and performs the same core operations, then tests missing targets, deletion down to empty and reuse. The circular scenario also rotates. The diagrams and link tables come from executing the actual Python methods shown above.

The table keeps references to removed nodes for teaching, so a detached row is not a claim that the object has already been reclaimed. It also shows exactly where head and tail point after each complete operation.

21 | ONE CALLER, THREE IMPLEMENTATIONS

Place the three Python definitions in one file, then add the following caller. Click Run in your editor. Each class has the same basic method names and first-match contract, so exercise works with all three.

def exercise(ListClass):
    items = ListClass()
    for value in (10, 20, 30):
        items.append(value)
    items.prepend(5)
    print(items.insert_after(10, 15))
    print(items.values())
    print(items.find(20) is not None)
    print(items.delete_first(20))
    print(items.values(), items.size)
    print(items.delete_first(99))

for ListClass in (SinglyList, DoublyList, CircularList):
    exercise(ListClass)

circle = CircularList()
for value in (10, 20, 30):
    circle.append(value)
circle.rotate()
print(circle.values())

For each implementation, the results are True; [5, 10, 15, 20, 30]; True; True; [5, 10, 15, 30] 4; False. The final circular rotation prints [20, 30, 10]. Each semicolon here separates an output line.

The caller does not edit a link field. It requests operations, then inspects returned values and snapshots. This carries the ADT boundary from B4.1.1 into working code.

22 | COMPLETE JAVA IMPLEMENTATIONS

Save this as LinkedListsExample.java. It contains all three integer implementations and a common IntChain interface. Only LinkedListsExample is public. Use main to run the same application sequence for each representation.

import java.util.ArrayList;
import java.util.List;

interface IntChain {
    void append(int value);
    void prepend(int value);
    boolean insertAfter(int target, int value);
    boolean deleteFirst(int value);
    boolean contains(int value);
    List<Integer> values();
}

class SNode {
    int value;
    SNode next;
    SNode(int value) { this.value = value; }
}
class SinglyList implements IntChain {
    private SNode head, tail;
    private int size;
    public void append(int value) {
        SNode n = new SNode(value);
        if (tail == null) head = n;
        else tail.next = n;
        tail = n;
        size++;
    }
    public void prepend(int value) {
        SNode n = new SNode(value);
        n.next = head;
        head = n;
        if (tail == null) tail = n;
        size++;
    }
    private SNode find(int value) {
        for (SNode n = head; n != null; n = n.next) {
            if (n.value == value) return n;
        }
        return null;
    }
    public boolean contains(int value) { return find(value) != null; }
    public boolean insertAfter(int target, int value) {
        SNode p = find(target);
        if (p == null) return false;
        SNode n = new SNode(value);
        n.next = p.next;
        p.next = n;
        if (p == tail) tail = n;
        size++;
        return true;
    }
    public boolean deleteFirst(int value) {
        SNode p = null, n = head;
        while (n != null) {
            if (n.value == value) {
                if (p == null) head = n.next;
                else p.next = n.next;
                if (n == tail) tail = p;
                n.next = null;
                size--;
                return true;
            }
            p = n;
            n = n.next;
        }
        return false;
    }
    public List<Integer> values() {
        List<Integer> result = new ArrayList<>();
        for (SNode n = head; n != null; n = n.next) result.add(n.value);
        return result;
    }
}

class DNode {
    int value;
    DNode prev, next;
    DNode(int value) { this.value = value; }
}
class DoublyList implements IntChain {
    private DNode head, tail;
    private int size;
    public void append(int value) {
        DNode n = new DNode(value);
        n.prev = tail;
        if (tail == null) head = n;
        else tail.next = n;
        tail = n;
        size++;
    }
    public void prepend(int value) {
        DNode n = new DNode(value);
        n.next = head;
        if (head == null) tail = n;
        else head.prev = n;
        head = n;
        size++;
    }
    private DNode find(int value) {
        for (DNode n = head; n != null; n = n.next) {
            if (n.value == value) return n;
        }
        return null;
    }
    public boolean contains(int value) { return find(value) != null; }
    public boolean insertAfter(int target, int value) {
        DNode p = find(target);
        if (p == null) return false;
        DNode n = new DNode(value);
        n.prev = p;
        n.next = p.next;
        if (p.next == null) tail = n;
        else p.next.prev = n;
        p.next = n;
        size++;
        return true;
    }
    public boolean deleteFirst(int value) {
        DNode n = find(value);
        if (n == null) return false;
        if (n.prev == null) head = n.next;
        else n.prev.next = n.next;
        if (n.next == null) tail = n.prev;
        else n.next.prev = n.prev;
        n.prev = null;
        n.next = null;
        size--;
        return true;
    }
    public List<Integer> values() {
        List<Integer> result = new ArrayList<>();
        for (DNode n = head; n != null; n = n.next) result.add(n.value);
        return result;
    }
    public List<Integer> reverseValues() {
        List<Integer> result = new ArrayList<>();
        for (DNode n = tail; n != null; n = n.prev) result.add(n.value);
        return result;
    }
}

class CNode {
    int value;
    CNode next;
    CNode(int value) { this.value = value; }
}
class CircularList implements IntChain {
    private CNode tail;
    private int size;
    private CNode head() { return tail == null ? null : tail.next; }
    public void append(int value) {
        CNode n = new CNode(value);
        if (tail == null) n.next = n;
        else {
            n.next = tail.next;
            tail.next = n;
        }
        tail = n;
        size++;
    }
    public void prepend(int value) {
        CNode n = new CNode(value);
        if (tail == null) {
            n.next = n;
            tail = n;
        } else {
            n.next = tail.next;
            tail.next = n;
        }
        size++;
    }
    private CNode find(int value) {
        CNode n = head();
        for (int i = 0; i < size; i++) {
            if (n.value == value) return n;
            n = n.next;
        }
        return null;
    }
    public boolean contains(int value) { return find(value) != null; }
    public boolean insertAfter(int target, int value) {
        CNode p = find(target);
        if (p == null) return false;
        CNode n = new CNode(value);
        n.next = p.next;
        p.next = n;
        if (p == tail) tail = n;
        size++;
        return true;
    }
    public boolean deleteFirst(int value) {
        CNode p = tail, n = head();
        for (int i = 0; i < size; i++) {
            if (n.value == value) {
                if (size == 1) tail = null;
                else {
                    p.next = n.next;
                    if (n == tail) tail = p;
                }
                n.next = null;
                size--;
                return true;
            }
            p = n;
            n = n.next;
        }
        return false;
    }
    public List<Integer> values() {
        List<Integer> result = new ArrayList<>();
        CNode n = head();
        for (int i = 0; i < size; i++) {
            result.add(n.value);
            n = n.next;
        }
        return result;
    }
    public void rotate() { if (tail != null) tail = tail.next; }
}

public class LinkedListsExample {
    public static void exercise(IntChain items) {
        items.append(10);
        items.append(20);
        items.append(30);
        items.prepend(5);
        System.out.println(items.insertAfter(10, 15));
        System.out.println(items.values());
        System.out.println(items.contains(20));
        System.out.println(items.deleteFirst(20));
        System.out.println(items.values());
        System.out.println(items.deleteFirst(99));
    }
    public static void main(String[] args) {
        exercise(new SinglyList());
        exercise(new DoublyList());
        exercise(new CircularList());
        CircularList turns = new CircularList();
        turns.append(10);
        turns.append(20);
        turns.append(30);
        turns.rotate();
        System.out.println(turns.values());
    }
}

Each implementation prints true; [5, 10, 15, 20, 30]; true; true; [5, 10, 15, 30]; false. The final rotation prints [20, 30, 10]. Python also prints size in its shared caller; this compact Java caller prints the values only.

Java uses private metadata and contains rather than returning an internal node to callers. The underlying find methods remain internal. These interface differences are intentional; the shared insertion, first-match deletion and sequence behaviours are the same.

23 | APPLY A CIRCULAR LIST TO TURNS

turns = CircularList()
for player in ("Maya", "Leo", "Sam"):
    turns.append(player)
print(turns.head.value)
turns.rotate()
print(turns.head.value)
turns.delete_first("Leo")
print(turns.values())
# Maya
# Leo
# ['Sam', 'Maya']

After rotating, Leo is the head, so the logical order is Leo, Sam, Maya. Removing Leo reconnects the last node to Sam. Maya is still the tail, and its next supplies the new head Sam.

For a real game, decide whether a removed current player’s successor acts next and how to handle no players. That application policy should be clear before the code chooses rotation and deletion order.

24 | COSTS OF THESE EXACT METHODS

Operation SinglyList DoublyList CircularList
append / prepend O(1) O(1) O(1)
find by value O(n) O(n) O(n)
insert_after by target value O(n) O(n) O(n)
delete_first by value O(n) O(n) O(n)
values snapshot O(n) time and output space O(n) time and output space O(n) time and output space
Extra navigation Forward only Forward and reverse Forward with wraparound

The search is included in these public operations. If a separate API accepted an already-known valid doubly linked node, unlinking could be O(1). This lesson deliberately uses first-match value methods to keep caller behaviour consistent.

Each structure has O(n) total storage, with different link overhead and practical allocation costs. A maintained tail gives singly linked append constant link work but does not remove the predecessor-search cost for tail deletion.

25 | TEST STRUCTURE AS WELL AS OUTPUT

For every class, test append and prepend on empty and non-empty lists, insertion after head and tail, and deletion of head, middle, tail and the only node. Include duplicate values and absent targets. A failed request must preserve size and sequence.

For singly linked lists, head and tail must both be None exactly when empty, and tail.next must be None when non-empty. For doubly linked lists, also check head.prev and each reciprocal neighbour route; reverse_values should match reversed forward values.

For circular lists, size zero implies no tail. Otherwise exactly size next steps from head must visit distinct node identities and return to head, and the final visited node must be tail. Repeated values are allowed, so compare node identity for this structural test.

26 | BUILD, TRACE, THEN EXPLAIN

Your challenge is a small playlist tool supporting add-last, add-first, insert-after-first-match, remove-first-match and show-all. Implement it using two of the representations, keep the same user-facing contract and use the same tests on both.

Explain each update in terms of the old neighbour, the preserved successor and the new route. If a method fails, draw the smallest failing state first. A singleton or endpoint often exposes the missing branch faster than a large random example.

The next lesson introduces binary search trees, where nodes can have left and right children instead of a single sequence successor. Carry forward the habit of defining the invariant before changing references.

MATCH THE CONSTRUCTION OPERATION

Terminology

Terminology

Construction

Creating the node types, metadata and operations that maintain a linked structure.

Head

The reference or derived entry point identifying the first logical node.

Tail

The final logical node, retained as metadata in these implementations.

SNode

A singly linked node with value and next fields.

DNode

A doubly linked node with value, prev and next fields.

CNode

A node used in the circular singly linked implementation.

append

Insert a new node at the logical end.

prepend

Insert a new node at the logical beginning.

find

Return the first matching node, or None in the Python contract.

First-match policy

Only the first matching value from head is selected by the operation.

insert_after

Locate a matching node and splice a new node after it.

delete_first

Remove the first matching node and report success or absence.

Predecessor

The node immediately before the current node in the sequence.

Successor

The next node in the logical sequence.

Endpoint update

A change to head or tail required by an insertion or removal.

Singleton list

A linked list containing exactly one node.

Empty state

The representation used when no nodes remain, including size zero.

Detachment

Clearing a removed node’s old links after reconnecting the live structure.

Reciprocal links

Matching next and prev routes between adjacent doubly linked nodes.

Circular closure

The final next reference returns to the logical head.

Derived head

An entry point computed from other metadata, here tail.next.

Bounded traversal

Visiting a specified number of nodes rather than waiting for an absent link.

Rotation

Changing the logical start of a circle without necessarily moving or relinking nodes.

Identity comparison

Checking whether two references reach the same object.

Metadata

Information such as endpoints and size maintained alongside nodes.

Invariant

A structural property each complete operation must preserve.

Absent-target result

A documented failure result, here False, with no mutation.

Traversal snapshot

A separate collection of values produced from the current chain.

Known-node unlinking

Removal starting with an available node and required neighbour references.

Contract consistency

Different representations preserve the same stated observable rules.

Questions

Questions

CHECK YOUR UNDERSTANDING

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

1. Which define the shared first-match contract?
2. For appending to an empty linear list, which must hold?
3. Which preserve a singly linked prepend?
4. Which are necessary for doubly linked insertion between A and B?
5. When deleting a doubly linked only node, what is correct?
6. Which describe this circular representation?
7. Which stop circular search safely under the invariant?
8. What distinguishes circular append and prepend here?
9. Which describe the public method costs?
10. Which tests check structure?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Describe the initialization of the three list implementations.

2. Explain appending to an empty and non-empty singly linked list.

3. Construct the reference updates to insert X after a known A in a singly linked list.

4. Explain why singly linked deletion needs previous and current.

5. Describe how doubly linked deletion handles both endpoints.

6. Explain why circular head is derived from tail.next.

7. Distinguish circular append and prepend.

8. Trace circular deletion from a singleton.

9. Explain why circular search can use range(size).

10. Evaluate the cost of delete_first in the doubly linked implementation.

11. Construct a test plan for duplicates, missing targets and endpoints.

12. Explain rotation for the circular turn manager.

CONSTRUCT AND APPLY | A TURN MANAGER

Construct a turn manager using CircularList. Append Maya, Leo and Sam, rotate once, remove Leo and report the new head and sequence. Then remove the remaining players and append a new player to demonstrate safe empty-state reuse.

Reveal a worked application
turns = CircularList()
for player in ("Maya", "Leo", "Sam"):
    turns.append(player)
turns.rotate()
turns.delete_first("Leo")
assert turns.head.value == "Sam"
assert turns.values() == ["Sam", "Maya"]
turns.delete_first("Sam")
turns.delete_first("Maya")
assert turns.tail is None and turns.size == 0
turns.append("Jenny")
assert turns.head is turns.tail
assert turns.tail.next is turns.head

The last assertions verify a valid singleton circle rather than only its printed value. Explain why the tail’s next route supplies the new head after removing Leo.

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.3 Construct Linked Lists (HL) is coming soon. Complete the matching task and written questions in your exercise book.