### Tutorial Playlist

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

{

//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;

/* change prev of head node to newnode */

}

/* A c++ program to print the list */

{

{

cout << head->data << " ";

}

}

int main()

{

/*lets create a linked list: 2->3->5->7 */

cout << "Created Doubly Linked list:" << endl;

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

#### Full Stack Web Developer Course

To become an expert in MEAN Stack

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

{

/* 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;

/* change prev of head node to 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 */

{

Â Â Â Â // 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()

{

/* Let us create a linked list: 2->3->5->7 */

cout << "Original Linked list" << endl;

cout << "\nReversed Linked list" << endl;

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*/

{

/* create newnode */

Node* newnode = new Node();

/* put in the data */

newnode->data = newdata;

and previous as NULL */

newnode->prev = NULL;

}

/* 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 */

{

/* create newnode */

Node* newnode = new Node();

/* 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

{

newnode->prev = NULL;

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()

{

// Insert 6 at the last

// Insert 7 at the beginning

// Insert 1 at the beginning

// Insert 4 at the end

// Insert 8, after 7

cout << "Created DLL is: ";

return 0;

}

#### Stand Out From Your Peers this Appraisal Season

Start Learning With Our FREE Courses

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

{

/* base case */

if (*head == NULL || del == NULL)

return;

/* If head node is the node to be deleted */

/* 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*/

{

/* create newnode */

Node* newnode = new Node();

/* put in the data */

newnode->data = newdata;

and previous as NULL */

newnode->prev = NULL;

}

/* 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()

{

/* Let us create the linked list 2<->3<->5<->7 */

cout << "Original Linked list ";

/* delete nodes from the linked list */

/* Modified linked list will be NULL<-5->NULL */

cout << "\nModified Linked list ";

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