Dremendo Tag Line

Doubly Linked List in C++ Programming

Function in C++

In this lesson, we will understand what is Doubly Linked List in C++ Programming and how to create them along with some examples.

What is Doubly Linked List in C++

Just like Singly Linked List, a Doubly Linked List in C++ is a data structure in which data is store in the form of structure called a node. But in doubly linked list each node has three parts, the data part, the previous pointer part and the next pointer part.

The data part stores the data, the previous pointer part stores the memory address of the previous node, and the next pointer part stores the memory address of the next node as shown in the below image.

c doubly linked list

In the above image, start is a structure pointer that stores the memory address of the first node.

The first node has three parts, the data part and the pointer parts prev and next. The prev part stores the memory address of the previous node and the next part stores the memory address of the next node.

In a doubly linked list data, are not stored in a contagious memory location. A new node can be created anywhere in the memory at runtime.

Just like singly linked list, we can create more nodes as we want by linking the newly created node with the last node.

video-poster

Structure of a Doubly Linked List Program

Below we have given the complete structure of a singly linked list program in C++ along with all the operation that we are going to perform on it.

Program

#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <malloc.h>

using namespace std;

// Define node structure
typedef struct node
{
    int data;
    struct node *prev;
    struct node *next;
} node;

int main()
{
    node *start=NULL,*newnode,*temp,*rn;
    int ch,n,x,c,f;

    for(;;)		// An infinite loop
    {
        system("cls");		// for clearing the screen
        cout<<"1. Add\n";
        cout<<"2. Display\n";
        cout<<"3. Insert Before\n";
        cout<<"4. Insert After\n";
        cout<<"5. Count\n";
        cout<<"6. Search\n";
        cout<<"7. Delete\n";
        cout<<"8. Reverse\n";
        cout<<"Enter Choice: ";
        cin>>ch;

        switch(ch)
        {
            case 1:		// Create new node
                break;

            case 2:		// Display all nodes
                break;

            case 3:		// Insert node before
                break;

            case 4:		// Insert node after
                break;

            case 5:		// Count total nodes
                break;

            case 6:		// Search a node
                break;

            case 7:		// Delete a node
                break;

            case 8:		// Reverse list
                break;

            default:	// default case for wrong choice input
                cout<<"Wrong Choice";
                getch();	// pause the loop to see the message
        }
    }
    return 0;
}

The above program shows how a singly linked list program will look with all the operations on it. Now we will discuss each part of the above program and the program required to be written in each case for each individual operations like create, insert before, insert after and so on.

Define Node Structure

So first of all we will define a node structure above the main() function that will store data and the address of the previous and next node, as shown below.

Example

typedef struct node
{
    int data;
    struct node *prev;
    struct node *next;
} node;

In the above code, node is the name of a structure data type. It contains an integer variable data to store the number, a node type pointer variable *prev to store the memory address of the previous node and another node type pointer variable *next to store the memory address of the next node.

Declare Variables

After defining the node structure, now we will declare the necessary variables required for our program as shown below

Example

node *start=NULL, *newnode, *temp, *rn;
int ch, n, x, c, f;

The description of the above variables are as follows.

  • *start will store the address of the first node in the memory. The default value is NULL.
  • *newnode will store the address of newly created node.
  • *temp will store the address of a selected node for temporary purpose. This variable will be used to reverse the linked list.
  • *rn will store the address of recent node. This variable will be used when we will read each node one by one.
  • ch will store the choice of the menu input by the user like 1, 2, 3, etc.
  • n will store the number input by the user and will be used later on in the program for various purposes.
  • x will store the number input by the user and will be used later on in the program for various purposes.
  • c will be used to count the total number of nodes present in the linked list.
  • f will be used to check if a node is found or not. When a node is found in the list the value of f will be 1 otherwise 0.

Add Operation (case 1:)

In the add operation, we will add new node in the linked list using the program given below.

case 1:

cout<<"Enter a number ";
cin>>n;

// Create a new node
newnode=new node;
newnode->data=n;
newnode->prev=NULL;
newnode->next=NULL;

if(start==NULL)
{
    start=newnode;		// points to the first node in memory
}
else
{
    rn=start;	// recent node

    // find the last node in memory
    while(rn->next!=NULL)
    {
        rn=rn->next;	// move to the next node
    }
    rn->next=newnode;	// last node
    newnode->prev=rn;	// new node->prev = recent node
}
break;

Display Operation (case 2:)

In the display operation, we will display all the nodes on the screen using the program given below.

case 2:

if(start==NULL)
{
    cout<<"List is empty";
    getch();	// pause the loop to see the message
}
else
{
    rn=start;	// recent node

    // display the nodes on the screen
    while(rn!=NULL)
    {
        cout<<rn->data<<" ";
        rn=rn->next;
    }
    getch(); // pause the loop to see the nodes
}
break;

Insert Before Operation (case 3:)

In the insert before operation, we will insert a new node before a selected node in the linked list using the program given below.

case 3:

f=0;
if(start==NULL)
{
    cout<<"List is empty";
    getch();	// pause the loop to see the message
}
else
{
    cout<<"Insert Number ";
    cin>>n;
    cout<<"Insert Before ";
    cin>>x;

    // Create a new node
    newnode=new node;
    newnode->data=n;
    newnode->prev=NULL;
    newnode->next=NULL;

    // search number x in the list from the starting node
    rn=start;
    while(rn!=NULL)
    {
        if(start==rn && rn->data==x)	// insert before first node
        {
            newnode->next=rn;	// newnode->next = recent node
            rn->prev=newnode;	// recent node->prev = newnode
            start=newnode;		// start = new node
            f=1;
            break;
        }
        else if(start!=rn && rn->data==x)	// insert before recent node
        {
            newnode->next=rn;				// newnode->next = recent node
            newnode->prev=rn->prev;			// new node->previous = recent node->previous
            newnode->prev->next=newnode;	// new node->previous->next = new node
            rn->prev=newnode;				// recent node->previous = new node
            f=1;
            break;
        }
        rn=rn->next;		// recent node = recent node->next
    }

    if(f==0)
    {
        cout<<"Number not found";

        // delete the newely created node
        delete newnode;

        getch();	// pause the loop to see the message
    }
}
break;

Insert After Operation (case 4:)

In the insert after operation, we will insert a new node after a selected node in the linked list using the program given below.

case 4:

f=0;
if(start==NULL)
{
    cout<<"List is empty";
    getch();	// pause the loop to see the message
}
else
{
    cout<<"Insert Number ";
    cin>>n;
    cout<<"Insert After ";
    cin>>x;

    // Create a new node
    newnode=new node;
    newnode->data=n;
    newnode->prev=NULL;
    newnode->next=NULL;

    // search number x in the list from the starting node
    rn=start;
    while(rn!=NULL)
    {
        if(rn->data==x && rn->next==NULL)	// insert after last node
        {
            newnode->prev=rn;		// newnode->previous = recent node
            rn->next=newnode;		// recent node->next = newnode
            f=1;
            break;
        }
        else if(rn->data==x && rn->next!=NULL)	// insert after recent node
        {
            newnode->next=rn->next;		// newnode->next = recent node->next
            newnode->next->prev=newnode;	// new node->next->previous = newnode
            newnode->prev=rn;	// new node->previous = recent node
            rn->next=newnode; 	// recent node->next = new node
            f=1;
            break;
        }
        rn=rn->next;		// recent node = recent node->next
    }

    if(f==0)
    {
        cout<<"Number not found";

        // delete the newely created node
        delete newnode;

        getch();	// pause the loop to see the message
    }
}
break;

Count Operation (case 5:)

In the count operation, we will count the total numbers of nodes present in the linked list using the program given below.

case 5:

c=0;
if(start==NULL)
{
    cout<<"List is empty";
    getch();	// pause the loop to see the message
}
else
{
    // count from the first node till last node
    rn=start;
    while(rn!=NULL)
    {
        c=c+1;
        rn=rn->next;		// recent node = recent node->next
    }
    cout<<"Total Nodes = "<<c;
    getch();	// pause the loop to see the message
}
break;

Search Operation (case 6:)

In the search operation, we will search if a given node present in the linked list using the program given below.

case 6:

f=0;
c=0;
if(start==NULL)
{
    cout<<"List is empty";
    getch();	// pause the loop to see the message
}
else
{
    cout<<"Enter Number to Search ";
    cin>>x;

    // search number x in the list from the starting node
    rn=start;
    while(rn!=NULL)
    {
        c=c+1;			// count the numbers
        if(rn->data==x)
        {
            cout<<"Number "<<rn->data<<" Found at Position "<<c;
            f=1;
            break;
        }
        rn=rn->next;		// recent node = recent node->next
    }

    if(f==0)
    {
        cout<<"Number not found";
    }
    getch();	// pause the loop to see the message
}
break;

Delete Operation (case 7:)

In the delete operation, we will delete a given node from the linked list using the program given below.

case 7:

f=0;
if(start==NULL)
{
    cout<<"List is empty";
    getch();	// pause the loop to see the message
}
else
{
    cout<<"Enter Number to Delete ";
    cin>>x;

    // search number x in the list from the starting node
    rn=start;
    while(rn!=NULL)
    {
        if(start==rn && rn->data==x)	// delete the first node
        {
            start=rn->next;		// start = recent node->next
            rn->next->prev=NULL;	// recent node->next->prev = NULL
            delete rn;			// delete the recent node
            f=1;
            cout<<"Number Deleted Successfully";
            break;
        }
        else if(rn->next!=NULL && rn->data==x)	// delete other node
        {
            rn->prev->next=rn->next;	// recent node->previous->next = recent node->next
            rn->next->prev=rn->prev;	// recent node->next->prev = recent node->previous
            delete rn;			// delete the recent node
            f=1;
            cout<<"Number Deleted Successfully";
            break;
        }
        else if(rn->next==NULL && rn->data==x)	// delete the last node
        {
            rn->prev->next=NULL;
            delete rn;
            f=1;
            cout<<"Number Deleted Successfully";
            break;
        }
        rn=rn->next;		// recent node = recent node->next
    }

    if(f==0)
    {
        cout<<"Number not found";
    }
    getch();	// pause the loop to see the message
}
break;

Reverse Operation (case 8:)

In the reverse operation, we will reverse the reading order of nodes in the linked list by changing their pointer direction using the program given below.

case 8:

if(start==NULL)
{
    cout<<"List is empty";
    getch();	// pause the loop to see the message
}
else
{
    rn=start;		// recent node = start

    while(rn!=NULL)
    {
        temp = rn->prev;		// temp = recent node->previous
        rn->prev = rn->next;	// recent node->previous = recent node->next
        rn->next = temp;		// recent node->next = temp
        rn = rn->prev;			// recent node = recent node->prev
    }
    start=temp->prev;           // start = temp->previous

    // print the reverse list
    rn=start;
    while(rn!=NULL)
    {
        cout<<rn->data<<" ";
        rn=rn->next;
    }
    getch();	// pause the loop to see the nodes
}
break;