Doubly Linked List

Doubly Linked List

• The doubly linked list has two link fields. One link field is previous pointer and the other link field is that next pointer. The typical structure of each node in doubly linked list is like this.

'C++' structure of doubly linked list:

typedef struct node

{

   int Data;

   struct node *prev;

   struct node *next;

}

• The linked representation of a doubly linked list is

• Thus the doubly linked list can traverse in both the directions, forward as well as backwards.

• Now, there may be one question in your mind that how do the empty doubly circular linked lists look? Here is the representation.

That means the prev and next pointers are pointing to the self node.

Logic for doubly linked list

In doubly linked list there are following operations

1. Create

2. Display

3. Insert

4. Delete

The node in Doubly Linked List (DLL) will look like this

1. Creation of node

Initially set new node as

For the first time flag = 0

Now set flag = 1, if we want to create more node then ‒

If we want to attach node 30 then

This we can continue to create a doubly linked list.

2. Display of doubly linked list

We assign head node address to temp node.

while (temp → next!= NULL)

{

// display data at temp node.

temp =  temp →next;

}

This will display 10      20       30 as a doubly linked.

3. Deletion of a node in doubly linked list

Consider,

I) (curr→next)→prev = temp;

II) temp→ next) = curr→next;

Then delete curr.

4. Insertion of a node

Consider a list

Suppose we want to insert 31 after 30 then first search for node 30 call it as temp node. Then create a node containing value 31.

(I) n1→next = temp→>next;

(II) temp→next→ prev = n1;

(III) temp→ next = n1

(IV) n1→ prev = temp

Thus "Node inserted".

/**************************************************************************

Demonstration Program to perform various operations such as insertion, deletion, finding the lenghth of the doublly linked list.

**************************************************************************/

// List of include files

#include<iostream>

using namespace std;

// class defination

class dll

{

private:

struct node

{

   int Data;

   structnode *next;

   structnode *prev;

}*head;

public:

dll();

void create();

void print();

void insert _beg();

void insert_ after();

void insert_ end();

void del();

int length();

~dll();

};

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Constructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

dll::dll()

{

   head=NULL;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The destructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

dll::~dll()

{

   node *temp, *temp1; //free the memory

   temp=head;

   while(templ=NULL)

   {

      templ=temp‒>next;

      delete temp;

      temp=temp1;

   }

}

/ *

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Create function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void dll::create():

{

   // Local declarations here

   node *n1,*last, *temp;

   char ans ='y';

   int flag=0;

   int val;

   do

   {

      cout<<"\nEnter the data:";

      cin>>val;

      // allocate new node

      n1 = new node;

      if (n1 = = NULL)

      cout<<"Unable to allocate memory\n";

      n1 ‒> Data = val

      n1‒>next = NULL;

      n1 ‒> prev = NULL;

      if (flag= =0) // Executed only for the first time

      {

         temp=n1;

         last=temp;

         flag=1;

      }

      else

      {

            // last keeps track of the most recently created node

            last‒>next=n1;

            n1‒>prev=last;

            last=n1;

      }

cout<<"\n\nEnter more?";

ans = getche();

}while(ans= ='y' || ans = ='Y');

cout<<"\nThe List is created\n";

head=temp;

getch();

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The length function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

int dll::length()

{

node *curr

int count;

count = 0;

curr= head;

if ( curr = = NULL )

{

   cout<<"The list is empty\n",

   getch();

   return 0;

}

while (curr != NULL)

{

   count++;

   curr = curr‒>next; // traverse till end

}

getch();

return count;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The print function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void dll ::print()

{

   node *temp;

   temp =  head;

   if ( temp = = NULL)

   {

      cout<<"\nThe list is empty\n";

      getch(); clrscr();

      return;

   }

   else

   {

      cout<<"\nThe list is:";

      while(temp ! = NULL)

      {

      cout<<temp‒>Data<<" ";

      temp = temp ‒>next;

      }

   }

   getch();

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The del function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void dll:: del()

{

node *curr, *temp;

int data;

curr = head;

cout<<"\nEnter the data of the node you want to delete: ";

cin>>data;

while(curr!= NULL)

{

   if(curr‒>Data= =data) //traverse till the required node to delete

   break;         //is found

   curr=curr‒>next;

}

if(curr= =NULL)

   cout<<"\nNode not found";

else

{

   if(curr= =head)

   {

      if(head‒>next= =NULL&&head‒>prev= = NULL)//only one node

      head=NULL;

   else

   {

      head=curr‒>next;// first node

      head‒>prev=NULL;

   }

}

else

{

   temp=curr‒>prev; //intermediate or end node

   if(curr‒>next!=NULL)

    (curr‒>next)‒>prev=temp;

   temp‒>next=curr‒>next;

}

delete curr; //free memory

cout<<"\nThe item is deleted\n";

}

getch();

}

/*‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

Function to insert at end

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒*/

void dll::insert_end()

{

node *temp, *n1;

int val,flag=0;

cout<<"\nEnter the data of the new node to insert";

cin>>val;

temp=head;

if(temp= = NULL)

   flag=1;

else

{

   while(temp‒>next!= NULL) // traverse till end

   temp=temp‒>next;

}

// allocate new node

n1 = new node;

if (n1 = = NULL )

cout<<"\nUnable to allocate memory\n";

n1‒> Data = val;

n1 ‒> next =NULL;

n1 ‒> prev = NULL;

if(flag= =0)

{

   temp‒>next=n1; // attach at end

   n1‒>prev=temp;

}

else

   head=n1;         //if list empty make this node as head node

cout<<"\nNode inserted";

}

/*‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

Function to insert after a node

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒*/

void dll:: insert_after()

{

node *temp, *nl;

int val,val1;

cout<<"\nEnter the data of the new node to insert";

cin>>val;

cout<<"\nEnter the data of the node after which to insert";

cin>>val1;

temp=head;

while(temp!= NULL)

{

   if(temp‒>Data= =val1) //traverse till the required node after which to insert

   break;

   temp=temp‒>next;

}

if(temp! =NULL)

{

   /* allocate new node */

   n1 = new node;

   if (n1= = NULL)

   cout<<"Unable to allocate memory\n";

   n1‒> Data = val;

   n1‒> next = NULL;

   n1‒> prev = NULL;

   /* after temp attach*/

   n1‒>next= temp‒>next;

   temp‒>next‒>prev=n1;

   temp‒>next=n1;

   n1‒>prev=temp;

   cout<<"\nNode inserted";

}

else

   cout<<"\nNode after which to insert not found";

}

/*‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

Function to insert at the beginning

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒*/

void dll:: insert_beg()

{

node *temp, *n1;

int data;

cout<<"\nEnter the data of the new node to insert";

cin>>data;

/* allocate new node */

n1= new node;

if (n1 = = NULL)

   cout<<"Unable to allocate memory\n";

n1 ‒> Data = data;

n1‒>next = NULL;

n1‒> prev = NULL;

if(head)

{

   n1‒>next=head; //attach before head

   head‒>prev=n1;

}

head=n1; //make this node as head

cout<<"\nNode inserted";

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The main function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void main()

{

dll d;

int ch,ch1,cnt;

char ans = 'y';

do

{

   clrscr();

   cout<<"\n"<<<"MENU";

   cout<<"\n1.Create\n2.Display\n3.Insert\n4.Delete\n5.Length";

   cout<<"\nEnter ur choice:";

   cin>>ch;

   switch(ch)

   {

      case 1: d.create();

            break;

      case 2: d.print();

            break;

      case 3: clrscr();

            d.print();

            cout<<"\nMenu";

            cout<<"\n1.Insert at beginning\n2.Insert after";

            cout<<"\n3.Insert at end";

            cout<<"\nEnter your choice";

            cin>>ch1;

            switch(chl)

            {

               case 1: d.insert_beg();

                     d.print();

               break;

         case 2: d.insert_after();

               d.print();

               break;

         case 3: d.insert_end();

               d.print();

               break;

         default:cout<<"\nInvalid choice";

   }

   break;

   case 4: d.print();

         d.del();

         d.print();

         break;

   case 5: cnt=d.length();

         cout<<"The length is: "<<cnt;

         break;

   default: cout<<"\nInvalid choice";

}

cout<<"\n Do You Want To Continue?";

cin>>ans;

}while(ans= ='y'||ans= ='Y');

getch();

return;

}

Output

MENU

1.Create

2.Display

3.Insert

4.Delete

5.Length

Enter ur choice:1

Enter the data :1

Enter more?y

Enter the data :2

Enter more?y

Enter the data :3

Enter more?y

Enter the data :4

Enter more?y

Enter the data :5

Enter more?n

The List is created

Do You Want To Continue?

MENU

1.Create

2.Display

3.Insert

4.Delete

5.Length

Enter ur choice:2

The list is:1  2  3  4  5

 

Difference between Singly and Doubly Linked List

Singly linked list

1. Singly linked list is a collection of nodes and each node is having one data field and next link field.

For example:

2. The elements can be accessed using next link.

3. No extra field is required; hence node takes less memory in SLL.

4. Less efficient access to elements.

Doubly linked list

1. Doubly linked list is a collection of nodes and each node is having one data field, one previous link field and one next link field

For example:

2. The elements can be accessed using both previous link as well as next link.

3. One field is required to store previous link hence node takes more memory in DLL.

4. More efficient access to elements.

 

Review Questions

1. Explain various operations performed on the doubly linked list.

2. Explain the insertion and deletion operation in doubly linked list.