﻿ Doubly Linked List - Data Structures Handbook

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:

1. The pointer to the previous Node in the list.
2. The data to be stored on that Node.
3. The pointer to the next node in the list.
```struct Node
{
int data;
struct Node *previous, *next;

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

1. Create a new Node with the given value and set the Node’s next pointer to NULL.
2. Check whether the list is Empty (`head == NULL`).
3. If it is Empty, then assign NULL to `newNode → previous` and `newNode` to `head`.
4. If it is not Empty, then, define a node pointer `temp` and initialize it with `head`.
5. Keep moving the temp to its next node until it reaches the last node in the list.
6. 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;
{
newNode -> previous = NULL;
}
else
{
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

1. Create `newNode` with the given value and `newNode → previous` as NULL.
2. Check whether list is Empty (`head == NULL`)
3. If it is Empty then, assign NULL to `newNode → next` and newNode to head.
4. 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;
{
newNode -> next = NULL;
}
else
{
}
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

1. Create a newNode with the given value.
2. Check whether the list is Empty (`head == NULL`)
3. If it is Empty then set NULL to `newNode → previous` , `newNode → next` and `head = newNode`.
4. Define a `temp` Node and set it to `head`.
5. 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)
6. 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.
7. 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;
{
newNode -> previous = newNode -> next = NULL;
}
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

1. Check whether the list is Empty (`head == NULL`).
2. If it is Empty, then throw an error and terminate the function.
3. If it is not Empty then, define a Node pointer `temp` and initialize with `head`.
4. Check whether the list has only one Node (`temp → previous` and `temp → next` both are NULL)
5. If it is TRUE, then assign NULL to `head` and delete `temp`. And terminate from the function.
6. If it is FALSE, then keep moving temp until it reaches the last node in the list. (until `temp → next != NULL`)
7. Set `temp → previous → next = NULL` and `free(temp)`.
```void deleteEnd()
{
printf("List is Empty");
else
{
if(temp -> previous == temp -> next)
{
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

1. Check whether the list is Empty (`head == NULL` )
2. If it is Empty then, throw an error terminate the function.
3. If it is not Empty then, define a Node pointer `temp` and initialize with `head`.
4. Check whether the list is having only one node (`temp → previous = temp → next`).
5. If it is TRUE, then set `head = NULL` and `free(temp)`.
6. If it is FALSE, then set `temp → next = head` , `head → previous = NULL` and `free(temp)`.
```void deleteBeginning()
{
printf("List is Empty");
else
{
if(temp -> previous == temp -> next)
{
free(temp);
}
else{
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

1. Check whether the list is Empty (`head == NULL`)
2. If it is Empty then, throw an error and terminate the function.
3. If it is not Empty, then define a Node pointer `temp` and initialize with `head`.
4. Keep moving the temp until it reaches to the exact node to be deleted or to the last node.
5. If it is reached to the last node, then display ‘Given node not found in the list’ and terminate the function.
6. 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
7. If list has only one node and that is the node which is to be deleted then set `head = NULL` and `free(temp)`.
8. If list contains multiple nodes, then check whether temp is the first node in the list (`temp == head`).
9. 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)`.
10. If `temp` is not the first node, then check whether it is the last node in the list ( `temp → next == NULL`).
11. If `temp` is the last node then set `temp → previous → next = NULL` and `free(temp)`.
12. 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)
{
printf("List is Empty");
else
{
while(temp -> data != delValue)
{
if(temp -> next == NULL)
{
}
else
{
temp = temp -> next;
}
}
{
free(temp);
}
else
{
temp -> previous -> next = temp -> next;
free(temp);
}
printf("\nDeletion successful");
}
}```

## Applications of Doubly Linked List

1. 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.
2. Most Recently Used algorithm: Applications that use a Most Recently Used (MRU) list.
3. In Games: A list can be used to represent a deck of cards (or anything that requires an order) in a game.
Scroll to top

By using this website you agree to accept our Privacy Policy and Terms and Conditions