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.

In this "Doubly linked list" tutorial, you will look into the following topics:

- How do you implement a Doubly linked list?
- What operations can you perform on a Doubly linked list?
- How do you traverse a doubly linked list?
- How do you insert a node in a Doubly linked list?
- How do you remove a node from a Doubly linked list?
- What are the benefits of a Doubly linked list?
- What are the limitations of a Doubly linked list?

## 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?

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.

Advance your career as a MEAN stack developer with theÂ Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

## 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.