Doubly Linked List

Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node (previous pointer). A sample node in a doubly linked list is shown in the figure.

A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is shown in the following image.

In C, structure of a node in doubly linked list can be given as :

1. struct node   
2. {  
3.     struct node *prev;   
4.     int data;  
5.     struct node *next;   
6. }