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.

• Maksim Dmitriev: I added revision 4.