A Doubly linked list is used in navigation systems or to represent a classic deck of cards. A Doubly linked list is a bidirectional linked list; i.e., you can traverse it from head to tail node or tail to head node. Unlike singly-linked lists, its node has an extra pointer that points at the last node.
How Do You Implement a Doubly Linked List?
You create nodes of doubly-linked lists using classes or structures. These nodes are then linked with each other using the next and the previous pointer.
Code:
//A c++ program to implement linked list
#include <bits/stdc++.h>
using namespace std;
/* A class to create node */
class Node
{
public:
int data;
Node *next;
Node *prev;
};
//A function to insert at the
//beginning of the list
void push(Node** head, int newdata)
{
//create new node
Node* newnode = new Node();
/* put in the data */
newnode->data = newdata;
/* As we are adding at the beginning,
prev is always NULL */
newnode->prev = NULL;
/* link new node's next to head */
newnode->next = (*head);
/* change prev of head node to newnode */
if((*head) != NULL)
(*head)->prev = newnode ;
/* changing head node */
(*head) = newnode;
}
/* A c++ program to print the list */
void printlist(Node *head)
{
while(head != NULL)
{
cout << head->data << " ";
head = head->next;
}
}
int main()
{
/* We will start with an empty list */
Node* head = NULL;
/*lets create a linked list: 2->3->5->7 */
push(&head, 7);
push(&head, 5);
push(&head, 3);
push(&head, 2);
cout << "Created Doubly Linked list:" << endl;
printlist(head);
return 0;
}
What Operations Can You Perform on a Doubly Linked List?
It is possible to perform three types of operations on this kind of linked list, they are:
- Traversal
- Insertion
- Deletion
How Do You Traverse a Doubly Linked List?
In a doubly linked list traversal operation, we visit every node at least once to display all the data elements or perform operations.
You can traverse this linked list in two different directions, they are:
- Normal traversal, i.e., from head node to tail node
- Reverse traversal, i.e., from tail node to head node
Code:
/* A C++ code to traverse a linked list */
#include <bits/stdc++.h>
using namespace std;
/* A class to create a node */
class Node
{
public:
int data;
Node *next;
Node *prev;
};
//A function to insert at the
//beginning of the list
void push(Node** head, int newdata)
{
/* creating newnode */
Node* newnode = new Node();
/* put in the data */
newnode->data = newdata;
/* since we are insert at the beginning of the list,
prev is always NULL */
newnode->prev = NULL;
/* link the next of newnode to the head */
newnode->next = (*head);
/* change prev of head node to newnode */
if((*head) != NULL)
(*head)->prev = newnode ;
/* changing head */
(*head) = newnode;
}
/* A c++ program to traverse the linked list */
void traverse(Node *node)
{
while(node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
/* Function to reverse traverse a Linked List */
void revtraverse(Node **head)
{
Node* tail = *head;
// Traversing till tail of the linked list
while (tail->next != NULL) {
tail = tail->next;
}
// Traversing linked list from tail
// and printing the node->data
while (tail != *head) {
cout << tail->data << " ";
tail = tail->prev;
}
cout << tail->data << endl;;
}
int main()
{
/* Start with the empty list */
Node* head = NULL;
/* Let us create a linked list: 2->3->5->7 */
push(&head, 7);
push(&head, 5);
push(&head, 3);
push(&head, 2);
cout << "Original Linked list" << endl;
traverse(head);
/* Reverse linked list */
cout << "\nReversed Linked list" << endl;
revtraverse(&head);
return 0;
}
How Do We Insert a Node in a Doubly Linked List?
To insert a node, you need to change the previous node's next (if any) to the new node and the next node's previous (if any) to the new node. You can insert a new node in three different locations.
- At the beginning of the list
- At the end of the list
- After a given node
Code:
/* A c++ program to perform all insertion operations*/
#include <bits/stdc++.h>
using namespace std;
// A class to create nodes
class Node
{
public:
int data;
Node* next;
Node* prev;
};
/* A function to insert a node at the beginning of the list*/
void push(Node** head, int newdata)
{
/* create newnode */
Node* newnode = new Node();
/* put in the data */
newnode->data = newdata;
/* link the new node's next to head
and previous as NULL */
newnode->next = (*head);
newnode->prev = NULL;
/* link the head node's prev to new node */
if ((*head) != NULL)
(*head)->prev = newnode;
/* changing head */
(*head) = newnode;
}
/* A function to insert a node after a given node */
void insertAfter(Node* prevnode, int newdata)
{
/*1. check if the given prevnode is NULL */
if (prevnode == NULL)
{
cout<<"given previous node can't be null";
return;
}
/* 2. allocate new node */
Node* newnode = new Node();
/* 3. put in the data */
newnode->data = newdata;
/* 4. Make new node's next as prevnode's next */
newnode->next = prevnode->next;
/* 5. Make the prevnode's next as newnode */
prevnode->next = newnode;
/* 6. Make prevnode as newnode's prev */
newnode->prev = prevnode;
/* 7. Change previous of newnode's next node */
if (newnode->next != NULL)
newnode->next->prev = newnode;
}
/* A function to insert at the end of the list */
void append(Node** head, int newdata)
{
/* create newnode */
Node* newnode = new Node();
Node* last = *head;
/* put in the data */
newnode->data = newdata;
/*This newnode is going to be the last node, so
we will make next of it as NULL*/
newnode->next = NULL;
/* check if the Linked List is empty, then make the new
node as head */
if (*head == NULL)
{
newnode->prev = NULL;
*head = newnode;
return;
}
/* Else traverse till the last node */
while (last->next != NULL)
last = last->next;
/* Change the next of last node */
last->next = newnode;
/* Make last node as new node's prev */
newnode->prev = last;
return;
}
// A function to print the list
void printList(Node* node)
{
while (node != NULL)
{
cout<<" "<<node->data<<" ";
node = node->next;
}
}
int main()
{
/* Start with the empty list */
Node* head = NULL;
// Insert 6 at the last
append(&head, 6); //6->NULL
// Insert 7 at the beginning
push(&head, 7); //7->6->NULL
// Insert 1 at the beginning
push(&head, 1); //1->7->6->NULL
// Insert 4 at the end
append(&head, 4); //1->7->6->4->NULL
// Insert 8, after 7
insertAfter(head->next, 8); //1->7->8->6->4->NULL
cout << "Created DLL is: ";
printList(head);
return 0;
}
How Do You Remove a Node From a Doubly Linked List?
You need to change the previous node's next to the deleted node's next and the next node's previous to the deleted node's previous to remove a node. You can delete a node from three different positions.
- From the beginning of the list
- From the end of the list
- After a given node
Code:
// A C++code to perform all deletion operations on Linked List*/
#include <bits/stdc++.h>
using namespace std;
/* A class to create nodes */
class Node
{
public:
int data;
Node* next;
Node* prev;
};
/*A Function to delete a node in a Linked List.*/
void deleteNode(Node** head, Node* del)
{
/* base case */
if (*head == NULL || del == NULL)
return;
/* If head node is the node to be deleted */
if (*head == del)
*head = del->next;
/* Change next only if node to be
deleted is NOT the last node */
if (del->next != NULL)
del->next->prev = del->prev;
/* Change prev only if node to be
deleted is NOT the first node */
if (del->prev != NULL)
del->prev->next = del->next;
/* Finally, free the memory occupied by del*/
free(del);
return;
}
/* A function to insert a node at the beginning of the list*/
void push(Node** head, int newdata)
{
/* create newnode */
Node* newnode = new Node();
/* put in the data */
newnode->data = newdata;
/* link the new node's next to head
and previous as NULL */
newnode->next = (*head);
newnode->prev = NULL;
/* link the head node's prev to new node */
if ((*head) != NULL)
(*head)->prev = newnode;
/* changing head */
(*head) = newnode;
}
/* Function to print nodes in a given linked list
This function is the same as printList() of singly linked list */
void printList(Node* node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
int main()
{
/* Start with the empty list */
Node* head = NULL;
/* Let us create the linked list 2<->3<->5<->7 */
push(&head, 7);
push(&head, 5);
push(&head, 3);
push(&head, 2);
cout << "Original Linked list ";
printList(head);
/* delete nodes from the linked list */
deleteNode(&head, head); /*delete first node*/
deleteNode(&head, head->next); /*delete middle node*/
deleteNode(&head, head->next); /*delete last node*/
/* Modified linked list will be NULL<-5->NULL */
cout << "\nModified Linked list ";
printList(head);
return 0;
}
What Are the Benefits of a Doubly Linked List?
- It is easy to reverse this linked list.
- It is easier to delete a node from this linked list as compared to a singly linked list.
- During its execution, it can easily assign or reassign memory.
- Reverse traversal is faster in this linked list.
- You can implement complex data structures like stacks and binary trees.
What Are the Limitations of a Doubly Linked List?
- It requires more space for each node because these nodes have an extra pointer.
- Its insertion and deletion operations are slower than singly-linked lists as it requires more steps.
- Because of random storage in memory, elements need to be accessed sequentially.
Next Steps
"Circular Linked list" can be your next stop. Circular Linked lists are made up of nodes that point to the next node. It is similar to a singly linked list, except its tail node points to the head node. So while traversing, you have to be careful; otherwise, it might end up in an endless loop.
If you are perhaps looking to build a career in software development, explore Simplilearn’s Post Graduate Program in Full Stack Web Development in collaboration with Caltech CTME. This online coding bootcamp in-demand skills in today’s top full stack skills, languages and tools. You also get masterclasses from faculty at Caltech CTME, a post graduate certificate from the university and many other great benefits. It is ideal for you and is designed to give you the work-ready software development training you need to succeed today.
If you have any questions about this article, please feel free to leave them in the comment section below. Our 24/7 expert team will make sure to answer all your queries for you at the earliest.
