# Doubly Linked List – Explanation and Implementation

A doubly linked list is an advanced form of linked list which has the ability to traverse back and forth i.e. in both the direction. It possesses an extra pointer Prev in addition to the fields of a node in singly linked list. Conventionally, in a singly and circular linked list, Data and Next are two parts of a node. But, doubly linked list defines three Data, Next and Prev and the meaning of each section is as follows-

• Prev – Points to previous node
• Data – Containing data
• Next – Pointing next node

This Prev part makes this linked list has a huge implementation in many places.

#### Structure and Declaration

```struct node {
int data;
struct node *next;
struct node *prev;
}
```

#### Implementation in C language

```#include<stdio.h>
#include<stdlib.h>

//DECLARATION
struct node
{
int data;
struct node *next;
struct node *prev;
};

//This function prints the content of linked list--forward direction
void printLLForward(struct node *list)
{
while (list)
{
printf(" %d ", list->data);
list = list->next; // accessing and assigning the next node of list
}
}

// This function prints the linked list--backward direction
void printLLBackward(struct node *list)
{

while (list->next != NULL)
{
list = list->next;
}

while (list)
{
printf(" %d ", list->data);
list = list->prev; // accessing and assigning the prev node of list
}
}

// Main method to initialize the program
int main()
{
//INITIALIZATION
//Declare and allocate 3 nodes in the heap
struct node* first = (struct node*)malloc(sizeof(struct node));
struct node* second = (struct node*)malloc(sizeof(struct node));
struct node* third = (struct node*)malloc(sizeof(struct node));

//ASSIGNINMENT
first->data = 10; //assign data in first node
first->next = second; // Link first node with second
first->prev = NULL;

second->data = 20; //assign data to second node
second->next = third;
second->prev = first;

third->data = 30; //assign data to third node
third->next = NULL; // last node pointing to the first node
third->prev = second;

printf("Printing the linked list in forward direction :\t");
printf("\nPrinting the linked list in backward direction:\t");

return 0;
}

```
```Output:-
Printing the linked list in forward direction :	 10  20  30
Printing the linked list in backward direction:	 30  20  10```

Note:-
Many a times Circular doubly linked list is used where Next of last node rather points to Prev of the first node. As a result, no need to traverse back if required to traverse again.

1. Insertion/Deletion takes O(1) most of the time.
2. Linked list reversal is easy.
3. Better access of nodes as back and forth traversing can be done anytime.