Removing duplicates from an unsorted linked list

Question

Does the code below look correct and efficient for removing duplicates from an unsorted linked list without using extra memory?

An object of type Node denotes a LL node.

void removeDuplicates()
{
  Node current = head; 
  while(current!=null)
  {
    Node prev = current;
    Node next = current.next;
    while(next!=null)
    {
      if(current.equals(next))
      {
         prev.next = next.next;
      }
      else
      {
         prev = next;
      }
      next = next.next;
    }
      current = current.next;
   }
}

Answer 1

This review is two-fold: once, in case you have to uphold your restriction and then what changes if you allow extra space.

Review

• Comments: they are simply missing. You need at least some javadoc, and for non-trivial methods like this some more never hurts. Oh, and skip the usual excuses about how this code is somehow special and doesn't need comments.

• Clarity and Intent: if (current.equals(head)) reads like you are comparing the actual nodes, while duplicity is a matter of equal node values. You may have overwritten the equals method accordingly (I assume so for the sake of correctness), but I would prefer to clearly portray your original intent here by comparing the actual values.

• Efficiency and readability: As the answer by zdd points out you could save one pointer, but that's kind of pointless. I prefer your version as its much clearer to a reader what current, prev and next are. However,efficiency is not going to get below O(n^2) with this approach.

Efficiency Improvement

You said that you need a solution "without using extra memory". What you really meant of course is a solution "with only a constant amount of additional memory" (your pointers require memory as well after all). What you did not require, however, is that this operation has to leave the list elements' ordering intact. Therefore, a faster approach in O(n log(n)) would be to first sort the list (in-place to satisfy the memory requirement), then simply walk through the list comparing only neighbors (another O(n)). While this does not make much difference of course for smaller lists, the memory requirement indicates much larger lists, and then the difference between O(n^2) and O(n log(n)) may well be the difference between another problem and a solution.

Answer 2

If you use Java, you can use contains method.

Then, if you replace ArrayList by LinkedList in the code here, and forget decoration, you can remove duplicate.

Using a temporary additinional List simplify the complexity.

Answer 3

I am not familiar with java, just write a C version, we can save a pointer, use only two, one pointer p for the header of current loop, another pointer q for the iterator of current loop.

// remove the duplicate elements in an unsorted link list
void remove_duplicate(Node* head)
{
    Node* p = head;
    while(p)
    {
        Node* q = p;
        while(q->next)
        {
            if(p->data == q->next->data)
            {
                Node* t = q->next;
                q->next = q->next->next;
                delete t;
                t = NULL;
            }
            else
                q = q->next;
        }
        p = p->next;
    }
}

Time complexity

for each node in the list, we need to loop all the nodes after it to determine whether there is a duplicate one, suppose you have N nodes in the link list, then, for the first element(head), we need to loop (N - 1) times, and for the second element, we need to loop (N - 2) times, so the sum of all loops is (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2 = O(N^2)