Ordered Linked Lists

IB Syllabus: B4.1.3 (HL) – Construct and apply linked lists: singly linked – insertion, deletion, traversal, search. This page focuses on maintaining sorted order.

This page is HL only.

Key Concepts
Worked Examples
Quick Code Check
Trace Exercise
Code Completion
Spot the Bug
Output Prediction
Practice Exercises
1. Core
2. Extension
3. Challenge
Connections

Key Concepts

An ordered linked list (also called a sorted linked list) is a singly linked list where nodes are always arranged in ascending (or descending) order based on their data values. Unlike a regular linked list where new items are added to the front or end, an ordered linked list inserts each new item at the correct position to maintain the sorted property.

Why Use an Ordered List?

Feature	Unordered List	Ordered List
Insertion	O(1) at front	O(n) – must find correct position
Search (item exists)	O(n) – must check every node	O(n) worst case, but can stop early
Search (item missing)	O(n) – must check every node	O(n) worst case, but stops as soon as a larger value is passed
Traversal output	Arbitrary order	Already sorted – no extra sorting step
Deletion	O(n) to find	O(n) to find, can stop early if passed

The key advantage: early termination. When searching for a value that does not exist, an unordered list must visit every node. An ordered list can stop as soon as it reaches a node with a larger value – the target cannot appear later in the list.

The Sorted Insertion Algorithm

To insert a value into an ordered list, you must handle four cases:

Empty list – the new node becomes the head
Insert before head – the new value is smaller than the current head
Insert in the middle – traverse until you find the first node larger than the new value, insert before it
Insert at the tail – the new value is larger than every existing node

Pointer order matters. When inserting in the middle, always set newNode.next to the successor before updating the predecessor’s next. Reversing this order loses the reference to the rest of the list.

Reusing the Node Class

This page uses the same Node class from the Linked Lists page:

public class Node {
    String data;
    Node next;

    public Node(String data) {
        this.data = data;
        this.next = null;
    }
}

Worked Examples

Example 1: Sorted Insertion

public class OrderedLinkedList {
    private Node head;

    public OrderedLinkedList() {
        head = null;
    }

    // Insert in sorted (ascending) order
    public void insertInOrder(String data) {
        Node newNode = new Node(data);

        // Case 1 & 2: empty list or insert before head
        if (head == null || data.compareTo(head.data) < 0) {
            newNode.next = head;
            head = newNode;
            return;
        }

        // Case 3 & 4: find the correct position
        Node current = head;
        while (current.next != null && current.next.data.compareTo(data) < 0) {
            current = current.next;
        }

        // Insert after current
        newNode.next = current.next;
        current.next = newNode;
    }

    public void printAll() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public int size() {
        int count = 0;
        Node current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

    public static void main(String[] args) {
        OrderedLinkedList roster = new OrderedLinkedList();
        roster.insertInOrder("Diana");
        roster.insertInOrder("Ben");
        roster.insertInOrder("Eve");
        roster.insertInOrder("Aiko");
        roster.insertInOrder("Carlos");

        roster.printAll();
        System.out.println("Size: " + roster.size());
    }
}

Output:

Aiko -> Ben -> Carlos -> Diana -> Eve -> null
Size: 5

Despite being inserted in a random order, the names appear sorted because insertInOrder places each name at the correct alphabetical position. The compareTo method returns a negative value if the left string comes before the right alphabetically, zero if equal, and positive if after.

How each insertion works:

Inserted	List before	Position	List after
Diana	(empty)	Head (case 1)	Diana
Ben	Diana	Before head (case 2)	Ben -> Diana
Eve	Ben -> Diana	After Diana (case 4)	Ben -> Diana -> Eve
Aiko	Ben -> Diana -> Eve	Before head (case 2)	Aiko -> Ben -> Diana -> Eve
Carlos	Aiko -> Ben -> Diana -> Eve	Between Ben and Diana (case 3)	Aiko -> Ben -> Carlos -> Diana -> Eve

Example 2: Search with Early Termination

// Search that stops early when the target cannot exist
public boolean contains(String target) {
    Node current = head;
    while (current != null) {
        int comparison = current.data.compareTo(target);
        if (comparison == 0) {
            return true;     // found it
        }
        if (comparison > 0) {
            return false;    // passed where it would be -- not in list
        }
        current = current.next;
    }
    return false;            // reached end of list
}

In an unordered list, contains("Carl") would check every single node. In an ordered list, the method stops as soon as it reaches “Carlos” – because “Carlos” comes after “Carl” alphabetically, “Carl” cannot appear later in the list.

Example 3: Remove from an Ordered List

// Remove first occurrence, maintaining order
public boolean remove(String target) {
    if (head == null) {
        return false;
    }
    if (head.data.equals(target)) {
        head = head.next;
        return true;
    }
    Node current = head;
    while (current.next != null) {
        int comparison = current.next.data.compareTo(target);
        if (comparison == 0) {
            current.next = current.next.next;  // skip target node
            return true;
        }
        if (comparison > 0) {
            return false;    // passed where it would be
        }
        current = current.next;
    }
    return false;
}

public static void main(String[] args) {
    OrderedLinkedList list = new OrderedLinkedList();
    list.insertInOrder("Mango");
    list.insertInOrder("Apple");
    list.insertInOrder("Cherry");
    list.insertInOrder("Banana");

    System.out.println("Before:");
    list.printAll();

    list.remove("Cherry");
    System.out.println("After removing Cherry:");
    list.printAll();

    System.out.println("Contains Banana? " + list.contains("Banana"));
    System.out.println("Contains Cherry? " + list.contains("Cherry"));
}

Output:

Before:
Apple -> Banana -> Cherry -> Mango -> null
After removing Cherry:
Apple -> Banana -> Mango -> null
Contains Banana? true
Contains Cherry? false

Quick Code Check

Q1. What is the key difference between an ordered and an unordered linked list?

Q2. What does "Apple".compareTo("Cherry") return?

Q3. When inserting into an ordered list, what happens if the new value is smaller than the head?

Q4. Why can an ordered linked list search terminate early when the target is not found?

Q5. What is the time complexity of inserting into an ordered linked list?

Trace Exercise

Trace the state of the ordered linked list after each insertInOrder call.

OrderedLinkedList list = new OrderedLinkedList();
list.insertInOrder("Mango");
list.insertInOrder("Apple");
list.insertInOrder("Cherry");
list.insertInOrder("Banana");
list.insertInOrder("Peach");

After inserting	Insertion case	Full list (head to tail)
Mango		Mango -> null
Apple
Cherry
Banana
Peach

Code Completion

Complete the insertInOrder method to insert a value at the correct sorted position.

Fill in the blanks to find the insertion point and insert:

public void insertInOrder(String data) {
    Node newNode = new Node(data);
    if (head == null || data.(head.data) < 0) {
        newNode.next = head;
        head = ;
        return;
    }
    Node current = head;
    while (current. != null && current.next.data.compareTo(data) < 0) {
        current = current.next;
    }
    newNode.next = current.next;
    current. = newNode;
}

Complete the early-termination search method.

Fill in the blanks for the search that stops when it passes the target:

public boolean contains(String target) {
    Node current = head;
    while (current != null) {
        int comparison = current.data.compareTo();
        if (comparison == ) {
            return true;
        }
        if (comparison > 0) {
            return ;
        }
        current = current.next;
    }
    return false;
}

Spot the Bug

This insertInOrder method inserts "Apple" after "Mango" instead of before it:

1public void insertInOrder(String data) { 2 Node newNode = new Node(data); 3 if (head == null || data.compareTo(head.data) > 0) { 4 newNode.next = head; 5 head = newNode; 6 return; 7 }

Pick the correct fix for line 3:

This insertion loop puts values in the wrong position -- "Cherry" ends up before "Apple":

1// After head check passed: 2Node current = head; 3while (current.next != null && 4 current.next.data.compareTo(data) > 0) { 5 current = current.next; 6}

Pick the correct fix for line 4:

Output Prediction

What does this code print?

OrderedLinkedList nums = new OrderedLinkedList();
nums.insertInOrder("50");
nums.insertInOrder("20");
nums.insertInOrder("40");
nums.insertInOrder("10");
nums.insertInOrder("30");
nums.printAll();

Type the exact output: