Swap items of a linked list in pairs

Question

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();
            curr.setNext(prev);
            prev.setNext(null);
            if (prev == mFirst) {
                mFirst = curr;
            }
            if (old != null) {
                old.setNext(curr);
            }
            old = prev;
            prev = next;
            if (prev != null) {
                curr = prev.getNext();
                if (curr == null) {
                    old.setNext(prev);
                    mLast = prev;
                }
            } else {
                mLast = old;
                break;
            }
        }
    }
}

Testing:

package com.reversell;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class SinglyLinkedListTest {

    private int[] single = new int[] {
            12
    };

    private int[] twoElems = new int[] {
            12, 34
    };
    private int[] twoElemsReversedPairs = new int[] {
            34, 12
    };

    private int[] threeElems = new int[] {
            12, 34, 78
    };
    private int[] threeElemsReversedPairs = new int[] {
            34, 12, 78
    };

    private int[] evenElems = new int[] {
            12, 34, 78, 124
    };
    private int[] evenElemsReversedPairs = new int[] {
            34, 12, 124, 78
    };

    private int[] oddElems = new int[] {
            12, 34, 78, 45, 90
    };
    private int[] oddElemsReversedPairs = new int[] {
            34, 12, 45, 78, 90
    };

    @Test
    public void test() {
        assertEquals(true, doReverse(new SinglyLinkedList(single), single, single));

        assertEquals(true, doReverse(new SinglyLinkedList(twoElems), twoElems, twoElemsReversedPairs));

        assertEquals(true, doReverse(new SinglyLinkedList(threeElems), threeElems, threeElemsReversedPairs));

        assertEquals(true, doReverse(new SinglyLinkedList(oddElems), oddElems, oddElemsReversedPairs));

        assertEquals(true, doReverse(new SinglyLinkedList(evenElems), evenElems, evenElemsReversedPairs));

    }

    private boolean isFirstCorrect(SinglyLinkedList linkedList, int value) {
        return linkedList.getFirst().getData() == value;
    }

    private boolean isLastCorrect(SinglyLinkedList linkedList, int value) {
        return linkedList.getLast().getData() == value;
    }

    private boolean doReverse(SinglyLinkedList list, int[] origArray, int[] reversedArray) {
        boolean checkOrig = isListCorect(list, origArray);
        if (!checkOrig) {
            return false;
        }
        list.reversePairs();

        return isFirstCorrect(list, reversedArray[0]) && isLastCorrect(list,
                reversedArray[reversedArray.length - 1]) && isListCorect(list, reversedArray);
    }

    private boolean isListCorect(SinglyLinkedList list, int[] array) {
        Node curr = list.getFirst();
        int arrayIndex = 0;
        while (curr != null) {
            if (array[arrayIndex] != curr.getData()) {
                return false;
            }
            curr = curr.getNext();
            arrayIndex++;
        }
        return true;
    }

}

Answer 1

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<Integer> 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.