Doubly Linked List in C++

Doubly linked list in C++

What is a doubly linked list in CPP programming?

Doubly linked list in C++ is the advanced and complex type of linked list that allows users to easily navigate through the linked list in both directions, from head to tail as well as from tail to head. The beginning node of the linked list is referred to as the header and the last node is referred to as the tail. Unlike the single-linked list, each node of the double-linked list is divided into three corresponding sections, previous which points the address of previous node , data which stores the value of the node and next which points the next node in the list.

 

Why
Doubly Linked List?

Saves time

A doubly linked list can be traversed in both the directions hence it saves time when we need to traversed in the list.

Efficient operations on a specific position

Insertion and deletion operations of specific position are more efficient in doubly linked list.

Effective memory utilization

It utilizes memory as we can construct and delete nodes according to our need so wastage of the memory is not there.

STRUCTURE

STRUCTURE

Structure of doubly linked list

Using the following statements in our program we can create a doubly linked list. This set of code will construct a doubly linked list that will store integer type of data.

struct Node 
{
  int Data;
  Struct Node* next;
  Struct Node* prev;
};
Doubly Linked List in C++ programming

Operation on doubly linked list in C++

We can perform following operations on a doubly linked list in CPP programming language.

C++ programming code for creating a doubly linked list

Run
#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *prev;
   struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
   struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
   newnode->data = newdata;
   newnode->prev = NULL;
   newnode->next = head;
   if(head != NULL)
   head->prev = newnode ;
   head = newnode;
}
void display() {
   struct Node* ptr;
   ptr = head;
   while(ptr != NULL) {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   }
}
int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   insert(9);
   cout<<"The doubly linked list is: ";
   display();
   return 0;
}
Output:
The doubly linked list is: 9 2 7 1 3

Disadvantages of doubly linked list in CPP programming

  1. Doubly linked list has two pointer so it requires more memory per node.
  2. Insertion and deletion operations are efficient but they requires more time as two pointer need to be maintained.