# Removing duplicates from unsorted LinkedList

## Removing Duplicates:

/**
* Remove duplicates without using a buffer.
*
*/

//if the linked list is empty
throw new RuntimeException("linked list is empty");
//return;
}
boolean flag = false ;

while(current != null) {
while(runner != current) {
if(current.getData() != runner.getData()) {
runner = runner.getNext();
flag = false;
} else {
previous.setNext(current.getNext());
current = previous.getNext();
flag = true;
break;
}
}
if(!flag) {
previous = current;
current = current.getNext();
}
}
}


class LinkedListNode {
private int data;

this.data = data;
this.next = null;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

return next;
}
this.next = next;
}

public void appendAtTail(final int data) {
while(current.next != null) {
current = current.next;
}
current.next = newNode;
}
}


## Test Case:

@Test
public void testRemoveDuplicatesFromUnsortedSortedLL() {
}


I wrote this code recently to remove duplicates from linked list without using buffer and was trying to analyze its complexity : Time taken for traversing is O(n) For each operation we need to move runner node n times to remove duplicates Total Complexity : O(n2). Is this correct ?? I guess not because this is no better than using two for loops and comparing each element with the rest of the elements in the LinkedList . What am I doing wrong here?

• What makes you think that you does something wrong? Doesn't your code give you the results that you expect? Nov 22, 2014 at 22:46
• @SimonAndréForsberg No my code works . I meant the code that I wrote still gives O(n^2) complexity which is not efficient . Nov 22, 2014 at 23:10

Yes, this looks $O(n^2)$: when all elements are unique, the program will compare all elements with all other elements.

A better solution will be to use a Set to keep track of the already seen items. You will still have to iterate over all items, but you won't have to compare to all other elements, but simply do a lookup in the Set, which in case of a HashSet will be $O(1)$ complexity. Of course, when all elements are unique, then this method will use twice as much memory as your original. That's a trade-off you'll have to consider.

Unfortunately you didn't provide the implementation of LinkedListNode so it's not easy to play with this code. But looking at it I'm wondering if it correctly removes all duplicates, for example will it turn 1->2->2->2->2->3 into 1->2->3. (Maybe it does, a bit hard to decipher, but I suggest to do a quick test. And maybe next time include enough code so that reviewers can test run easily.)

UPDATE

As you remarked in your last comment, another way, without using a buffer / Set is to sort the list first, and remove the duplicates after. That would have $O(n\log n)$ complexity. However, keep in mind that the elements will be reordered with that approach (if they were not ordered to begin with). Depending on your use case, that may be perfectly acceptable, of course.

• I know how to solve this in O(n) using external buffer but my question was how to make the solution efficient without using buffer . even though in the above code we dont compare each element with the rest of the elements but the complexity is still O(n2) Nov 22, 2014 at 23:20
• Ah ok that's what you meant by buffer... Without a map/set, there's no way around $O(n^2)$: you have to compare all elements against all other, unless there are other conditions you can benefit from, for example the list items being sorted. Nov 22, 2014 at 23:24
• Well another way is to sort the linkedList = O(nlogn) and then remove duplicates from sortedLinkedList = O(n) which is total O(nlogn) operation but this is not inplace algorithm . I guess you are right that without using external storage the complexity will be O(n2) Nov 22, 2014 at 23:40
• Good point! I updated my post to mention that. Nov 23, 2014 at 22:35
• If you control the linked list class you could let each node have two additional pointers (sorted next and previous) you could then implement say quick sort on these pointers and use those to remove duplicates. Without affecting the original ordering :) you will use additional memory per node but it will probably be small in comparison to the size of T. Apr 24, 2017 at 10:07