Remove duplicates in a linked list

Question

I have seen , written and tested a few logics to remove duplicates in linked list. e.g. Using two loops (O(n2)) , or sorting and removing duplicates though it doesn't preserve order.
I am just wondering is it valid or legible if we pull out the elements of a linked list and start creating a binary search tree of them which detects duplicates using the standard duplicate detection in a binary tree algorithm.
Is that going to be any more efficient than existing logics, or worse?

Answer 1

Thiss solution solve the problem where no extra memory is allowed and changes the linked list in place. The solution is in C#

public static void removeDuplicates(Node root) { 
        Node reset = root;
        Node current = null;
        Node previous = null;
        Hashtable h = new Hashtable();
        //initialize hash table to all 0 values
        while (root != null)
        {
            if(!h.ContainsKey(root.value))
                h.Add(root.value, 0);
            root = root.next;
        }

        root = reset;
        ///count the number of times an element appears
        while (root != null)
        {
            h[root.value] = int.Parse(h[root.value].ToString()) + 1;
            root = root.next;
        }

        root = reset;
        previous = root;
        current = previous.next;            
        while (current != null) {
            if (int.Parse(h[current.value].ToString())>1)
            {
                h[current.value] = int.Parse(h[current.value].ToString())-1;
                previous.next = current.next;
                current = current.next;
            }
            else {
                previous = previous.next;
                current = current.next;
            }
        }

      // print them for visibility purposes
        while (reset != null) {
            Console.Write(reset.value + "->");
            reset = reset.next;
        }

    }

 static void Main(string[] args)
    {
        Node one = new Node(1);
        Node two = new Node(1);
        Node three = new Node(1);
        Node four = new Node(2);
        Node five = new Node(2);

   RemoveDuplicates(one);
   }

Answer 2

Your Binary Search tree (BST) alternative would be faster. Lets do some analysis:

1. Instantiate a BST object O(1)
2. Populate the BST with each node from the linked list N * O(log(N))
   Note that duplicates would not be added to the tree, as part of the insert operation.
3. Rebuild the linked list from the BST O(N)

The BST approach to removing duplicates runs in O(1)+O(N)+O(N*log(N)) =O(N*log(N))

It requires more code and more memory to run, but will remove duplicates in quasi-linear time.

Answer 3

You can do it in O(n) time with O(n) additional memory. This is better than BST approach:

1. Allocate an array of booleans, sized n, initialize all cells to false.
2. Traverse the linked list:
   • For each node hash/map the value into a unique index in the array.
   • Set the cell value to true.
3. Create a pointer to a new list.
4. Traverse the original list:
   • For each node hash/map the value into a unique index in the array.
   • If the cell value is true, add the node to a new list.
   • Set the cell value to false.
5. Set the old list head to a new list head and delete the old one.

Answer 4

The best options (fastern) is to create the binary tree to find the duplicate, but you will need more memory and code for it.

In c# you have the Dictionary, in c++ I think that there is any template of library that you can use