# 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

- 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. - 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 the`head`

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 the`tail`

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 data`x`

and`prev`

as`NULL`

.##### Set

`temp->next`

to`head`

and`head->prev`

to`temp`

to insert`temp`

before the`head`

.##### Set

`temp`

as the head of the linked list.

### Insert Node at the End of the DLL `append()`

##### Create a new node

`temp`

with data`x`

and its`prev`

as`NULL`

.##### Initialize

`tail`

pointing towards the`head`

.##### If the linked list is empty, set

`temp`

as`head`

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 the`temp`

and`temp->prev`

as the`tail`

.

### Insert Node Before a Given Node `insertBefore()`

##### if

`next`

==`NULL`

, return;##### Create a new node

`curr`

with data`x`

.##### Set

`curr->prev`

as`next->prev`

to add a new node before`next`

and`next->prev`

as`curr`

to establish backward links.##### Set

`curr->next`

as`next`

and finally check if`curr->prev`

is`NULL`

.##### If it is not

`NULL`

, set`curr->prev->next`

as`curr`

to complete the insertion else`curr`

is the first node of the linked list. Set`head`

as`curr`

.

### Insert Node After a Given Node `insertAfter()`

##### if

`prev`

==`NULL`

, return;##### Create a new node

`curr`

with data`x`

.##### Set

`curr->next`

as`prev->next`

to add a new node after`prev`

and`prev->next`

as`curr`

to establish forward links.##### Set

`curr->prev`

as`prev`

and finally check if`curr->next`

is`NULL`

. If it is not`NULL`

,set`curr->next->prev`

as`curr`

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