Swap items of a linked list in pairs - revision 2

Question

The first revision is available here and the code is available on GitHub. I modified the method reversePairs and added mSize to convert my singly linked list to an array.

Now my main question is the following: do I test all possible types of input for this problem?

SinglyLinkedList

package com.reversell;

public class SinglyLinkedList {

    private Node mFirst;
    private Node mLast;
    private int mSize;

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

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

    public int getSize() {
        return mSize;
    }

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

    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() {
        // The list is empty or contains one element
        if (mFirst == null || mFirst.getNext() == null) {
            return;
        }
        Node temp = null;
        Node fop = mFirst;
        mFirst = mFirst.getNext();
        while (fop != null && fop.getNext() != null) {
            if (temp != null) {
                // Set the next element of temp, where temp is the predecessor of fop.
                temp.setNext(fop.getNext());
            }
            // 12 -> 34 -> 88
            temp = fop.getNext(); // temp == 34
            fop.setNext(temp.getNext()); // 12 -> 88
            temp.setNext(fop); // 34 -> 12
            temp = temp.getNext(); // temp == 12
            fop = temp.getNext(); // fop == 88
            if (fop == null) {
                mLast = temp;
            } else {
                mLast = fop;
            }
        }
    }
}

Unit tests.

package com.reversell;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;

import org.junit.Test;

public class SinglyLinkedListTest {

    // The list is empty. We don't run the while loop in reversePairs
    @Test
    public void testEmpty() {
        int[] orig = new int[] {};
        int[] expected = new int[] {};
        SinglyLinkedList linkedList = new SinglyLinkedList(orig);
        assertArrayEquals(expected, toArray(reverse(linkedList)));
        assertNull(linkedList.getLast());
    }

    // The list contains one element. We don't run the while loop in reversePairs
    @Test
    public void testSingleElement() {
        int[] orig = new int[] { 12 };
        int[] expected = new int[] { 12 };

        SinglyLinkedList linkedList = new SinglyLinkedList(orig);
        assertArrayEquals(expected, toArray(reverse(linkedList)));
        assertEquals(new Node(expected[expected.length - 1]), linkedList.getLast());
    }

    // The while loop is run once.
    // We leave the loop because fop is null. We don't go inside (temp != null)
    @Test
    public void testTwoElements() {
        int[] orig = new int[] { 12, 34 };
        int[] expected = new int[] { 34, 12 };

        SinglyLinkedList linkedList = new SinglyLinkedList(orig);
        assertArrayEquals(expected, toArray(reverse(linkedList)));
        assertEquals(new Node(expected[expected.length - 1]), linkedList.getLast());
    }

    // The while loop is run once.
    // We leave the loop because fop.getNext() is null. We don't go inside (temp != null)
    @Test
    public void testThreeElements() {
        int[] orig = new int[] { 12, 34, 78 };
        int[] expected = new int[] { 34, 12, 78 };

        SinglyLinkedList linkedList = new SinglyLinkedList(orig);
        assertArrayEquals(expected, toArray(reverse(linkedList)));
        assertEquals(new Node(expected[expected.length - 1]), linkedList.getLast());
    }

    // The while loop is run more than once.
    // We go inside (temp != null).
    @Test
    public void testFourElements() {
        int[] orig = new int[] { 12, 34, 78 };
        int[] expected = new int[] { 34, 12, 78 };

        SinglyLinkedList linkedList = new SinglyLinkedList(orig);
        assertArrayEquals(expected, toArray(reverse(linkedList)));
        assertEquals(new Node(expected[expected.length - 1]), linkedList.getLast());
    }


    private SinglyLinkedList reverse(SinglyLinkedList list) {
        list.reversePairs();
        return list;
    }

    private int[] toArray(SinglyLinkedList list) {
        int[] arr = new int[list.getSize()];
        Node node = list.getFirst();
        int index = 0;
        while (node != null) {
            arr[index++] = node.getData();
            node = node.getNext();
        }
        return arr;
    }
}

Answer 1

My first impressions:

• There is altogether too much code, and it's too confusing.
• Your SinglyLinkedList class should not expose Nodes in its interface.
• If there is just one method to add a node to a singly-linked list, it should be addFirst() rather than addLast(). (Manipulating the end of the list efficiently requires that you maintain an mLast pointer, which is an unnecessary complication. Minimalism is crucial for interview situations.)
• Instead of print(), it would be more idiomatic to define toString().

"Raw" vs. "polished" linked lists

There are two styles of linked lists.

The simple kind exposes the list nodes as the interface. For an example of this, see Reversing k-sized sequences in a linked list. (This node-swapping question is a specific case of that problem where k = 2.) The user just manipulates pointers as necessary. There is no additional bookkeeping for, say, the size of the list.

In contrast, the Java LinkedList class presents a data structure where the nodes are an implementation detail that is hidden from the user.

What you have done, though, is a dangerous hybrid. By accepting and returning Nodes, you make is possible for other code to manipulate the node pointers behind your back, possibly rendering your mLast and mSize inconsistent.

Therefore, your method signatures should be designed such that they only accept and return ints, not Nodes.

Simplification

The problem can be solved without keeping track of mLast and mSize, so you should drop them. Then you no longer need to worry whether reversePairs() sets mLast correctly.

You can eliminate special cases by introducing a dummy node. In particular, a dummy node would let you get rid of the special handling for array[0] (and the special handling for an empty array). It would also make it impossible for mFirst to be null, thus eliminating that special case from reversePairs().

fop and temp aren't exactly variable names that make sense. temp, in particular, is almost always a horrible name that can be improved. In my solution below, I've defined a, b, c, and d up front for each iteration, and it's very simple to just adjust their next pointers.

public class SinglyLinkedList {
    /** Dummy node */    
    private final Node head = new Node(0);

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

    public void addFirst(int datum) {
        Node n = new Node(datum);
        n.setNext(this.head.getNext());
        this.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() {
        StringBuilder s = new StringBuilder("[");
        for (Node n = this.head.getNext(); n != null; n = n.getNext()) {
            s.append(n);
            s.append(", ");
        }
        if (s.length() >= 2) s.setLength(s.length() - 2);   // Remove final ", "
        return s.append(']').toString();
    }
}