A doubly linked list is a more complex type of linked list which contains a pointer to the **next** as well as the **previous** node in the sequence. This solves the issue of reverse traversal that was not possible in the singly linked list. It is also known as a **two-way** list.

**The Node Structure**

Each Node of the doubly-linked list will have 3 parts:

- The pointer to the previous Node in the list.
- The data to be stored on that Node.
- The pointer to the next node in the list.

struct Node { int data; struct Node *previous, *next; } *head = NULL;

## Operations in a Linked List

The few basic operations in a doubly linked list including adding, deleting and modifying.

### Insertion to the end of the list

New data can be added to the end of the linked list by creating a new node with the data to be used, traversing to the end of the list and then appending this data to the end.

**Steps**

- Create a new Node with the given value and set the Node’s next pointer to NULL.
- Check whether the list is Empty (
`head == NULL`

). - If it is Empty, then assign NULL to
`newNode → previous`

and`newNode`

to`head`

. - If it is not Empty, then, define a node pointer
`temp`

and initialize it with`head`

. - Keep moving the temp to its next node until it reaches the last node in the list.
- Set
`newNode`

to`temp → next`

and`temp`

to`newNode → previous`

.

void insertAtEnd(int value) { struct Node *newNode; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode -> data = value; newNode -> next = NULL; if(head == NULL) { newNode -> previous = NULL; head = newNode; } else { struct Node *temp = head; while(temp -> next != NULL) temp = temp -> next; temp -> next = newNode; newNode -> previous = temp; } printf("\nInsertion successful"); }

### Insertion to the beginning of the list

New data can be added to the beginning of the linked list by creating a new node with the data to be used, replacing the head pointer to the new node and replacing the connections.

**Steps**

- Create
`newNode`

with the given value and`newNode → previous`

as NULL. - Check whether list is Empty (
`head == NULL`

) - If it is Empty then, assign NULL to
`newNode → next`

and newNode to head. - If it is not Empty then set
`head`

to`newNode → next`

and newNode to head.

void insertAtBeginning(int value) { struct Node *newNode; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode -> data = value; newNode -> previous = NULL; if(head == NULL) { newNode -> next = NULL; head = newNode; } else { newNode -> next = head; head -> previous = newNode; head = newNode; } printf("\nInsertion successful"); }

### Insertion after an element in the list

New data can be added at any position in the list by traversing to that position using a loop, creating a new Node and then manipulating the links to insert it at that position.

**Steps**

- Create a newNode with the given value.
- Check whether the list is Empty (
`head == NULL`

) - If it is Empty then set NULL to
`newNode → previous`

,`newNode → next`

and`head = newNode`

. - Define a
`temp`

Node and set it to`head`

. - Keep moving the temp to its next node until it reaches to the node after which we want to insert the newNode (run a for-loop till position – 1)
- If temp reaches the end of the list (
`temp → next == NULL`

), Set`flag`

to 0 (signifies element is not found) and break out of the loop. - If flag is 1, set
`newNode → next = temp → next`

,`temp → next → previous = newNode`

,`temp → next = newNode`

and`newNode → previous = temp`

.

void insertAfter(int value, int pos) { int i, flag = 1; struct Node *newNode, *temp = head; newNode = (struct Node*)malloc(sizeof(struct Node)); newNode -> data = value; if(head == NULL) { newNode -> previous = newNode -> next = NULL; head = newNode; } else { for (i = 0; i < pos - 1; i++) { temp = temp -> next; if (temp -> next == NULL) { flag = 0; break; } } if (flag) { newNode -> next = temp -> next; temp -> next -> previous = newNode; temp -> next = newNode; newNode -> previous = temp; printf("\nInsertion successful\n"); } else printf("Number of elements is less than position entered"); } }

### Deletion from the end of the list

New data can be added to the end of the linked list by creating a new node with the data to be used, traversing to the end of the list and then appending this data to the end.

**Steps**

- Check whether the list is Empty (
`head == NULL`

). - If it is Empty, then throw an error and terminate the function.
- If it is not Empty then, define a Node pointer
`temp`

and initialize with`head`

. - Check whether the list has only one Node (
`temp → previous`

and`temp → next`

both are NULL) - If it is TRUE, then assign NULL to
`head`

and delete`temp`

. And terminate from the function. - If it is FALSE, then keep moving temp until it reaches the last node in the list. (until
`temp → next != NULL`

) - Set
`temp → previous → next = NULL`

and`free(temp)`

.

void deleteEnd() { if(head == NULL) printf("List is Empty"); else { struct Node *temp = head; if(temp -> previous == temp -> next) { head = NULL; free(temp); } else{ while(temp -> next != NULL) temp = temp -> next; temp -> previous -> next = NULL; free(temp); } printf("\nDeletion successful"); } }

### Deletion from the beginning of the list

New data can be added to the beginning of the linked list by creating a new node with the data to be used, replacing the head pointer to the new node and replacing the connections.

**Steps**

- Check whether the list is Empty (
`head == NULL`

) - If it is Empty then, throw an error terminate the function.
- If it is not Empty then, define a Node pointer
`temp`

and initialize with`head`

. - Check whether the list is having only one node (
`temp → previous = temp → next`

). - If it is TRUE, then set
`head = NULL`

and`free(temp)`

. - If it is FALSE, then set
`temp → next = head`

,`head → previous = NULL`

and`free(temp)`

.

void deleteBeginning() { if(head == NULL) printf("List is Empty"); else { struct Node *temp = head; if(temp -> previous == temp -> next) { head = NULL; free(temp); } else{ head = temp -> next; head -> previous = NULL; free(temp); } printf("\nDeletion successful"); } }

### Deletion at a specific position in the list

New data can be deleted at any position in the list by traversing to that position using a loop, deleting the required Node and then manipulating the links to make the list continuous.

**Steps**

- Check whether the list is Empty (
`head == NULL`

) - If it is Empty then, throw an error and terminate the function.
- If it is not Empty, then define a Node pointer
`temp`

and initialize with`head`

. - Keep moving the temp until it reaches to the exact node to be deleted or to the last node.
- If it is reached to the last node, then display ‘Given node not found in the list’ and terminate the function.
- If it is reached to the exact node which we want to delete, then check whether the list is having only one node or not
- If list has only one node and that is the node which is to be deleted then set
`head = NULL`

and`free(temp)`

. - If list contains multiple nodes, then check whether temp is the first node in the list (
`temp == head`

). - If temp is the first node, then move the head to the next node (
`head = head → next`

), set head of previous to NULL (`head → previous = NULL`

) and`free(temp)`

. - If
`temp`

is not the first node, then check whether it is the last node in the list (`temp → next == NULL`

). - If
`temp`

is the last node then set`temp → previous → next = NULL`

and`free(temp)`

. - If
`temp`

is not the first node and not the last node, then set`temp → previous → next = temp → next`

,`temp → next → previous = temp → previous`

and`free(temp)`

.

void deleteSpecific(int delValue) { if(head == NULL) printf("List is Empty"); else { struct Node *temp = head; while(temp -> data != delValue) { if(temp -> next == NULL) { printf("\nGiven node is not found in the list"); } else { temp = temp -> next; } } if(temp == head) { head = NULL; free(temp); } else { temp -> previous -> next = temp -> next; free(temp); } printf("\nDeletion successful"); } }

## Applications of Doubly Linked List

**Storing the browsing history**: The browser history system in popular web browsers which allow going forward and backwards in browsing history can be implemented using this.**Most Recently Used algorithm**: Applications that use a Most Recently Used (MRU) list.**In Games**: A list can be used to represent a deck of cards (or anything that requires an order) in a game.