Learn-dsa..in 30 days!



























CC-9 : Implement DoubleLinkedList.

Description:

Create and test a DoubleLinkedList implementation.

DoubleLinkedList

DoubleLinkedLists 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 DoubleLinkedList. 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 null indicating there are no other nodes in the DoubleLinkedList. The nextNode variable of the node will point to the next node if there is a next node or else it will point to null (similarly previousNode will point to previous node, if any). 

 null  <-   11   -> null

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

 null  <-  23 <- -> 47 <- ->11 -> null

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 DoubleLinkedList that contains a reference to the firstNode of the DoubleLinkedList and also contains all the code to add/delete/traverse/access nodes of the DoubleLinkedList. (partial code snapshot of the DoubleLinkedList is given below): 

public class DoubleLinkedList {
private DoubleLinkedListNode firstNode=null;
public DoubleLinkedListNode getFirstNode() {
	...
}
public void setFirstNode(DoubleLinkedListNode firstNode) {
	...
}
public DoubleLinkedListNode getLastNode() {
	...
}
public boolean addLast(int data){
	...
}

...
...
...
}

Addition of node to end of DoubleLinkedList

Pseudocode:

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

Code:

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;			
	}
}

Addition of node to start of SingleLinkedList.

Pseudocode:

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

Code:

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;			
	}
}

Addition of node to particular position in DoubleLinkedList.

Pseudocode:

To handle addition of a newNode to index pos of a DoubleLinkedList, we need to handle 3 cases:
If pos is 0 add newNode to start of DoubleLinkedList.
If pos is equal to number of nodes in the DoubleLinkedList, then add new node to end of the DoubleLinkedList.
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;
	}
	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 DoubleLinkedList.

Pseudocode:

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

Code:

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

Deletion of last node of DoubleLinkedList.

Pseudocode:

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

Code:

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;
}

Deletion of intermediate node of DoubleLinkedList.

Pseudocode:

To handle deletion of a node from index pos of a DoubleLinkedList, we need to handle 3 cases:
If pos is 0, remove the firstNode of DoubleLinkedList.
If pos is equal to number of nodes in the DoubleLinkedList, then remove the last node of the DoubleLinkedList.
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){	
	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;  	  	
 }

Accessing a node at a particular index in the DoubleLinkedList.

Pseudocode:

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

Code:

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;
}

Accessing/ printing the nodes of the DoubleLinkedList.

Pseudocode:

The nextNode link of each node can be used to traverse the nodes of the DoubleLinkedList.

Code:

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

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us