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 the linked list is sorted(Use sorting of linked list), traverse the linked list from the root node to till the end of the linked list. While traversing, compare each node with the next consecutive node (because linked list is sorted). If the current node and next node value are the 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:
- If linked list is empty, no action needed
- If linked list has only one element, no action needed
- 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
- Start a while loop with condition nextNode = ! null
- 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
- Decrease the size of linked list by 1. Now currentNode will be same the nextNode = currentNode.next
- 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:
- If linked list is empty, no action needed
- If linked list has only one element, no action needed
- 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.
- Start a while loop with condition currentNode = ! null
- 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.
- Decrease the size of linked list by 1 and update the reference of currentNode as nextNode
- 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.
package com.study.singlyLinkedList;
public class Node<T> {
private T data ;
private Node<T> node;
public Node(T data) {
this.data = data;
}
public Node<T> getNode() {
return node;
}
public void setNode(Node<T> node) {
this.node = node;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
@Override
public String toString() {
return data+"" ;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
result = prime * result + ((node == null) ? 0 : node.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof Node))
return false;
Node other = (Node) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
return true;
}
}
package com.study.singlyLinkedList;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
public class SinglyLinkedList<T> {
private int size = 0;
private Node<T> node;
/**
* 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.
*
*/
public void removeDuplicate() {
//If root node is null
if(node ==null) {
return;
}
// size of linked list is 1
if(node.getNode()==null) {
return;
}
// sort the linked list
sort();
Node<T> currentNode=node;
Node<T> nextNode=node.getNode();
while(nextNode != null) {
if(currentNode.getData().equals(nextNode.getData())) {
currentNode.setNode(nextNode.getNode());
nextNode=currentNode.getNode();
size--;
}
else {
currentNode=currentNode.getNode();
nextNode=nextNode.getNode();
}
}
}
/**
* 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
*
*/
public void removeDuplicateUsingHashing() {
//If root node is null
if(node ==null) {
return;
}
// size of linked list is 1
if(node.getNode()==null) {
return;
}
Set<T> hash=new HashSet<>();
Node<T> currentNode=node;
Node<T> previousNode=null;
while(currentNode!=null) {
if(hash.contains(currentNode.getData())) {
Node<T> nextNode=currentNode.getNode();
if(previousNode!=null) {
previousNode.setNode(nextNode);
}
currentNode=nextNode;
size--;
}
else {
hash.add(currentNode.getData());
previousNode=currentNode;
currentNode=currentNode.getNode();
}
}
}
/**
* Sort Linked list using Merge sort algorithm
*
*/
public void sort() {
this.node=sort(this.node);
}
private Node<T> sort(Node<T> node) {
if(node ==null || node.getNode()==null) {
return node;
}
// Get the middle of the linked list
Node<T> middleNode=getMiddle(node);
Node<T> rightNode=middleNode.getNode();
// set the next of middle node to null
middleNode.setNode(null);
Node<T> leftNode=node;
// Apply mergeSort on left list
Node<T> sortedLeft = sort(leftNode);
// Apply mergeSort on right list
Node<T> sortedRight = sort(rightNode);
Node<T> sortedList =mergerSortedList(sortedLeft,sortedRight);
return sortedList;
}
/**
* Merge two nodes left node and right node in increasing order
* @param left
* @param right
* @return
*/
private Node<T> mergerSortedList(Node<T> left , Node<T> right){
Node<T> mergedList=null;
if(left== null ) {
return right;
}
if(right== null ) {
return left;
}
if (left.getData().hashCode() <= right.getData().hashCode()) {
mergedList = left;
mergedList.setNode(mergerSortedList(left.getNode(), right));
}
else {
mergedList = right;
mergedList.setNode(mergerSortedList(left, right.getNode()));
}
return mergedList;
}
/**
* Returns the data at middle of the linked list
* @return
*/
public T getMiddle() {
return getMiddle(this.node).getData();
}
/**
*
* @param node
* @return
*/
private Node<T> getMiddle(Node<T> node) {
if(node ==null || node.getNode()==null) {
return node;
}
Node<T> fastPointer=node.getNode();
Node<T> slowPointer=node;
// Move fast pointer by two and slow pointer by one
// Finally slow pointer will point to middle node when fast
// pointer will reach at end of the linked list
while (fastPointer !=null) {
fastPointer=fastPointer.getNode();
if(fastPointer!=null) {
slowPointer=slowPointer.getNode();
fastPointer=fastPointer.getNode();
}
}
return slowPointer;
}
/**
* Reverse the linked list by reversing the pointers in reverse direction
*/
public void reverse() {
Node<T> current=this.node;
Node<T> previous=null;
Node<T> next=null;
while(current !=null) {
next = current.getNode();
current.setNode(previous);
previous=current;
current=next;
}
this.node=previous;
}
/**
* Reverse the linked list using stack
*/
public void reverseUsingStack() {
// Push all node to Stack starting from root
Stack<Node<T>> stack=new Stack<Node<T>>();
Node<T> currentNode=this.node;
while(currentNode !=null) {
stack.push(currentNode);
currentNode=currentNode.getNode();
}
// clear the linked list.
this.node = null;
this.size = 0;
//Pop the data from Stack and add it to linked list
if(!stack.empty()) {
Node<T> rootNode=stack.pop();
Node<T> previousNode=rootNode;
currentNode=rootNode;
while(!stack.empty()) {
currentNode = stack.pop();
previousNode.setNode(currentNode);
previousNode=currentNode;
}
previousNode.setNode(null);
this.node=rootNode;
}
}
/**
* Add element at last.
*
* @param data
*/
public void add(T data) {
if (data == null) {
return;
}
if (node == null) {
node = new Node<T>(data);
} else {
Node<T> newNode = new Node<T>(data);
Node<T> lastNode = getLastNode(node);
lastNode.setNode(newNode);
}
size++;
}
/**
* Add element at first. set the newly created node as root node
*
* @param data
*/
public void addAtFirst(T data) {
if (data == null) {
return;
}
Node<T> newNode = new Node<T>(data);
if (this.node != null) {
newNode.setNode(this.node);
this.node = newNode;
} else {
this.node = newNode;
}
size++;
}
/**
* Add the element at specified index. Index start from 0 to n-1 where n=size of
* linked list. If index is negative value, nothing will be added to linked
* list.
*
* if index =0 , element will be added at head and element become the first
* node.
*
* @param data
* @param index
* - index at which element to be added.
*/
public void add(T data, int index) throws IndexOutOfBoundsException {
if (data == null) {
return;
}
// If index=0 , we should add the data at head
if (index == 0) {
addAtFirst(data);
return;
}
// If index= size, we should add the data at last
if (index == this.size) {
add(data);
} else if (index < this.size) {
Node<T> newNode = new Node<T>(data);
// get the node at (index) from linked list and mark as rightNode.
// get the node at (index-1) from linked list and mark as leftNode.
// set node of newly created node as right node.
// set node of left nose as newly created Node.
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index);
newNode.setNode(rightNode);
leftNode.setNode(newNode);
size++;
} else {
throw new IndexOutOfBoundsException("Index not available.");
}
}
public T get(int index) {
return getNode(index).getData();
}
/**
* Returns the index of data. Index starts from 0 to n. If data not found in
* list, return -1
*
* @param data
* @return
*/
public int indexof(T data) {
Node<T> pointerNode = this.node;
int index = 0;
while (pointerNode != null && pointerNode.getData() != null) {
if (pointerNode.getData().equals(data)) {
return index;
} else {
pointerNode = pointerNode.getNode();
index++;
}
}
return -1;
}
private Node<T> getNode(int index) {
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , return head
if (index == 0) {
return this.node;
}
// If index= size, return last node
if (index == this.size - 1) {
return getLastNode(this.node);
}
int pointer = 0;
Node<T> pointerNode = this.node;
while (pointer <= index) {
if (pointer == index) {
return pointerNode;
} else {
pointerNode = next(pointerNode);
pointer++;
}
}
return null;
}
private Node<T> getLastNode(Node<T> node) {
Node<T> lastNode = node;
if (lastNode.getNode() != null) {
return getLastNode(lastNode.getNode());
} else {
return lastNode;
}
}
private Node<T> next(Node<T> node) {
if (node.getNode() != null) {
return node.getNode();
} else {
return null;
}
}
public int size() {
return this.size;
}
/**
* Delete the first occurrence of element from linked list if exists and returns
* true. If data not available , it returns false;
*
* @param data
* @return
*/
public boolean delete(T data) {
if (this.node == null) {
return false;
}
Node<T> pointerNode = this.node;
// If input data is the head of linked list.
if (pointerNode.getData().equals(data)) {
this.node = next(pointerNode);
size--;
return true;
}
int indexofData = indexof(data);
if(indexofData >0 ) {
return deleteByIndex(indexofData);
}
else {
return false;
}
}
/**
* Delete the data by index.
*
* @param index
* @return
*/
public boolean deleteByIndex(int index) {
if (this.node == null) {
return false;
}
if (index < 0 || index > this.size - 1) {
throw new IndexOutOfBoundsException("Index not available.");
}
// If index=0 , put head node = Node at index 1.
if (index == 0) {
if(this.node.getNode()!=null) {
this.node = getNode(index + 1);
}else {
this.node=null;
}
size--;
return true;
}
// If index= size -1 means need to delete last node, get the 2nd last node and
// set next node as null.
if (index == this.size - 1) {
getNode(index - 1).setNode(null);
size--;
return true;
}
// if index is in between 0 and size of linked list , set Node of leftNode as
// rightNode
Node<T> leftNode = getNode(index - 1);
Node<T> rightNode = getNode(index + 1);
leftNode.setNode(rightNode);
size--;
return true;
}
/**
* Clear the linked list
*/
public void clear() {
this.node = null;
this.size = 0;
}
@Override
public String toString() {
String represent = "[";
Node<T> nextNode = this.node;
while (nextNode != null) {
represent = represent + nextNode.toString();
nextNode = next(nextNode);
if (nextNode != null) {
represent = represent + ",";
}
}
represent = represent + "]";
return represent;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((node == null) ? 0 : node.hashCode());
result = prime * result + size;
return result;
}
/**
* Two linked list is equal when their size is equals and both have similar node structure
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof SinglyLinkedList))
return false;
SinglyLinkedList other = (SinglyLinkedList) obj;
if (node == null) {
if (other.node != null)
return false;
} else if (!node.equals(other.node))
return false;
if (size != other.size)
return false;
return true;
}
}
Below is the main class to test these two APIs.
package com.study.singlyLinkedList;
public class TestSinglyLinkedList {
public static void main(String[] args) {
SinglyLinkedList<Integer> linkedList=new SinglyLinkedList<Integer>();
// linked list with 0 node
System.out.println("Original List: "+ linkedList);
linkedList.removeDuplicate();
System.out.println("After removing duplicate: " + linkedList);
linkedList.removeDuplicateUsingHashing();
System.out.println("After removing duplicate using Hashing: " + linkedList);
System.out.println(" ");
// Adding one node
linkedList.add(19);
System.out.println("Original List: "+ linkedList);
linkedList.removeDuplicate();
System.out.println("After removing duplicate: " + linkedList);
linkedList.removeDuplicateUsingHashing();
System.out.println("After removing duplicate using Hashing: " + linkedList);
System.out.println(" ");
// Adding more nodes
linkedList.add(19);
linkedList.add(10);
linkedList.add(57);
linkedList.add(10);
linkedList.add(7);
linkedList.add(19);
linkedList.add(57);
System.out.println("Original List: "+ linkedList);
linkedList.removeDuplicate();
System.out.println("After removing duplicate: " + linkedList);
linkedList.removeDuplicateUsingHashing();
System.out.println("After removing duplicate using Hashing: " + linkedList);
System.out.println(" ");
}
}
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 🙂
That’s all about How to Remove duplicate nodes from linked list in Java. Hope you like this post. Please leave yours comments/suggestions.
You may like –
- Singly Linked List Implementation using in java.
- Singly Linked List Implementation using generics in Java.
- Delete/Remove operations in Linked list.
- Reverse of Singly Linked List.
- Implementation of Index based Linked List.
- Merge sort for Linked List in Java
- Rotation of Linked List.
- Intersection of two linked lists.
- Iterator for singly linked list java.
