Swap items of a linked list in pairs - revision 4

Question

Here is the source of the question.

The solution on GitHub.

Revision 1.

Revision 2.

Revision 3.

@200_success' suggestions from revision 3:

• The iterator's next() will throw a NoSuchElementException if we run off the last element of the list while iterating.
• Iterator.remove() is implemented.
• The implementation of SinglyLinkedList.toString() is more straightforward.

---

My changes:

• toArray and size for tests.
• I made Node a static nested class of SinglyLinkedList as they do with Entry in the Java LinkedList class. It allowed me not to implement setNext, getNext, and getData of Node. Anyway, Node not accessible for client code. So I think I can access members of Node directly, and it's not dangerous.

The questions I have now:

1. Do my tests cover all the edge cases of the algorithm? See SinglyLinkedList.reversePairs() and SinglyLinkedListTest.
2. Do I need to null out the reference to cur in my iterator's remove() method? See the uploaded image below the questions.
3. Why would I need SinglyLinkedList.equals() which was suggested here?

My iterator's remove()

SinglyLinkedList

package com.singlylinkedlist;
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;
 public SinglyLinkedList(int[] data) {
 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++;
 }
 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.next) != null && (c = b.next) != null) {
 Node d = c.next;
 a.next = c;
 c.next = b;
 b.next = d;
 a = b;
 }
 }
 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;
 Node current = head;
 Node next = current.next;
 @Override
 public void remove() {
 prev.next = next;
 current.next = null;
 current = null; // TODO: Do I need to eliminate this obsolete reference?
 current = next;
 if (current == null) {
 next = null;
 } else {
 next = current.next;
 }
 }
 @Override
 public Integer next() {
 if (!hasNext()) {
 throw new NoSuchElementException();
 }
 prev = current;
 current = next;
 next = next.next;
 return current.data;
 }
 @Override
 public boolean hasNext() {
 return next != null;
 }
 };
 }
 private static class Node {
 Node next;
 int data;
 Node(int data) {
 this.data = data;
 }
 @Override
 public boolean equals(Object obj) {
 if (obj == this) {
 return true;
 }
 if (!(obj instanceof Node)) {
 return false;
 }
 Node another = (Node) obj;
 return data == another.data;
 }
 @Override
 public int hashCode() {
 int result = 17;
 result = 31 * result + data;
 return result;
 }
 }
}

SinglyLinkedListTest

package com.singlylinkedlist;
import org.junit.Assert;
import org.junit.Test;
public class SinglyLinkedListTest {
 @Test
 public void testEmpty() {
 int[] orig = new int[] {};
 int[] reversed = new int[] {};
 SinglyLinkedList linkedList = new SinglyLinkedList(orig);
 linkedList.reversePairs();
 Assert.assertArrayEquals(reversed, linkedList.toArray());
 }
 @Test
 public void testSingle() {
 int[] orig = new int[] { 1 };
 int[] reversed = new int[] { 1 };
 SinglyLinkedList linkedList = new SinglyLinkedList(orig);
 linkedList.reversePairs();
 Assert.assertArrayEquals(reversed, linkedList.toArray());
 }
 @Test
 public void testLoopOnce() {
 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 testLoopMoreThanOnce() {
 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());
 }
}

Answer 1

Note that you are taking an improper shortcut with your box-and-pointer diagrams by labelling the boxes with variable names. Such a shortcut will lead to errors in reasoning. Here's how you should draw your first diagram instead:

$$ \newcommand{ptr}[1]{\overset{\mathtt{#1}}{\longrightarrow}} \begin{align} & \mathtt{prev} && \mathtt{cur} && \mathtt{next} \\ & \downarrow && \downarrow && \downarrow \\ & \fbox{Node}\ptr{next} && \fbox{Node}\ptr{next} && \fbox{Node}\ptr{next} \cdots \end{align} $$

prev, cur, and next are variables that refer to instances of Node. Each instance is an object that has no intrinsic name.

---

Iterator.remove() must throw an IllegalStateOperation if next() has not yet been called, or if next() has not been called between two calls to remove(). In addition, you may choose to throw a ConcurrentModificationException if you detect contention.

I don't believe you need three Node variables in the iterator. Here's how I would write it:

public Iterator<Integer> iterator() {
 return new Iterator<Integer>() {
 Node prev = head, current = head;
 boolean removable = false;
 @Override
 public void remove() {
 if (!this.removable) {
 throw new IllegalStateException("next() has not been called");
 }
 this.removable = false;
 this.prev.next = this.current.next;
 }
 @Override
 public Integer next() {
 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;
 }
 };
}

---

The equals() and hashCode() methods of Node are never called in this code, nor is the Node ever revealed outside the class. Therefore, these methods are dead code.

They could be implemented more simply:

@Override
public boolean equals(Object obj) {
 return obj == this ||
 (obj instanceof Node && this.data == ((Node)obj).data);
}
@Override
public int hashCode() {
 return this.data;
}

I think that there is no point to adding 527 to every hashcode.

• Maksim Dmitriev: I don't understand the logic of your remove(). It looks like you remove prev rather than current. However, it works as expected
• Maksim Dmitriev: I deleted hashCode and equals(). They aren't essential in my solution. But what do you mean by adding 527?
• 200_success: 31 * result is always 527.
• 200_success: this.prev.next = this.current.next does the real work. this.prev = null doesn't delete prev; it just unsets prev such that you can't remove() again until you call next() first. (The difference between unsetting and deleting illustrates why you shouldn't label box-and-pointer diagrams the way you did.)
• Maksim Dmitriev: I got your idea about 527. In fact, I just copied the example from Effective Java 2nd Edition (page 48).