Implementation of Doubly Linked List in C

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called Nodes. Each Node contains two fields, called Links, that are references to the Previous and to the Next Node in the sequence of Nodes as well as field named Data.
For every Linked List we have something called Head which marks the starting of a list. So we have two main structures namely

• Node
• Head

Why we need a new structure for HEAD variable ? 
Just for convenience I decided to have HEAD its own structure. You can even use the Node structure.

Node
Every Node in a Doubly Linked List has three main members namely

• PREV
• DATA
• NEXT

As their names say

• PREV - holds the memory location of the Previous Node in the List. If there are none we point towards NULL. For the First Node in the List PREV points to NULL.
• NEXT - holds the memory location of the Next Node in the List. If there are none we point towards NULL. For the Last Node in the List NEXT points to NULL.
• DATA - In simple words it holds Data. In our case it holds the memory location to the actual data to be held by the Node.

typedef struct node
{
    struct node *prev;
    void        *data;
    struct node *next;
}NODE;

Head

Head acts as the  "head" of the List. Head structure has two members namely

• LENGTH - holds the count of number of Nodes in the List.
• FIRST - hold the memory location of the first Node in the List. If the List is EMPTY it points to NULL.

typedef struct head 
{
    unsigned int length;
    struct node  *first;
}HEAD;

NOTE: Our Head structure doesn't contain any pointer to the Tail of the List. Eventhough its a best way to include a pointer to Tail Node we decided to cover that implementation in Circular Doubly Linked List.

Figure 1: Basic structures used for Doubly Linked List Example

Pictorially, a Doubly Linked List can be depicted as shown Figure-2.

Figure 2: Doubly Linked List

In this introductory article let use see very basic operations which we don't discuss much in later articles.

Creating a Node

Whenever we have to add a new Node we have to create one dynamically.So we will have a function called createNode which creates a new Node and returns the pointer to it.

NODE* createNode()
{
    NODE *newNode = (NODE *)calloc(sizeof(NODE));

    return newNode;
}

Creating a Head

Since I have decided to have my own head structure I need to create a HEAD variable for every Doubly Linked List. So we have a to create HEAD variable which acts as the index to which we have add or delete a Node.

HEAD* createHead()
{
    HEAD *head = (HEAD *)calloc(sizeof(HEAD));

    return head;
}

Traversing a Doubly Linked List

Doubly Linked List are more convenient than Singly Linked List since we maintain links for bi-directional traversing. If we are given a pointer to a Node which is at a arbitrary position we can traverse in both directions and display the contents in the whole List.

But in a Singly Linked List we can only traverse in one direction from Head to Tail where as in Doubly Linked List we can traverse from Head to Tail as well as Tail to Head.

As usual the logic would be a simple while loop and traversing using the NEXT and PREV pointers in the Node to traverse to the desired location in the List.

Part-1 : Creating a Node in Doubly Linked List
Part-2 : Deleting a Node in Doubly Linked List