Updated April 17, 2023
Introduction to Doubly linked list in C++
A doubly linked list plays a pivotal role in C++, which is used for many of the operations and manipulations with elements present within the entire list. A doubly linked list is made up of many nodes represented back to back, which is created and uses self-referencing pointers. Nodes present as part of a doubly-linked list are used to get the data with pointers that point to the next data present within the node and references present within the node that helps depict the next node or the previous node it is pointing to at.
Syntax
There is no specific syntax for the doubly linked list, but it is represented in the following way where some operations can be performed:
#include<iostream>
struct Node_0
{
int dta;
struct Node_0 *prv;
struct Node_0 *nxt;
}Scenarios to be performed:
- Insertion at the front of the list
- Insertion at the end of the list
- Insertion before a node
- Insertion after a node
- Deletion of the first node
- Deletion of the last node
- Deletion of the node with the presence of data
How doubly linked list works in C++?
- The doubly linked list is a very efficient data structure for any programming language, so do in C++; it is used for the manipulation of elements.
- The doubly linked list is made up of many nodes in a sequence, and it further provides pointer concepts for performing various operations on top of those nodes present within the list.
- Each node has a significance, and it is majorly categorized into three parts such as first part, which signifies the data of the node, followed by the second part of the node, which consists of the reference to the next node, and the third part which consists of the reference pointing to previous of the node in the list.
- Suppose, for instance, any doubly linked list is initialized, then in that case, the first node and its reference play a very crucial situation in the sense it is used for accessing any value or the element within the entire list.
- This first node defined in the entire list is mainly called a head node that can access any of the nodes within the list, as mentioned before.
- The fashion in which nodes are arranged consists of multiple nodes, therefore, the second node comprises the reference to the next node, and it happens to be designed in the same format, but the last node comprises the null reference, which indicates the end of the list, unlike circular doubly linked list.
- Traversal in a double linked list is possible in both ways, beginning from the first node until the end of the list as the last node.
- Traversing also consists of some rules and regulations for performing any manipulation with the elements; unlike single-linked lists in doubly linked lists, it is required first to check whether the node initialized is empty or not. Once it is investigated that the Node is set properly, then it will be useful in the long run for accessing any element within the entire list.
- For insertion of a new node also require some constant checks on the previous node and the next node with the proper set of links within each other having proper interlinking between all the nodes.
- Something the same happens when it is required to delete node either from the beginning, end, and middle anywhere; what matters most is the proper set of pointers pointing to the prev node or the next node logically in the entire list.
- There is a case of reversal of entire doubly linked list then in that scenario also some steps needs to be followed like :
- The pointer starts by pointing to the last node of the entire list, which is now the first node.
- Once the last node becomes the first node, then its previous node’s pointer must be NULL.
- A node which is the last node should be NULL.
- It’s almost at the verge where all the pointer points to the previous node, and so on untilling all the nodes are in a proper format.
- All the complex data structures with pointers and operations can be easily satisfied by using a doubly-linked list because of its flexibility and versatility to play around with elements easily.
Example of Doubly linked list in C++
This program demonstrates the implementation of Doubly Linked List with the insertion of the element before the list, insertion at the last of the list, and then displaying all the elements.
#include<iostream>
using namespace std;
struct Nd_0 {
int dta;
struct Nd_0* nxt_1;
struct Nd_0* prv_1;
};
void insrt_frnt(struct Nd_0** head, int dta)
{
struct Nd_0* newnd_0 = new Nd_0;
newnd_0->dta = dta;
newnd_0->nxt_1 = (*head);
newnd_0->prv_1 = NULL;
if ((*head) != NULL)
(*head)->prv_1 = newnd_0;
(*head) = newnd_0;
}
void insrt_After_node_0(struct Nd_0* prv_10, int new_data_8)
{
if (prv_10 == NULL) {
cout<<"Previous_Node_Required_is_not_null:";
return;
}
struct Nd_0* newNd_1 = new Nd_0;
newNd_1->dta = new_data_8;
newNd_1->nxt_1 = prv_10->nxt_1;
prv_10->nxt_1 = newNd_1;
newNd_1->prv_1 = prv_10;
if (newNd_1->nxt_1 != NULL)
newNd_1
->nxt_1->prv_1 = newNd_1;
}
void insert_end_8(struct Nd_0** hed_0, int nw_dta_3)
{
struct Nd_0* newNdo_3 = new Nd_0;
struct Nd_0* lst_0 = *hed_0;
newNdo_3->dta = nw_dta_3;
newNdo_3->nxt_1 = NULL;
if (*hed_0 == NULL) {
newNdo_3->prv_1 = NULL;
*hed_0 = newNdo_3;
return;
}
while (lst_0->nxt_1 != NULL)
lst_0 = lst_0->nxt_1;
lst_0->nxt_1 = newNdo_3;
newNdo_3->prv_1 = lst_0;
return;
}
void displList_0(struct Nd_0* nd_2) {
struct Nd_0* lst_0;
while (nd_2 != NULL) {
cout<<nd_2->dta<<"<==>";
lst_0 = nd_2;
nd_2 = nd_2->nxt_1;
}
if(nd_2 == NULL)
cout<<"NULL";
}
int main() {
struct Nd_0* hed_0 = NULL;
insert_end_8(&hed_0, 20);
insrt_frnt(&hed_0, 52);
insrt_frnt(&hed_0, 10);
insert_end_8(&hed_0, 50);
insrt_After_node_0(hed_0->nxt_1, 25);
cout<<"Doubly linked list is as follows: "<<endl;
displList_0(hed_0);
return 0;
}Output:
Conclusion
A doubly linked list is part of a data structure used to implement complex structure and pointer-related issues. It is mostly used for making memory management and working in proper order. Doubly linked lists have given developers the flexibility to play around with the pointers of previous and next nodes when it comes to manipulation and operations.
Recommended Articles
This is a guide to the Doubly linked list in C++. Here we discuss How a doubly linked list works in C++ along with the example and output. You may also have a look at the following articles to learn more –
