Swap items of a linked list in pairs - revision 5

Question

Here is the source of the question.

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

• Revision 1
• Revision 2
• Revision 3
• Revision 4

This revision is available on GitHub.

I decided not to delete my iterator although it's not essential for pair-reversing items in a singly linked list. But with help of @200_success I have a good iterator, and I want to keep it.

In this revision I'd love to focus on code coverage. I use EclEmma for Eclipse to see which branches of code are covered.

SinglyLinkedList

package com.singlylinkedlist;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class SinglyLinkedList implements Iterable<Integer> {
 /** Dummy node */
 private final Node head = new Node(0);
 private int size;
 private int modCount = 0;
 public SinglyLinkedList(int... data) {
 if (data == null) {
 return;
 }
 for (int i = data.length - 1; i >= 0; i--) {
 addFirst(data[i]);
 }
 }
 public void addFirst(int datum) {
 Node n = new Node(datum);
 n.next = head.next;
 head.next = n;
 size++;
 modCount++;
 }
 public boolean reversePairs() {
 if (size < 2) {
 return false;
 }
 // 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.next) != null && (c = b.next) != null) {
 Node d = c.next;
 a.next = c;
 c.next = b;
 b.next = d;
 a = b;
 }
 modCount++;
 return true;
 }
 public int getSize() {
 return size;
 }
 public int[] toArray() {
 int array[] = new int[size];
 int i = 0;
 Iterator<Integer> iterator = iterator();
 while(iterator.hasNext()) {
 array[i++] = iterator.next();
 }
 return array;
 }
 @Override
 public String toString() {
 Iterator<Integer> iterator = iterator();
 if (!iterator.hasNext()) {
 return "[]";
 }
 StringBuilder s = new StringBuilder("[" + iterator.next());
 while(iterator.hasNext()) {
 int nodeValue = iterator.next();
 s.append(" -> " + nodeValue);
 }
 return s.append(']').toString();
 }
 @Override
 public Iterator<Integer> iterator() {
 return new Iterator<Integer>() {
 Node prev = head, current = head;
 boolean removable = false;
 int expectedModCount = modCount;
 @Override
 public void remove() {
 if (!this.removable) {
 throw new IllegalStateException("next() has not been called");
 }
 checkForComodification();
 this.removable = false;
 this.prev.next = this.current.next;
 updateModCount();
 size--;
 }
 @Override
 public Integer next() {
 checkForComodification();
 if (!hasNext()) {
 throw new NoSuchElementException();
 }
 if (this.removable) this.prev = this.current;
 this.current = this.current.next;
 this.removable = true;
 return this.current.data;
 }
 @Override
 public boolean hasNext() {
 return this.current.next != null;
 }
 void checkForComodification() {
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 }
 void updateModCount() {
 expectedModCount++;
 modCount++;
 }
 };
 }
 private static class Node {
 Node next;
 int data;
 Node(int data) {
 this.data = data;
 }
 }
}

SinglyLinkedListTest

package com.singlylinkedlist;
import org.junit.Assert;
import org.junit.Test;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class SinglyLinkedListTest {
 @Test
 public void testEmpty() {
 // we'll leave the while loop because size == 0
 SinglyLinkedList linkedList = new SinglyLinkedList(new int[] {});
 boolean modified = linkedList.reversePairs();
 Assert.assertFalse(modified);
 }
 @Test
 public void testSingle() {
 // we'll leave the while loop because size == 1
 SinglyLinkedList linkedList = new SinglyLinkedList(new int[] { 1 });
 boolean modified = linkedList.reversePairs();
 Assert.assertFalse(modified);
 }
 @Test
 public void test_b_and_c_null() {
 // Initially (b != null && c != null)
 // Then we'll leave the while loop because (b == null && c == null)
 int[] orig = new int[] { 1, 2 };
 int[] reversed = new int[] { 2, 1 };
 SinglyLinkedList linkedList = new SinglyLinkedList(orig);
 linkedList.reversePairs();
 Assert.assertArrayEquals(reversed, linkedList.toArray());
 }
 @Test
 public void test_b_not_null_c_null() {
 // Initially (b != null && c != null)
 // Then we'll leave the while loop because (b != null && c == null)
 int[] orig = new int[] { 1, 2, 3 };
 int[] reversed = new int[] { 2, 1, 3 };
 SinglyLinkedList linkedList = new SinglyLinkedList(orig);
 linkedList.reversePairs();
 Assert.assertArrayEquals(reversed, linkedList.toArray());
 }
 @Test
 public void testLoopMoreThanOnceEven() {
 int[] orig = new int[] { 1, 2, 3, 4, 5, 6 };
 int[] reversed = new int[] { 2, 1, 4, 3, 6, 5 };
 SinglyLinkedList linkedList = new SinglyLinkedList(orig);
 linkedList.reversePairs();
 Assert.assertArrayEquals(reversed, linkedList.toArray());
 }
 @Test
 public void testLoopMoreThanOnceOdd() {
 int[] orig = new int[] { 1, 2, 3, 4, 5, 6, 7 };
 int[] reversed = new int[] { 2, 1, 4, 3, 6, 5, 7 };
 SinglyLinkedList linkedList = new SinglyLinkedList(orig);
 linkedList.reversePairs();
 Assert.assertArrayEquals(reversed, linkedList.toArray());
 }
 @Test
 public void testToStringEmpty() {
 SinglyLinkedList linkedList = new SinglyLinkedList(null);
 Assert.assertEquals("[]", linkedList.toString());
 }
 @Test
 public void testToStringNoNext() {
 SinglyLinkedList linkedList = new SinglyLinkedList(1);
 Assert.assertEquals("[1]", linkedList.toString());
 }
 @Test
 public void testToStringHasNext() {
 SinglyLinkedList linkedList = new SinglyLinkedList(1, 2);
 Assert.assertEquals("[1 -> 2]", linkedList.toString());
 }
 @Test(expected = ConcurrentModificationException.class)
 public void testAddAfterCreatingIterator() {
 SinglyLinkedList linkedList = new SinglyLinkedList(new int[] { 1, 2, 3, 4 });
 Iterator<Integer> iterator = linkedList.iterator();
 if (iterator.hasNext()) {
 linkedList.addFirst(12);
 iterator.next();
 }
 }
 @Test(expected = IllegalStateException.class)
 public void testRemoveTwice() {
 SinglyLinkedList linkedList = new SinglyLinkedList(new int[] { 1, 2, 3, 4 });
 Iterator<Integer> iterator = linkedList.iterator();
 while (iterator.hasNext()) {
 iterator.remove();
 }
 }
 @Test(expected = NoSuchElementException.class)
 public void testNextAfterIteration() {
 SinglyLinkedList linkedList = new SinglyLinkedList(new int[] { 1, 2, 3, 4 });
 Iterator<Integer> iterator = linkedList.iterator();
 while (iterator.hasNext()) {
 iterator.next();
 }
 iterator.next();
 }
 @Test
 public void testRemove() {
 SinglyLinkedList linkedList = new SinglyLinkedList(new int[] { 1, 2, 3, 4 });
 Iterator<Integer> iterator = linkedList.iterator();
 while (iterator.hasNext()) {
 int data = iterator.next();
 if (data == 1 || data == 4) {
 iterator.remove();
 }
 }
 Assert.assertArrayEquals(new int [] {2, 3}, linkedList.toArray());
 }
}

Formally testLoopMoreThanOnceEven and testLoopMoreThanOnceOdd don't add to code coverage, but I added them because I wanted to make sure the references a, b, and c are reassigned correctly.

• Emz: private int modCount = 0; to initialize it with 0 is pointless as the default value is already 0 which can be read here. I also recommend adding a full javadoc coverage to it. More can be read here..
• Maksim Dmitriev: @Emz, this problem is from a job interview. I don't think I would have time to write documentation there

Answer 1

 Node a = this.head, b, c;

What does this do? It's a rather weird declaration.

 while ((b = a.next) != null && (c = b.next) != null) {
 Node d = c.next;
 a.next = c;
 c.next = b;
 b.next = d;
 a = b;
 }

Unneeded local store, d can be removed:

 while ((b = a.next) != null && (c = b.next) != null) {
 a.next = c;
 b.next = c.next;
 c.next = b;
 a = b;
 }

Expanded explanation for those who have a hard time following along:

a = 1
a.next = 2
b = 2
b.next = 3
c = 3
c.next = 4
a.next = c
a = 1
a.next = 3
b = 2
b.next = 3
c = 3
c.next = 4
b.next = c.next
a = 1
a.next = 3
b = 2
b.next = 4
c = 3
c.next = 4
c.next = b
a = 1
a.next = 3
b = 2
b.next = 4
c = 3
c.next = 2

Now 1 points to 3 points to 2 points to 4. ACBD. Just like the example. Lastly,

a = b for next iteration

• Maksim Dmitriev: d can't be removed. There is b.next = d; in SinglyLinkedList
• Pimgd: @MaksimDmitriev You're wrong, see updated answer.