Learn-dsa..in 30 days!



























Implement CircularDoubleLinkedList.

Description:

Create and test a CircularDoubleLinkedList implementation.

CircularDoubleLinkedList.

CircularDoubleLinkedLists consist of list of nodes, where each node has a 2 links. The first link points to the previous node and the second link points to the next node in the CircularDoubleLinkedList. Additionally, the last node points forward to the firstNode, and firstNode points backwards to last node, creating a CircularDoubleLinked structure. The structure of a DoubleLinkedListNode is shown below. In the image as the first node is the only node in the list, the nextNode and previousNode links will point to firstNode indicating there are no other nodes in the CircularDoubleLinkedList. 

Points to firstNode  <-   11  ->Points to firstNode

In the below image, node with data 23 is the first node the CircularDoubleLinkedList so its previousNode link points to the last node of CircularDoubleLinkedList. Similarly, node with data 11 is the last node the CircularDoubleLinkedList so its nextNode link points to firstnode of CircularDoubleLinkedList. 

 Points to last node  <-  23 <-->47 <- ->11->Points to firstNode

Below is the code for the DoubleLinkedListNode java class: 

public class DoubleLinkedListNode implements Node {
	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;
	}
}

Besides DoubleLinkListNode class shown above we also need a class named CircularDoubleLinkedListclass that contains a reference to the firstNode of the CircularDoubleLinkedList and also contains all the code to add/delete/traverse/access nodes of the CircularDoubleLinkedList. (partial code snapshot of the DoubleLinkedList is given below): 

public class CircularDoubleLinkedList {
private SingleLinkedListNode firstNode=null;

public SingleLinkedListNode getFirstNode() {
	return firstNode;
}

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

public boolean addLast(int data){
	...
}
	

public boolean addFirst(int data){
	...
}
	
...
...
...
}

Addition of node to end of CircularSingleLinkedList.

Pseudocode:

To handle addition of a newNode to end of a CircularDoubleLinkedList, we need to handle 2 cases:
If the CircularDoubleLinkedList is empty, add the newNode as the firstNode of the CircularDoubleLinkedList.
If the CircularDoubleLinkedList already has nodes:
Find the current last node of the CircularDoubleLinkedList and add the newNode as the nextNode of this last node.
Set prevNode of newNode to current last node.
Set nextNode of newNode to current firstNode.

Code:

public boolean addLast(int data){
	DoubleLinkedListNode node=new DoubleLinkedListNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(node);
		node.setPreviousNode(node);
		return true;
	}
	else {
		DoubleLinkedListNode currentNode=firstNode;
		while (currentNode.getNextNode()!=firstNode) {currentNode=currentNode.getNextNode();}
		node.setPreviousNode(currentNode);	
		node.setNextNode(firstNode);
		currentNode.setNextNode(node);
		firstNode.setPreviousNode(node);
		return true;		
	}
}

Addition of node to start of CircularDoubleLinkedList.

Pseudocode:

To handle addition of newNode to start of a CircularDoubleLinkedList, we need to handle 2 cases:
If the CircularDoubleLinkedList is empty, add newNode as the firstNode of the CircularDoubleLinkedList.
If the CircularDoubleLinkedList already has nodes:
Set nextNode variable of the newNode to current firstNode of the CircularDoubleLinkedList.
Set prevNode variable of the current firstNode to newNode.
Set nextNode variable of last node of CircularDoubleLinkedList to newNode.
Set prevNode of newNode to last node of CircularDoubleLinkedList.
Set newNode as the firstNode of the CircularDoubleLinkedList.

Code:

public boolean addFirst(int data){
	DoubleLinkedListNode node=new DoubleLinkedListNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(node);
		node.setPreviousNode(node);
		return true;
	}else {
	DoubleLinkedListNode currentNode=firstNode;
	while (currentNode.getNextNode()!=firstNode) {currentNode=currentNode.getNextNode();}
		node.setNextNode(firstNode);
		node.setPreviousNode(currentNode);
		firstNode.setPreviousNode(node);
		firstNode=node; 
		currentNode.setNextNode(node);
		return true;			
	}
}

Addition of node to particular position in CircularDoubleLinkedList.

Pseudocode:

To handle addition of a newNode to index pos of a CircularDoubleLinkedList, we need to handle 3 cases:
If pos is 0 add newNode to start of CircularDoubleLinkedList.
If pos is equal to number of nodes in the CircularDoubleLinkedList, then add new node to end of the CircularDoubleLinkedList.
If pos is an intermediate index:
Identify the node oldPrevNode at position pos-1,and identify oldNextNode at position pos.
Set nextNode of newNode to oldNextNode.
Set nextNode of oldPrevNode to newNode.
Set prevNode of newNode to oldPrevNode.
Set prevNode of oldNextNode to newNode.

Code:

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;
	}
	if (firstNode==null) { return false;}
	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;  	
}

Deletion of first node of CircularDoubleLinkedList.

Pseudocode:

To handle deletion of firstNode of CircularDoubleLinkedList, we need to handle 2 cases:
If the CircularDoubleLinkedList has only one node, the set firstNode variable of CircularDoubleLinkedList null.
If the CircularDoubleLinkedList already has more than 1 nodes:
Set firstNode of CircularDoubleLinkedList to firstNode.nextNode.
Set prevNode of new firstNode to last node of the CircularDoubleLinkedList.
Set nextNode of last node of CircularDoubleLinkedList to new firstNode.

Code:

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

Deletion of last node of CircularDoubleLinkedList.

Pseudocode:

To handle deletion of last node of CircularDoubleLinkedList, we need to handle 2 cases:
If the CircularDoubleLinkedList has only one node, the set firstNode variable of CircularDoubleLinkedList to null.
If the CircularDoubleLinkedList already has more than 1 nodes:
Find the second last node of the CircularDoubleLinkedList and store its reference in prevNode.
Set prevNode.nextNode to firstNode.
Set firstNode.prevNode to prevNode.

Code:

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

Deletion of intermediate node of CircularDoubleLinkedList.

Pseudocode:

To handle deletion of a node from index pos of a CircularDoubleLinkedList, we need to handle 3 cases:
If pos is 0, remove the firstNode of CircularDoubleLinkedList.
If pos is equal to number of nodes in the CircularDoubleLinkedList, then remove the last node of the CircularDoubleLinkedList.
If pos is an intermediate index:
Identify the node prevNode at position pos-1.
Identify the node currentNode at position pos.
Set prevNode.nextNode to currentNode.nextNode.
Set currentNode.prevNode to prevNode.

Code:

public boolean removeAtPos(int pos){	
	if (firstNode == null) { return false; }
	DoubleLinkedListNode currentNode=firstNode;
	DoubleLinkedListNode prevNode=null;
  	int idx=0;
  	do {
  		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++;
  	} while (currentNode !=firstNode); 	
  	return false;  	  	
}

Accessing a node at a particular index in the CircularDoubleLinkedList.

Pseudocode:

To access a node at particular index, use the nextNode link to traverse through the CircularDoubleLinkedList till the required node is reached.

Code:

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

Getting the size of the CircularDoubleLinkedList.

Pseudocode:

To get the size of the CircularDoubleLinkedList traverse the CircularDoubleLinkedList from firstNode to last node and increment a variable idx for each node traversed.

Code:

public void traverseForward() {
	DoubleLinkedListNode currentNode=firstNode;
	do {
  		System.out.println(currentNode.getNodeData());
  		currentNode=currentNode.getNextNode();
  	}while (currentNode !=firstNode);
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us