Doubly Linked List Tutorial

By Pritam
Jul 30th, 2012
8 Comments
805 Views

Continuing with our tutorials series on data structure, let’s discuss Doubly Linked List in this article. Earlier in this series of article we discussed Singly Linked List, it’s definition and various operations which can be performed on it along with code snippets. Let’s now dig into Doubly Linked List and understand what all operations are supported by it.

[linkad]

Doubly Linked List

Doubly Linked List

Definition:

A doubly linked list, in computer science, 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. The beginning and ending nodes’ previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list.

Noticeable differences between singly and doubly linked lists :

  • Although doubly linked lists require more space per node as compared to singly linked list, and their elementary operations are more expensive; but they are often easier to manipulate because they allow sequential access to the list in both directions.
  • In doubly linked list insertion or deletion of any node, whose address is given, can be carried out in constant number of operations and on the other hand in singly linked list the same operation would require the address of the predecessor’s address which of course is not a problem with doubly linked list as we can move in both directions.


The below figure show how a doubly linked list looks like :

Doubly Linked List

[linkad]

Let’s now directly jump over to various operations which can be performed over doubly linked list:

  • Add a node in a list at beginning or at end or in between.
  • Delete a node from list at specific location.
  • Reverse a list.
  • Count nodes present in the list.
  • Print the list to see all the nodes present in the list.

First let’s have a look at the node definition :

struct node{
    int data;
    struct node *prev;
    struct node *next;
};

It’s evident from the above node definition that a node in a doubly linked list have 2 links (next and prev) and one data value (data).

  • Add a node in a list.
    Insertion of a node in a linked list can be done at three places, viz. at start, in between at a specified location or at end.

    • Inserting a node at the start of list :
      Algorithm :

      1. Update the next pointer of the new node to the head node and make prev pointer of the new node as NULL
      2. Now update head node’s prev pointer to point to new node and make new node as head node.
    • Inserting a node in between of list :
      Algorithm :

      1. Traverse the list to the position where the new node is to be inserted.Let’s call this node as Position Node (we have to insert new node just next to it).
      2. Make the next pointer of new pointer to point to next node of position node. Also make the prev point of new node to point to position node.
      3. Now point position node’s next pointer to new node and prev node of next node of position node to point to new node.
    • Inserting a node at the end of the list :
      Algorithm :

      1. Traverse the list to end. Let’s call the current last node of list as Last node.
      2. Make next pointer of New node to point to NULL and prev pointer of new node to point to Last node.
      3. Update next pointer of Last node to point to new Node.

    Thus we see how easily we can add a node in a list. Let us now write code for all the three cases.Please note here that we are passing double pointer in the function as we may require to change the head pointer.

    void AddNode(struct node **head, int position, int value)
    {
        int currentNodePosition=1;
        struct node *temp, *newNode;
        newNode = (struct node *)malloc(sizeof(struct node));
    
        if(*head == NULL)
        {
            printf("\nList Empty.");
            position=1;
        }
    
        if(!newNode)
        {
            printf("\nError while allocating memory to new Node");
            return;
        }
    
        newNode->data = value;
        if(position==1)
        {
            printf("\nInserting node at the beginning of the list");
            newNode->next = *head;
            newNode->prev = NULL;
            //*head->prev = newNode;
            *head = newNode;
            return;
        }
    
        temp = *head;
        while((currentNodePosition<position-1)&& (temp->next!=NULL))
        {
            temp = temp->next;
            currentNodePosition++;
        }
    
        if(temp->next==NULL)
        {
            printf("\nInserting node at the last.");
            newNode->next = temp->next;
            newNode->prev = temp;
            temp->next = newNode;
        }
        else
        {
            printf("\nInserting node at position : %d",position);
            newNode->next = temp->next;
            newNode->prev = temp;
            temp->next->prev = newNode;
            temp->next = newNode;
            return;
        }
    }
    
  • Delete a node from a list.

    As similar to Insertion of a node in a linked list, deletion can also be done at three places, viz. from start, in between at a specified location or from end.

    • Deletion of node from start of list :
      Algorithm :

      1. Create a temporary node which will point to the same node where Head pointer is pointing.
      2. Now move the head pointer to point to the next node. Also change the heads prev to NULL. Then dispose off the node pointed by temporary node.
    • Deletion of node from end of list :
      Algorithm :

      1. Traverse the list till end. While traversing maintain the previous node address also. Thus when we reach at end then we have one pointer pointing to NULL and other pointing to penultimate node.
      2. Update the next pointer of penultimate node to point to NULL.
      3. Dispose off the Last Node.
    • Deletion of node from an intermediate position :
      Algorithm :

      1. As similar to previous case maintain two pointer, one pointing to the node to be deleted and other to the node previous to our target node (Node to be deleted).
      2. Once we reach our target node, change previous node next pointer to point to next pointer of target node and make prev pointer of next node of target node to point to previous node of target node.
      3. Dispose off the target node.

    I know there is a lot of confusion in the algorithm. To clear the confusion have a look at the code part below.

    void DeleteNodeFromList(struct node **head, int position)
    {
        struct node *temp, *temp2;
        temp = *head;
        int currentNodePosition = 1;
    
        if(*head == NULL)
        {
            printf("\nList is empty");
            return;
        }
    
        if(position == 1)
        {
            temp = temp->next;
            if(*head != NULL)
            {
                temp->prev = NULL;
            }
            free(temp);
            return;
        }
    
        while((currentNodePosition<position)&& (temp->next!=NULL))
        {
            printf("\nDeleting node from starting");
            temp = temp->next;
            currentNodePosition++;
        }
    
        if(temp->next == NULL)
        {
            printf("\nDeleting node from last");
            temp2 = temp->prev;
            temp2->next = NULL;
            free(temp);
            return;
        }
        else
        {
            temp2 = temp->prev;
            temp2->next = temp->next;
            temp->next->prev = temp2;
            free(temp);
            return;
        }
    }
    
  • Reversing a list.

    This is one of the favorite question which interviewer is bound to ask while interviewing a candidate on data structures. There are many ways to accomplish this but we will explain the way we implemented in our example.

    Algorithm :

    • First swap prev and next pointer of all nodes.
    • Point head to the tail node as tail node is now our new head node.

    This method is pretty straight forward and fast also. Below is the code snippet of reversing a Doubly Linked List.

    void ReverseList(struct node **head)
    {
        struct node *temp, *temp2;
        temp = *head;
        temp2 = NULL;
    
        while(temp != NULL)
        {
            temp2 = temp->next;
            temp->next = temp->prev;
            temp->prev = temp2;
    
            if(temp->prev == NULL)
            {
                *head = temp;
            }
    
            temp = temp->prev;
        }
    }
    
  • Counting nodes in list/ Printing content of list.
    This one is the easiest operation on Doubly Linked List. All what you have to do is to traverse the list and while traversing you need to keep on increment counter (while counting nodes in list)/ you need to print the data of each node (while printing the nodes). The code snippets are as below :

    void PrintList(struct node ** head)
    {
        struct node *temp;
        temp = *head;
        if(temp == NULL)
        {
            printf("List is empty");
            return;
        }
    
        while(temp->next != NULL)
        {
            printf("%d <==>",temp->data);
            temp= temp->next;
        }
    
        printf("%d",temp->data);
        return;
    }
    
    void CountNodesInList(struct node ** head)
    {
        struct node *temp;
        int numberOfNodes = 1;
        temp = *head;
        if(temp == NULL)
        {
            printf("\nList is empty");
            return;
        }
    
        while(temp->next != NULL)
        {
            temp= temp->next;
            numberOfNodes++;
        }
    
        if(numberOfNodes==1)
        {
            printf("\nThere is %d node in the list.",numberOfNodes);
        }
        else
        {
            printf("\nThere are %d node/s in the list.",numberOfNodes);
        }
        return;
    }
    

Those were the major operations which can be performed on a Doubly Linked List. Please find the complete code snippet here. Visit idlebrains for more tutorials on data structures. Visit singly linked list to refresh your memories with your very own singly linked list.

I wish you learn with as much fun as i did while writing this article. Do post your suggestions, doubts, or comments. Keep an eye on idlebrains for much more and Stay tuned with us.

About the Author

- Co-Founder of IdleBrains, is software Engineer by profession with expertise in .NET technologies and data structures. An avid reader and writer, loves to keep himself well versed with new technologies. When not working can be found on Badminton court or chatting with friends. Among other hobbies, loves to listen old hindi numbers of Kishore Kumar and Mukesh.

8 Responses to “Doubly Linked List Tutorial”

  1. Monica Sinha says:

    Can u plz tell me the program to merge two doubly linked list in c code . Plz reply

  2. I will right away seize your rss feed as I can not to find your e-mail subscription link or e-newsletter service. Do you’ve any? Kindly allow me know in order that I may just subscribe. Thanks.

  3. radhu says:

    thanku for the detailed explanation

  4. RUMA says:

    IT IS REALLY VERY USEFUL IN SHORT .

  5. Walter_Porcellini says:

    good mornign sir.
    I have seen your interesting tutorial about the double linked list.
    Functions are ok but i don’t know how to run this program ,pratically into the main i try to do something but it doesn’t works .Your link “Please find the complete code snippet here” doesn’t work , no page opening when i click on it .
    Could you please tell me what to do ?
    Thanks a lot
    Regards
    Walter

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

facebook comments:


Get Widget