Clever Geek Handbook

Removing duplicates from a singly linked list

Is there a way to change the linked list so that we remove all duplicates from it.

Think about what to do for linear time and constant memory usage. I tried to put all the elements of a list in HashMap

, which gives us constant time, but using linear memory.

Is there another way?

+3


source to share


2 answers


You can use a method stream().distinct()

to do this for linear time:



List<String> result = list.stream()
        .distinct()
        .collect(Collectors.toList());
+1


source


Algorithmically this sounds impossible (or someone here will surprise me).

but you can create a simulated list without duplicates without creating an algorithm this way:



public class SimulatedNoDuplicatesList extends LinkedList {
    private List originalList;
    SimulatedNoDuplicatesList(List original) {
        originalList = original;
    }
// override all the methods that you want to use with the old list. for example
//   @Override
    public Object get(int i) {
        if (!super.contains(i) && originalList.contains(i)) {
            super.add(originalList.get(i));
        }
        return super.get(i);
    }
}
0


source






More articles:


All Articles