Doubly Linked List
 Double Linked List vs Linked List
 Doubly Linked List Traversal Algorithm
 Doubly Linked List Insertion
 Doubly Linked List Insertion Illustration
 Doubly Linked List Traversal & Insertion Implementation
 Doubly Linked List Traversal & Insertion Algorithm Complexity
A Doubly Linked List is a linear data structure. It is a collection of objects defined as nodes. But unlike the linked list, the node has two pointers, one previous pointer and the other next pointer. Just like linked list nodes are stored in random positions in memory and not stored in contiguous locations.
Double Linked List vs Linked List
 Doublelinked lists allow us to traverse the linked list in both forward and backward directions, but it comes at the cost of extra space required by the
prev
pointer for every node.  It is very easy to insert elements inside a doubly linked list as we do not have to maintain multiple pointers or traverse linked lists to find the previous pointer, but we do have to modify more pointers as compared to the linked list.
Doubly Linked List Traversal Algorithm
Forward Direction
Let the head
be the first node of the linked list.

Initialize
curr
pointing to thehead
node of the linked list. 
While
curr
does not reach the end of the list i.e.curr
!=NULL
, do the following: print the data stored inside the current node.
curr=curr>next
; If the last node, store as the
tail
to facilitate backward traversal.
Similarly, we can do the backward traversal by starting from the tail
and changing curr
to curr>prev
.
Reverse Direction
Let the tail
be the last node of the linked list.

Initialize
curr
pointing to thetail
node of the linked list. 
While
curr
does not reach the start of the list i.e.curr
!=NULL
, do the following: print the data stored inside the current node.
curr=curr>prev
Doubly Linked List Insertion
There are 4
cases for the doubly linked list for inserting elements just like linked lists.
Insert Node at the Head of the DLL push()

Create a new node
temp
with datax
andprev
asNULL
. 
Set
temp>next
tohead
andhead>prev
totemp
to inserttemp
before thehead
. 
Set
temp
as the head of the linked list.
Insert Node at the End of the DLL append()

Create a new node
temp
with datax
and itsprev
asNULL
. 
Initialize
tail
pointing towards thehead
. 
If the linked list is empty, set
temp
ashead
of the linked list and return. 
Else iterate towards the end of the linked list, such that
tail>next
!=NULL
, so that you land at the last element 
Set
tail>next
as thetemp
andtemp>prev
as thetail
.
Insert Node Before a Given Node insertBefore()

if
next
==NULL
, return; 
Create a new node
curr
with datax
. 
Set
curr>prev
asnext>prev
to add a new node beforenext
andnext>prev
ascurr
to establish backward links. 
Set
curr>next
asnext
and finally check ifcurr>prev
isNULL
. 
If it is not
NULL
, setcurr>prev>next
ascurr
to complete the insertion elsecurr
is the first node of the linked list. Sethead
ascurr
.
Insert Node After a Given Node insertAfter()

if
prev
==NULL
, return; 
Create a new node
curr
with datax
. 
Set
curr>next
asprev>next
to add a new node afterprev
andprev>next
ascurr
to establish forward links. 
Set
curr>prev
asprev
and finally check ifcurr>next
isNULL
. If it is notNULL
,setcurr>next>prev
ascurr
to complete the insertion.
Doubly Linked List Insertion Illustration
Insert Node at the Head of the DLL push()
Insert Node at the End of the DLL append()
Insert Node Before a Given Node insertBefore()
Insert Node After a Given Node insertAfter()
Doubly Linked List Traversal & Insertion Implementation
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node* prev;
};
void push(Node** head, int x) {
Node* curr = new Node();
curr>data = x;
curr>next = (*head);
curr>prev = NULL;
if ((*head) != NULL) (*head)>prev = curr;
(*head) = curr;
}
void insertAfter(Node* prev, int x) {
if (prev == NULL) {
cout << "the given previous node cannot be NULL";
return;
}
Node* curr = new Node();
curr>data = x;
curr>next = prev>next;
prev>next = curr;
curr>prev = prev;
if (curr>next != NULL) curr>next>prev = curr;
}
void insertBefore(struct Node** head, struct Node* next, int x) {
if (next == NULL) {
return;
}
Node* curr = new Node();
curr>data = x;
curr>prev = next>prev;
next>prev = curr;
curr>next = next;
if (curr>prev != NULL)
curr>prev>next = curr;
else
(*head) = curr;
}
void append(Node** head, int x) {
Node* curr = new Node();
Node* tail = *head;
curr>data = x;
curr>next = NULL;
if (*head == NULL) {
curr>prev = NULL;
*head = curr;
return;
}
while (tail>next != NULL) tail = tail>next;
tail>next = curr;
curr>prev = tail;
return;
}
void printList(Node* node) {
Node* tail = NULL;
cout << "Forward Traversal:";
while (node != NULL) {
cout << " " << node>data << " ";
tail = node;
node = node>next;
}
cout << "\nReverse Traversal:";
while (tail != NULL) {
cout << " " << tail>data << " ";
tail = tail>prev;
}
cout << "\n";
}
int main() {
Node* head = NULL;
append(&head, 6);
push(&head, 7);
push(&head, 1);
append(&head, 4);
printList(head);
insertAfter(head>next, 8);
insertBefore(&head, head>next>next, 3);
printList(head);
return 0;
}
Doubly Linked List Traversal & Insertion Algorithm Complexity
Traversal
Time Complexity
 Average Case
To traverse the complete doubly linked list, we have to visit every node. So, if it has n
nodes the averagecase time complexity of traversal is of the order of O(n)
. The time complexity is of the order of O(n)
.
 Best Case
The bestcase time complexity is O(n)
. It is the same as averagecase time complexity.
 Worst Case
The worstcase time complexity is O(n)
. It is the same as bestcase time complexity.
Space Complexity
The traversal algorithm’s space complexity is O(1)
as no extra space other than curr
pointer is required.
Insertion
Time Complexity
 Average Case
The insertion of an element for all 4
cases requires a maximum of 4
link changes, and hence the time complexity of insertion is O(1)
.
 Best Case
The bestcase time complexity is O(1)
. It is the same as averagecase time complexity.
 Worst Case
The worstcase time complexity is O(1)
. It is the same as bestcase time complexity.
Space Complexity
The insertion algorithm’s space complexity is O(1)
for all 4
types of insertion.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn