Harshit Jindal Oct 12, 2023

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.

1. Double-linked 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.
2. 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.

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

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

There are `4` cases for the doubly linked list for inserting elements just like linked lists.

## 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->prev = NULL;
}
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
}

void append(Node** head, int x) {
Node* curr = new Node();
curr->data = x;
curr->next = NULL;
curr->prev = NULL;
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() {
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 average-case time complexity of traversal is of the order of `O(n)`. The time complexity is of the order of `O(n)`.

• Best Case

The best-case time complexity is `O(n)`. It is the same as average-case time complexity.

• Worst Case

The worst-case time complexity is `O(n)`. It is the same as best-case 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 best-case time complexity is `O(1)`. It is the same as average-case time complexity.

• Worst Case

The worst-case time complexity is `O(1)`. It is the same as best-case 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.