5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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.. \$\endgroup\$ – Emz Aug 12 '15 at 13:35
  • \$\begingroup\$ @Emz, this problem is from a job interview. I don't think I would have time to write documentation there \$\endgroup\$ – Maksim Dmitriev Aug 12 '15 at 16:28
3
\$\begingroup\$
    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
\$\endgroup\$
  • \$\begingroup\$ d can't be removed. There is b.next = d; in SinglyLinkedList \$\endgroup\$ – Maksim Dmitriev Nov 1 '15 at 15:54
  • 1
    \$\begingroup\$ @MaksimDmitriev You're wrong, see updated answer. \$\endgroup\$ – Pimgd Nov 1 '15 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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