Are you wondering how to remove duplicates from a list? Be quick to take a look at our free sample in which this issue is explicated by an expert. After reading this sample, you will know how to deal with duplicates. On our blog, you can find many samples which can help you to solve diverse academic problems. All of them are completed by experts from AssignmentShark who possess deep knowledge in a variety of spheres.
Our service is oriented for students who need help with technical disciplines. If you can’t cope with a certain problem, you should apply to us and our experts will help you to cope with your tasks. Also, you have the ability to read many useful articles for free. One more thing you should know is that AssignmentShark never shares the personal or financial information of its clients. Even experts will not know your real name, and you won’t know their names. So, if our sample on how to remove duplicates from a list won’t be enough to help you with all of the issues you are interested in, feel free to make the order. Our online assignment help is available 24/7!
Remove Duplicates From an Unsorted List
We have an unsorted linked list with many random elements there. What we need to do is to find all the duplicates and remove them from the list.
Solution
There are a lot of different ways to find the duplicates in the list. We can create a lot of subarrays and put them there, or, for example, use one subarray with different keywords for each specimen of duplicates. But we will use a way that is a bit smarter. To do this, we will need a simple hash table. In the following solution, we pass through the list and add every element to the hash table. When the repeating unit is found, it is removed and the cycle continues. The whole problem can be solved in a single pass by using the linked list.
public static void removeDuplicates (Node nod) {
Hashtable hashes = new Hashtable();
node prev = null;
while (nod != null) {
if (hashes.containsKey(nod.data)) {
prev.next = nod.next;
} else {
hashes.put(nod.data, true);
prev = nod;
}
nod = nod.next;
}
}
The above solution will require O(N) time, where N is a number of elements in the linked list.
An additional constraint: the use of the buffer is forbidden. In this case, we can implement the cycle with the help of two pointers: current (running through a linked list) and moving (check any subsequent nodes for the presence of duplicates).
public static void removeDuplicates (Node head) {
if (head == null) return;
Node curr = head;
while (curr != null) {
Node mov = curr;
while (mov.next != null) {
if (mov.next.data == curr.data) {
mov.next = mov.next.next;
} else{
mov = mov.next;
}
}
curr = curr.next;
}
}
This code requires only O (1) space.
Thanks for your attention!