# What is Doubly Linked List?

A doubly linked list is the collection of nodes in which every node has three fields previous pointer, data field and next pointer. or A doubly linked list is one in which all nodes are linked together by multiple links which help in accessing both the successor node (next node) and predecessor node (previous node) from any arbitrary node within the list.

`*prev`

– address of the previous node`data`

– data item`*next`

– address of next node

If you want to read about Linked list you should check this article: Linked List and Basic Linked List

### Difference between doubly linked list and singly linked list:

Singly Linked List (SLL) | Doubly Linked List (DLL) |

1. Each node consists of a data value and a pointer to the next node. | 1. Each node consists of a data value, a pointer to the next node, and a pointer to the previous node. |

2. Traversal can occur in one way only (forward direction). | 2. Traversal can occur in both ways. |

3. It requires less space. | 3. It requires more space because of an extra pointer. |

4. It can be implemented on the stack. | 4. It has multiple usages. It can be implemented on the stack, heap, and binary tree. |

### Representation of Doubly Linked List

**A node of doubly linked list is represented as:**

```
struct node {
int data; //actual data
struct node *next; //pointer for next node
struct node *prev; //pointer for previous node
}
```

Each struct node has a data item, a pointer to the previous struct node, and a pointer to the next struct node.

**A three-member doubly linked list can be created as**:

```
/* Initialize nodes */
struct node *head;
struct node *one = NULL;//first node
struct node *two = NULL; //second node
struct node *three = NULL; //third node
/* Allocate memory for three node */
one =(struct Node*) malloc(sizeof(struct node));
two =(struct Node*) malloc(sizeof(struct node));
three =(struct Node*) malloc(sizeof(struct node));
/* Assign data values */
one->data = 1; //assign data in first node
two->data = 2; //assign data in second node
three->data = 3; // assign data in third node
/* Connect nodes */
one->next = two; // Link first node and second node ( next node )
one->prev = NULL; //assign null to previous of first node
two->next = three;// Link second node and third node ( next node )
two->prev = one ;// Link second and first node ( previous node )
three->next = NULL;//assign NULL to next of last node
three->prev = two;// Link third and second node ( previous node )
/* Save address of first node in head */
head = one;
```

In the above code, `one`

, `two`

, and `three`

are the nodes with data items **1**, **2**, and **3** respectively.

**For node one**:`next`

stores the address of`two`

and`prev`

stores`null`

(there is no node before it)**For node two**:`next`

stores the address of`three`

and`prev`

stores the address of`one`

**For node three**:`next`

stores`null`

(there is no node after it) and`prev`

stores the address of`two`

.

### C program for Doubly linked list

```
#include <stdio.h>
#include <stdlib.h>
// node creation
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// insert node at the front
void insertFront(struct Node** head, int data) {
// allocate memory for newNode
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to newNode
newNode->data = data;
// make newNode as a head
newNode->next = (*head);
// assign null to prev
newNode->prev = NULL;
// previous of head (now head is the second node) is newNode
if ((*head) != NULL)
(*head)->prev = newNode;
// head points to newNode
(*head) = newNode;
}
// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {
// check if previous node is null
if (prev_node == NULL) {
printf("previous node cannot be null");
return;
}
// allocate memory for newNode
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to newNode
newNode->data = data;
// set next of newNode to next of prev node
newNode->next = prev_node->next;
// set next of prev node to newNode
prev_node->next = newNode;
// set prev of newNode to the previous node
newNode->prev = prev_node;
// set prev of newNode's next to newNode
if (newNode->next != NULL)
newNode->next->prev = newNode;
}
// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
// allocate memory for node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to newNode
newNode->data = data;
// assign null to next of newNode
newNode->next = NULL;
// store the head node temporarily (for later use)
struct Node* temp = *head;
// if the linked list is empty, make the newNode as head node
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
// if the linked list is not empty, traverse to the end of the linked list
while (temp->next != NULL)
temp = temp->next;
// now, the last node of the linked list is temp
// assign next of the last node (temp) to newNode
temp->next = newNode;
// assign prev of newNode to temp
newNode->prev = temp;
}
// delete a node from the doubly linked list
void deleteNode(struct Node** head, struct Node* del_node) {
// if head or del is null, deletion is not possible
if (*head == NULL || del_node == NULL)
return;
// if del_node is the head node, point the head pointer to the next of del_node
if (*head == del_node)
*head = del_node->next;
// if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node
if (del_node->next != NULL)
del_node->next->prev = del_node->prev;
// if del_node is not the first node, point the next of the previous node to the next node of del_node
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
// free the memory of del_node
free(del_node);
}
// print the doubly linked list
void displayList(struct Node* node) {
struct Node* last;
while (node != NULL) {
printf("%d->", node->data);
last = node;
node = node->next;
}
if (node == NULL)
printf("NULL\n");
}
int main() {
// initialize an empty node
struct Node* head = NULL;
insertEnd(&head, 5);
insertFront(&head, 1);
insertFront(&head, 6);
insertEnd(&head, 9);
// insert 11 after head
insertAfter(head, 11);
// insert 15 after the seond node
insertAfter(head->next, 15);
displayList(head);
// delete the last node
deleteNode(&head, head->next->next->next->next->next);
displayList(head);
}
```

**Output:**

### Application of Doubly Linked list

- Redo and undo functionality in software.
- Forward and backward navigation in browsers.
- For navigation systems where forward and backward navigation is required.

learning everything from everywhere!!