A doubly linked list is a type of linked list in which each node consists of 3 components:
*prev- address of the previous nodedata- data item*next- address of next node
Note: Before you proceed further, make sure to learn about pointers and structs.
Representation of Doubly Linked List
Let's see how we can represent a doubly linked list on an algorithm/code. Suppose we have a doubly linked list:
Here, the single node is represented as
struct node {
int data;
struct node *next;
struct node *prev;
}
Each struct node has a data item, a pointer to the previous struct node, and a pointer to the next struct node.
Now we will create a simple doubly linked list with three items to understand how this works.
/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;
/* Connect nodes */
one->next = two;
one->prev = NULL;
two->next = three;
two->prev = one;
three->next = NULL;
three->prev = two;
/* Save address of first node in head */
head = one;
In the above code, one, two, and three are the nodes with data items 1, 2, and 3 respectively.
- For node one:
nextstores the address oftwoandprevstoresnull(there is no node before it) - For node two:
nextstores the address ofthreeandprevstores the address ofone - For node three:
nextstoresnull(there is no node after it) andprevstores the address oftwo.
Note: In the case of the head node, prev points to null, and in the case of the tail pointer, next points to null. Here, one is a head node and three is a tail node.
Insertion on a Doubly Linked List
Pushing a node to a doubly-linked list is similar to pushing a node to a linked list, but extra work is required to handle the pointer to the previous node.
We can insert elements at 3 different positions of a doubly-linked list:
Suppose we have a double-linked list with elements 1, 2, and 3.
1. Insertion at the Beginning
Let's add a node with value 6 at the beginning of the doubly linked list we made above.
1. Create a new node
- allocate memory for
newNode - assign the data to
newNode.
2. Set prev and next pointers of new node
- point
nextofnewNodeto the first node of the doubly linked list - point
prevtonull
3. Make new node as head node
- Point
prevof the first node tonewNode(now the previousheadis the second node) - Point
headtonewNode
Code for Insertion at the Beginning
// insert node at the front
void insertFront(struct Node** head, int data) {
// allocate memory for newNode
struct Node* newNode = new Node;
// assign data to newNode
newNode->data = data;
// point next of newNode to the first node of the doubly linked list
newNode->next = (*head);
// point prev to NULL
newNode->prev = NULL;
// point previous of the first node (now first node is the second node) to newNode
if ((*head) != NULL)
(*head)->prev = newNode;
// head points to newNode
(*head) = newNode;
}
2. Insertion in between two nodes
Let's add a node with value 6 after node with value 1 in the doubly linked list.
1. Create a new node
- allocate memory for
newNode - assign the data to
newNode.
2. Set the next pointer of new node and previous node
- assign the value of
nextfrom previous node to thenextofnewNode - assign the address of
newNodeto thenextof previous node
3. Set the prev pointer of new node and the next node
- assign the value of
prevof next node to theprevofnewNode - assign the address of
newNodeto theprevof next node
The final doubly linked list is after this insertion is:
Code for Insertion in between two Nodes
// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {
// check if previous node is NULL
if (prev_node == NULL) {
cout << "previous node cannot be NULL";
return;
}
// allocate memory for newNode
struct Node* newNode = new Node;
// assign data to newNode
newNode->data = data;
// set next of newNode to next of prev node
newNode->next = prev_node->next;
// set next of prev node to newNode
prev_node->next = newNode;
// set prev of newNode to the previous node
newNode->prev = prev_node;
// set prev of newNode's next to newNode
if (newNode->next != NULL)
newNode->next->prev = newNode;
}
3. Insertion at the End
Let's add a node with value 6 at the end of the doubly linked list.
1. Create a new node
2. Set prev and next pointers of new node and the previous node
If the linked list is empty, make the newNode as the head node. Otherwise, traverse to the end of the doubly linked list and
The final doubly linked list looks like this.
Code for Insertion at the End
// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
// allocate memory for node
struct Node* newNode = new Node;
// assign data to newNode
newNode->data = data;
// assign NULL to next of newNode
newNode->next = NULL;
// store the head node temporarily (for later use)
struct Node* temp = *head;
// if the linked list is empty, make the newNode as head node
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
// if the linked list is not empty, traverse to the end of the linked list
while (temp->next != NULL)
temp = temp->next;
// now, the last node of the linked list is temp
// point the next of the last node (temp) to newNode.
temp->next = newNode;
// assign prev of newNode to temp
newNode->prev = temp;
}
Deletion from a Doubly Linked List
Similar to insertion, we can also delete a node from 3 different positions of a doubly linked list.
Suppose we have a double-linked list with elements 1, 2, and 3.
1. Delete the First Node of Doubly Linked List
If the node to be deleted (i.e. del_node) is at the beginning
Reset value node after the del_node (i.e. node two)
Finally, free the memory of del_node. And, the linked will look like this
Code for Deletion of the First Node
if (*head == del_node)
*head = del_node->next;
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
free(del);
2. Deletion of the Inner Node
If del_node is an inner node (second node), we must have to reset the value of next and prev of the nodes before and after the del_node.
For the node before the del_node (i.e. first node)
Assign the value of next of del_node to the next of the first node.
For the node after the del_node (i.e. third node)
Assign the value of prev of del_node to the prev of the third node.
Finally, we will free the memory of del_node. And, the final doubly linked list looks like this.
Code for Deletion of the Inner Node
if (del_node->next != NULL)
del_node->next->prev = del_node->prev;
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
3. Delete the Last Node of Doubly Linked List
In this case, we are deleting the last node with value 3 of the doubly linked list.
Here, we can simply delete the del_node and make the next of node before del_node point to NULL.
The final doubly linked list looks like this.
Code for Deletion of the Last Node
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
Here, del_node ->next is NULL so del_node->prev->next = NULL.
Note: We can also solve this using the first condition (for the node before del_node) of the second case (Delete the inner node).
Doubly Linked List Code in Python, Java, C, and C++
import gc
# node creation
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
# insert node at the front
def insert_front(self, data):
# allocate memory for newNode and assign data to newNode
new_node = Node(data)
# make newNode as a head
new_node.next = self.head
# assign null to prev (prev is already none in the constructore)
# previous of head (now head is the second node) is newNode
if self.head is not None:
self.head.prev = new_node
# head points to newNode
self.head = new_node
# insert a node after a specific node
def insert_after(self, prev_node, data):
# check if previous node is null
if prev_node is None:
print("previous node cannot be null")
return
# allocate memory for newNode and assign data to newNode
new_node = Node(data)
# set next of newNode to next of prev node
new_node.next = prev_node.next
# set next of prev node to newNode
prev_node.next = new_node
# set prev of newNode to the previous node
new_node.prev = prev_node
# set prev of newNode's next to newNode
if new_node.next:
new_node.next.prev = new_node
# insert a newNode at the end of the list
def insert_end(self, data):
# allocate memory for newNode and assign data to newNode
new_node = Node(data)
# assign null to next of newNode (already done in constructor)
# if the linked list is empty, make the newNode as head node
if self.head is None:
self.head = new_node
return
# store the head node temporarily (for later use)
temp = self.head
# if the linked list is not empty, traverse to the end of the linked list
while temp.next:
temp = temp.next
# now, the last node of the linked list is temp
# assign next of the last node (temp) to newNode
temp.next = new_node
# assign prev of newNode to temp
new_node.prev = temp
return
# delete a node from the doubly linked list
def deleteNode(self, dele):
# if head or del is null, deletion is not possible
if self.head is None or dele is None:
return
# if del_node is the head node, point the head pointer to the next of del_node
if self.head == dele:
self.head = dele.next
# if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node
if dele.next is not None:
dele.next.prev = dele.prev
# if del_node is not the first node, point the next of the previous node to the next node of del_node
if dele.prev is not None:
dele.prev.next = dele.next
# free the memory of del_node
gc.collect()
# print the doubly linked list
def display_list(self, node):
while node:
print(node.data, end="->")
last = node
node = node.next
# initialize an empty node
d_linked_list = DoublyLinkedList()
d_linked_list.insert_end(5)
d_linked_list.insert_front(1)
d_linked_list.insert_front(6)
d_linked_list.insert_end(9)
# insert 11 after head
d_linked_list.insert_after(d_linked_list.head, 11)
# insert 15 after the seond node
d_linked_list.insert_after(d_linked_list.head.next, 15)
d_linked_list.display_list(d_linked_list.head)
# delete the last node
d_linked_list.deleteNode(d_linked_list.head.next.next.next.next.next)
print()
d_linked_list.display_list(d_linked_list.head)
public class DoublyLinkedList {
// node creation
Node head;
class Node {
int data;
Node prev;
Node next;
Node(int d) {
data = d;
}
}
// insert node at the front
public void insertFront(int data) {
// allocate memory for newNode and assign data to newNode
Node newNode = new Node(data);
// make newNode as a head
newNode.next = head;
// assign null to prev of newNode
newNode.prev = null;
// previous of head (now head is the second node) is newNode
if (head != null)
head.prev = newNode;
// head points to newNode
head = newNode;
}
// insert a node after a specific node
public void insertAfter(Node prev_node, int data) {
// check if previous node is null
if (prev_node == null) {
System.out.println("previous node cannot be null");
return;
}
// allocate memory for newNode and assign data to newNode
Node new_node = new Node(data);
// set next of newNode to next of prev node
new_node.next = prev_node.next;
// set next of prev node to newNode
prev_node.next = new_node;
// set prev of newNode to the previous node
new_node.prev = prev_node;
// set prev of newNode's next to newNode
if (new_node.next != null)
new_node.next.prev = new_node;
}
// insert a newNode at the end of the list
void insertEnd(int data) {
// allocate memory for newNode and assign data to newNode
Node new_node = new Node(data);
// store the head node temporarily (for later use)
Node temp = head;
// assign null to next of newNode
new_node.next = null;
// if the linked list is empty, make the newNode as head node
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
// if the linked list is not empty, traverse to the end of the linked list
while (temp.next != null)
temp = temp.next;
// assign next of the last node (temp) to newNode
temp.next = new_node;
// assign prev of newNode to temp
new_node.prev = temp;
}
// delete a node from the doubly linked list
void deleteNode(Node del_node) {
// if head or del is null, deletion is not possible
if (head == null || del_node == null) {
return;
}
// if del_node is the head node, point the head pointer to the next of del_node
if (head == del_node) {
head = del_node.next;
}
// if del_node is not at the last node, point the prev of node next to del_node
// to the previous of del_node
if (del_node.next != null) {
del_node.next.prev = del_node.prev;
}
// if del_node is not the first node, point the next of the previous node to the
// next node of del_node
if (del_node.prev != null) {
del_node.prev.next = del_node.next;
}
}
// print the doubly linked list
public void printlist(Node node) {
Node last = null;
while (node != null) {
System.out.print(node.data + "->");
last = node;
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
DoublyLinkedList doubly_ll = new DoublyLinkedList();
doubly_ll.insertEnd(5);
doubly_ll.insertFront(1);
doubly_ll.insertFront(6);
doubly_ll.insertEnd(9);
// insert 11 after head
doubly_ll.insertAfter(doubly_ll.head, 11);
// insert 15 after the seond node
doubly_ll.insertAfter(doubly_ll.head.next, 11);
doubly_ll.printlist(doubly_ll.head);
// delete the last node
doubly_ll.deleteNode(doubly_ll.head.next.next.next.next.next);
doubly_ll.printlist(doubly_ll.head);
}
}
#include <stdio.h>
#include <stdlib.h>
// node creation
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// insert node at the front
void insertFront(struct Node** head, int data) {
// allocate memory for newNode
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to newNode
newNode->data = data;
// make newNode as a head
newNode->next = (*head);
// assign null to prev
newNode->prev = NULL;
// previous of head (now head is the second node) is newNode
if ((*head) != NULL)
(*head)->prev = newNode;
// head points to newNode
(*head) = newNode;
}
// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {
// check if previous node is null
if (prev_node == NULL) {
printf("previous node cannot be null");
return;
}
// allocate memory for newNode
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to newNode
newNode->data = data;
// set next of newNode to next of prev node
newNode->next = prev_node->next;
// set next of prev node to newNode
prev_node->next = newNode;
// set prev of newNode to the previous node
newNode->prev = prev_node;
// set prev of newNode's next to newNode
if (newNode->next != NULL)
newNode->next->prev = newNode;
}
// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
// allocate memory for node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to newNode
newNode->data = data;
// assign null to next of newNode
newNode->next = NULL;
// store the head node temporarily (for later use)
struct Node* temp = *head;
// if the linked list is empty, make the newNode as head node
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
// if the linked list is not empty, traverse to the end of the linked list
while (temp->next != NULL)
temp = temp->next;
// now, the last node of the linked list is temp
// assign next of the last node (temp) to newNode
temp->next = newNode;
// assign prev of newNode to temp
newNode->prev = temp;
}
// delete a node from the doubly linked list
void deleteNode(struct Node** head, struct Node* del_node) {
// if head or del is null, deletion is not possible
if (*head == NULL || del_node == NULL)
return;
// if del_node is the head node, point the head pointer to the next of del_node
if (*head == del_node)
*head = del_node->next;
// if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node
if (del_node->next != NULL)
del_node->next->prev = del_node->prev;
// if del_node is not the first node, point the next of the previous node to the next node of del_node
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
// free the memory of del_node
free(del_node);
}
// print the doubly linked list
void displayList(struct Node* node) {
struct Node* last;
while (node != NULL) {
printf("%d->", node->data);
last = node;
node = node->next;
}
if (node == NULL)
printf("NULL\n");
}
int main() {
// initialize an empty node
struct Node* head = NULL;
insertEnd(&head, 5);
insertFront(&head, 1);
insertFront(&head, 6);
insertEnd(&head, 9);
// insert 11 after head
insertAfter(head, 11);
// insert 15 after the seond node
insertAfter(head->next, 15);
displayList(head);
// delete the last node
deleteNode(&head, head->next->next->next->next->next);
displayList(head);
}
#include <iostream>
using namespace std;
// node creation
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// insert node at the front
void insertFront(struct Node** head, int data) {
// allocate memory for newNode
struct Node* newNode = new Node;
// assign data to newNode
newNode->data = data;
// make newNode as a head
newNode->next = (*head);
// assign null to prev
newNode->prev = NULL;
// previous of head (now head is the second node) is newNode
if ((*head) != NULL)
(*head)->prev = newNode;
// head points to newNode
(*head) = newNode;
}
// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {
// check if previous node is null
if (prev_node == NULL) {
cout << "previous node cannot be null";
return;
}
// allocate memory for newNode
struct Node* newNode = new Node;
// assign data to newNode
newNode->data = data;
// set next of newNode to next of prev node
newNode->next = prev_node->next;
// set next of prev node to newNode
prev_node->next = newNode;
// set prev of newNode to the previous node
newNode->prev = prev_node;
// set prev of newNode's next to newNode
if (newNode->next != NULL)
newNode->next->prev = newNode;
}
// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
// allocate memory for node
struct Node* newNode = new Node;
// assign data to newNode
newNode->data = data;
// assign null to next of newNode
newNode->next = NULL;
// store the head node temporarily (for later use)
struct Node* temp = *head;
// if the linked list is empty, make the newNode as head node
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
// if the linked list is not empty, traverse to the end of the linked list
while (temp->next != NULL)
temp = temp->next;
// now, the last node of the linked list is temp
// assign next of the last node (temp) to newNode
temp->next = newNode;
// assign prev of newNode to temp
newNode->prev = temp;
}
// delete a node from the doubly linked list
void deleteNode(struct Node** head, struct Node* del_node) {
// if head or del is null, deletion is not possible
if (*head == NULL || del_node == NULL)
return;
// if del_node is the head node, point the head pointer to the next of del_node
if (*head == del_node)
*head = del_node->next;
// if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node
if (del_node->next != NULL)
del_node->next->prev = del_node->prev;
// if del_node is not the first node, point the next of the previous node to the next node of del_node
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
// free the memory of del_node
free(del_node);
}
// print the doubly linked list
void displayList(struct Node* node) {
struct Node* last;
while (node != NULL) {
cout << node->data << "->";
last = node;
node = node->next;
}
if (node == NULL)
cout << "NULL\n";
}
int main() {
// initialize an empty node
struct Node* head = NULL;
insertEnd(&head, 5);
insertFront(&head, 1);
insertFront(&head, 6);
insertEnd(&head, 9);
// insert 11 after head
insertAfter(head, 11);
// insert 15 after the seond node
insertAfter(head->next, 15);
displayList(head);
// delete the last node
deleteNode(&head, head->next->next->next->next->next);
displayList(head);
}
Doubly Linked List Complexity
| Doubly Linked List Complexity | Time Complexity | Space Complexity |
| Insertion Operation | O(1) or O(n) | O(1) |
| Deletion Operation | O(1) | O(1) |
1. Complexity of Insertion Operation
- The insertion operations that do not require traversal have the time complexity of
O(1). - And, insertion that requires traversal has time complexity of
O(n). - The space complexity is
O(1).
2. Complexity of Deletion Operation
- All deletion operations run with time complexity of
O(1). - And, the space complexity is
O(1).
Doubly Linked List Applications
- Redo and undo functionality in software.
- Forward and backward navigation in browsers.
- For navigation systems where forward and backward navigation is required.
Singly Linked List Vs Doubly Linked List
| Singly Linked List | Doubly Linked List |
| Each node consists of a data value and a pointer to the next node. | Each node consists of a data value, a pointer to the next node, and a pointer to the previous node. |
| Traversal can occur in one way only (forward direction). | Traversal can occur in both ways. |
| It requires less space. | It requires more space because of an extra pointer. |
| It can be implemented on the stack. | It has multiple usages. It can be implemented on the stack, heap, and binary tree. |