Delete duplicates from unsorted linked list E.g: if a linked list contains 2->3->1->3->4 then the result should be 2->3->1->4. Notice that 3 has been eliminated.


This code is attributed to GeeksforGeeks.  I'm looking for code-review, optimizations and best practices.

public class EliminateDuplicateUnsortedLL&lt;T&gt; {

    private Node&lt;T&gt; first;
    private Node&lt;T&gt; last;

    public EliminateDuplicateUnsortedLL(List&lt;T&gt; items) {
        for (T item : items) {
            add(item);
        }
    }

    public void add(T item) {
        Node&lt;T&gt; node = new Node&lt;&gt;(item);
        if (first == null) {
            first = last = node;
        } else {
            last.next = node;
            last = node;
        }
    }

    private static class Node&lt;T&gt; {
        private Node&lt;T&gt; next;
        private T item;

        Node(T item) {
            this.item = item;
        }
    }


    public void eliminateDuplicates() {
        final Set&lt;T&gt; set = new HashSet&lt;T&gt;();
        Node&lt;T&gt; prev = null;
        for (Node&lt;T&gt; x = first; x != null; x = x.next) {
            if (set.contains(x.item)) {
                prev.next = x.next;
            } else {
                set.add(x.item);
                prev = x;
            }
        }
        last = prev;
    }


    public List&lt;T&gt; toList() {
        final List&lt;T&gt; list = new ArrayList&lt;&gt;();

        for (Node&lt;T&gt; x = first; x != null; x = x.next) {
            list.add(x.item);
        }

        return list;
    }

    @Override
    public int hashCode() {
        int hashCode = 1;
        for (Node&lt;T&gt; x = first; x != null; x = x.next)
            hashCode = 31*hashCode +  x.hashCode();
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        EliminateDuplicateUnsortedLL&lt;T&gt; other = (EliminateDuplicateUnsortedLL&lt;T&gt;) obj;
        Node&lt;T&gt; currentListNode = first; 
        Node&lt;T&gt; otherListNode =  other.first;

        while (currentListNode != null &amp;&amp; otherListNode != null) {
            if (currentListNode.item != otherListNode.item) return false;
            currentListNode = currentListNode.next;
            otherListNode = otherListNode.next;
        }
        return currentListNode == null &amp;&amp; otherListNode == null;
    }
}


Unit tests:

public class EliminateDuplicateUnsortedLLTest {

    @Test
    public void test1() {
        EliminateDuplicateUnsortedLL&lt;Integer&gt; edu1 = new EliminateDuplicateUnsortedLL&lt;Integer&gt;(Arrays.asList(1, 2, 3, 4, 5, 4, 3, 7));
        edu1.eliminateDuplicates();

        EliminateDuplicateUnsortedLL&lt;Integer&gt; eduExpected1 = new EliminateDuplicateUnsortedLL&lt;Integer&gt;(Arrays.asList(1, 2, 3, 4, 5, 7));
        assertEquals(eduExpected1, edu1);
    }


    @Test
    public void test2() {
        EliminateDuplicateUnsortedLL&lt;Integer&gt; edu2 = new EliminateDuplicateUnsortedLL&lt;Integer&gt;(Arrays.asList(7, 2, 5, 10, 4, 2, 9, 10));
        edu2.eliminateDuplicates();

        EliminateDuplicateUnsortedLL&lt;Integer&gt; eduExpected2 = new EliminateDuplicateUnsortedLL&lt;Integer&gt;(Arrays.asList(7, 2, 5, 10, 4, 9));
        assertEquals(eduExpected2, edu2);
    }

    @Test
    public void testAllDuplicates() {
        EliminateDuplicateUnsortedLL&lt;Integer&gt; edu3 = new EliminateDuplicateUnsortedLL&lt;Integer&gt;(Arrays.asList(2, 2, 2, 2, 2));
        edu3.eliminateDuplicates();

        EliminateDuplicateUnsortedLL&lt;Integer&gt; eduExpected3 = new EliminateDuplicateUnsortedLL&lt;Integer&gt;(Arrays.asList(2));
        assertEquals(eduExpected3, edu3);
    }

}
I also am not a fan of the code organization. I think a better way to approach this would be to implement the List interface around an ordered set like a LinkedHashSet as something like a SetList. Many of the methods could simply be delegated to the internal set, and only a few would really be left to implement.

Your code has a separate method, eliminateDuplicates, to filter out the duplicates, rather than filtering them as they are added. This means that, if that method is not called, the list is not consistent with its requirements. I would still get all the duplicates. A better strategy is to remove the duplicates as they are added to keep the list always consistent with its advertised behavior.

Lastly, the names of your test methods could use a little work. Names like test1 and test2 don't tell much of what the tests are or what they are testing.



Here's an example of such an implementation. It implements both List&lt;T&gt; and Set&lt;T&gt;, and so can be used in either place. I used two internal structures for simplicity.

public final class LinkedHashSetList&lt;E&gt; implements Set&lt;E&gt;, List&lt;E&gt;
{
    private Set&lt;E&gt; set;
    private List&lt;E&gt; list;

    public LinkedHashSetList() {
        set = new HashSet&lt;&gt;();
        list = new LinkedList&lt;&gt;();
    }

    public LinkedHashSetList(Collection&lt;? extends E&gt; c) {
        // LinkedHashSet so I don't have to track uniqueness and order
        set = new LinkedHashSet&lt;&gt;(c);
        list = new LinkedList&lt;&gt;(set);
    }

    @Override
    public boolean add(E el) {
        if(set.contains(el)) {
            return false;
        }

        list.add(el);
        set.add(el);
        return true;
    }

    // Optional method not implemented
    @Override
    public void add(int index, E element) {
        throw new UnsupportedOperationException("LinkedHashSetList#add(int, E) not implemented!");
    }

    @Override
    public boolean addAll(Collection&lt;? extends E&gt; c) {
        boolean isChanged = false;

        for(E el: c) {
            isChanged = isChanged || add(el);
        }

        return isChanged;
    }

    // Optional method not implemented
    @Override
    public boolean addAll(int index, Collection&lt;? extends E&gt; c) {
        throw new UnsupportedOperationException("LinkedHashSetList#addAll(int, Collection&lt;? extends E&gt; c) not implemented!");
    }

    // Optional method not implemented
    @Override
    public boolean retainAll(Collection&lt;?&gt; c) {
        throw new UnsupportedOperationException("LinkedHashSetList#retainAll(Collection&lt;?&gt; c) not implemented!");
    }

    @Override
    public E remove(int index) {
        E el = list.remove(index);
        set.remove(el);
        return el;
    }

    @Override
    public boolean remove(Object el) {
        list.remove(el);
        return set.remove(el);
    }

    @Override
    public boolean removeAll(Collection&lt;?&gt; c) {
        list.removeAll(c);
        return set.removeAll(c);
    }

    @Override
    public void clear() {
        list.clear();
        set.clear();
    }

    // Optional method not implemented
    @Override
    public E set(int index, E el) {
        throw new UnsupportedOperationException("LinkedHashSetList#set(int, E) not implemented!");
    }

    @Override
    public E get(int index) {
        return list.get(index);
    }

    @Override
    public boolean contains(Object el) {
        return set.contains(el);
    }

    @Override
    public boolean containsAll(Collection&lt;?&gt; c) {
        return set.containsAll(c);
    }

    @Override
    public int indexOf(Object el) {
        return list.indexOf(el);
    }

    @Override
    public int lastIndexOf(Object el) {
        return list.indexOf(el);
    }

    // WARNING: Changes to sublist can affect this list in undefined ways
    @Override
    public List&lt;E&gt; subList(int fromIndex, int toIndex) {
        return list.subList(fromIndex, toIndex);
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public int size() {
        return list.size();
    }

    // Not safe if remove is called on iterator
    @Override
    public Iterator&lt;E&gt; iterator() {
        return list.iterator();
    }

    // Not safe if remove is called on iterator
    @Override
    public ListIterator&lt;E&gt; listIterator() {
        return list.listIterator();
    }

    // Not safe if remove is called on iterator
    @Override
    public ListIterator&lt;E&gt; listIterator(int index) {
        return list.listIterator(index);
    }

    @Override
    public Object[] toArray() {
        return list.toArray();
    }

    @Override
    public &lt;T&gt; T[] toArray(T[] a) {
        return list.toArray(a);
    }
}


Unit Tests:

public class LinkedHashSetListTest
{
    @Test
    public void testRemovesDuplicates() {
        LinkedHashSetList&lt;Integer&gt; lhsl = new LinkedHashSetList&lt;&gt;(Arrays.asList(1, 1, 2, 2, 3, 3, 1, 7, 4, 6, 6));
        Integer[] expected = { 1, 2, 3, 7, 4, 6 };
        assertArrayEquals(expected, lhsl.toArray(new Integer[expected.length]));
    }

    @Test
    public void testRemovesNothingWhenNoDuplicates() {
        LinkedHashSetList&lt;Integer&gt; lhsl = new LinkedHashSetList&lt;&gt;(Arrays.asList(1, 2, 3, 7, 4, 6));
        Integer[] expected = { 1, 2, 3, 7, 4, 6 };
        assertArrayEquals(expected, lhsl.toArray(new Integer[expected.length]));
    }

    @Test
    public void testEmptyList() {
        LinkedHashSetList&lt;Integer&gt; lhsl = new LinkedHashSetList&lt;&gt;(new LinkedList&lt;Integer&gt;());
        Integer[] expected = {};
        assertArrayEquals(expected, lhsl.toArray(new Integer[expected.length]));
    }
}


Caveats regarding sublists and iterators are noted. The solution to the iterators would be to create a new Iterator specifically for this class. Sublisting is a bit more complicated to solve, since the sublist is backed by the original list.