Remove duplicate nodes from linked list

In this post, we will discuss, how to remove duplicate nodes from linked list.We should consider two states of linked list while removing the duplicate nodes. Sorted linked list and unsorted linked list. In previous post, we saw the sorting logic of linked list. We will make use of sorting methods and then remove the duplicate nodes from linked list. We will discuss about two approaches to remove duplicate from linked list.

For Sorted Linked List : If linked list is sorted(Use sorting of linked list), traverse the linked list from root node to till end of the linked list.While traversing, compare each node with next consecutive node (because linked list is sorted). If current node and next node value is same then remove the next node and point the next pointer of current node to next pointer of deleted node.To explain this logic, check the below algorithm.[Try Yourself]

Algorithm: 

  1. If linked list is empty, no action needed
  2. If linked list has only one element, no action needed
  3. If linked list is not empty and has more than 1 elements, declare two pointers , currentNode and nextNode. Initialize currentNode = root and nextNode = root.nextNode
  4. Start a while loop with condition nextNode = ! null
  5. In while loop, check if current node data and next node data is equal, remove the next node. To remove the next node, set currentNode.next = nextNode.next
  6. Decrease the size of linked list by 1. Now currentNode will be same the nextNode = currentNode.next
  7. If current node data and next node data is not equal , update the pointers. currentNode = currentNode.next and nextNode = currentNode.next

Execution Process:

For Unsorted Linked List: If linked list is unsorted and no sorting method is available, we can use Hashing Technique to remove the duplicate nodes. Traverse the linked list from root node to end of the linked list and check if current node data is in HashSet. If yes, remove the current node. If no, add the current node data to HashSet and shift the pointer to next node.[Try Yourself]

Algorithm:

  1. If linked list is empty, no action needed
  2. If linked list has only one element, no action needed
  3. If linked list is not empty and has more than 1 elements, declare two pointers, currentNode and previous node.Initialize currentNode = root and previousNode = null.Create an object of HashSet.
  4. Start a while loop with condition currentNode = ! null
  5. If hashSet contains the data of currentNode then remove the current node.To remove the current node, set next node of previousNode as next node of currentNode.
  6. Decrease the size of linked list by 1 and update the reference of currentNode as nextNode
  7. If hashSet does not contain the data of currentNode, put the currentNode data to HashSet and update the reference of previousNode = currentNode and currentNode = currentNode.next

Execution Process:

Below is the JAVA implementation to remove duplicate from linked list. We have two methods, removeDuplicate() which will first sort the linked list and then remove the duplicate node and another method removeDuplicateUsingHashing() will remove the duplicate node for any sorted/unsorted linked list.

 

Below is the main class to test these two APIs.

 

Output:

*****************************************************************************************

Original List: []
After removing duplicate: []
After removing duplicate using Hashing: []

Original List: [19]
After removing duplicate: [19]
After removing duplicate using Hashing: [19]

Original List: [19,19,10,57,10,7,19,57]
After removing duplicate: [7,10,19,57]
After removing duplicate using Hashing: [7,10,19,57]

*****************************************************************************************

 

Extension to this implementation, try to create the linked list which will accept NULL data and then remove the duplicate nodes. Play around the nodes, It will be fun 🙂

Hope you like this post. Please leave yours comments/suggestions.

You may like –

Top