# C - Doubly Linked List

A doubly linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains three sub-elements. A data part that stores the value of the element, the previous part that stores the pointer to the previous node, and the next part that stores the pointer to the next node as shown in the below image:

The first node also known as HEAD is always used as a reference to traverse the list. The previous of head node and next of last node points to NULL. A doubly linked list can be visualized as a chain of nodes, where every node points to previous and next node.

## Implementation of Doubly Linked List

### Representation:

In C, a node can be created using structure as shown below:

//node structure struct Node { int data; struct Node* next; struct Node* prev; };

### Create a Doubly Linked List

Let us create a simple doubly linked list which contains three data nodes.

#include <stdio.h> #include <stdlib.h> //node structure struct Node { int data; struct Node* next; struct Node* prev; }; // test the code int main() { //create the head node with name MyList struct Node* MyList = NULL; //Add first node. struct Node* first; //allocate second node in the heap first = (struct Node*)malloc(sizeof(struct Node)); first->data = 10; first->next = NULL; first->prev = NULL; //linking with head node MyList = first; //Add second node. struct Node* second; //allocate second node in the heap second = (struct Node*)malloc(sizeof(struct Node)); second->data = 20; second->next = NULL; //linking with first node second->prev = first; first->next = second; //Add third node. struct Node* third; //allocate third node in the heap third = (struct Node*)malloc(sizeof(struct Node)); third->data = 30; third->next = NULL; //linking with second node third->prev = second; second->next = third; return 0; }

### Traverse a Doubly Linked List

A doubly linked list can be traversed using a temp node. Keep on moving the temp node to the next one and displaying its content. At the end of the list, the temp node will become NULL.

#include <stdio.h> #include <stdlib.h> //node structure struct Node { int data; struct Node* next; struct Node* prev; }; //display the content of the list void PrintList(struct Node* head_ref) { struct Node* temp = head_ref; if(head_ref != NULL) { printf("\nThe list contains: "); while (temp->next != NULL) { printf("%i ",temp->data); temp = temp->next; } printf("%i ",temp->data); } else { printf("\nThe list is empty."); } } // test the code int main() { //create the head node with name MyList struct Node* MyList = NULL; //Add first node. struct Node* first; //allocate second node in the heap first = (struct Node*)malloc(sizeof(struct Node)); first->data = 10; first->next = NULL; first->prev = NULL; //linking with head node MyList = first; //Add second node. struct Node* second; //allocate second node in the heap second = (struct Node*)malloc(sizeof(struct Node)); second->data = 20; second->next = NULL; //linking with first node second->prev = first; first->next = second; //Add third node. struct Node* third; //allocate third node in the heap third = (struct Node*)malloc(sizeof(struct Node)); third->data = 30; third->next = NULL; //linking with second node third->prev = second; second->next = third; //print the content of list PrintList(MyList); return 0; }

The above code will give the following output:

The list contains: 10 20 30