C++ Program To Implement Doubly Linked-List

In this article, you will learn to write a C++ Program to implement Doubly Linked-List. The doubly linked-list is a linear data structure that allows traversing the list in both direction.

This program is written using Turbo C++ 3.0 compiler installed on a Windows 7 64-bit PC.

Problem Definition

The doubly linked-list structure has two links for each node – previous and next. The previous link points to previous node and next node points to next node to current node. This allows moving through the list in both direction.

Doubly-Linked-List

Program Code – Doubly Linked-List


/* C++ Program to Implement a Doubly linked-list

File Name: DoublyLinkedList.cpp

Author: NotesforMSc
*/

#include "iostream.h"
#include "stdio.h"
#include "alloc.h"
#include "conio.h"

//Defining structure of the node

struct Double {

   int info;
   struct Double *next;
   struct Double *previous;
   };

//Defining class doubly linked-list

class doubly_link {

   public:
      int num;
      Double start, *temp;
   public:
      void Doubly_Create(Double *);
      void Doubly_Insert(Double *);
      void Doubly_Delete(Double *);
      void display(Double *);
      };

      //Function definition for doubly_create()

  void doubly_link::Doubly_Create(Double *node) {

     start.next = NULL;
     start.previous = NULL;

     //Start is the first node in the Doubly linked-list

     node= &start;
     num = 0;
     cout << "Input $ to break, else press enter:";
     char ch;
     ch = getche();

     while(ch != '$') {

     //Create memory space for next node to start node

	node->next = (Double *)malloc (sizeof(Double));

     //Point the previous link of next node to start node

	node->next->previous = node;

     //The next node becomes the start node now

	node = node->next;

     //Read data value for the node

	cout << "\n Input data for node:" << (num + 1) << ":";
	cin >> node->info;

     //The Next Pointer of the node points to NULL

	node->next = NULL;

	cout << "Input $ sign to end, else press enter:";
	ch = getche();

	num++;
     }
	cout << "\nTotal Nodes =" << num;
	}

     //Function definition for Doubly_Delete()

     void doubly_link::Doubly_Delete(Double *node) {

	node = start.next;

	if(node == NULL) {

	   cout << "\n Underflow";
	   }
	else {

	//If you want to delete Node, change the
	//next pointer of Previous node, point to Next node,
	//and change the previous pointer of Next node,
	//point to Previous node.

	  node->previous->next = node->next;
	  node->next->previous = node->previous;
	  free(node);
	  }
	}

	//Function definition for Doubly_Insert()

	void doubly_link::Doubly_Insert(Double *node) {

	   temp = (Double*)malloc(sizeof(Double));

	   cout << "\n Insert the node value:";
	   cin >> temp->info;

	   node = start.next;

	   if(node == NULL) {

	      cout << "\n Node is empty";
	      }
	   else {

	   //The temp node next points to node

	      temp->next = node;

	   //The temp node previous points to
	   //start node next (node->previous)

	      temp->previous = node->previous;

	   //Start node (node->previous) next pointer
	   //points to new temp node

	      node->previous->next = temp;
	      }
	   }

	  //Function definition for display()

	  void doubly_link::display(Double *node) {

	      node = start.next;

	      do {
		 cout << "-->";
		 cout << " " << node->info;
		 node = node->next;
		 }while(node != NULL);

		 getch();
	      }

	      //MAIN PROGRAM STARTS HERE

	      void main() {

		 doubly_link dlinked_list;
		 int br;

		 clrscr();

		 cout << "\t\t\tDOUBLY LINKED LIST";
		 cout <<"\n\t\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n";
		 cout << "1-Create List" << endl;
		 cout << "2-Insert Nodes" << endl;
		 cout << "3-Delete Nodes" << endl;
		 cout << "4-Display List" << endl;
		 cout << "0-Exit" << endl;
		 cout << "\n";
		 cout << "Enter Your Choice, 0 to end:";
		 cin  >> br;

		 while(br != 0) {

		   switch(br) {

		    case 1:

		     Double *node = (Double *)malloc(sizeof(Double));
		     dlinked_list.Doubly_Create(node);
		     break;

		    case 2:
		     cout << "\nInserted node\n\n";
		     dlinked_list.Doubly_Insert(node);
		     break;

		    case 3:
		     cout << "\nDeleted node\n\n";
		     dlinked_list.Doubly_Delete(node);
		     break;

		    case 4:
		     dlinked_list.display(node);
		     break;

		    default:
		     cout << "Sorry ! Wrong Input" << endl;
		     break;
		 }
		 cout << "\n Enter Your Choice, 0 to end:" << endl;
		 cin >> br;
	      }
	  }

Output – Doubly Linked-List


                              DOUBLY LINKED LIST
		   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
		    1-Create List
		    2-Insert Nodes
		    3-Delete Nodes
		    4-Display List
		    0-Exit
		 
		    Enter Your Choice, 0 to end: 1
                    Input $ to break, else press enter:
                    Input data for node: 44
                    
                    Input $ to break, else press enter:
                    Input data for node: 88
                    
                    Input $ to break, else press enter:$

                    Enter Your Choice, 0 to end: 4

                    -->44 -->88

                    Enter Your Choice, 0 to end: 2
                    Insert the node value : 55

                    Enter Your Choice, 0 to end: 4

                    -->55 -->44 -->88

                    Enter Your Choice, 0 to end: 0
                                    
Skip to content