Doubly Linked List - Data Structures Handbook

A doubly linked list is a more complex type of linked list which contains a pointer to the next as well as the previous node in the sequence. This solves the issue of reverse traversal that was not possible in the singly linked list. It is also known as a two-way list.

The Node Structure

Each Node of the doubly-linked list will have 3 parts:

The pointer to the previous Node in the list.
The data to be stored on that Node.
The pointer to the next node in the list.

struct Node
{
   int data;
   struct Node *previous, *next;
} *head = NULL;

Operations in a Linked List

The few basic operations in a doubly linked list including adding, deleting and modifying.

Insertion to the end of the list

New data can be added to the end of the linked list by creating a new node with the data to be used, traversing to the end of the list and then appending this data to the end.

Steps

Create a new Node with the given value and set the Node’s next pointer to NULL.
Check whether the list is Empty (head == NULL).
If it is Empty, then assign NULL to newNode → previous and newNode to head.
If it is not Empty, then, define a node pointer temp and initialize it with head.
Keep moving the temp to its next node until it reaches the last node in the list.
Set newNode to temp → next and temp to newNode → previous.

void insertAtEnd(int value)
{
   struct Node *newNode;
   newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode -> data = value;
   newNode -> next = NULL;
   if(head == NULL)
   {
      newNode -> previous = NULL;
      head = newNode;
   }
   else
   {
      struct Node *temp = head;
      while(temp -> next != NULL)
         temp = temp -> next;
      temp -> next = newNode;
      newNode -> previous = temp;
   }
   printf("\nInsertion successful");
}

Insertion to the beginning of the list

New data can be added to the beginning of the linked list by creating a new node with the data to be used, replacing the head pointer to the new node and replacing the connections.

Steps

Create newNode with the given value and newNode → previous as NULL.
Check whether list is Empty (head == NULL)
If it is Empty then, assign NULL to newNode → next and newNode to head.
If it is not Empty then set head to newNode → next and newNode to head.

void insertAtBeginning(int value)
{
    struct Node *newNode;
    newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode -> data = value;
    newNode -> previous = NULL;
    if(head == NULL)
    {
       newNode -> next = NULL;
       head = newNode;
    }
    else
    {
       newNode -> next = head;
       head -> previous = newNode;
       head = newNode;
    }
    printf("\nInsertion successful");
}

Insertion after an element in the list

New data can be added at any position in the list by traversing to that position using a loop, creating a new Node and then manipulating the links to insert it at that position.

Steps

Create a newNode with the given value.
Check whether the list is Empty (head == NULL)
If it is Empty then set NULL to newNode → previous , newNode → next and head = newNode.
Define a temp Node and set it to head.
Keep moving the temp to its next node until it reaches to the node after which we want to insert the newNode (run a for-loop till position – 1)
If temp reaches the end of the list (temp → next == NULL ), Set flag to 0 (signifies element is not found) and break out of the loop.
If flag is 1, set newNode → next = temp → next , temp → next → previous = newNode , temp → next = newNode and newNode → previous = temp.

void insertAfter(int value, int pos)
{
   int i, flag = 1;
   struct Node *newNode, *temp = head;
   newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode -> data = value;
   if(head == NULL)
   {
      newNode -> previous = newNode -> next = NULL;
      head = newNode;
   }
   else
   {
    for (i = 0; i < pos - 1; i++) {
        temp = temp -> next;
        if (temp -> next == NULL) {
            flag = 0;
            break;
        }
    }

    if (flag) {
        newNode -> next = temp -> next;
        temp -> next -> previous = newNode;
        temp -> next = newNode;
        newNode -> previous = temp;
        printf("\nInsertion successful\n");
    }
    else
        printf("Number of elements is less than position entered");
   }
}

Deletion from the end of the list

New data can be added to the end of the linked list by creating a new node with the data to be used, traversing to the end of the list and then appending this data to the end.

Steps

Check whether the list is Empty (head == NULL).
If it is Empty, then throw an error and terminate the function.
If it is not Empty then, define a Node pointer temp and initialize with head.
Check whether the list has only one Node (temp → previous and temp → next both are NULL)
If it is TRUE, then assign NULL to head and delete temp. And terminate from the function.
If it is FALSE, then keep moving temp until it reaches the last node in the list. (until temp → next != NULL)
Set temp → previous → next = NULL and free(temp).

void deleteEnd()
{
   if(head == NULL)
      printf("List is Empty");
   else
   {
      struct Node *temp = head;
      if(temp -> previous == temp -> next)
      {
         head = NULL;
         free(temp);
      }
      else{
         while(temp -> next != NULL)
            temp = temp -> next;
         temp -> previous -> next = NULL;
         free(temp);
      }
      printf("\nDeletion successful");
   }
}

Deletion from the beginning of the list

New data can be added to the beginning of the linked list by creating a new node with the data to be used, replacing the head pointer to the new node and replacing the connections.

Steps

Check whether the list is Empty (head == NULL )
If it is Empty then, throw an error terminate the function.
If it is not Empty then, define a Node pointer temp and initialize with head.
Check whether the list is having only one node (temp → previous = temp → next).
If it is TRUE, then set head = NULL and free(temp).
If it is FALSE, then set temp → next = head , head → previous = NULL and free(temp).

void deleteBeginning()
{
   if(head == NULL)
      printf("List is Empty");
   else
   {
      struct Node *temp = head;
      if(temp -> previous == temp -> next)
      {
         head = NULL;
         free(temp);
      }
      else{
         head = temp -> next;
         head -> previous = NULL;
         free(temp);
      }
      printf("\nDeletion successful");
   }
}

Deletion at a specific position in the list

New data can be deleted at any position in the list by traversing to that position using a loop, deleting the required Node and then manipulating the links to make the list continuous.

Steps

Check whether the list is Empty (head == NULL)
If it is Empty then, throw an error and terminate the function.
If it is not Empty, then define a Node pointer temp and initialize with head.
Keep moving the temp until it reaches to the exact node to be deleted or to the last node.
If it is reached to the last node, then display ‘Given node not found in the list’ and terminate the function.
If it is reached to the exact node which we want to delete, then check whether the list is having only one node or not
If list has only one node and that is the node which is to be deleted then set head = NULL and free(temp).
If list contains multiple nodes, then check whether temp is the first node in the list (temp == head).
If temp is the first node, then move the head to the next node (head = head → next), set head of previous to NULL (head → previous = NULL ) and free(temp).
If temp is not the first node, then check whether it is the last node in the list ( temp → next == NULL).
If temp is the last node then set temp → previous → next = NULL and free(temp).
If temp is not the first node and not the last node, then set temp → previous → next = temp → next , temp → next → previous = temp → previous and free(temp).

void deleteSpecific(int delValue)
{
   if(head == NULL)
      printf("List is Empty");
   else
   {
      struct Node *temp = head;
      while(temp -> data != delValue)
      {
         if(temp -> next == NULL)
         {
            printf("\nGiven node is not found in the list");
         }
         else
         {
            temp = temp -> next;
         }
      }
      if(temp == head)
      {
         head = NULL;
         free(temp);
      }
      else
      {
         temp -> previous -> next = temp -> next;
         free(temp);
      }
      printf("\nDeletion successful");
   }
}

Applications of Doubly Linked List

Storing the browsing history: The browser history system in popular web browsers which allow going forward and backwards in browsing history can be implemented using this.
Most Recently Used algorithm: Applications that use a Most Recently Used (MRU) list.
In Games: A list can be used to represent a deck of cards (or anything that requires an order) in a game.