/* Ajith - Syntax Higlighter - End ----------------------------------------------- */

2.24.2012

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

8 comments :

  1. Quite nice idea to store the count of number of nodes in the list. My teacher told me that the head has no data but only link to the next node. Thanks for this great idea.

    ReplyDelete
  2. There are many ways to implement it .. For example check the article on Circular Doubly Linked List (which I am gonna write soon) will even help to make things much easier using a doubly linked list

    ReplyDelete
  3. In create_head
    //NODE *head = (HEAD *)malloc(sizeof(HEAD));

    Why Head is a pointer to Node ?

    why can't it be like this ?
    HEAD *head = (HEAD *)malloc(sizeof(HEAD));

    ReplyDelete
  4. Thanks for finding out the error .. I have updated the same

    ReplyDelete
  5. //if(newNode)
    memset(newNode, 0, sizeof(newNode));

    can u please explain what this condition means?..thanks in advance

    ReplyDelete
    Replies
    1. Since we are using malloc function we are just making sure that memory allocated have NULL value inside it so we are doing memset

      Delete
    2. I have updated the code with calloc operation so that we dont need to do memset operation.

      Delete

Your comments are moderated