What is Doubly Linked List C++
Doubly Linked List is a linked list with two pointers one points to the previous node and the other points to the Next node of a list.
In doubly linked list we can traverse the list both sides from Head to the last node (tail) and from Tail to the head back.
See Also: What is a Singly Linked List
The doubly linked list is a dynamic linear data structure that grows and shrinks at the run time so there is no fixed size of nodes of a doubly linked list.
Note: The pointer is a variable that holds the address of another variable.
Also Read: Stack Using Linked List C++
Doubly Linked List Example
Step 1: Create a Structure Node
Simply Create a structure & name it Node with three fields.
- Int data, which stores the actual data.
- node *Next is a pointer to the next node.
- node *Prev is a pointer to the previous node.
Also, make two pointers to the node.
- *Head is also a pointer that holds first node.
- *Tail is a pointer that holds the address of the last node.
Step 2: Add nodes to List
2. Insert Nodes at the end of a Doubly linked list.
a. Now if head==null means there is no element in the list, so put this new node in the head, set both prev and next pointers to point to null, and point tail to this new node also.
b. Else, add new node and set tail to point to this node.
As we discussed earlier that how we create a doubly linked list and how we add nodes, now we will discuss how we insert nodes at the front or beginning and inserting nodes in the middle at some specific position or in between the nodes, position given by the user.
Also Read: Queue Using Array In C++
Step 3: Insert at Front
Insert at Front of a Doubly linked list
Let us Insert Nodes at Front of Linked list
- add_at_Front is simply a function name you can name it anything.
- Double_List it a class which we made in the first topic.
Now, try to understand.
1. At first we check if (head==Null) that means there is no
element, so we simply print message and return.
2. Else, there can be a single node or more than 1 node. Make a pointer to the node *temp with New keyword, like Node *temp; and then *temp=new node;
1. Now put the value of n in temp->data.
2. Since temp will be now the first element so prev=NULL.
3. Put temp->next to point the head, because it is first node.
4. Now Assign temp to head, now head is temp.
Step 4: Insert Node at Middle of a list
1. Double_List::add_at_pos(int n, int pos)
Add_at_Pos is another function it can be Insert_at_Pos or Insert at middle of a linked list.
Here we receive two arguments int n, int pos which user passes from the Main() function. n is data, and pos is the position at which we want to insert a new element or node.
1. Int count=1 simply used to count the total nodes.
2. The flag is used here because we have to insert in between the nodes so we need at least 2 nodes.
3. While loop here simply traverses the list until the position.
4. After the while loop, we check if(flag=1) means that the position is available because it is not changed in the while loops if condition.
Suggestion: Queue Using Linked List C++
Now understand the Logic here how we insert the node.
Recall here, temp is the new node which we have to insert, and the head is assigned in S, we never alter the head itself so that we will not lose it thus losing the entire list.
1. S is here the position after that we have to insert, so what S is pointing
point that to the new node i.e, temp->next.
2. S-next-prev is the S itself, but it now should be the new node temp.
3. Now point S-next to the temp i.e, new node.
4. Put new nodes prev pointer to the S node.
Now Else, means flag=0, so the exact position is not valid.
Step 5: Display( ) and Reverse( ) Doubly Linked List.
In Display we traverse the list and print the nodes at the same time. In Reverse we use the Tail which exactly behaves as Head, we traverse by the prev pointer to the head .
Step 6. Main() Function.
1. While(1) is an infinite loop and it never ends until we exit from it.
2. Switch() it simply switches the functions like add, display etc.
3. We call the functions of class Double Linked list here by making an
object of it. e.g, Double_List dl.
Therefore, dl.Display, dl.add-front, dl.insert-at-pos, etc.. calls the functions.
Recommended: Doubly Circular Linked List
Doubly Linked List C++ Program
//techindetail.com
//Doubly Linked List C/C++
#include<iostream>
using namespace std;
struct node
{
int data;
node *next;
node *prev;
}*head,*tail;
void init()
{
head=NULL;
tail=NULL;
}
class Double_List
{
public:
void create_list(int n);
void add_begin();
void add_pos(int n,int pos);
void display();
void reverse();
};
int main()
{
int count;
node *s;
init();
int choice,pos;
Double_List dl;
while(1)
{
cout<<"\n _ __ _____ ____ _____ ___ _ \n";
cout<<"1 Create list of 4 nodes: 2 add-begin:";
cout<<" 3 add-pos: 4 Display: 5 Reverse: 6 exit \n";
cin>>choice;
switch(choice)
{
case 1:
dl.create_list(11);
dl.create_list(22);
dl.create_list(33);
dl.create_list(44);
break;
case 2:
dl.add_begin();
break;
case 3:
dl.add_pos(100,6);
break;
case 4:
dl.display();
break;
case 5:
dl.reverse();
break;
case 6:
return 0;
default:
cout<<"wrong choice \n";
}
s=head;
count=0;
while(s!=NULL)
{
count++;
s=s->next;
}
cout<<"\t\t No. of Nodes: = "<<count<<endl;
}
return 0;
}
void Double_List::create_list(int n)
{
struct node *newnode;
newnode=new node;
newnode->data=n;
if(head==NULL)
{
head=newnode;
newnode->prev=NULL;
newnode->next=NULL;
tail=newnode;
}
else
{
newnode->prev=tail;
tail->next=newnode;
newnode->next=NULL;
tail=newnode;
}
}
void Double_List::add_begin()
{
if(head==NULL)
{
cout<<" NO element, ist create : \n";
return;
}
node *temp=new node;
int n;
cout<<"enter value : ";
cin>>n;
temp->data=n;
temp->prev=NULL;
temp->next=head;
head->prev=temp;
head=temp;
cout<<" Insert Sucessfull.... \n";
}
void Double_List::add_pos(int n,int pos)
{
node *temp,*s;
temp=new node;
temp->data=n;
s=head;
int count=1, flag=1;
if(pos==1)
{
cout<<"try another pos: \n";
return;
}
else
{
while(count!=pos-1)
{
s=s->next;
if(s==NULL)
{
flag=0;
break;
}
count++;
}
if(flag==1)
{
temp->next=s->next;
s->next->prev=temp;
s->next=temp;
temp->prev=s;
cout<<"Insert at Pos: "<<pos<<" is Succesfull.. \n";
cout<<"While loop runs( Traverse ) "<<count<<" times \n";
}
else
cout<<"Pos not found: \n";
}
}
void Double_List::display()
{
node *q;
if(head==NULL)
{
cout<<" list empty.. \n";
return;
}
q=head;
cout<<" The Double Linked list is \n";
while(q!=NULL)
{
cout<<q->data<<" <--> ";
q=q->next;
}
}
void Double_List::reverse()
{
node *r;
if(tail==NULL)
{
cout<<"EMPTY list: \n";
return;
}
else
{
r=tail;
while(r!=NULL)
{
cout<<r->data<<" <--> ";
r=r->prev;
}cout<<"reverse sucessful: \n";
}
}Code language: C++ (cpp)Output of Doubly Linked List C++ Program Code
See Also: Circular Linked List C++ Program
3. Applicatons of Linked lists:
In Tress and Graphs, you will see a large no of complex data structures that are mostly solved and constructed by the use of singly linked lists and doubly linked lists.
Binary Tree is a good example of doubly-linked lists. In which the prev pointer is treated as the child and next pointer as the t child of a parent node.
There are other large applications of linked lists in data structures and programming which you will accordingly.
Note: See also related articles below:
- Array a Linear Data Structure.
- Linked Lists C/C++.
- Doubly Circular Linked Lists.
- Singly Circular Linked Lists.
- Stack Using Arrays C++.
- Queue Using Arrays.
- Tree Data Structure
- Graph Data Structure