Linked Lists

IB Syllabus: B4.1.2, B4.1.3 (HL) – Evaluate linked lists. Construct and apply linked lists: singly linked – insertion, deletion, traversal, search.

This page is HL only.

Table of Contents

1. Key Concepts
   1. The Node
   2. Head and Tail
   3. Key Terminology
   4. Linked List vs Array
2. Worked Examples
   1. Example 1: Building a Linked List from Scratch
   2. Example 2: Add to End, Search, and Remove
   3. Example 3: Insertion at a Specific Position
3. Quick Code Check
4. Trace Exercise
5. Code Completion
6. Spot the Bug
7. Output Prediction
8. Practice Exercises
   1. Core
   2. Extension
   3. Challenge
9. Connections

---

Key Concepts

A linked list is a linear collection of elements called nodes, where each node stores data and a reference (pointer) to the next node in the sequence. Unlike an array, the elements are not stored in contiguous memory – each node can be anywhere in the heap, connected only by references.

The Node

Every node in a singly linked list has two parts:

• Data – the value stored in the node
• Next – a reference to the next node (or null if it is the last node)

public class Node {
    String data;
    Node next;

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

The Node class is self-referential – the field next is of type Node, meaning each node points to another node of the same type.

Head and Tail

• The head is a reference to the first node in the list. It is how we access the list.
• The tail is the last node in the list. Its next field is null.
• An empty list has head == null.

Key Terminology

Term	Meaning
Node	A single element containing data and a pointer
Head	Reference to the first node
Tail	The last node (next is null)
Successor	The next node after a given node
Predecessor	The node before a given node
Null pointer	A reference that points to nothing – marks the end of the list
Traversal	Visiting every node from head to tail by following next references

Linked List vs Array

Feature	Array	Singly Linked List
Size	Fixed at creation	Grows/shrinks dynamically
Memory layout	Contiguous block	Scattered nodes connected by references
Access by index	O(1) – direct	O(n) – must traverse from head
Insert at front	O(n) – shift all elements	O(1) – update head reference
Insert at end	O(1) if space available	O(n) – must traverse to tail (O(1) with tail reference)
Delete from front	O(n) – shift all elements	O(1) – update head reference
Memory per element	Data only	Data + one reference (overhead)

---

Worked Examples

Example 1: Building a Linked List from Scratch

public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        head = null;
    }

    // Add a new node to the front of the list
    public void addToFront(String data) {
        Node newNode = new Node(data);
        newNode.next = head;   // point new node to current head
        head = newNode;        // update head to new node
    }

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

    // Return the number of nodes
    public int size() {
        int count = 0;
        Node current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

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

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

Output:

Apple -> Banana -> Cherry -> null
Size: 3

Notice how addToFront reverses the insertion order: “Cherry” was added first but ends up at the tail, because each new node is placed before the current head.

Order of operations matters. In addToFront, you must set newNode.next = head before updating head = newNode. If you reverse these, the old head is lost and the list breaks. This is the most common linked list mistake.

Example 2: Add to End, Search, and Remove

public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        head = null;
    }

    public void addToFront(String data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Add a new node to the end of the list
    public void addToEnd(String data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;    // empty list: new node becomes head
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;  // traverse to last node
        }
        current.next = newNode;      // link last node to new node
    }

    // Search for a value -- return true if found
    public boolean contains(String target) {
        Node current = head;
        while (current != null) {
            if (current.data.equals(target)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // Remove the first occurrence of a value
    public boolean remove(String target) {
        if (head == null) {
            return false;              // empty list
        }
        if (head.data.equals(target)) {
            head = head.next;          // remove head node
            return true;
        }
        Node current = head;
        while (current.next != null) {
            if (current.next.data.equals(target)) {
                current.next = current.next.next;  // skip the target node
                return true;
            }
            current = current.next;
        }
        return false;                  // not found
    }

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

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

        System.out.println("Initial list:");
        roster.printAll();

        System.out.println("Contains Ben? " + roster.contains("Ben"));
        System.out.println("Contains Eve? " + roster.contains("Eve"));

        roster.remove("Ben");
        System.out.println("After removing Ben:");
        roster.printAll();

        roster.remove("Aiko");
        System.out.println("After removing Aiko (head):");
        roster.printAll();
    }
}

Output:

Initial list:
Aiko -> Ben -> Carlos -> Diana -> null
Contains Ben? true
Contains Eve? false
After removing Ben:
Aiko -> Carlos -> Diana -> null
After removing Aiko (head):
Carlos -> Diana -> null

How remove works:

• Remove head: if the target is the head node, simply set head = head.next – the old head is skipped.
• Remove middle/end: traverse until current.next holds the target. Then set current.next = current.next.next to skip the target node. The skipped node is no longer reachable and will be garbage collected.

Example 3: Insertion at a Specific Position

// Insert at a given index (0-based)
public void insertAt(int index, String data) {
    if (index == 0) {
        addToFront(data);
        return;
    }
    Node newNode = new Node(data);
    Node current = head;
    for (int i = 0; i < index - 1; i++) {
        if (current == null) {
            return;  // index out of bounds
        }
        current = current.next;
    }
    if (current == null) {
        return;  // index out of bounds
    }
    newNode.next = current.next;   // new node points to successor
    current.next = newNode;        // predecessor points to new node
}

Inserting in the middle requires finding the predecessor node (the node at index - 1), then redirecting references:

1. Set newNode.next to the predecessor’s current successor
2. Set the predecessor’s next to the new node

No shifting of elements is needed – just two reference updates.

---

Quick Code Check

Q1. What two things does a node in a singly linked list contain?

Q2. How is the end of a singly linked list identified?

Q3. What is the time complexity of adding a node to the front of a singly linked list?

Q4. In the addToFront method, why must newNode.next = head come before head = newNode?

Q5. To remove a node from the middle of a singly linked list, you:

Q6. What is the time complexity of accessing the element at index k in a singly linked list?

---

Trace Exercise

Trace through the following code and fill in the state of the list after each operation.

SinglyLinkedList list = new SinglyLinkedList();
list.addToFront("C");
list.addToFront("B");
list.addToFront("A");
list.addToEnd("D");
list.remove("B");

After operation	Head node	Full list (head to tail)	size()
addToFront("C")		C -> null
addToFront("B")			2
addToFront("A")		A -> B -> C -> null
addToEnd("D")	A
remove("B")			3

---

Code Completion

Complete the contains method that searches the linked list for a target value.

Fill in the blanks to traverse the list and search for the target:

public boolean contains(String target) {
    Node current = ;
    while (current != ) {
        if (current.data.(target)) {
            return true;
        }
        current = current.;
    }
    return false;
}

---

Complete the addToEnd method that adds a node after the last node.

Fill in the blanks:

public void addToEnd(String data) {
    Node newNode = new (data);
    if (head == null) {
        head = newNode;
        return;
    }
    Node current = head;
    while (current. != null) {
        current = current.next;
    }
    current. = newNode;
}

---

Spot the Bug

This addToFront method loses all existing nodes when adding:

1public void addToFront(String data) { 2 Node newNode = new Node(data); 3 head = newNode; 4 newNode.next = head; 5}

Pick the correct fix:

---

This addToEnd method throws a NullPointerException:

1public void addToEnd(String data) { 2 Node newNode = new Node(data); 3 Node current = head; 4 while (current != null) { 5 current = current.next; 6 } 7 current.next = newNode; 8}

Pick the correct fix for line 4:

---

Output Prediction

What does this code print?

SinglyLinkedList nums = new SinglyLinkedList();
nums.addToFront("20");
nums.addToFront("30");
nums.addToFront("10");
nums.printAll();
System.out.println(nums.size());

Type the exact output:

---

What does this code print?

SinglyLinkedList colors = new SinglyLinkedList();
colors.addToEnd("Red");
colors.addToEnd("Green");
colors.addToEnd("Blue");
colors.remove("Green");
colors.printAll();
System.out.println(colors.contains("Green"));

Type the exact output:

---

Practice Exercises

Core

1. Build and print – Create a SinglyLinkedList, add five city names using addToEnd, then call printAll to display the list. Verify the output order matches the insertion order.
2. Count nodes – Without looking at the size() method above, write your own version that traverses the list and counts nodes. Test it on a list with 0, 1, and 5 elements.
3. Remove head – Create a list with three elements. Remove the head element. Print the list. Then remove the head again. Print the list. Verify the output at each step.

Extension

1. Get by index – Write a method public String get(int index) that returns the data at a given index (0-based). Traverse the list index times from the head. Return null if the index is out of bounds.
2. Insert after value – Write a method public void insertAfter(String target, String data) that finds the node containing target and inserts a new node with data immediately after it. Handle the case where target is not found.

Challenge

1. Reverse the list – Write a method public void reverse() that reverses the linked list in place by redirecting all next references. Use three pointers: prev, current, and nextNode. After reversal, the old tail should be the new head.
2. Detect and describe – A friend claims: “Linked lists are always better than arrays because insertion is O(1).” Write a paragraph explaining why this claim is misleading. Include at least two scenarios where an array would be the better choice, with reference to time complexity.

---

Connections

• Prerequisites: What Are ADTs? – understanding interface vs implementation
• Prerequisites: Object References – null, aliasing, and reference semantics
• Related: 1D Arrays – the static alternative for sequential data
• Next: Ordered Linked Lists – maintaining sorted order during insertion