Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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<T> {

    private Node<T> first;
    private Node<T> last;

    public EliminateDuplicateUnsortedLL(List<T> items) {
        for (T item : items) {
            add(item);
        }
    }

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

    private static class Node<T> {
        private Node<T> next;
        private T item;

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


    public void eliminateDuplicates() {
        final Set<T> set = new HashSet<T>();
        Node<T> prev = null;
        for (Node<T> 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<T> toList() {
        final List<T> list = new ArrayList<>();

        for (Node<T> x = first; x != null; x = x.next) {
            list.add(x.item);
        }

        return list;
    }

    @Override
    public int hashCode() {
        int hashCode = 1;
        for (Node<T> 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<T> other = (EliminateDuplicateUnsortedLL<T>) obj;
        Node<T> currentListNode = first; 
        Node<T> otherListNode =  other.first;

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

Unit tests:

public class EliminateDuplicateUnsortedLLTest {

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

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


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

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

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

        EliminateDuplicateUnsortedLL<Integer> eduExpected3 = new EliminateDuplicateUnsortedLL<Integer>(Arrays.asList(2));
        assertEquals(eduExpected3, edu3);
    }

}
share|improve this question
    
Why not use the LinkedHashSet as suggested in one of the answers? That seems to provide what you need with no additional code (ordering like a List and unique elements like a Set). Do you need both the view with duplicates and the de-duplicated view? Then using two structures would be simpler. –  Maarten Winkels Aug 13 at 22:00
    
These are interview questions - they want / demand an implementation not a ready made API. –  JavaDeveloper Aug 14 at 20:17

4 Answers 4

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<T> and Set<T>, and so can be used in either place. I used two internal structures for simplicity.

public final class LinkedHashSetList<E> implements Set<E>, List<E>
{
    private Set<E> set;
    private List<E> list;

    public LinkedHashSetList() {
        set = new HashSet<>();
        list = new LinkedList<>();
    }

    public LinkedHashSetList(Collection<? extends E> c) {
        // LinkedHashSet so I don't have to track uniqueness and order
        set = new LinkedHashSet<>(c);
        list = new LinkedList<>(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<? extends E> 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<? extends E> c) {
        throw new UnsupportedOperationException("LinkedHashSetList#addAll(int, Collection<? extends E> c) not implemented!");
    }

    // Optional method not implemented
    @Override
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException("LinkedHashSetList#retainAll(Collection<?> 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<?> 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<?> 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<E> 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<E> iterator() {
        return list.iterator();
    }

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

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

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

    @Override
    public <T> T[] toArray(T[] a) {
        return list.toArray(a);
    }
}

Unit Tests:

public class LinkedHashSetListTest
{
    @Test
    public void testRemovesDuplicates() {
        LinkedHashSetList<Integer> lhsl = new LinkedHashSetList<>(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<Integer> lhsl = new LinkedHashSetList<>(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<Integer> lhsl = new LinkedHashSetList<>(new LinkedList<Integer>());
        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.

share|improve this answer
    
eliminateDuplicates, to filter out the duplicates, rather than filtering them as they are added - as said this is an interview question, its specific 'given a list with ... do ...' –  JavaDeveloper Aug 14 at 20:18
    
@JavaDeveloper I'm not sure what you are trying to say? The fact that this is an interview question doesn't change anything for me. I'd think knowing how not to reinvent the wheel by using core libraries is something they might want to see. If there are more details or restrictions to the question, then you should add them. –  cbojar Aug 14 at 23:14

Your implementations of equals and hashCode violate the contract of hashCode:

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

The following code prints true false:

EliminateDuplicateUnsortedLL<Integer> a = new EliminateDuplicateUnsortedLL<>(Arrays.asList(1));
EliminateDuplicateUnsortedLL<Integer> b = new EliminateDuplicateUnsortedLL<>(Arrays.asList(1));
System.out.printf("%b %b%n", a.equals(b), a.hashCode() == b.hashCode());
share|improve this answer
    
The reason is that he didn't (or did improperly) override the implementation of hashCode in Node<T>. Unfortunately, Node<T>'s implementation wasn't included. –  cbojar Aug 14 at 16:34
    
@cbojar Node<T>'s implementation is included in the question. –  mjolka Aug 14 at 22:33
    
Ah, indeed it is. I missed it in there. Well then we can plainly see that the problem lies in failing to override hashCode in Node<T>. –  cbojar Aug 14 at 23:06
    
@cbojar I would say the problem was overriding equals and hashCode in the first place; we're not placing them in a hash map, and don't need them. The unit tests can use toList and compare to that. It would also make the tests shorter: assertEquals(Arrays.asList(2), linkedList.toList());. –  mjolka Aug 14 at 23:40

I don't like how you organised your code. I would think you just need an utility method

List <T> removeDuplicates (List <T> source)

Or a class:

ListWithoutDuplicates extends List <T>

In the first case you would need to produce a new list filtering the source one. In the second you would need to wrap an existing list providing a view that does not show its duplicate elements.

What I don't like in this approach is that the name suggests that we have a linked list but it does not follow the APIs in the list interface.

Another thing that looks quite bad to me is that you need to explicitly call the method to remove duplicates

share|improve this answer
    
you need to explicitly call the method to remove duplicates - thats what is demanded in interview question –  JavaDeveloper Aug 14 at 20:20

Unit testing

Your unit tests are not easy to read. You could improve that by extracting the common logic of what they do to a helper method that you can reuse by all of those tests, for example:

private void assertEqualsAfterDeleteDups(List<Integer> expected, List<Integer> orig) {
    LinkedList<Integer> linkedList = new LinkedList<>(orig);
    linkedList.eliminateDuplicates();
    assertEquals(new LinkedList<>(expected), linkedList);
}

This way, instead of:

@Test
public void test2() {
    LinkedListWithEliminateDups<Integer> edu2 = new LinkedListWithEliminateDups<Integer>(Arrays.asList(7, 2, 5, 10, 4, 2, 9, 10));
    edu2.eliminateDuplicates();

    LinkedListWithEliminateDups<Integer> eduExpected2 = new LinkedListWithEliminateDups<Integer>(Arrays.asList(7, 2, 5, 10, 4, 9));
    assertEquals(eduExpected2, edu2);
}

You could write in a more compact way:

@Test
public void test2() {
    assertEqualsAfterDeleteDups(Arrays.asList(7, 2, 5, 10, 4, 9), Arrays.asList(7, 2, 5, 10, 4, 2, 9, 10));
}

And you could apply this to all your test methods.

I also strongly recommend to do not only assertEquals, but throw in at least a few assertNotEquals as well. It's important to test your implementation from multiple angles, otherwise there could be bugs that remain hidden from one-sided tests.

So I would add another helper for the not-equals tests:

private void assertNotEqualsAfterDeleteDups(List<Integer> expected, List<Integer> orig) {
    LinkedList<Integer> linkedList = new LinkedList<>(orig);
    linkedList.eliminateDuplicates();
    assertNotEquals(new LinkedList<>(expected), linkedList);
}

And I would add some more tests for potential corner cases:

@Test
public void testEliminateSingleDup() {
    assertEqualsAfterDeleteDups(Arrays.asList(1, 2, 3, 4, 5, 7), Arrays.asList(1, 2, 3, 4, 5, 4, 3, 7));
    assertNotEqualsAfterDeleteDups(Arrays.asList(1, 3, 4, 5, 7), Arrays.asList(1, 2, 3, 4, 5, 4, 3, 7));
    assertNotEqualsAfterDeleteDups(Arrays.asList(1, 2, 3), Arrays.asList(4, 5, 6));
}

@Test
public void testEliminateSingleDupAtStart() {
    assertEqualsAfterDeleteDups(Arrays.asList(1, 2, 3), Arrays.asList(1, 1, 2, 3));
}

@Test
public void testEliminateSingleDupAtEnd() {
    assertEqualsAfterDeleteDups(Arrays.asList(1, 2, 3), Arrays.asList(1, 2, 3, 3));
}

@Test
public void testEliminateManyDups() {
    assertEqualsAfterDeleteDups(Arrays.asList(1, 2, 3), Arrays.asList(1, 1, 2, 2, 2, 3, 3, 3));
}

@Test
public void testEliminateNothing() {
    assertEqualsAfterDeleteDups(Arrays.asList(1, 2, 3), Arrays.asList(1, 2, 3));
    assertNotEqualsAfterDeleteDups(Arrays.asList(1, 2), Arrays.asList(1, 2, 3));
}

@Test
public void testEmpty() {
    assertEqualsAfterDeleteDups(Arrays.asList(), Arrays.asList());
    assertNotEqualsAfterDeleteDups(Arrays.asList(2), Arrays.asList());
}

@Test
public void testSingletonList() {
    assertEqualsAfterDeleteDups(Arrays.asList(2), Arrays.asList(2));
    assertNotEqualsAfterDeleteDups(Arrays.asList(3), Arrays.asList(2));
}

Reuse your previous LinkedList classes

The linked list implementation is almost the same as in your previous question. I strongly recommend to start using inheritance, and instead of copy-pasting the previous implementation and adding a single new eliminateDuplicates method, extend the previous implementation.

Your new class for this problem could be:

class LinkedListWithEliminateDups<T> extends LinkedList<T> {

    public LinkedListWithEliminateDups(List<T> items) {
        super(items);
    }

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

And the old class that you can use as the base:

class LinkedList<T> {

    Node<T> first;
    Node<T> last;

    public LinkedList(List<T> items) {
        for (T item : items) {
            create(item);
        }
    }

    private void create(T item) {
        Node<T> node = new Node<>(item);
        if (first == null) {
            first = last = node;
        } else {
            last.next = node;
            last = node;
        }
    }

    @Override
    public int hashCode() {
        int hashCode = 1;
        for (Node<T> node = first; node != null; node = node.next) {
            hashCode = 31 * hashCode + node.hashCode();
        }
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof LinkedList) {
            LinkedList<T> other = (LinkedList<T>) obj;
            Node<T> currentListNode = first;
            Node<T> otherListNode = other.first;

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

    static class Node<T> {
        Node<T> next;
        T item;

        Node(T item) {
            this.item = item;
        }
    }
}
share|improve this answer
    
I'm not sure what the not-equals tests would buy you other than to test JUnit's assertions which is out of scope, but +1 for the rest. –  David Harkness Aug 13 at 23:45
    
While trying to refactor his equals method, I broke it, and all the assertEquals were passing, because with the broken code anything was equal to anything. I've experienced similar in real life too, if your tests are one-sided you can miss important bugs. Notice I didn't add this kind of inverse test everywhere, only in a few places, for sanity. Probably I should split the test cases to make that more explicit. –  janos Aug 14 at 6:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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