C++ Program to implement a doubly linked list.

by Arun Vishnu · Published November 28, 2008 · Updated October 24, 2011

/**************************************************************	
	Author: Arun Vishnu M V
	Web: www.arunmvishnu.com
	Description: C++ Program to implement a doubly linked list.
***************************************************************/
#include<iostream.h>
#include<conio.h>
#include<process.h>
//   Creating a NODE Structure
struct node
{
   int data;  // data
   struct node *next,*back; //  link to next node and previous node
};

// Creating a class LIST
class list
{
   struct node *root,*end;
   public:
      void create(); // to create a list
      void insert();  // insertion
      void del();    // deletion
      void show();   // show
};
// Creating a new node
void list::create()
{
   struct node *nxt_node,*pre_node;
   int value,no,i;
   root=nxt_node=NULL;
   cout<<"\nCREATING A NEW LIST.........\n\nHow many nodes : ";
   cin>>no;
   for(i=1;i<=no;i++)
   {
      cout<<"Enter the DATA: ";
      cin>>value;
      nxt_node=new node;
      nxt_node->data=value;
      nxt_node->next=NULL;
      nxt_node->back=NULL;
      if(root==NULL)
	 root=nxt_node;
      else
      {
	 pre_node->next=nxt_node;
	 nxt_node->back=pre_node;
      }
      pre_node=nxt_node;
   }
   end=nxt_node;
   cout<<"\nThe list is created!";
   show();
}

// Displaying LIST
void list::show()
{
   struct node *ptr=root;
   cout<<"\n\nThe List is (first to last order)\n";
   cout<<"root -> ";
   while(ptr!=NULL)
   {
      cout<< ptr->data << " -> ";
      ptr = ptr->next;
   }
   cout<<"end";
   ptr=end;
   cout<<"\n\nThe List is (last to first order)\n";
   cout<<"end <- ";
   while(ptr!=NULL)
   {
      cout << ptr->data <<" <- ";
      ptr= ptr-> back;
   }
   cout<<"root";
   getch();
}

// Insert node at any position
void list::insert()
{
   int position,dat;
   struct node *ptr_b,*ptr_f,*ptr;
   cout<<"\nInsertion of a new node \n";
   cout<<"Enter the DATA after which the new node is to be inserted.\n";
   cout<<"[ If the data is not found the new node will be";
   cout<<" created at first ]\n\t->:  ";
   cin>>position;
   cout<<"Enter the data to insert: ";
   cin>>dat;
   ptr_b=root;
   ptr=new node;
   ptr->data=dat;
   while(ptr_b->next!=NULL && ptr_b->data!=position)
   {
      ptr_b=ptr_b->next;
   }
   if(ptr_b->next==NULL && ptr_b->data!=position)
   //Insertion at first
   {
      root->back=ptr;
      ptr->next=root;
      ptr->back=NULL;
      root=ptr;
   }
   else if(ptr_b->next==NULL && ptr_b->data==position)
   //insertion at the end of list
   {
      ptr_b->next=ptr;
      ptr->next=NULL;
      ptr->back=ptr_b;
      end=ptr;
   }
   else
   //Insertion between two nodes
   {
      ptr_f=ptr_b->next;
      ptr->next=ptr_b->next;
      ptr->back=ptr_b;
      ptr_b->next=ptr;
      ptr_f->back=ptr;
   }
   cout<< "\nNew node is inserted!!";
   getch();
}  //End of insertion

//Delete node from any position
void list::del()
{
   int position,dat;
   struct node *ptr_b,*ptr_f,*ptr;
   cout<<"Enter the data to be beleted: ";
   cin>>position;
   ptr=root;
   while(ptr->next != NULL && ptr->data != position)
   {
      ptr=ptr->next;
   }
   if(ptr->next==NULL && ptr->data!=position)
   //Data not found
   {
      cout<<"\nData not found!!";
      getch();
      return;
   }
   else if(ptr->next==NULL && ptr->data==position)
   //Deletion from the end of list
   {
      ptr_b=ptr->back;
      dat=ptr->data;
      ptr_b->next=NULL;
      end=ptr_b;
   }
   else
   //Deletion between two nodes or first node
   {
      dat=ptr->data;
      if(root==ptr)  // delete first node
      {
	  root=ptr->next;
	  ptr_f=root;
	  ptr_f->back=NULL;
      }
      else // Deletion between two nodes
      {
	 dat = ptr->data;
	 ptr_b = ptr->back;
	 ptr_b->next = ptr->next;
	 ptr_f = ptr_b->next;
	 ptr_f->back = ptr_b;
       }
   }
   delete ptr;
   cout<<"\nThe node is deleted!!\nData= " << dat;
   getch();
}  //End of deletion


// Main function
int main()
{
   clrscr();
   list l;
   l.create(); // to create a new node
   int choice;
   while(1)
   {
      cout<<"\n-----------------------------------------------------------";
      cout<<"\n\t\tDOUBLY LINKED LIST\n\n";
      cout<<"1:Insertion\n2:Deletion\n3:Display List\n4:Exit";
      cout<<"\nEnter your choice(1-4): ";
      cin>>choice;
      switch(choice)
      {
       case 1:  // Insertion
	  l.insert();
	  break;
       case 2:   // Deletion
	  l.del();
	  break;
       case 3:  // Display
	  l.show();
	  break;
       case 4:  // Exit
	  exit(0);
	  break;
       default:
	  cout<<"Please enter correct choice(1-4)!!";
	  getch();
	  break;
       }
   }
   return 0;
}