What are Doubly Linked Lists?


After reading this article you should be able to answer the following questions.

  • What are doubly linked lists?
  • How doubly linked lists are implemented?
  • What are the applications for doubly linked lists?
  • How doubly linked lists are different than singly-linked lists?

Introduction

The following are problems with singly linked lists:

  1. A singly linked list allows traversal of the list in only one direction.
  2. Deleting a node from a list requires keeping track of the previous node, that is, the node whose link points to the node to be deleted.
  3. If the link in any node gets corrupted, the remaining nodes of the list become unusable.

These problems of singly linked lists can be overcome by adding one more link to each node, which points to the previous node. When such a link is added to every node of a list, the corresponding linked list is called a doubly linked list. Therefore, a doubly linked list is a linked list in which every node contains two links, called left link and right link, respectively.

The left link of the node points to the previous node, whereas the right points to the next node. Like a singly linked list, a doubly linked list can also be a chain or it may be circular with or without a header node. If it is a chain, the left link of the first node and the right link of the last node will be NULL, as shown in Figure 1.

Figure 1 : Doubly Linked List as a chain

If it is a circular list without a header node, the right link of the last node points to the first node. The left link of the first node points to the last node, as shown in Figure 2

Figure 2 : Doubly Linked List maintained as circular list

If it is a circular list with a header node, the left link of the first node and the right link of the last node point to the header node. The right link of the header node points to the first node and the left link of the header node points to the last node of the list, as shown in Figure 3.

Figure 3 : A doubly linked list maintained as a circular list with a header node.

Therefore, the following representation is required to be used for the nodes of a doubly linked list.


struct dnode  {
      int data;
      struct dnode *left,*right;
   };

Inserting into a doubly linked list is done as :

struct dnode *insert(struct dnode *p, struct dnode **q, int n)
{
        struct dnode *temp;
        /* if the existing list is empty then insert a new node as the
           starting node */
        if(p==NULL)
        {
                p=(struct dnode *)malloc(sizeof(struct dnode)); /* creates new
                                                                   node data value
                                                                   passed as parameter */

                if(p==NULL)
                {
                        printf("Error\n");
                        exit(0);
                }
                p->data = n;
                p-> left = p->right =NULL;
                *q =p;
        }
        else
        {
                temp = (struct dnode *)malloc(sizeof(struct dnode)); /* creates
                                                                        new node using
                                                                        data value passed as
                                                                        parameter and puts its
                                                                        address in the temp
                                                                      */
                if(temp == NULL)
                {
                        printf("Error\n");
                        exit(0);
                }
                temp->data = n;
                temp->left = (*q);
                temp->right = NULL;
                (*q)->right = temp;
                (*q) = temp;
        }
        return (p);
}

Advertisements
  1. How to implement a linked list? « Encrypt3d
  2. Deleting a node from doubly linked list « Encrypt3d

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: