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

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

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

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 {
prev = x;
}
}
last = prev;
}

public List<T> toList() {
final List<T> list = new ArrayList<>();

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

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);
}

}

-
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 '14 at 22:00
These are interview questions - they want / demand an implementation not a ready made API. – JavaDeveloper Aug 14 '14 at 20:17

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;

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;
}

return true;
}

// Optional method not implemented
@Override
public void add(int index, E element) {
}

@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() {
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.

-
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 '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 '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());

-
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 '14 at 16:34
@cbojar Node<T>'s implementation is included in the question. – mjolka Aug 14 '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 '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 '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

-
you need to explicitly call the method to remove duplicates - thats what is demanded in interview question – JavaDeveloper Aug 14 '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) {
}


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) {
}


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));
}


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 {
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) {
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;
}
}
}

-
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 '14 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 '14 at 6:32