CC-11 : Remove duplicates DoubleLinkedList.

Description:

Given a DoubleLinkedList with integer data, remove nodes that have duplicate data.

Test cases and expected outputs:

Input Parameters	Expected outputs
63->97->96->32->53->97	63->96->32->53->97
88->77->77->66->33->55->77	88->66->33->55->77

Pseudocode:

Java.util.HashSet class can be used to check for duplicates. Create and instance of HashSet class called “uniqueValues” which accepts integer values.

Iterate the DoubleLinkedList from firstNode to end of the list. For each node, check if the data value already exists in the “uniqueValues” HashSet.

If the current node’s data value does not exist in the HashSet, add it to HashSet as a unique value.

Else, if the current node’s data value exists in the HashSet, we have found a duplicate, so currentNode can be removed from DoubleLinkedList.

Code:

public  void doubleLinkedListRemoveDuplicates(DoubleLinkedList doubleLinkedList) throws Exception{
	DoubleLinkedListNode currentNode=doubleLinkedList.getFirstNode();
	HashSet<Integer> uniqueDataValues=new HashSet<Integer>();
	do{
		if (uniqueDataValues.contains(currentNode.getNodeData())) {
			doubleLinkedList.remove(currentNode.getNodeData());
		}else {
			uniqueDataValues.add(currentNode.getNodeData());
		}
		currentNode=currentNode.getNextNode();					
	}while (currentNode!=null);
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

Note: For easier code execution and easier reference, the class below contains code for DoubleLInkedList and DoubleLinkedListNode as internal classes. Ideally both these classes should be separate public classes.

import java.util.HashSet;

public class DoubleLinkedListRemoveDuplicates {

public  void doubleLinkedListRemoveDuplicates(DoubleLinkedList doubleLinkedList) throws Exception{
	DoubleLinkedListNode currentNode=doubleLinkedList.getFirstNode();
	HashSet<Integer> uniqueDataValues=new HashSet<Integer>();
	do{
		if (uniqueDataValues.contains(currentNode.getNodeData())) {
			doubleLinkedList.remove(currentNode.getNodeData());
		}else {
			uniqueDataValues.add(currentNode.getNodeData());
		}
		currentNode=currentNode.getNextNode();					
	}while (currentNode!=null);
}
	

public static void main(String[] args) {

	try {
	DoubleLinkedListRemoveDuplicates doubleLinkedListRemoveDuplicates= new 	DoubleLinkedListRemoveDuplicates();
	DoubleLinkedList doubleLinkedList=doubleLinkedListRemoveDuplicates.new DoubleLinkedList();
	doubleLinkedList.addFirst(97);
	doubleLinkedList.addFirst(53);
	doubleLinkedList.addFirst(32);
	doubleLinkedList.addFirst(96);
	doubleLinkedList.addFirst(97);
	doubleLinkedList.addFirst(63);
	doubleLinkedList.printDoubleLinkListForwardDirection();
	System.out.print("REMOVING DUPLICATES");
	
	doubleLinkedListRemoveDuplicates.doubleLinkedListRemoveDuplicates(doubleLinkedList);
	doubleLinkedList.printDoubleLinkListForwardDirection();
	
	doubleLinkedList=doubleLinkedListRemoveDuplicates.new DoubleLinkedList();
	doubleLinkedList.addFirst(77);
	doubleLinkedList.addFirst(55);
	doubleLinkedList.addFirst(33);
	doubleLinkedList.addFirst(66);
	doubleLinkedList.addFirst(77);
	doubleLinkedList.addFirst(77);
	doubleLinkedList.addFirst(88);
	doubleLinkedList.printDoubleLinkListForwardDirection();
	System.out.print("REMOVING DUPLICATES");
	doubleLinkedListRemoveDuplicates=new DoubleLinkedListRemoveDuplicates();
	doubleLinkedListRemoveDuplicates.doubleLinkedListRemoveDuplicates(doubleLinkedList);
	doubleLinkedList.printDoubleLinkListForwardDirection();
	
	
	doubleLinkedList=doubleLinkedListRemoveDuplicates.new DoubleLinkedList();
	doubleLinkedList.addFirst(77);
	doubleLinkedList.addFirst(55);
	doubleLinkedList.addFirst(33);
	doubleLinkedList.addFirst(66);
	doubleLinkedList.addFirst(99);
	doubleLinkedList.addFirst(44);
	doubleLinkedList.addFirst(88);
	doubleLinkedList.printDoubleLinkListForwardDirection();
	System.out.print("REMOVING DUPLICATES");
	doubleLinkedListRemoveDuplicates=new DoubleLinkedListRemoveDuplicates();
	doubleLinkedListRemoveDuplicates.doubleLinkedListRemoveDuplicates(doubleLinkedList);
	doubleLinkedList.printDoubleLinkListForwardDirection();
    
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	}
	
}

class DoubleLinkedList {

private DoubleLinkedListNode firstNode=null;
	
public DoubleLinkedListNode getFirstNode() {
	return firstNode;
}

public void setFirstNode(DoubleLinkedListNode firstNode) {
	this.firstNode = firstNode;
}

public DoubleLinkedListNode getLastNode() {
	DoubleLinkedListNode currentNode=firstNode;
	DoubleLinkedListNode prevNode=null;
  	while (currentNode !=null) {
  		prevNode=currentNode;
  		currentNode=currentNode.getNextNode();
  	}
  	return prevNode;
}

public boolean addLast(int data){
	DoubleLinkedListNode node=new DoubleLinkedListNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(null);
		node.setPreviousNode(null);
		return true;
	}
	else {
		DoubleLinkedListNode currentNode=firstNode;
		while (currentNode.getNextNode()!=null) {currentNode=currentNode.getNextNode();}
		node.setPreviousNode(currentNode);			
		currentNode.setNextNode(node);
		node.setNextNode(null);
		return true;			
	}
}
		
public boolean addFirst(int data){
	DoubleLinkedListNode node=new DoubleLinkedListNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(null);
		node.setPreviousNode(null);
		return true;
	}else {
		node.setNextNode(firstNode);
		firstNode.setPreviousNode(node);
		firstNode=node; 
		node.setPreviousNode(null);
		return true;			
	}
}
	
public boolean add(int data, int pos){	
	int size=getSize();
	if ((pos<0) || (pos > size)) { return false;}
	if (pos==0) {
		addFirst(data);
		return true;
	}
	if (pos==size) {
		addLast(data);
		return true;
	}
	DoubleLinkedListNode node=new DoubleLinkedListNode();
	node.setNodeData(data);
	DoubleLinkedListNode currentNode=firstNode;
	DoubleLinkedListNode prevNode=null;
	int idx=0;
	while (currentNode !=null) {
	  	if ((idx==pos)){
	  		node.setNextNode(prevNode.getNextNode());
	  		prevNode.setNextNode(node);
	  	  	//setup previous node linkages
	  	  	node.getNextNode().setPreviousNode(node);
	  	  	node.setPreviousNode(prevNode);
	  	  	return true;
	  	  }
	  	prevNode=currentNode;
	  	currentNode=currentNode.getNextNode();
	  	idx++;
	  }  	
	  return false;  	
}	

public int getSize() {
	DoubleLinkedListNode currentNode=firstNode;
  	int idx=0;
  	while (currentNode !=null) {
  		currentNode=currentNode.getNextNode();
  		idx++;
  	}
  	return idx;
}	

public boolean removeFirst() {
	if (firstNode == null) { return false; }
	if (firstNode.getNextNode()==null) {
		firstNode=null; 
		return true;
	}
	firstNode=firstNode.getNextNode(); 
	firstNode.setPreviousNode(null);
	return true;
}

public boolean removeLast() {
	if (firstNode == null) { return false; }
	DoubleLinkedListNode currentNode=firstNode;
	DoubleLinkedListNode prevNode=null;
	while (currentNode !=null) {
		if (currentNode.getNextNode()==null) {
			if (prevNode==null) {
				firstNode=null;
				return true;
			}
  			prevNode.setNextNode(null);
  			currentNode.setPreviousNode(null);
  			return true;
		}
		prevNode=currentNode;
  		currentNode=currentNode.getNextNode();    		
  	}	
	return false;
}

public boolean remove(int data){	
	DoubleLinkedListNode currentNode=firstNode;
	DoubleLinkedListNode prevNode=null;
  	while (currentNode !=null) {
  		if (currentNode.getNodeData() == data) {
  			if (prevNode==null) {
  				removeFirst();
  				return true;
  			}
  			if (currentNode.getNextNode()==null) {
  				removeLast();
  				return true;
  			}
  			prevNode.setNextNode(currentNode.getNextNode());
  			prevNode.getNextNode().setPreviousNode(prevNode);
  			return true;
  		}
  		prevNode=currentNode;
  		currentNode=currentNode.getNextNode();  		
  	}  	
  	return false;  	
 }	

public boolean removeAtPos(int pos){	
	DoubleLinkedListNode currentNode=firstNode;
	DoubleLinkedListNode prevNode=null;
  	int idx=0;
  	while (currentNode !=null) {
  		if (idx==pos) {
  			if (prevNode==null) {
  				removeFirst();
  				return true;
  			}
  			if (currentNode.getNextNode()==null) {
  				removeLast();
  				return true;
  			}
  			prevNode.setNextNode(currentNode.getNextNode());
  			return true;
  		}
  		prevNode=currentNode;
  		currentNode=currentNode.getNextNode();  
  		idx++;
  	}  	
  	return false;  	  	
 }		

public int get(int idx) {
	DoubleLinkedListNode currentNode=firstNode;
  	int currIdx=0;
  	while (currentNode !=null) {
  		if (currIdx==idx) {return currentNode.getNodeData();}
  		currentNode=currentNode.getNextNode();
  		currIdx++;
  	}
  	return Integer.MIN_VALUE;
}

public void traverseForward() {
	DoubleLinkedListNode currentNode=firstNode;
	while (currentNode !=null) {
  		System.out.println(currentNode.getNodeData());
  		currentNode=currentNode.getNextNode();
  	}
}
			
	// print DoubleLinkList forward direction
 public void printDoubleLinkListForwardDirection() throws Exception    {
	// Case 1: The Linked list is empty !!
	if (firstNode == null) { System.out.println("Double Linked list empty"); return; }
	// Case 2: Print Double LinkedList node by node (first to last)
	DoubleLinkedListNode currentNode=firstNode;
	System.out.println();
	System.out.println("****************************************************************************");
	System.out.print("DoubleLinkedList nodes (first node to last node): ");
	do  {
		    System.out.print(currentNode.getNodeData());
		    if (currentNode.getNextNode()!=null)  System.out.print(" -> ");
			currentNode=currentNode.getNextNode();
			
		} while( currentNode != null);
	
		System.out.println();
		System.out.println("****************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		;
		return;
	}
    
 // print DoubleLinkList backward direction
    public void printDoubleLinkListBackwardDirection() throws Exception    {
    	// Case 1: The Linked list is empty !!
    	if (firstNode == null) { System.out.println("Double Linked list empty"); return; }
    	// Case 2: Print Double LinkedList node by node (last to first)
    	// This while loop executes till we reach last node in the LinkedList
    	DoubleLinkedListNode currentNode=firstNode;
		while (currentNode.getNextNode()!=null) {currentNode=currentNode.getNextNode();}
		//currentNode is at end of LinkedList	
		System.out.println();
		System.out.println("****************************************************************************");
		System.out.print("DoubleLinkedList nodes (last node to first node): ");
		do  {
			    System.out.print(currentNode.getNodeData());
			    if (currentNode != firstNode)  System.out.print(" -> ");
				currentNode=currentNode.getPreviousNode();
				
			} while( currentNode != null);
		
			System.out.println();
			System.out.println("****************************************************************************");
			System.out.println();
			Thread.sleep(2000);
			;
			return;
	}

}


class DoubleLinkedListNode  {
	private DoubleLinkedListNode nextNode=null;
	private DoubleLinkedListNode previousNode=null;
	
	private int nodeData=0;

	public DoubleLinkedListNode getNextNode() {
		return nextNode;
	}
	public void setNextNode(DoubleLinkedListNode nextNode) {
		this.nextNode = nextNode;
	}
	public DoubleLinkedListNode getPreviousNode() {
		return previousNode;
	}
	public void setPreviousNode(DoubleLinkedListNode previousNode) {
		this.previousNode = previousNode;
	}
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}
}

	
	
}