Swap items of a linked list in pairs - revision 3

Question

Here is the source of the question.

Revision 1.

Revision 2.

When I started the second round of code review, I wanted to make sure that I had included all the possible input types. However, I received many useful suggestions from @200_success.

I took some time to learn them, and now I want to post my code again.

In this revision:

• The class SinglyLinkedList no longer exposes node pointers. getNext of the class Node returning the pointer to the next element is package-private. SinglyLinkedList can use it, and client code can't.
• I don't maintain mLast which is unnecessary for a short interview problem. If I was told to prepend and append items, I would need mFirst and mLast.
• I deleted mSize which was only used for toArray
• I wrote new tests which (I think) cover all the edge cases of 200_success' algorithm.
• I don't use toArray for testing. I use a copy constructor to make a copy of an original list before reversing. Each list has an iterator. I compare values of the two lists iterating over them. If I used toArray, I would create two arrays (one from an original list and one from its reversed version) which would mean twice as much memory as I use.

Node

package com.singlylinkedlist;

class Node {

    private Node next;
    private int data;

    Node(int data) {
        this.data = data;
    }

    int getData() {
        return data;
    }

    void setNext(Node n) {
        this.next = n;
    }

    Node getNext() {
        return next;
    }
}

SinglyLinkedList.

package com.singlylinkedlist;

import java.util.Iterator;

public class SinglyLinkedList implements Iterable<Integer> {

    /** Dummy node */
    private final Node head = new Node(0);

    public SinglyLinkedList(int[] data) {
        for (int i = data.length - 1; i >= 0; i--) {
            addFirst(data[i]);
        }
    }

    public SinglyLinkedList(SinglyLinkedList from) {
        Node source = from.head.getNext();
        Node dst = head;
        while (source != null) {
            dst.setNext(new Node(source.getData()));
            source = source.getNext();
            dst = dst.getNext();
        }
    }

    public void addFirst(int datum) {
        Node n = new Node(datum);
        n.setNext(head.getNext());
        head.setNext(n);
    }

    public void reversePairs() {
        // For each loop iteration, transform
        //
        // maybe null --+
        // |
        // v
        // Original: (a) -> b -> c -> d ...
        // To: a -> c -> (b) -> d ...
        // ^
        // |
        // +-- becomes "a" of the next iteration

        Node a = this.head, b, c;
        while ((b = a.getNext()) != null && (c = b.getNext()) != null) {
            Node d = c.getNext();
            a.setNext(c);
            c.setNext(b);
            b.setNext(d);
            a = b;
        }
    }

    @Override
    public String toString() {
        Iterator<Integer> iterator = iterator();
        if (!iterator.hasNext()) {
            return "[]";
        }

        StringBuilder s = new StringBuilder("[");
        while(true) {
            int nodeValue = iterator.next();
            s.append(nodeValue);
            if (!iterator.hasNext()) {
                return s.append(']').toString();
            }
            s.append(" -> ");
        }
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {

            Node current = head;

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }

            @Override
            public Integer next() {
                current = current.getNext();
                return current.getData();
            }

            @Override
            public boolean hasNext() {
                return current.getNext() != null;
            }

        };
    }

}

Unit tests.

package com.singlylinkedlist;

import org.junit.Assert;
import org.junit.Test;

import java.util.Iterator;

public class SinglyLinkedListTest {

    @Test
    public void testEmpty() {
        doReverse(new int[] {});
    }

    @Test
    public void testSingle() {
        doReverse(new int[] { 1 });
    }

    @Test
    public void testLoopOnce() {
        doReverse(new int[] { 1, 2 });
    }

    @Test
    public void testLoopMoreThanOnce() {
        doReverse(new int[] { 1, 2, 3, 4, 5, 6 });
    }

    private void doReverse(int[] data) {
        SinglyLinkedList orig = new SinglyLinkedList(data);
        SinglyLinkedList copy = new SinglyLinkedList(orig);
        orig.reversePairs();

        Iterator<Integer> origIterator = orig.iterator();
        Iterator<Integer> copyIterator = copy.iterator();

        // The list is empty
        if (!origIterator.hasNext()) {
            return;
        }
        int origFirstInPair = origIterator.next();
        int copyFirstInPair = copyIterator.next();
        while (true) {
            if (!origIterator.hasNext()) {
                Assert.assertTrue(origFirstInPair == copyFirstInPair);
                return;
            }
            int origSecondInPair = origIterator.next();
            int copySecondInPair = copyIterator.next();
            Assert.assertTrue(origFirstInPair == copySecondInPair && origSecondInPair == copyFirstInPair);
            if (!origIterator.hasNext()) {
                return;
            }
            origFirstInPair = origIterator.next();
            copyFirstInPair = copyIterator.next();
        }
    }
}

Answer 1

I like your code a lot. =)

In the copy constructor, if you're going to abbreviate dst, then also abbreviate src for parallelism. But I don't think you need a copy constructor at all for this exercise: just construct both lists from the same input array.

Your toString() would be better with a more straightforward loop:

public String toString() {
    Iterator<Integer> iterator = iterator();
    if (!iterator.hasNext()) {
        return "[]";
    }

    StringBuilder s = new StringBuilder("[").append(iterator.next());
    while (iterator.hasNext()) {
        s.append(" -> ").append(iterator.next());
    }
    return s.append(']').toString();
}

The iterator's next() should throw NoSuchElementException instead of crashing with a NullPointerException.

The ability to remove a node from the middle of a list efficiently is the linked list's forte. If you're going to implement an iterator, I would expect you not to wimp out on remove().

---

Your unit test is as complex as the linked list code being tested, which doesn't inspire the feeling that it is obviously correct. A better strategy would be

expectReverse(new int[] {2, 1, 4, 3, 6, 5},
              new int[] {1, 2, 3, 4, 5, 6});

To write such a test, it would be useful to define and test a SinglyLinkedList.equals() method.