Java Data Structure Implementation : Doubly Link List

This program demonstrates the doubly link list implementation in Java. The Insert, Delete, Search Operation has been implemented.

Find the Java Code below :

import java.util.Scanner;

/*
* This class demonstrates Doubly Link List Implementation in java with Add/Delete/Search Operations.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 28th March, 2013
*/
public class DoublyLinkList {

public DoublyLinkList prev;
public int id;
public DoublyLinkList next;

public DoublyLinkList() {}

public DoublyLinkList(int id){
this.prev = null;
this.id = id;
this.next = null;
}

/**
* This method add a new node into the doubly link list at last.
* @param startNode The Starting node of link list.
* @param nodeToBeInserted The node which you want to insert
* @return void.
*/
public static void addNewNodeAtLast(DoublyLinkList startNode, DoublyLinkList nodeTobeInserted){
DoublyLinkList lastNodeOfList = getLastNode(startNode);
lastNodeOfList.next = nodeTobeInserted;
nodeTobeInserted.prev = lastNodeOfList;
}

/**
* This method add a new node into the doubly link list at start.
* @param startNode The Starting node of link list.
* @param nodeToBeInserted The node which you want to insert
* @return void.
*/
public static DoublyLinkList addNewNodeAtFirst(DoublyLinkList startNode, DoublyLinkList nodeTobeInserted){
nodeTobeInserted.prev = null;
nodeTobeInserted.next = startNode;
startNode.prev = nodeTobeInserted;
return nodeTobeInserted;
}

/**
* This method add a new node into the doubly link list at specific location.
* @param specificPositionedNode The Specific Node of which you want to insert.
* @param nodeToBeInserted The node which you want to insert
* @return void
*/
public static void addNewNodeAtSpecificPosition(DoublyLinkList specificNode, DoublyLinkList nodeTobeInserted){
if(specificNode.next == null){
addNewNodeAtLast(specificNode, nodeTobeInserted);
}else{
DoublyLinkList previousNode = specificNode.next.prev;
DoublyLinkList nextNode = specificNode.next;
nodeTobeInserted.prev = specificNode;
nodeTobeInserted.next = nextNode;
specificNode.next = nodeTobeInserted;
previousNode.prev = nodeTobeInserted;
}
}

/**
* This method search a specific node in the doubly link list.
* @param startNode start node of link list.
* @param searchNodeId search information of node which you want to search
* @return void.
*/
public static DoublyLinkList traverseLinkListSpecificNode(DoublyLinkList startNode, int searchNodeId){
DoublyLinkList specificLocationNode = null;
if(startNode.id == searchNodeId){
specificLocationNode = startNode;
}else{
while(startNode!=null){
if(startNode.id == searchNodeId){
specificLocationNode = startNode;
break;
}
startNode = startNode.next;
}
}
if(specificLocationNode!=null)
System.out.println("Specific Node Id is :"+specificLocationNode.id);
else
System.out.println("Not found");
return specificLocationNode;
}

/**
* This method removes the node from last of doubly link list.
* @param startNode Remove the last node of link list.
* @return void.
*/
public static void removeNodeFromLast(DoublyLinkList startNode){
DoublyLinkList lastNode = DoublyLinkList.getLastNode(startNode);
lastNode.prev.next = null;
}

/**
* This method removes a node from start of doubly link list.
* @param startNode Remove the start node of link list.
* @return LinkList.
*/
public static DoublyLinkList removeNodeFromFirst(DoublyLinkList startNode){
if(startNode.next==null){
startNode = null;
}else{
System.out.println("Just about to delete");
startNode = startNode.next;
startNode.prev = null;
}
return startNode;
}

/**
* This method removes a node from specific position of doubly link list.
* @param startNode start node of link list.
* @param nodeToBeRemovedId Node id of which you want to remove
* @return void.
*/
public static DoublyLinkList removeNodeFromSpecificPosition(DoublyLinkList startNode, int nodeTobeRemoved){
DoublyLinkList specificPositionedNode = DoublyLinkList.traverseLinkListSpecificNode(startNode, nodeTobeRemoved);
if(specificPositionedNode==null){
System.out.println("Node not found to delete");
return startNode;
}else{
if(specificPositionedNode.next==null){
DoublyLinkList.removeNodeFromLast(startNode);
return startNode;
}else{
if(specificPositionedNode.prev == null){
System.out.println("Removint First Node");
startNode = DoublyLinkList.removeNodeFromFirst(startNode);
return startNode;
}else{
DoublyLinkList nextNode = specificPositionedNode.next;
DoublyLinkList prevNode = specificPositionedNode.prev;
prevNode.next = nextNode;
nextNode.prev = prevNode;
return startNode;
}
}
}
}

/**
* This method traverse the whole doubly link list.
* @param startNode start node of link list.
* @return void.
*/
public static void traverseLinkList(DoublyLinkList startNode){
if(startNode == null){
System.out.println("No Element");
}else{
while(startNode!=null){
System.out.println("Node Id : "+ startNode.id);
startNode = startNode.next;
}
}

}

/**
* This method returns the last node of the doubly link list.
* @param startNode start node of link list.
* @return void.
*/
public static DoublyLinkList getLastNode(DoublyLinkList startNode){
DoublyLinkList lastNode=null;
if(startNode.next==null){
lastNode = startNode;
}else{
while(startNode.next!=null){
System.out.println("In while Loop");
lastNode = startNode.next;
startNode = startNode.next;
}
}
System.out.println("Last Node Id In Get Last Method is : "+lastNode.id);
return lastNode;
}

/**
* This method main method to perform the Doubly Link List Operations.
* @param args command line argument list
* @return void.
*/
public static void main(String[] args){
int userOperation = 0,nodeId=-1, nodePostion= -1;
DoublyLinkList startNode = null;
DoublyLinkList nodeToBeInserted = null;
Scanner sc = new Scanner(System.in);
do{
String menuString = "\tDoubly Link List \nWhat operation you want to perform?"+
"\n 1. Insert New Node at Last"+
"\n 2. Insert New Node at Start"+
"\n 3. Insert New Node at Specific Position"+
"\n 4. Remove Node from Last"+
"\n 5. Remove Node from Start"+
"\n 6. Remove Node from Specific Position"+
"\n 7. Traverse Whole List"+
"\n 8. Traverse Specific Node in List"+
"\n -1. Exit from Menu"+
"\n Please enter Operation Number : ";
System.out.println(menuString);
userOperation = sc.nextInt();

switch(userOperation){
case 1:
System.out.println("Plese enter node Id : ");
nodeId = sc.nextInt();
nodeToBeInserted = new DoublyLinkList(nodeId);
if(startNode == null){
System.out.println("start Node is Null");
startNode = nodeToBeInserted;
}else{
System.out.println("Adding New Node At Last");
DoublyLinkList.addNewNodeAtLast(startNode, nodeToBeInserted);
}
break;
case 2:
System.out.println("Plese enter node Id : ");
nodeId = sc.nextInt();
nodeToBeInserted = new DoublyLinkList(nodeId);
if(startNode == null){
System.out.println("start Node is Null");
startNode = nodeToBeInserted;
}else{
System.out.println("Adding New Node At First");
startNode = DoublyLinkList.addNewNodeAtFirst(startNode, nodeToBeInserted);
}
break;
case 3:
System.out.println("Node Id after which you want to insert new node. Enter Node Id?");
nodePostion = sc.nextInt();
DoublyLinkList specificPositionedNode = DoublyLinkList.traverseLinkListSpecificNode(startNode, nodePostion);
if(specificPositionedNode==null){
System.out.println("Entered Id not found in list");
}else{
System.out.println("Plese enter node Id : ");
nodeId = sc.nextInt();
nodeToBeInserted = new DoublyLinkList(nodeId);
DoublyLinkList.addNewNodeAtSpecificPosition(specificPositionedNode,nodeToBeInserted);
}
break;
case 4:
if(startNode.next == null){
startNode = null;
}else{
DoublyLinkList.removeNodeFromLast(startNode);
}
System.out.println("Last Node has been removed");
break;
case 5:
startNode = DoublyLinkList.removeNodeFromFirst(startNode);
System.out.println("Starting Node has been removed");
break;
case 6:
System.out.println("At which position you want to delete node. Enter Position?");
nodePostion = sc.nextInt();
startNode = DoublyLinkList.removeNodeFromSpecificPosition(startNode, nodePostion);
break;
case 7:
DoublyLinkList.traverseLinkList(startNode);
break;
case 8:
System.out.println("Please enter node Id to Search : ");
nodePostion = sc.nextInt();
DoublyLinkList.traverseLinkListSpecificNode(startNode,nodePostion);
break;
case -1:
System.out.println("Exit Application");
System.exit(0);
default : System.out.println("Exit from System");
}
}while(userOperation!=-1);
}
}

Any suggestion is invited if any.

Advertisements

2 thoughts on “Java Data Structure Implementation : Doubly Link List

  1. Pingback: Java Data Structure Implementation : Hashtable using Link List | Madan Gopal Singh Shekhawat

  2. Pingback: Java Data Structure Implementation : Undirected Simple Graph | Madan Gopal Singh Shekhawat

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s