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
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.
private int modCount = 0;to initialize it with0is pointless as the default value is already0which can be read here. I also recommend adding a full javadoc coverage to it. More can be read here.. \$\endgroup\$