patternjavaMinor

Delete duplicates from unsorted linked list

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

deleteunsortedlistfromlinkedduplicates

Problem

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 {

private Node first;
private Node last;

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

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

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

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

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

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

return list;
}

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

while (currentLis

Solution

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

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

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

    public LinkedHashSetList(Collection 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 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 c) {
        throw new UnsupportedOperationException("LinkedHashSetList#addAll(int, Collection 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 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 iterator() {
        return list.iterator();
    }

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

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

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

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

Unit Tests:

```
public class LinkedHashSetListTest
{
@Test
public void testRemovesDuplicates() {
LinkedHashSetList 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() {

Code Snippets

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

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

Context

StackExchange Code Review Q#59948, answer score: 7

Revisions (0)

No revisions yet.