Java LinkedList — Node, first and next for the exam’s linked list (no ArrayList and without losing the queue)

When I opened the brief for Practical Exam 3, the first line in bold said: Java arrays and collections may not be used. No ArrayList, no LinkedList, no Stack. I was given Node, a ContainerBase with a first and an empty class that had to inherit from it. I’d already built linked lists in Python, but in Java every null is a NullPointerException waiting to happen, and == on text doesn’t do what it seems to. This article is what I wish I’d read before that exam.

This is Java LinkedList the way FP2 asks for it: a linked list written by hand, with nodes that point at one another. We use the same template as the exam (Node with value and next, ContainerBase with first and toString(), and your class with extends) and the usual example: the booking queue for a book at the faculty library (the rule that staff jump the queue is made up). Every program has been compiled and run with Java 21, and the outputs are real.

If you’re coming from Python LinkedList, the idea is identical; the syntax changes, along with two traps of Java’s own. And if you’re coming from the last topic, Java collections, here you’ll build from the inside something similar to what java.util.LinkedList gives you ready-made.

What a linked list is and why the exam doesn’t allow ArrayList

An ArrayList stores its elements in an array inside: consecutive slots. That’s why get(3) is instant, but add(0, x) has to shift every element one place to the right. A linked list does the opposite: each element lives in its own object, a node, anywhere in memory, and each node knows who comes after it. The list only stores the first one.

Operation	ArrayList	Linked list (only first)
Read position i	O(1): direct jump	O(n): i hops from the head
Insert at the front	O(n): shifts everything	O(1): two references change
Insert at the end	O(1) almost always	O(n): you have to reach the last node (O(1) with last)
Delete when you’re already on the previous node	O(n)	O(1)
Search for a value	O(n)	O(n)

Why does the exam forbid collections? Because what’s being assessed is whether you can handle references by hand: link, unlink, traverse and not leave loose nodes behind. It’s the foundation of the trees and graphs that come in other subjects.

The node: value and next

A node stores two things: the data (value) and the reference to the next node (next), which is null in the last one. This is the Node class given in the exam, with a String as its data:

public class Node {
    public String value;     // the data: who made the booking
    public Node next;        // the next node (null if it is the last)

    public Node(String value) {
        this.value = value;
    }
}

We create three nodes and chain them by hand:

public class Nodes {
    public static void main(String[] args) {
        Node laura = new Node("Laura");
        Node pablo = new Node("Pablo");
        Node marta = new Node("Marta");
        laura.next = pablo;                              // Laura points at Pablo
        pablo.next = marta;                              // Pablo points at Marta; marta.next is still null

        System.out.println(laura.value);                 // the data of the first node
        System.out.println(laura.next.value);            // one hop
        System.out.println(laura.next.next.value);       // two hops
        System.out.println(laura.next.next.next);        // three hops: null
        System.out.println(laura.next == pablo);         // the SAME object?

        for (Node n = laura; n != null; n = n.next) {    // the usual traversal
            System.out.print(n.value + " -> ");
        }
        System.out.println("null");

        System.out.println(laura.next.next.next.value);  // one hop too many
    }
}

Output:

Laura
Pablo
Marta
null
true
Laura -> Pablo -> Marta -> null
Exception in thread "main" java.lang.NullPointerException: Cannot read field "value" because "laura.next.next.next" is null
        at Nodes.main(Nodes.java:20)

• laura.next.value gives Pablo: from Laura you follow one arrow.
• laura.next.next.next gives null: Marta is the last one and her next was never changed.
• laura.next == pablo gives true: it isn’t a copy, it’s the same object. Here == is exactly what we want (comparing references).
• The for is the classic traversal in Java: start at the head, move on with n = n.next and stop when n is null. You’ll write it in almost every method.
• The last line asks for .value of null and Java throws NullPointerException. Since Java 14 the message says exactly what was null: "laura.next.next.next" is null.

The exam’s base class: ContainerBase and first

In the exam, the list doesn’t start from scratch: you’re given a base class that stores the head and knows how to draw itself. This is ours, the same as the one in the practical mock exam:

public class ContainerBase {
    protected Node first;    // the head: the first node (null if empty)

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("➡");
        int steps = 0;       // cap in case there is a cycle
        for (Node n = first; n != null && steps < 1000; n = n.next, steps++) {
            sb.append(n.value).append("->");
        }
        return sb.append("null").toString();
    }
}

Three things to look at:

• first is protected: classes that inherit from ContainerBase can use it. Your class will handle it directly.
• toString() is already written and draws the list as ➡Laura->Pablo->null. Thanks to it, System.out.println(queue) shows the whole chain.
• The 1000-step cap is a safety net: if a bug of yours makes the list form a cycle, toString() doesn’t hang forever.

Your class inherits from it with extends and adds whatever methods the brief asks for. Ours is called BookingQueue.

Inserting at the front: the order of two lines

public void insertFront(String member) {
    Node newNode = new Node(member);
    newNode.next = first;                   // 1. the new node points at the current head...
    first = newNode;                        // 2. ...and it becomes the head
    size++;
}

The order is not negotiable: first newNode.next = first (the new node points at the current head) and then first = newNode. The other way round, first is already the new node when you do newNode.next = first, so the node points at itself and the rest of the queue is left with nobody pointing at it. That’s what the “Wrong” row of the drawing shows: toString() would print “Ana” a thousand times, up to its cap.

Notice the size++ too: we keep the size in an attribute of our own (private int size) so that getSize() doesn’t have to traverse. In exchange, every method that adds or removes nodes has to update it.

Inserting at the end and traversing

public void insertBack(String member) {
    Node newNode = new Node(member);
    if (first == null) {                   // empty list: the new node is the head
        first = newNode;
    } else {
        Node current = first;
        while (current.next != null) {     // we stop AT the last one, not after it
            current = current.next;
        }
        current.next = newNode;
    }
    size++;
}

• The empty list is a separate case: if first is null, there’s no last node to hook onto and the new one becomes the head. Without that if, first.next would throw NullPointerException.
• while (current.next != null) stops at the last node. To visit them all you use n != null; to stop at the last one and hook something onto it, current.next != null. Mixing them up is the quiz’s mistake.

This is the trace when inserting Iván behind Ana -> Laura -> Pablo -> Marta:

Lap	current	current.next	Does the while go on?
Before	Ana	Laura	Yes
1	Laura	Pablo	Yes
2	Pablo	Marta	Yes
3	Marta	null	No: Marta is the last one
After	Marta	Iván	(the new node is hooked on)

Four nodes visited to add one: that’s why inserting at the end is O(n) if you only store first. In the practice we add a last so it becomes instant.

Searching is the same traversal with a comparison:

public boolean contains(String member) {
    for (Node n = first; n != null; n = n.next) {
        if (n.value.equals(member)) {      // equals: compares the text, not the address
            return true;
        }
    }
    return false;
}

Deleting: the previous/current pair

To delete a node, the previous one has to skip over it: previous.next = current.next. The deleted node is left with nobody pointing at it and Java’s garbage collector frees it. Since you can’t go backwards from a node, you traverse with two references that move together. The head has no previous node: it’s a separate case.

public boolean remove(String member) {
    if (first == null) {
        return false;
    }
    if (first.value.equals(member)) {      // case 1: it is the head
        first = first.next;
        size--;
        return true;
    }
    Node previous = first;                 // cases 2 and 3: we look for its PREVIOUS node
    Node current = first.next;
    while (current != null) {
        if (current.value.equals(member)) {
            previous.next = current.next;  // previous skips over current
            size--;
            return true;
        }
        previous = current;                // both move forward, always as a pair
        current = current.next;
    }
    return false;                          // it was not there
}

Trace of remove("Pablo") on Laura -> Pablo -> Marta -> Iván, and of remove("Iván"):

Call	previous	current	current.value.equals(member)?	What happens
remove("Pablo")	Laura	Pablo	Yes	Laura.next = Marta, size--, true
remove("Iván"), lap 1	Laura	Marta	No	both move on
remove("Iván"), lap 2	Marta	Iván	Yes	Marta.next = null, size--, true

The method returns true or false instead of throwing an exception, as exam briefs usually ask (“return false if it wasn’t there”). Case 3 (deleting the last one) is the same code as case 2: current.next is null and the previous node becomes the last one.

The complete class in action

The whole BookingQueue class:

/** Booking queue for a book: a linked list that inherits from ContainerBase. */
public class BookingQueue extends ContainerBase {
    private int size;                          // kept up to date so we never traverse

    public void insertFront(String member) {
        Node newNode = new Node(member);
        newNode.next = first;                  // 1. the new node points at the current head...
        first = newNode;                       // 2. ...and it becomes the head
        size++;
    }

    public void insertBack(String member) {
        Node newNode = new Node(member);
        if (first == null) {                   // empty list: the new node is the head
            first = newNode;
        } else {
            Node current = first;
            while (current.next != null) {     // we stop AT the last one, not after it
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    public boolean contains(String member) {
        for (Node n = first; n != null; n = n.next) {
            if (n.value.equals(member)) {      // equals: compares the text, not the address
                return true;
            }
        }
        return false;
    }

    public boolean remove(String member) {
        if (first == null) {
            return false;
        }
        if (first.value.equals(member)) {      // case 1: it is the head
            first = first.next;
            size--;
            return true;
        }
        Node previous = first;                 // cases 2 and 3: we look for its PREVIOUS node
        Node current = first.next;
        while (current != null) {
            if (current.value.equals(member)) {
                previous.next = current.next;  // previous skips over current
                size--;
                return true;
            }
            previous = current;                // both move forward, always as a pair
            current = current.next;
        }
        return false;                          // it was not there
    }

    public int getSize() {
        return size;
    }
}

And a test that goes through the three deletion cases and a member who isn’t there:

public class QueueTest {
    public static void main(String[] args) {
        BookingQueue queue = new BookingQueue();
        System.out.println("Empty: " + queue + " | size = " + queue.getSize());
        queue.insertBack("Laura");                    // normal bookings: at the end
        queue.insertBack("Pablo");
        queue.insertBack("Marta");
        System.out.println("Bookings: " + queue);
        queue.insertFront("Ana");                     // Ana is staff: she goes first (made-up rule)
        System.out.println("Ana in front: " + queue);
        queue.insertBack("Iván");
        System.out.println("Iván at the back: " + queue + " | size = " + queue.getSize());
        System.out.println("Pablo? " + queue.contains("Pablo") + " | Nora? " + queue.contains("Nora"));
        System.out.println("Removing Ana (head): " + queue.remove("Ana") + " " + queue);
        System.out.println("Removing Pablo (middle): " + queue.remove("Pablo") + " " + queue);
        System.out.println("Removing Iván (last): " + queue.remove("Iván") + " " + queue);
        System.out.println("Removing Nora (not there): " + queue.remove("Nora") + " | size = " + queue.getSize());
    }
}

Output:

Empty: ➡null | size = 0
Bookings: ➡Laura->Pablo->Marta->null
Ana in front: ➡Ana->Laura->Pablo->Marta->null
Iván at the back: ➡Ana->Laura->Pablo->Marta->Iván->null | size = 5
Pablo? true | Nora? false
Removing Ana (head): true ➡Laura->Pablo->Marta->Iván->null
Removing Pablo (middle): true ➡Laura->Marta->Iván->null
Removing Iván (last): true ➡Laura->Marta->null
Removing Nora (not there): false | size = 2

Check it against the drawings: Ana goes in at the front without traversing anything; Iván at the back, traversing four nodes; out go Ana (head), Pablo (middle) and Iván (last), and size ends at 5 − 3 = 2 without traversing. With Nora, who never booked, remove returns false.

From the Python you know to the exam’s Java

If you did the Python topic, all of this will sound familiar. The translation is almost word for word:

Python (FP2)	Java (FP2)
self.__first	first (protected in ContainerBase)
node.next_node	n.next
None	null
while current is not None:	while (current != null) or for (Node n = first; n != null; n = n.next)
current.value == member	current.value.equals(member)
raise ValueError(...)	Usual in the exam: return false, null or -1
__len__ with __length	getSize() with private int size
__str__	toString() (already written in ContainerBase)

The biggest difference isn’t in the table: in Java everything has a type. Node stores a String, so you can’t put a number into this queue without changing the class.

What if the data isn’t a String?

In the exam you’re given a Node made for the brief’s data: a Box with a label and kilos, a loan, a number. The structure doesn’t change: only the type of value. In the practice you’ll see a Node with int value for loan days.

The general version would be a generic node, Node<T>, like the ones in the collections you saw in the previous topic:

public class Node<T> {
    public T value;
    public Node<T> next;
}

That way, Node<String> and Node<Integer> share code. The FP2 exam uses nodes with a concrete type, which is what we practise here; if a brief uses <T>, everything in this article works the same.

Java’s trap: == versus equals

In Python, == between two strings compares their content. In Java, == between two objects asks whether they’re the same object. With String that’s a trap, because two equal texts can be different objects. This is the same queue, but comparing with ==:

public class EqualsTest {
    public static void main(String[] args) {
        String typed = "Pablo";
        String fromFile = new String("Pablo");      // the same text in ANOTHER object (like what comes from a file)
        System.out.println(typed == fromFile);         // same object?
        System.out.println(typed.equals(fromFile));    // same text?

        BadQueue queue = new BadQueue();
        queue.insertBack("Laura");
        queue.insertBack(fromFile);
        System.out.println(queue + " | Pablo? " + queue.contains("Pablo"));
        System.out.println("Removing Pablo: " + queue.remove("Pablo") + " " + queue);
    }
}

Output:

false
true
➡Laura->Pablo->null | Pablo? false
Removing Pablo: false ➡Laura->Pablo->null

The Pablo who went into the queue was created with new String (as would happen if it came from a file or from Scanner), and the "Pablo" we look for is another object. == says they aren’t the same, so contains answers false and remove finds nobody, even though you can see “Pablo” in the queue. With equals, as in BookingQueue, it always works.

If first were private

Why protected and not private, which is what we were taught for attributes? Look at what happens if we change it to private in ContainerBase and compile the same BookingQueue:

BookingQueue.java:7: error: first has private access in ContainerBase
        newNode.next = first;                   // 1. the new node points at the current head...
                       ^

…and so on up to 12 errors, one for each use of first. private only lets the attribute be used inside its own class, and BookingQueue is another class, even though it inherits from it. With protected, subclasses can use it. It’s Java’s equivalent of the problem Python’s double-underscore attributes caused.

Common mistakes with linked lists in Java

Watch it step by step in Python Tutor

Python Tutor runs Java and draws every object with its arrows: choose Java in the drop-down. It has to be a single public class, so the node goes inside as a nested class (static class Node). This program puts Ana between Laura and Pablo:

public class Tutor {
    static class Node {
        String value;
        Node next;

        Node(String value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Node laura = new Node("Laura");
        Node pablo = new Node("Pablo");
        Node marta = new Node("Marta");
        laura.next = pablo;
        pablo.next = marta;
        Node first = laura;

        Node ana = new Node("Ana");    // Ana squeezes in between Laura and Pablo
        ana.next = laura.next;         // 1. link it to the rest
        laura.next = ana;              // 2. hook it on

        for (Node n = first; n != null; n = n.next) {
            System.out.println(n.value);
        }
    }
}

Output:

Laura
Ana
Pablo
Marta

What to watch step by step:

1. After the three new Node, you’ll see three loose objects with next set to null.
2. With laura.next = pablo and pablo.next = marta the arrows appear. No object moves.
3. At ana.next = laura.next, Ana already points at Pablo and Laura still does too: two arrows to the same node.
4. At laura.next = ana a single arrow changes. Pablo and Marta don’t notice.
5. During the for, watch how the variable n jumps from object to object until it’s null.

Quick summary

Operation	Key code	Cost
Insert at the front	newNode.next = first; first = newNode;	O(1)
Insert at the back	Empty case; otherwise while (current.next != null) and current.next = newNode	O(n)
Traverse	for (Node n = first; n != null; n = n.next)	O(n)
Search	Traverse with equals	O(n)
Remove	Head on its own; the rest with previous.next = current.next	O(n)
Size	private int size kept up to date	O(1)

Three ideas to keep:

1. Link first, move afterwards. The wrong order leaves nodes with nobody pointing at them.
2. null is the end and also the trap. Always think about the empty list and the last node.
3. Text with equals, nodes with ==.

In the Java LinkedList practice we write three classes like the exam’s: a queue with first and last, a sorted list of loans with “remove all” and a queue that turns itself around without creating nodes.

Next step: practiceJava LinkedList practice — the booking queue with first and last, the sorted loans and the queue turned around (like in Exam 3)

Did this article help you? Here is how you can support SergioLearns →