Reputation: 425
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?
Upvotes: 1
Views: 2232
Reputation: 375
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);
}
Upvotes: 0
Reputation: 5488
Your Binary Search tree (BST) alternative would be faster. Lets do some analysis:
O(1)
N * O(log(N))
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.
Upvotes: 1
Reputation: 18368
You can do it in O(n)
time with O(n)
additional memory. This is better than BST approach:
Upvotes: 2
Reputation: 46
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
Upvotes: 0