Swap items of a linked list in pairs

Here is the source of the question:
GitHub


Given a singly linked list, swap the list items in pairs (reconnect
the pointers, not simply swap the values). For example:


Before: A->B->C->D


After: B->A->D->C

See the method reversePairs.

Node

class Node {

    private Node next;
    private int data;

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

    public int getData() {
        return data;
    }

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

    public Node getNext() {
        return next;
    }

    @Override
    public String toString() {
        return Integer.toString(data);
    }

}

SinglyLinkedList

```
public class SinglyLinkedList {

private Node mFirst;
private Node mLast;

public SinglyLinkedList(Node first) {
this.mFirst = first;
this.mLast = first;
}

public SinglyLinkedList(int []array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException();
}
this.mFirst = new Node(array[0]);
this.mLast = this.mFirst;
for (int i = 1; i < array.length; i++) {
addLast(new Node(array[i]));
}
}

public void addLast(Node node) {
mLast.setNext(node);
mLast = node;
}

public Node getFirst() {
return mFirst;
}

public Node getLast() {
return mLast;
}

public void print() {
Node current = mFirst;
System.out.print("[");
while (current != null) {
System.out.print(current);
current = current.getNext();
if (current != null) {
System.out.print(", ");
}
}
System.out.print("]");
System.out.println();
}

public void reversePairs() {
Node prev = mFirst;
Node curr = prev.getNext();
Node old = null;
while (curr != null) {
Node next = curr.getNext();

Simpler implementation

The implementation is a bit confusing:

-
Variable names like prev and old have too similar meanings,
which makes it hard to follow what they are referring to

-
The check prev == mFirst in every loop cycle is redundant: the condition will only be true near the head of the list

In addition, the current implementation doesn't handle the case of an empty list.

I propose this alternative, simpler implementation:

public void reversePairs() {
    Node sentinel = new Node(0);
    sentinel.setNext(mFirst);

    Node node = sentinel;
    while (true) {
        Node next = node.getNext();
        if (next == null || next.getNext() == null) {
            break;
        }
        node.setNext(swap(next));
        node = next;
        mLast = next;
    }

    mFirst = sentinel.getNext();

    if (mLast.getNext() != null) {
        mLast = mLast.getNext();
    }
}

private Node swap(Node node) {
    Node next = node.getNext();
    Node nextnext = next.getNext();
    node.setNext(nextnext);
    next.setNext(node);
    return next;
}

Note that this can be even more simple if you can let go of the mLast field: you could simply remove all the references to mLast from the above.
I don't think mLast is very useful in a singly linked list.

Unit testing

The way you test the implementation is convoluted, hard to follow,
because you are violating many good practices of unit testing:

• Test methods should:

• test just one thing

• be short

• be simple

• communicate clearly the inputs, expected outputs, and the causality relationship between the two

• A test class should not have non-trivial logic (who will test the test?)

Consider this alternative implementation for the test cases:

@Test
public void test_12_reversed_is_12() {
    assertArrayEquals(new int[]{12}, reversed(12));
}

@Test
public void test_12_34_reversed_is_34_12() {
    assertArrayEquals(new int[]{34, 12}, reversed(12, 34));
}

@Test
public void test_12_34_78_reversed_is_34_12() {
    assertArrayEquals(new int[]{34, 12, 78}, reversed(12, 34, 78));
}

@Test
public void test_12_34_78_124_reversed_is_34_12_124_78() {
    assertArrayEquals(new int[]{34, 12, 124, 78}, reversed(12, 34, 78, 124));
}

Notice that:

• The input and expected outputs are perfectly clear, and so is each test case

• Using assertArrayEquals instead of assertEquals(true, ...) produces much more readable output in case of a failure. assertEquals(true, ...) will only tell you that something was not true, without giving you more hints to debug. assertArrayEquals will tell you the mismatched values.

reversed is a helper method to facilitate simple test cases:

private int[] reversed(int... nums) {
    SinglyLinkedList list = new SinglyLinkedList(nums);
    list.reversePairs();
    return toArray(list);
}

toArray is another helper that perhaps should be part of SinglyLinkedList itself:

private int[] toArray(SinglyLinkedList list) {
    List values = new ArrayList<>();

    Node node = list.getFirst();
    while (node != null) {
        values.add(node.getData());
        node = node.getNext();
    }

    int[] arr = new int[values.size()];
    for (int index = 0; index < arr.length; ++index) {
        arr[index] = values.get(index);
    }
    return arr;
}

Here's a test case I'd like to work but it doesn't:

@Test
public void test_empty_reversed_is_empty() {
    assertArrayEquals(new int[]{}, reversed());
}

This fails, because SinglyLinkedList cannot be created empty.
That's a pity, as an empty linked list is an interesting corner case,
and I think it should be supported.

StackExchange Code Review Q#96871, answer score: 9