Double Linked List Implementation

Program


package com.wordpress.sreeharshasite;
public class DLLNode

{

int data;

DLLNode prevNode;

DLLNode nextNode;

public DLLNode(int data)

{

this.data=data;

this.prevNode=null;

this.nextNode=null; }
}

<hr />

package com.wordpress.sreeharshasite;
public class DoubleLinkedList

{

int size=0;

DLLNode headNode=null;
public void addAtStart(int data)

{

DLLNode newNode=new DLLNode(data);

DLLNode currNode=headNode;

if(currNode==null)

{

headNode=newNode;

size++;

}

else

{

newNode.nextNode=headNode;

headNode.prevNode=newNode;

headNode=newNode;

size++;

}

}

public void addAtEnd(int data)

{

DLLNode newNode=new DLLNode(data);

DLLNode currNode=headNode;

/* scenario if no nodes in the list */ i

f(currNode==null)

{

addAtStart(data);

}

else

{

while(currNode.nextNode!=null)

{

currNode=currNode.nextNode;

}

currNode.nextNode=newNode;

newNode.prevNode=currNode;

size++;

}

}

public int deleteAtStart()

{

DLLNode currNode=headNode; DLLNode nextNode;

/* scenario 1:no nodes in the list */

if(currNode==null)

{

System.out.println("No elements in the list to delete");

return -1;

}

/* scenario 2:only one node in the list */

else if(currNode.nextNode==null)

{

int data=currNode.data;

headNode=null;

size--;

return data;

}

/*scenario 3:  More than one node in the list */

else

{

int data=currNode.data;

nextNode=currNode.nextNode;

nextNode.prevNode=null;

headNode=nextNode;

size--;

return data;

}

}

public int deleteAtEnd()

{

DLLNode currNode=headNode;

DLLNode prevNode=null;;

/* scenario 1:no nodes in the list */

if(currNode==null)

{

System.out.println("No elements in the list to delete");

return -1;

}

/* scenario 2:only one node in the list */

else if(currNode.nextNode==null)

{

deleteAtStart();

}

/* scenario 3: More than one node in the list */

else

{

while(currNode.nextNode.nextNode!=null)

{

currNode=currNode.nextNode;

}

prevNode=currNode;

int data=currNode.nextNode.data;

prevNode.nextNode=null;

size--;

return data;

}

return -1;

}

public void addAtPosition(int data,int position)

{

/* scenario 1: position is beyond the node size */

if((getSize()+2)<position)

{

System.out.println("Postion entered is invalid");

}

/* scenario 1: position is less than zero*/

else if(position<1)

{

System.out.println("Postion entered is invalid");

}

else

{

DLLNode currNode=headNode;

DLLNode newNode=new DLLNode(data);

DLLNode beforeNode=null;

/* scenario 3:if the node to be added is in the first position */

if(position==1)

{

addAtStart(data);

}

/* scenario 4:if the node to be added at the end */

else if(position==getSize()+1)

{

addAtEnd(data);

}

else {

/* scenario 5: if the node to be added in between the linked list */

int index=1;

while(currNode!=null)

{

currNode=currNode.nextNode;

index++;

if(position==index)

{

beforeNode=currNode.prevNode;

newNode.prevNode=currNode.prevNode;

newNode.nextNode=currNode;

currNode.prevNode=newNode;

beforeNode.nextNode=newNode;

size++;

}

}

}

}

}

public int getSize()

{

return size;

}
public void deleteAtPosition(int position)

{

/* scenario 1: position is beyond the node size */

if((getSize()+1)<=position)

{

System.out.println("Postion entered is invalid");

}

/* scenario 1: position is less than zero*/

else if(position<1)

{

System.out.println("Postion entered is invalid");

}

else

{

DLLNode currNode=headNode;

DLLNode beforeNode=null;

DLLNode afterNode=null;

/* scenario 3:if the node to be deleted is in the first position */

if(position==1)

{ deleteAtStart();

}

/* scenario 4:if the node to be deleted at the end */

else if(position==getSize())

{

deleteAtEnd();

}

else

{

/* scenario 5: if the node to be added in between the linked list */

int index=1;

while(currNode!=null)

{

currNode=currNode.nextNode;

index++;

if(position==index)

{

beforeNode=currNode.prevNode;

afterNode=currNode.nextNode;

beforeNode.nextNode=afterNode;

afterNode.prevNode=beforeNode;

size--;

}

}

}

}

}

public int search(int data)

{

DLLNode currNode=headNode;

int index=1;

while(currNode!=null)

{

if(currNode.data==data)

{

return index;

}

currNode=currNode.nextNode;

index++;

}

return -1;

}

public void displayNodes()

{

DLLNode currNode=headNode;

/*scenario: no nodes to display*/

if(currNode==null)

{

System.out.println("No nodes to display");

}

else

{

while(currNode!=null)

{

System.out.println("Data:"+currNode.data);

currNode=currNode.nextNode;

}

}

}

}

<hr />

package com.wordpress.sreeharshasite;
public class DoubleLinkedListDemo

{

public static void main(String[] args)

{

DoubleLinkedList dll=new DoubleLinkedList();

dll.addAtStart(24);

dll.addAtStart(48);

dll.addAtStart(72);

dll.addAtStart(96);

int data=dll.deleteAtStart();

System.out.println("Deleted data is:"+data);

dll.addAtEnd(120);

data=dll.deleteAtEnd();

System.out.println("Deleted data is:"+data);

dll.addAtPosition(96, 1);

dll.deleteAtPosition(6);

dll.displayNodes();

int position=dll.search(24);

System.out.println("Data position is:"+position);
}
}


Output

Deleted data is:96
Deleted data is:120
Postion entered is invalid
Data:96
Data:72
Data:48
Data:24
Data position is:4


 

Advertisements

I am Sreeharsha from Bengaluru. I am working in java for the past 6+ years. In this blog i will be sharing posts regarding java , advanced java , monthly challenges, collection of quotes , my themes and many more. If you like my posts please follow my blog.

Tagged with: , ,
Posted in Core Java, Data Structures

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

Follow My Diary on WordPress.com
Archives

Enter your email address to follow this blog and receive notifications of new posts by email.

%d bloggers like this: