C Programming language

In the various types of linked list like singly list and circular lists only forward traversing is possible but in the real world application it is necessary to traverse the list both in the forward direction and the backward direction. The most appropriate data structure for such an application is a doubly linked list.

A doubly linked list is a list in which all the nodes are connected to each other by the means of multiple links which helps in accessing both the predecessor and the successor node from the given node position. It provideds bi-directional traversing.

Each node in the doubly linked list has two link fields. These are used to point the next node in the list and the previous node in the list. The following figure show how can we represent graphically as:

Here, the next pointer will point to its successor node, while the prev pointer will point to its predecessor node. The structure declaration for the above node will be as :

#include <stdio.h>
struct node
{
int num;
struct node *next;
struct node *prev;
};
typedef struct node NODE;

Now we know how to declare a doubly linked list node, now we will see how to perform various insertion and deletion operations on the doubly linked list.

• Insertion and deletion are easier to perform as compare to other types of lists like singly linked lists and circular lists.
• Efficient utilization of the memory.
• Bi-directional traversal helps in efficient and easy accessibility of nodes.

There are various insertion operations that are performed on a doubly linked list which are as follows :

• Insertion at the front of the list.
• Insertion from the end of the list.
• Insertion at any specified position in the list.