2
\$\begingroup\$

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();
        }
    }
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.