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

In an Exam 3 mock I wrote removeDuplicates comparing with ==. I tested it with names typed into main and it worked first time. The lecturer’s tests read the names from a file and my method didn’t remove a single one. It was the == trap with Strings that we saw in the theory, and you’ll see it with real output in fragment 1 of “What’s wrong here?”.

You’ve seen the theory and practised with three library programs. Now it’s your turn. Three exercises at three levels on the same booking queue at the faculty library: read the booking at a position and find a member’s position, remove repeated members without collections and split the queue in half in a single pass. All three go after the mistakes that cost the most marks in the linked-structures exam: moving one node too far, comparing text with == and forgetting one end.

How to use this article: try each exercise on your own; if you’ve been stuck for more than ten minutes, open the hint; before looking at the solution, do “What’s wrong here?”, and paste your code into Python Tutor (choosing Java) to see the arrows. At the end there’s an exam-style quiz and the topic’s cheat sheet.

All three exercises use the exam’s template: the same Node and ContainerBase as in the theory (with first protected) and your class with extends ContainerBase, which has its own size and insertBack (the same as in the theory). Remember the rule: no arrays and no collections to store the data; in the tests we only use them to set up the names.

Java LinkedList exercises: basic level

Exercise 1: get the booking at a position and find a member

Write the SearchableQueue class with two methods:

• String get(int pos): the member at that position, starting at 0 at the head. If the position doesn’t exist (negative or greater than or equal to size), it returns null.
• int indexOf(String member): the position of the first occurrence of the member, or -1 if they’re not there. It has to work even if the text is another object (new String("Marta")).

With the empty queue and then with Laura -> Pablo -> Marta -> Pablo, the output must be:

Empty: get(0) = null, indexOf("Laura") = -1
➡Laura->Pablo->Marta->Pablo->null
get(0) = Laura, get(2) = Marta, get(3) = Pablo
get(4) = null, get(-1) = null
indexOf("Pablo") = 1, indexOf("Nora") = -1
indexOf(new String("Marta")) = 2

Java LinkedList exercises: intermediate level

Exercise 2: remove repeated members without collections

Some members book the same book two or three times. Write the NoDuplicatesQueue class with int removeDuplicates(), which keeps only the first occurrence of each member, modifying the queue itself (without creating another), keeps size correct and returns how many it deleted. No HashSet, no ArrayList and no arrays: the exam doesn’t allow them.

Expected output with these four queues:

➡Laura->Pablo->Laura->Marta->Pablo->Iván->Laura->null  =>  ➡Laura->Pablo->Marta->Iván->null (deleted 3, size 4)
➡Ana->Nora->Iván->null  =>  ➡Ana->Nora->Iván->null (deleted 0, size 3)
➡Marta->Marta->Marta->Marta->null  =>  ➡Marta->null (deleted 3, size 1)
➡null  =>  ➡null (deleted 0, size 0)

Java LinkedList exercises: final challenge

Exercise 3: split the queue in half in a single pass

The library opens a second desk and wants to share the booking queue between the two: the first half stays at the usual desk and the second moves to the new one, in the same order. If the queue has an odd number of people, the middle one stays at the first.

Write SplittableQueue splitInHalf(), which cuts the queue itself and returns another SplittableQueue with the second half, with both sizes correct. The challenge’s condition: a single pass, without using size to find the middle, and without creating new nodes.

Expected output:

➡Laura->Pablo->Marta->Iván->Nora->null  =>  ➡Laura->Pablo->Marta->null (3) + ➡Iván->Nora->null (2)
➡Laura->Pablo->Marta->Iván->null  =>  ➡Laura->Pablo->null (2) + ➡Marta->Iván->null (2)
➡Ana->null  =>  ➡Ana->null (1) + ➡null (0)
➡null  =>  ➡null (0) + ➡null (0)

What’s wrong here?

Three fragments with a mistake of the kind that comes up in exams. Predict what each one prints before reading the explanation.

Fragment 1: the repeats that won’t go

removeDuplicates with a single difference: it compares with ==.

public int removeDuplicates() {
    int deleted = 0;
    for (Node current = first; current != null; current = current.next) {
        Node previous = current;                      // we look for copies of current BEHIND it
        while (previous.next != null) {
            if (previous.next.value == current.value) {
                previous.next = previous.next.next;   // we skip the copy; previous does NOT move
                deleted++;
            } else {
                previous = previous.next;
            }
        }
    }
    size -= deleted;
    return deleted;
}

The test puts the same three names into two queues: in one with the literals as they are and in the other with new String(s), as if they came from a file or the keyboard:

public class BadTest {
    public static void main(String[] args) {
        NoDuplicatesQueue literals = new NoDuplicatesQueue();
        NoDuplicatesQueue fromFile = new NoDuplicatesQueue();
        for (String s : new String[] {"Laura", "Pablo", "Laura"}) {
            literals.insertBack(s);                 // literals: Java reuses the same object
            fromFile.insertBack(new String(s));     // as if they came from a file: different objects
        }
        System.out.println("Literals:  deleted " + literals.removeDuplicates() + " -> " + literals);
        System.out.println("From file: deleted " + fromFile.removeDuplicates() + " -> " + fromFile);
    }
}

Literals:  deleted 1 -> ➡Laura->Pablo->null
From file: deleted 0 -> ➡Laura->Pablo->Laura->null

What’s wrong: == compares references. Equal literals you write in the code are the same object (Java reuses them), so in the first queue the trick “works”. In the second, each new String is a different object and == says Laura isn’t Laura: nothing is deleted. That’s exactly my mock exam: tests don’t always use literals. Fix: previous.next.value.equals(current.value).

Fragment 2: the counter that falls short

public int count() {
    int total = 0;
    Node n = first;
    while (n.next != null) {              // WRONG: it stops BEFORE the last one
        total++;
        n = n.next;
    }
    return total;
}

It’s tested with Laura -> Pablo -> Marta and then with an empty queue:

➡Laura->Pablo->Marta->null has 2 nodes
Exception in thread "main" java.lang.NullPointerException: Cannot read field "next" because "n" is null
        at CountQueue.count(CountQueue.java:12)
        at CountTest.main(CountTest.java:9)

What’s wrong: two things, because of the same condition. while (n.next != null) stops at the last node without counting it: with three nodes it gives 2. And with the empty queue, n is already null before going in, so n.next throws the NullPointerException on line 12 of CountQueue.java, the while line. Notice that Java’s message tells you exactly what was null: "n". Fix: while (n != null), which counts them all and doesn’t go in with the empty queue.

Fragment 3: the empty queue that remembers someone

The practice’s serve for the queue with first and last, with one line missing:

public String serve() {
    if (first == null) {
        return null;                      // nobody to serve
    }
    String member = first.value;
    first = first.next;
    size--;
    return member;
}

Laura and Pablo are enqueued and both are served:

Empty: ➡null | first null, last Pablo, size 0

What’s wrong: when the last person is served, first becomes null but last still points at Pablo. The queue claims to be empty (➡null, size 0) and at the same time to have a last one. So far it only lies; the serious part comes with the next enqueue: since first == null, it makes the new node first and last and everything adds up again by chance. But if another method of yours uses last before that (for example, a peekLast() in the exam’s tests), the test fails. Fix: after first = first.next;, if (first == null) last = null;.

Solutions explained

Solution to exercise 1

public String get(int pos) {
    if (pos < 0 || pos >= size) {         // we validate BEFORE moving
        return null;
    }
    Node current = first;
    for (int i = 0; i < pos; i++) {       // pos hops from the head
        current = current.next;
    }
    return current.value;
}

public int indexOf(String member) {
    int pos = 0;
    for (Node n = first; n != null; n = n.next) {
        if (n.value.equals(member)) {
            return pos;                   // the first one that matches
        }
        pos++;
    }
    return -1;                            // not there
}

get: the validation goes before the loop because, otherwise, with pos equal to size the last hop leaves current at null and current.value throws NullPointerException. With a negative pos the for wouldn’t do a single lap and you’d return the head, which is worse: a wrong result with no error. Then, pos hops: for get(2), from Laura to Pablo (i = 0) and from Pablo to Marta (i = 1); with i = 2 the for ends and we return Marta.

indexOf: the counter pos moves at the same time as n. The return inside the loop means we return the first occurrence: with Pablo twice, it gives 1, not 3. And because we compare with equals, new String("Marta") is found at position 2.

Solution to exercise 2

public int removeDuplicates() {
    int deleted = 0;
    for (Node current = first; current != null; current = current.next) {
        Node previous = current;                      // we look for copies of current BEHIND it
        while (previous.next != null) {
            if (previous.next.value.equals(current.value)) {
                previous.next = previous.next.next;   // we skip the copy; previous does NOT move
                deleted++;
            } else {
                previous = previous.next;
            }
        }
    }
    size -= deleted;
    return deleted;
}

The outer for traverses the queue with current. For each member, the inner while starts with previous = current and always looks at previous.next: if it’s a copy, we skip it and previous doesn’t move; if not, it moves on. That way, when current reaches a node, all its copies behind it are already gone, and the for carries on with nodes that are the first occurrence of their value.

Trace with Marta -> Marta -> Marta -> Marta (current on the first Marta):

Three deleted and size 4 − 3 = 1, as in the output. With the first queue, Laura deletes her two copies, Pablo one and Marta and Iván none: 2 + 1 = 3 deleted and 7 − 3 = 4 nodes.

Why O(n²)? Each node traverses what’s behind it. With a HashSet of seen values it would be O(n), but the exam forbids collections. With library queues of a few dozen people, it doesn’t matter.

Solution to exercise 3

public SplittableQueue splitInHalf() {
    SplittableQueue second = new SplittableQueue();
    if (first == null || first.next == null) {     // 0 or 1 nodes: there is no second half
        return second;
    }
    Node slow = first;
    Node fast = first.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;                          // 1 hop
        fast = fast.next.next;                     // 2 hops
    }
    second.first = slow.next;                      // the second half starts after slow
    slow.next = null;                              // we cut the chain
    second.size = size / 2;                        // the first keeps the extra one if odd
    size = size - second.size;
    return second;
}

Special cases first: with 0 or 1 nodes there’s no second half, and the loop couldn’t start (first.next with first set to null throws NullPointerException). We return an empty queue.

The loop: fast makes two hops for every one of slow. Since it starts one node ahead, when fast can no longer make two hops, slow is on the last node of the first half. Trace with five people:

slow stops at Marta: the second half starts at Iván. With four, fast ends on Iván (whose next is null) and slow on Pablo: 2 + 2. Look at the drawing: the cut is two lines. First the new queue saves slow.next and then slow.next = null cuts the chain (once again, save first and move afterwards).

The sizes: the second half has size / 2 (integer division: 5 / 2 = 2) and the first, the rest (5 − 2 = 3). There’s no need to count again.

Why does second.first compile? first is protected and we’re inside SplittableQueue, which inherits from ContainerBase: we can touch the first of another object of our own class.

Exam-style quiz

Eleven questions like the ones in the FP2 linked-structures exam. Answer without looking at the article and then go over the explanations.

Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
a.next = b;
b.next = c;
Node newNode = new Node("X");
newNode.next = a.next;
a.next = newNode;
String s = "";
for (Node n = a; n != null; n = n.next) {
    s += n.value;
}
System.out.println(s);

public int count() {
    int total = 0;
    Node n = first;
    while (n.next != null) {
        total++;
        n = n.next;
    }
    return total;
}

Node previous = null;
Node current = first;
while (current != null) {
    Node nextNode = current.next;
    current.next = previous;
    previous = current;
    current = nextNode;
}
first = previous;
System.out.println(this);

String a = "Pablo";
String b = new String("Pablo");
System.out.println((a == b) + " " + a.equals(b));

Watch it step by step in Python Tutor

Go to Python Tutor, choose Java and paste this version of exercise 3 with the five-person queue (in Python Tutor everything goes in one class, so Node goes inside Tutor):

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

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

    public static void main(String[] args) {
        Node first = new Node("Laura");
        first.next = new Node("Pablo");
        first.next.next = new Node("Marta");
        first.next.next.next = new Node("Iván");
        first.next.next.next.next = new Node("Nora");

        Node slow = first;
        Node fast = first.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        Node second = slow.next;    // Iván
        slow.next = null;           // the first half ends at Marta
        System.out.println(first.value + " ... " + slow.value + " | " + second.value + " ... " + second.next.value);
    }
}

Output:

Laura ... Marta | Iván ... Nora

What to watch step by step:

1. After the five next lines, the chain goes from Laura to Nora and Nora’s arrow is null.
2. Before the loop, slow points at Laura and fast at Pablo, one node ahead.
3. On each lap, slow‘s arrow moves one node and fast‘s, two. Count the hops.
4. When fast becomes null, slow is on Marta, the third one.
5. After slow.next = null, Python Tutor draws two separate chains: Laura -> Pablo -> Marta and, apart, Iván -> Nora, which stays alive because second points at it.

Cheat sheet: Java LinkedList

The essentials in 30 seconds: a Node stores value and next; the list only stores first (protected in ContainerBase) and your class inherits with extends. To insert, link first and move afterwards. To delete, stop at the previous one. Traverse with for (Node n = first; n != null; n = n.next); to stop at the last one, while (n.next != null). Compare text with equals. Validate before moving on and always test the empty list and the one-node list.

Exercise templates:

Before handing in, ask yourself:

1. Does it work with the empty list and with a single node?
2. Is there any .value or .next on something that could be null?
3. Have I linked before moving in every reference change?
4. Do size (and last, if I have it) still tell the truth after my method?
5. Have I compared the text with equals?

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