Sort a linkedlist with 3 elements 0, 1 and 2 Given a linked list of 0s, 1s and 2s, sort it. Looking for code review, optimizations and best practices

public final class SortZeroesOnesTwos {

    private Node first;
    private Node last;
    private int size;

    public SortZeroesOnesTwos(List&lt;Integer&gt; items) {
        for (Integer item : items) {
            add(item);
        }
    }
    public void add(Integer item) {
        Node node = new Node(item);
        Node l = last;
        last = node;
        if (first == null) {
            first = node;
        } else {
            l.next = node;
        }
        size++;
    }

    private static class Node {
        private int item;
        private Node next;

        public Node(int item) {
            this.item = item;
        }
    }

    public void sortZeroesOnesAndTwos() {
        int[] a = new int[3];

        Node node = first;
        while (node != null) {
            a[node.item] = a[node.item] + 1; 
            node = node.next;
        }

        node = first;
        int i = 0;
        while (node != null) {
            if (a[i] == 0) { 
                i++; 
            } else { 
                node.item = i;
                node = node.next;
                a[i] = a[i] - 1;
            }
        }
    }

    public int[] toArray() {
        int[] result = new int[size];
        int i = 0;
        for (Node x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }
 }


public class SortZerosOnesTwosTest {

    @Test
    public void test1() {
        SortZeroesOnesTwos sortList = new SortZeroesOnesTwos(Arrays.asList(0, 1, 2, 1, 2, 0));
        sortList.sortZeroesOnesAndTwos();
        int[] expected = {0, 0, 1, 1, 2, 2};
        assertTrue(Arrays.equals(expected, sortList.toArray()));
    }


    @Test
    public void test2() {
        SortZeroesOnesTwos sortList2 = new SortZeroesOnesTwos(Arrays.asList(1, 2, 1, 2));
        sortList2.sortZeroesOnesAndTwos();
        int[] expected2 = {1, 1, 2, 2};
        assertTrue(Arrays.equals(expected2, sortList2.toArray()));
    }


    @Test
    public void test3() {
        SortZeroesOnesTwos sortList3 = new SortZeroesOnesTwos(Arrays.asList(0, 2, 0, 2));
        sortList3.sortZeroesOnesAndTwos();
        int[] expected3 = {0, 0, 2, 2};
        assertTrue(Arrays.equals(expected3, sortList3.toArray()));
    }

    @Test
    public void test4() {
        SortZeroesOnesTwos sortList4 = new SortZeroesOnesTwos(Arrays.asList(0, 1, 0, 1));
        sortList4.sortZeroesOnesAndTwos();
        int[] expected4 = {0, 0, 1, 1};
        assertTrue(Arrays.equals(expected4, sortList4.toArray()));
    }
}
The mash-up you continue to have with Objects and primitives is something that is easy to resolve, yet you don't. Is there some reason I am missing why it is important to convert your data to an Integer Object before converting it back to an int?


public void add(Integer item) {



Why can't that be:

public void add(int value) {


???? Your Node class stores it as an int, so there is no reason to do the multiple conversions.

The algorithm you have used for the 'sorting' is similar to what I would do. There are a few nitpicks though (one of them is not so small....):


Use Post-increment and Post-Decrement operators:


a[node.item] = a[node.item] + 1;



and


a[i] = a[i] - 1;



should be:

a[node.item]++;


and

a[i]--;

Why use a linked list at all? Seriously, what does the Node concept buy you? This problem could easily be solved with a primitive array (... or an ArrayList, or LinkedList if you were not using primitives .....). If your data was stored as an array, it would be as simple as:

public void sortZeroesOnesAndTwos() {
    int[] itemcount = new int[3];

    for (int item : data) {
        itemcount[item]++; 
    }

    int pos = 0;
    for (int item = 0; item &lt; a.length; item++) {
        while (itemcount[item]-- &gt; 0) {
            data[pos++] = item;
        }
    }
}