6
\$\begingroup\$

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;
   }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ It seems your method only remove the adjacent duplicate elements. is that the case? \$\endgroup\$ – zdd Oct 21 '12 at 1:43
  • \$\begingroup\$ no i don't intend for it to be that way. Every node is being compared to every NEXT LL node up to the end of the list. \$\endgroup\$ – Phoenix Oct 21 '12 at 2:42
  • \$\begingroup\$ Can you cite some examples of what you are saying \$\endgroup\$ – Phoenix Oct 21 '12 at 2:45
  • 1
    \$\begingroup\$ OK, take an unsorted list for example, 1->1->2->1->3->2->2->3, you code want to get a result of 1->2->3, right? \$\endgroup\$ – zdd Oct 21 '12 at 7:08
  • \$\begingroup\$ I think I understand your code now, you are right! but I have another version with a little difference, we can save a pointer, please see my answer. \$\endgroup\$ – zdd Oct 21 '12 at 10:03
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Frank thank you for the comments. I skipped writing the equals method but it is intended to compare node equality of data. You mention sorting linked lists. Will it be a merge sort for linked lists ? \$\endgroup\$ – Phoenix Oct 22 '12 at 13:23
  • \$\begingroup\$ Yes, you would probably use a merge sort, as it suits the linked list nicely. Ideally, you could simply use Collections.sort, but that makes a copy, which requires linear memory. \$\endgroup\$ – Frank Oct 22 '12 at 15:36
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.