Tag Archives: Link List

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

Java Data Structure Implementation : Link List

This program demonstrates the 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 Link List Implementation in java with Add/Delete/Search Operations.
* @author : Madan Gopal Singh
* @version : 1.0
* @date : 13th March, 2013
*/
public class LinkList {

public int id;
public String info;
public LinkList next;

public LinkList(){
}

public LinkList(LinkList l ){
this.next=l;
}

public LinkList(int id,String info) {
this.id=id;
this.info=info;
this.next=null;
}

/**
* This method add a new node into the 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(LinkList startNode,LinkList nodeToBeInserted){
LinkList lastNode = LinkList.getLastNode(startNode);
LinkList.addNewNodeAtSpecificPosition(lastNode, nodeToBeInserted);
}

/**
* This method add a new node into the 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 LinkList addNewNodeAtFirst(LinkList startNode,LinkList nodeToBeInserted){
nodeToBeInserted.next = startNode;
return nodeToBeInserted;
}

/**
* This method add a new node into the link list at start.
* @param specificPositionedNode The Specific Node of which you want to insert.
* @param nodeToBeInserted The node which you want to insert
* @return LinkList Link list with New Starting Node.
*/
public static void addNewNodeAtSpecificPosition(LinkList specificPositionedNode,LinkList nodeToBeInserted){
LinkList tempNode = null;
tempNode = specificPositionedNode.next;
specificPositionedNode.next=nodeToBeInserted;
nodeToBeInserted.next = tempNode;
}

/**
* This method removes the node from last.
* @param startNode Remove the last node of link list.
* @return void.
*/
public static void removeNodeFromLast(LinkList startNode){
LinkList secondLastNode = null;
if(startNode!=null){
while(startNode.next!=null){
System.out.println("Node Id : "+startNode.id+", Node Info : "+startNode.info);
secondLastNode = startNode;
startNode=startNode.next;
}
secondLastNode.next=null;
}else{
System.out.println("No Node in List Please add first");
}
}

/**
* This method removes a node from start of list.
* @param startNode Remove the start node of link list.
* @return LinkList.
*/
public static LinkList removeNodeFromFirst(LinkList startNode){
LinkList tempNode = startNode.next;
return tempNode;
}

/**
* This method removes a node from specific position of list.
* @param startNode start node of link list.
* @param nodeToBeRemovedId Node id of which you want to remove
* @return void.
*/
public static void removeNodeFromSpecificPosition(LinkList startNode,int nodeToBeRemovedId){
LinkList tempNode = null;
LinkList previousNode = null;
if(startNode!=null){
previousNode=startNode;
while(startNode.next!=null){
if(startNode.id==nodeToBeRemovedId){
tempNode = startNode.next;
previousNode.next = tempNode;
}
previousNode = startNode;
startNode=startNode.next;
}
}else{
System.out.println("No Node in List Please add first");
}
}

/**
* This method traverse the whole list.
* @param startNode start node of link list.
* @return void.
*/
public static void traverseLinkList(LinkList startNode){
if(startNode!=null){
while(startNode.next!=null){
System.out.println("Node Id : "+startNode.id+", Node Info : "+startNode.info);
startNode=startNode.next;
}
}else{
System.out.println("No Node in List Please add first");
}
}

/**
* This method search a specific node in the list.
* @param startNode start node of link list.
* @param searchNodeId search information of node which you want to search
* @return void.
*/
public static LinkList traverseLinkListSpecificNode(LinkList startNode,int searchNodeId){
LinkList positionedNode = null;
if(startNode!=null){
while(startNode.next!=null){
if(startNode.id==searchNodeId){
System.out.println("Node found at position "+startNode.id);
positionedNode = startNode;
break;
}
startNode=startNode.next;
}
}else{
System.out.println("No Node in List Please add first");
}
return positionedNode;
}

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

/**
* This method returns the last node of the list.
* @param args command line argument list
* @return void.
*/
public static void main(String[] args){
int userOperation = 0,nodeId=-1, nodePostion= -1;
String nodeInfo = "";
LinkList startNode = new LinkList(nodeId,nodeInfo);
LinkList nodeToBeInserted;
Scanner sc = new Scanner(System.in);
do{
String menuString = "What 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();
System.out.println("Please enter node Info : ");
nodeInfo = sc.next();
nodeToBeInserted = new LinkList(nodeId, nodeInfo);
LinkList.addNewNodeAtLast(startNode, nodeToBeInserted);
break;
case 2:
System.out.println("Plese enter node Id : ");
nodeId = sc.nextInt();
System.out.println("Please enter node Info : ");
nodeInfo = sc.next();
nodeToBeInserted = new LinkList(nodeId, nodeInfo);
startNode = LinkList.addNewNodeAtFirst(startNode, nodeToBeInserted);
break;
case 3:
System.out.println("At which position you want to insert new node. Enter Position?");
nodePostion = sc.nextInt();
LinkList specificPositionedNode = LinkList.traverseLinkListSpecificNode(startNode, nodePostion);
System.out.println("Plese enter node Id : ");
nodeId = sc.nextInt();
System.out.println("Please enter node Info : ");
nodeInfo = sc.next();
nodeToBeInserted = new LinkList(nodeId, nodeInfo);
LinkList.addNewNodeAtSpecificPosition(specificPositionedNode,nodeToBeInserted);
break;
case 4:
LinkList.removeNodeFromLast(startNode);
System.out.println("Last Node has been removed");
break;
case 5:
startNode = LinkList.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();
LinkList.removeNodeFromSpecificPosition(startNode, nodePostion);
break;
case 7:
LinkList.traverseLinkList(startNode);
break;
case 8:
System.out.println("Please enter node Id to Search : ");
nodePostion = sc.nextInt();
LinkList specificNode = LinkList.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.