IB Computer Science HL · Year 2 · Lesson 24

Linked-list operations and applications

Integrate insertion, deletion, traversal and search, including ordered insertion and exam-style edge cases.

Paper 250 minutesB4.1.2 · B4.1.3

Retrieve first, attempt the task, then reveal.

Course home IA hub 2027 case study

Targets

Operations matter more than memorizing a diagram

2 / 10

construct linked-list search, insertion, deletion and traversal in context;
describe ordered insertion without relying on a later sort;
handle empty/head/middle/end cases explicitly;
evaluate whether linked-list trade-offs fit the application compared with an array/list structure.

B4.1.2B4.1.3

Page 2 of 10

Learn + retrieve

Rapid Recall Deck

3 / 10

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”.

Recall deck answers

What four linked-list operations are explicitly required in B4? Insertion, deletion, traversal and search.
What must an ordered linked-list insertion preserve? The ordering rule while reconnecting the new node without losing the remaining chain.
Why is head insertion a special case? There is no previous node; head itself must be updated.
Why is deletion of the head a special case? The first reference must move directly to the second node.
What is a traversal pointer/reference used for? To walk through the structure without changing head.
What is one benefit of maintaining a linked list in sorted order? Later traversal follows the desired order without running a separate sorting algorithm.
What is one cost of maintaining sorted order? Insertion must search for the correct position before rewiring links.
Why can linked-list search still be O(n) even when insertions are efficient? Without a separate index or special structure, nodes are checked sequentially.
What edge cases should linked-list code consider? Empty list, insertion/deletion at head, target absent, one-node list and end-of-list updates.
What makes a linked-list solution exam-ready? Correct traversal/stopping logic, safe reference updates and behaviour matching the stated preconditions.

Page 3 of 10

Traverse without disturbing head

4 / 10

class PlayerNode:
    def __init__(self, name, score):
        self.name = name
        self.score = score
        self.next = None

class Leaderboard:
    def __init__(self):
        self.head = None

Construct search

Construct find_player(name) to return the first matching node, or None when absent.

def find_player(self, name):
    current = self.head
    while current is not None:
        if current.name == name:
            return current
        current = current.next
    return None

Page 4 of 10

Specimen-style reasoning

Describe the steps before translating them to code

5 / 10

Ordering ruleThe leaderboard is permanently stored in descending score order. The list is not empty. new_node has already been created.

Describe ordered insertion — no code yet

Head case — when must the new node become the head?

Traversal — what condition identifies the insertion position?

Pointer safety — which link should the new node save before its predecessor is redirected?

End case — what if the new score is the smallest?

If the new score should appear before the current head, point the new node to the old head and make it the new head.
Otherwise traverse while the next node exists and should remain ahead of the new score.
Set new_node.next to the predecessor’s old next.
Redirect the predecessor’s next to new_node. If the predecessor was the tail, the saved next value is None, so the new node becomes the tail.

Page 5 of 10

Construct + trace

Ordered insertion preserves structure and order

6 / 10

def add_in_order(self, new_node):
    if self.head is None or new_node.score > self.head.score:
        new_node.next = self.head
        self.head = new_node
        return

    current = self.head
    while current.next is not None and current.next.score >= new_node.score:
        current = current.next

    new_node.next = current.next
    current.next = new_node

Trace insertion

Start with scores 90 → 70 → 40. Trace insertion of score 75. Which node becomes current when the loop stops, and what is the final order?

current stops at the 90 node because the next score 70 is not greater than or equal to 75. The new node is inserted between 90 and 70, giving 90 → 75 → 70 → 40.

Explain pointer safety

Why does the method assign new_node.next = current.next before current.next = new_node?

The new node must first preserve the reference to the remainder of the list. Redirecting current.next first would remove the predecessor’s direct reference to that remainder.

Page 6 of 10

Deletion

Use the predecessor to bypass the removed node

7 / 10

Construct deletion by name

Construct remove_player(name). Return True if a node is deleted, otherwise False. Handle deletion of the head correctly.

def remove_player(self, name):
    if self.head is None:
        return False

    if self.head.name == name:
        self.head = self.head.next
        return True

    current = self.head
    while current.next is not None:
        if current.next.name == name:
            current.next = current.next.next
            return True
        current = current.next

    return False

Page 7 of 10

Exam lens

The specimen expects both code and algorithm descriptions

8 / 10

Teacher-created Paper 2 mini-set

1. A sorted singly linked list stores 12, 18, 31, 44. Describe the reference changes needed to insert 25.

2. Construct a traversal that prints every stored score.

3. Evaluate maintaining a scoreboard as a linked list in sorted order when new entries are frequent but the program rarely accesses a specific numeric index.

Traverse to 18, set the new node’s next to 31, then redirect 18’s next to the new node.

current = self.head
while current is not None:
    print(current.score)
    current = current.next

A strong evaluation recognizes the insertion advantage once position is found and natural maintained order, balanced against O(n) traversal/search and extra reference memory; the usage makes linked lists plausible because indexed access is unimportant.

Page 8 of 10

Exit check

Robust code survives the boundaries

9 / 10

Exit edge cases

List four linked-list edge cases you would test for add_in_order() or remove_player(), and state what correct behaviour should look like.

Examples: empty list; new node belongs at head; new node belongs at tail; one-node list; deleting the head; deleting a middle/tail node; target absent; equal scores under the chosen ordering rule. Correct behaviour must preserve all remaining links and the ordering/preconditions.

Page 9 of 10

Homework

Finish the learning cycle

10 / 10

IA — main task

Continue Criterion D implementation/testing and ensure your test evidence includes at least one boundary/edge case.

IA task complete

Paper 2 — short practice

Redo ordered insertion and deletion from memory. Then explain why the official specimen can ask for code in one part and a no-code algorithm description in another.

Practice complete

Designed by David Xu

Educators and students are welcome to use these materials for non-commercial teaching and learning with attribution. Please share the original link when possible. Reposting, redistributing modified copies, removing attribution, or commercial use requires prior permission.

End of Lesson 24.