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?

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.