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

Revising for Exam 3 I wrote a queue with first and last that worked beautifully… until I emptied it. peekFirst() said null, getSize() said 0 and peekLast() still said Pablo, who had left ages before. I’d forgotten one line in the case where the queue becomes empty. That case, the edge one, is exactly what the exam’s tests check, and you’ll see it with real output in program 1 and in the exercises.

In the Java LinkedList theory we saw the node, ContainerBase, inserting, traversing, removing and the == trap with text. Now we write three intermediate classes with the exam’s template (Node + ContainerBase + your class with extends), using the faculty library example: a booking queue that enqueues and serves without traversing, a sorted list of loan days with “remove all” and a queue that turns itself around without creating a single node. The data looks like the real thing: repeated values, empty queues and one-person queues. The library’s rules are made up.

Before you start

Make sure you’re clear on:

• The template: Node with public value and next, ContainerBase with protected Node first and a toString() that draws ➡A->B->null, and your class with extends ContainerBase.
• The traversal: for (Node n = first; n != null; n = n.next).
• The golden rule: link first, move afterwards.
• That text is compared with equals and that in the exam you can’t use arrays or collections to store the data.

If any of these feels shaky, go over the theory before carrying on.

Program 1: the booking queue with first and last

At the library, bookings are served in order of arrival: you enqueue at the back and serve at the front. With only first, enqueueing means traversing the whole queue. We want both operations to be instant, plus peekFirst(), peekLast() and getSize(). What makes it tricky: the empty queue and the one-person queue, where first and last are the same node.

The idea

We keep two references: first (inherited) to serve and last (ours, private) to enqueue. Enqueueing hooks the new node behind last and makes it the new last. Serving moves first to the second node. The special cases come from one question: what should first and last be when the queue is empty? Both null. So, if it’s empty when enqueueing, the new node is the first and the last; and if it becomes empty when serving, last also goes to null.

The code

/** Booking queue with first and last: enqueue at the back and serve at the front, neither one traversing. */
public class FastQueue extends ContainerBase {
    private Node last;                          // the last node: so enqueueing needs no traversal
    private int size;

    public void enqueue(String member) {
        Node newNode = new Node(member);
        if (first == null) {                    // empty queue: the new node is the first AND the last
            first = newNode;
        } else {
            last.next = newNode;                // the old last one points at the new node...
        }
        last = newNode;                         // ...and the new one becomes the last
        size++;
    }

    public String serve() {
        if (first == null) {
            return null;                        // nobody to serve
        }
        String member = first.value;
        first = first.next;
        if (first == null) {                    // it has become empty: last to null as well
            last = null;
        }
        size--;
        return member;
    }

    public String peekFirst() {
        return first == null ? null : first.value;
    }

    public String peekLast() {
        return last == null ? null : last.value;
    }

    public int getSize() {
        return size;
    }
}

And the test:

public class FastQueueTest {
    public static void main(String[] args) {
        FastQueue queue = new FastQueue();
        System.out.println("Serving an empty queue: " + queue.serve());
        queue.enqueue("Laura");
        queue.enqueue("Pablo");
        queue.enqueue("Marta");
        System.out.println(queue + " | first " + queue.peekFirst() + ", last " + queue.peekLast() + ", size " + queue.getSize());
        System.out.println("Serving " + queue.serve() + ": " + queue);
        System.out.println("Serving " + queue.serve() + ": " + queue);
        System.out.println("Serving " + queue.serve() + ": " + queue);
        System.out.println("Empty: first " + queue.peekFirst() + ", last " + queue.peekLast() + ", size " + queue.getSize());
        queue.enqueue("Nora");
        System.out.println("Nora arrives: " + queue + " | first " + queue.peekFirst() + ", last " + queue.peekLast());
    }
}

Output

Serving an empty queue: null
➡Laura->Pablo->Marta->null | first Laura, last Marta, size 3
Serving Laura: ➡Pablo->Marta->null
Serving Pablo: ➡Marta->null
Serving Marta: ➡null
Empty: first null, last null, size 0
Nora arrives: ➡Nora->null | first Nora, last Nora

Look at the last three lines: when Marta is served the queue is left empty and both ends are null. When Nora arrives, enqueue sees first == null, makes her first and last, and the queue works again. Serving an empty queue returns null instead of throwing a NullPointerException, which is what briefs usually ask for.

Questions you might ask

Why is last private and first not? first comes from ContainerBase (protected, so you can use it). last is a detail of your class: nobody outside should be able to change it.

Why does last = newNode go outside the if in enqueue? Because in both cases the new node ends up being the last one. The only thing that changes is who points at it: first (empty queue) or the old last node.

What happens if I forget the last = null in serve? The empty queue keeps “remembering” the last person. You’ll see it with real output in fragment 3 of the exercises.

Shouldn’t serve return the node? No: nodes are an internal detail. Whoever uses the queue wants the data (the name), so we return a String.

Try it yourself

• Add jumpQueue(String member), which inserts at the front (staff). Do you need to touch last in any case?
• Write serveSeveral(int n) that serves n people and returns how many it actually served.

Program 2: the sorted list of loans and “remove all”

The library stores how many days each loan lasted and wants them always sorted from smallest to largest, to see the shortest and longest at a glance. It also wants to remove all loans of a given length (for example, the 8-day ones, which were a promotion). What makes it tricky: there are repeated values, and the ones removed can be in a row and at the start.

The idea

• insertSorted: if the list is empty or the value goes before the head, it’s an “insert at the front”. Otherwise, we look for the last node smaller than the value and hook the new one behind it.
• removeAll: first the ones at the head are removed with a while (there may be several in a row). Then, with a previous reference, we always look at previous.next: if it has to go, we skip it and previous doesn’t move, because its new next hasn’t been checked yet.

The code

This time Node stores an int:

public class Node {
    public int value;        // the data: days a loan lasted
    public Node next;        // the next node (null if it is the last)

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

/** Days each loan lasted, always from smallest to largest. */
public class DaysList extends ContainerBase {
    private int size;

    public void insertSorted(int days) {
        Node newNode = new Node(days);
        if (first == null || days <= first.value) {          // case 1: empty, or it goes before everyone
            newNode.next = first;
            first = newNode;
        } else {
            Node current = first;
            while (current.next != null && current.next.value < days) {
                current = current.next;                      // we stop at the LAST one smaller than days
            }
            newNode.next = current.next;                     // 1. the new node points at the rest...
            current.next = newNode;                          // 2. ...and current points at the new node
        }
        size++;
    }

    public int removeAll(int days) {
        int deleted = 0;
        while (first != null && first.value == days) {      // the ones at the head (there may be several in a row)
            first = first.next;
            deleted++;
        }
        if (first != null) {
            Node previous = first;
            while (previous.next != null) {
                if (previous.next.value == days) {
                    previous.next = previous.next.next;      // we skip the next one; previous does NOT move
                    deleted++;
                } else {
                    previous = previous.next;
                }
            }
        }
        size -= deleted;
        return deleted;
    }

    public int getSize() {
        return size;
    }
}

The delicate part of insertSorted is the while condition: first current.next != null and then current.next.value < days. If you swap them, on the last node Java evaluates null.value and throws NullPointerException. And the last two lines follow the golden rule: the new node points at the rest before current points at the new node.

The test uses an array only to set up the data; the list doesn’t use it inside:

public class DaysTest {
    public static void main(String[] args) {
        DaysList lista = new DaysList();
        int[] arrivals = {15, 8, 42, 3, 27, 8, 19, 8};     // only for the test: the list does not use the array
        for (int d : arrivals) {
            lista.insertSorted(d);
            System.out.println("Inserting " + d + ": " + lista);
        }
        System.out.println("Removing the 8s: " + lista.removeAll(8) + " -> " + lista + " | size " + lista.getSize());
        System.out.println("Removing the 3s: " + lista.removeAll(3) + " -> " + lista);
        System.out.println("Removing the 100s: " + lista.removeAll(100) + " -> " + lista + " | size " + lista.getSize());
    }
}

Output

Inserting 15: ➡15->null
Inserting 8: ➡8->15->null
Inserting 42: ➡8->15->42->null
Inserting 3: ➡3->8->15->42->null
Inserting 27: ➡3->8->15->27->42->null
Inserting 8: ➡3->8->8->15->27->42->null
Inserting 19: ➡3->8->8->15->19->27->42->null
Inserting 8: ➡3->8->8->8->15->19->27->42->null
Removing the 8s: 3 -> ➡3->15->19->27->42->null | size 5
Removing the 3s: 1 -> ➡15->19->27->42->null
Removing the 100s: 0 -> ➡15->19->27->42->null | size 4

Let’s check the step for 27: the list is 3 -> 8 -> 15 -> 42; current starts at 3; since 8 < 27 it moves to 8, since 15 < 27 it moves to 15, and since 42 is no longer < 27 it stops at 15, so 27 lands between 15 and 42. Removing the 8s takes out three (they were in a row, in the middle), and size goes from 8 to 5. Removing 3 deletes the head with the first while. And with 100 nothing is removed and size stays at 4.

Trace of removeAll(8) on 3 -> 8 -> 8 -> 8 -> 15:

Lap	previous	previous.next	Is it 8?	What happens
1	3	8 (first)	Yes	3 skips to the second 8, previous stays
2	3	8 (second)	Yes	3 skips to the third
3	3	8 (third)	Yes	3 points at 15
4	3	15	No	previous moves to 15

Questions you might ask

Why <= in the head case and < in the loop? So that a value equal to the head goes in front without traversing. With repeated values, the order among equals doesn’t matter.

Why is the first loop in removeAll a while and not an if? Because there may be several equal values in a row at the start (3, 3, 3…). With an if you’d only remove the first one.

Why size -= deleted at the end and not size-- inside? It’s the same; counting the deleted ones also lets us return them, which is what the method asks for.

And if the list held Strings? The same pattern, comparing with equals and, to sort, with compareTo (which you saw in the Comparable topic).

Try it yourself

• Add median() that returns the middle value without using size for anything other than knowing how many hops to make.
• Write insertWithoutRepeats(int days), which doesn’t insert a value that’s already there (use the fact that the list is sorted to stop early).

Program 3: turning the queue around without creating nodes

Finally, the library wants to notify the booking queue from last to first (another made-up rule; the problem is an exam classic). You have to reverse the list itself, reusing the same nodes. What makes it tricky: changing every arrow without losing the way, with an empty or one-person queue.

The idea

Three references: previous (starts at null), current (starts at first) and nextNode. On each lap: save nextNode = current.next, turn the arrow current.next = previous and move both on. At the end, first = previous.

The code

/** Booking queue that can be turned around without creating new nodes. */
public class ReversibleQueue extends ContainerBase {

    public void insertBack(String member) {
        Node newNode = new Node(member);
        if (first == null) {
            first = newNode;
            return;
        }
        Node current = first;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    public void reverse() {
        Node previous = null;
        Node current = first;
        while (current != null) {
            Node nextNode = current.next;     // 1. save the rest BEFORE touching anything
            current.next = previous;          // 2. turn the arrow around
            previous = current;               // 3. move previous forward...
            current = nextNode;               // 4. ...and current
        }
        first = previous;                     // the new head is the old tail
    }
}

public class ReverseTest {
    public static void main(String[] args) {
        ReversibleQueue queue = new ReversibleQueue();
        queue.reverse();
        System.out.println("Empty reversed: " + queue);
        queue.insertBack("Laura");
        queue.reverse();
        System.out.println("One node reversed: " + queue);
        queue.insertBack("Pablo");
        queue.insertBack("Marta");
        queue.insertBack("Iván");
        System.out.println("Queue: " + queue);
        queue.reverse();
        System.out.println("Reversed: " + queue);
        queue.reverse();
        System.out.println("Again: " + queue);
    }
}

Output

Empty reversed: ➡null
One node reversed: ➡Laura->null
Queue: ➡Laura->Pablo->Marta->Iván->null
Reversed: ➡Iván->Marta->Pablo->Laura->null
Again: ➡Laura->Pablo->Marta->Iván->null

The empty queue and the one-node queue come out right without any if: with first set to null the while never runs, and with one node it does one lap that points Laura at null, which it already did. Reversing twice leaves the queue as it was.

Now the same method with the first two lines of the loop swapped:

public void reverse() {
    Node previous = null;
    Node current = first;
    while (current != null) {
        current.next = previous;          // WRONG: we turn the arrow around first...
        Node nextNode = current.next;     // ...and "the rest" is already previous
        previous = current;               // 3. move previous forward...
        current = nextNode;               // 4. ...and current
    }
    first = previous;                     // the new head is the old tail
}

Empty reversed: ➡null
One node reversed: ➡Laura->null
Queue: ➡Laura->Pablo->Marta->Iván->null
Reversed: ➡Laura->null
Again: ➡Laura->null

On the first lap, current.next = previous leaves Laura pointing at null and then nextNode = current.next saves… null. The loop ends, first becomes Laura and Pablo, Marta and Iván are left with nobody pointing at them. There’s no red error: just a queue that has lost three people.

Questions you might ask

Why is nextNode declared inside the loop? Because it’s only needed during one lap. Declaring it outside works too.

Do you need to touch size? No: reversing neither adds nor removes nodes. This class doesn’t even store it.

Could it be done with recursion? Yes, but each node is a call on the stack: with a very long list, StackOverflowError. The iterative one has no such limit.

What about building a new list by inserting at the front? That reverses too, but creates one node per element. If the brief says “without creating nodes”, it’s the three-reference one.

Try it yourself

• Add reverseFrom(int pos), which only reverses from a given position on.
• Write isPalindrome() without collections: reverse a copy (build it by traversing and using insertFront) and compare node by node with equals.

The pattern to take away

Pattern	When	Skeleton
Two ends	Queues: in at the back, out at the front	last.next = newNode; last = newNode; and first = first.next; (+ last = null if it empties)
Stop at the previous one	Sorted insertion, conditional removal	while (previous.next != null) and skip previous.next
Three references	Turning arrows around	nextNode = current.next; current.next = previous; …

Common mistakes in this practice

• Not setting last = null when the queue empties. peekLast() lies.
• Swapping the order of the condition current.next != null && current.next.value < x. NullPointerException on the last node.
• Using if instead of while to remove the ones at the head. The repeats at the start stay.
• Moving previous on when you delete. Repeats in a row stay.
• Turning an arrow without saving the next node first. The queue is left with one node.
• Storing the data in an array “to make sorting easier”. Forbidden in the exam.

Watch it step by step in Python Tutor

Go to Python Tutor, choose Java and paste this minimal version of the queue with first and last:

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

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

    public static void main(String[] args) {
        Node first = null;
        Node last = null;
        String[] llegan = {"Laura", "Pablo", "Marta"};
        for (String member : llegan) {          // enqueue: always at the back
            Node newNode = new Node(member);
            if (first == null) {
                first = newNode;
            } else {
                last.next = newNode;
            }
            last = newNode;
        }
        String served = first.value;          // serve: always at the front
        first = first.next;
        System.out.println(served + " | first " + first.value + " | last " + last.value);
    }
}

Output:

Laura | first Pablo | last Marta

What to watch step by step:

1. On the first lap of the for, first and last point at the same node, Laura.
2. On the second, Laura’s arrow changes (last.next = newNode) and then last jumps to Pablo; first doesn’t move.
3. When the for ends, first is on Laura and last on Marta, without having traversed anything.
4. When serving, only first changes. Laura is left with nobody pointing at her.

Summary and next step

• With first and last, enqueueing and serving are instant, but you have to maintain both.
• The empty queue is the case that breaks queues: both ends to null.
• To insert in order or remove conditionally, you stop at the previous node.
• previous doesn’t move when you delete.
• Reversing in place is three references and a fixed order: save, turn, move on.
• Always test the empty list, the one-node list and repeats in a row.

Checklist: have you practised it?

• Have you run the three programs and checked the outputs?
• Do you know what first, last and size hold right after serving the last person?
• Can you explain why the first loop of removeAll is a while?
• Can you write the four lines of the reversal loop from memory?
• Have you tried the “Try it yourself” tasks without looking at the theory?

If you answered yes to almost everything, you’re ready for the Java LinkedList exercises, where I no longer give you the code ready-made. See you there!

Next step: exercisesJava LinkedList exercises — the booking at position N, the repeated members and the queue split in half (with solutions and cheat sheet)

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