Doubly Linked List in Data Structure

Linked lists are a widely used data structure because of their wide range of applications. Linked lists are also of three types:

1. Singly linked list

2. Doubly linked list

3. Circular linked list

This article will cover doubly linked list in detail.

What is a doubly-linked list?

The singly linked list had a single pointer pointing to the next node. But a doubly linked list contains two pointers. One pointer points to the next node and one pointer to the previous node. Thus, a doubly linked list is a two-way chain.

Every node in a doubly linked list has-

  • Data
  • Address of the next node
  • Address of the previous node

The purpose of a doubly linked list is to enable both-way traversal while still allowing non-contiguous memory storage. Just like a singly linked list, we need to have a starting pointer pointing to the first node. The last node in the list points to NULL.

Representation of Doubly Linked List

A doubly linked list is represented as follows:

Doubly linked list Representation

The above list is comprised of 4 nodes having four data points- A, B, C, D. Each node has two links one pointing forward and one pointing backwards.

Each node has the following structure:

Node structure

 

It comprises of two pointers and a data field.

a. Data: It constitutes the value of the data item inside the list.

b. Prev: It is a pointer pointing towards the previous node. For the first node, Prev points to NULL.

c. Next: It links the current node to the next node in the linked list. The ‘Next’ of the last node points towards NULL.

Follow TechVidvan on Google & Stay updated with latest technology trends

Basic Operations on Double Linked List

The basic set of operations that we can perform on a doubly linked list are:

1. Traverse forward: It means visiting each node from the beginning till the end with the help of the ‘Next’ pointer.

2. Traverse backwards: This operation is performed to visit each node but in the reverse direction. It will traverse the list from the end to the beginning.

3. Insertion: This operation inserts an element at any given position in the list.

4. Deletion: Deletion operation helps in deleting a node from the linked list.

5. Display forward: This operation is used to print/display all the data elements of the linked list from beginning till the end.

6. Display backwards: it will display the elements from the end to the beginning.

7. Search: Search operation helps in searching an element by traversing it.

Memory Representation of Doubly Linked List

1. Each node in a doubly-linked list consists of 3 parts- two-pointers and a node.

2. Due to two-pointers additional to data values, a doubly-linked list takes a lot of space as compared to other data structures.

3. The following image shows the memory representation of a linked list.

Memory Representation of Doubly Linked List:

4. Here, -1 represents NULL.

5. The Prev of the first node i.e. A and the Next of the last node i.e. D point towards NULL.

6. This memory representation shows that the values need not be stored contiguously.

7. The values 1000, 1056, 2004 and so on represent addresses in the memory.

8. We traverse the list until we find -1 in the Next of a node.

Creating a Node in Doubly Linked List

Each node in a doubly linked list has data as well pointers. Therefore, we use a structure to create the node.
The structure template for the node looks as follows:

struct Node
{
    int data;     //The data point
    struct Node *Prev;   //Pointer to the previous node
    struct Node *Next;    //Pointer to the next node
};

Traversal in a Doubly Linked List

Traversal refers to linearly visiting each node. In a doubly linked list, we can traverse in both forward and backward directions.

The function to perform the traversal is as follows:

List_traversal(struct Node *Head)
{
    Prev = (struct Node *)malloc(sizeof(struct Node));
    Next = (struct Node *)malloc(sizeof(struct Node));
    if(Head == NULL)   //If the list is empty
        return;
    while(Next->data != NULL)
    {
        Print(Next->data);   //The display operation
        Next = Next->data;
    }
}

The time complexity for the traversal operation is O(n).

Doubly Linked List Methods

There are various inbuilt methods defined inside the doubly-linked list class. A few of these methods are:

1. add_front: This method adds a new node at the beginning of the doubly linked list.

2. add_after: It adds a new node after a particular node.

3. add_before: It is used to add a new node before a particular node in the list.

4. add_end: This method will add a new node at the end of the doubly linked list.

5. forward_traverse: It helps in traversing the list in the forward direction.

6. backward_traverse: It helps in traversing the list in the backward direction.

7. delete: This method deletes a node from the linked list.

Their implementation inside the class is shown below:

class doubly_linked_list
{
  node *First;  	// It points to the first node of the list
  node *Last;   	// It points to the last node of the list
  
  public:
      Doubly_Linked_List()
      {
        front = NULL;
        end = NULL;
      }
  void add_front(int );  //Adds a new node at the beginning
  void add_after(node* , int );   //Adds a new node after the given node
  void add_before(node* , int );  //Adds a new node before a given node
  void add_end(int );     //Adds a new node at the end of the list
  void delete_node(node*);    //Ddeletes a particular node
  void forward_traverse();    //traverses the doubly-linked list in forward direction
  void backward_traverse();   //traverses the doubly-linked list in backward direction
};

Insertion in a Linked List

Insertion in a linked list occurs at three different positions:

1. Insertion at the beginning of the list

2. Insertion after a particular node.

3. Insertion at the end of the list

Insertion at the beginning

We insert a node at the beginning such that the next pointer points to the node which was at first before. The previous pointer points to NULL.

Insert at start in Doubly Linked List

Here, we have tried to insert M at the beginning.

The pseudo-code for this operation will be:

Insertion_at_beginning(struct Node *Head, int key)
{
    Prev = (struct Node *)malloc(sizeof(struct Node));
    Next = (struct Node *)malloc(sizeof(struct Node));
    temp = (struct Node *)malloc(sizeof(struct Node));
    if(Head == NULL)
        return;
    while(Next->data != NULL)
    {
        temp->data = key;
        temp->Next = Head;
        Head->Prev = temp;
        Head = temp;
        temp->Prev = NULL;
    }
}

Here, we will make use of an extra pointer ‘temp’ to perform the insertion operation.

Insertion at the End

If the list is empty, we will insert a node right after the Head. If the list is not empty, we first need to traverse the whole list to insert a node at the end of the list.

Insertion at end in Doubly Linked List

In the above diagram, we are inserting M at the end.

The function for insertion at the end is:

Insertion_at_end(struct Node *Head, int key)
{
    Ptr = (struct Node *) malloc(sizeof(struct node));  
    Ptr->Next = NULL;  
    Ptr->Prev=NULL;  
    Ptr->data = key;  
    Head = Ptr;  
    Temp = head;   
    while (temp != NULL)  
        temp = temp -> next;   
    temp->Next = Ptr;   
    Ptr->Prev = temp;   
    Ptr->Next = NULL;   
}

Insertion after a particular node

Insertion after a particular node involves traversing all nodes before that node. We will make use of an extra pointer ‘temp’ for traversing the node up to a particular position.

For example, suppose we wish to insert a node having data value ‘M’ between node ‘B’ and node ‘C’, we will do it as follows:

Insert at particular position in Linked List

The function will be:

Insert_after_particular_position(struct Node *Head, int key)
{
    Ptr = (struct Node *) malloc(sizeof(struct node));  //Allocating memory for the new node
    temp = Head;  
    Ptr->data = key;
    for(i=0; i<position; i++)  
   {  
       temp = temp->Next;  
       if(temp == NULL) // i.e. if the list is empty   
             return;  
   }
   Ptr->Next = temp->Next;   
   Ptr->Prev = temp;   
   temp->Next = Ptr;   
   temp->Next->Prev = Ptr;    
}

Time complexity of Insertion:

Insertion operationComplexity 
At the beginningO(1)
After a particular nodeO(1)
At the endO(n)

Deletion from a Linked List:

Deletion involves deleting nodes from the list. It also works in three different cases:

1. Deletion from beginning

2. Deletion at the end

3. Deleting a node other than the first and the last node

1. Deletion from the beginning:

It involves deleting the first node of the doubly linked list. The following diagram shows the deletion operation at the beginning of the doubly linked list.

Deletion in doubly linked List

The deletion function will be:

Deletion_from_beginning(int key){
    struct Node *Ptr = Head;  
    if (Head == NULL) return;
    Head = Head->Next;
    Head->Prev = NULL;
    free(Ptr);
}

The free function is used to release the memory space. If we don’t release memory after using it, it might lead to memory leakage problems in future.

2. Deletion at the end:

If the list is empty, we will directly pass the return statement in the function. If the list contains a single node, we just need to make the Head point towards NULL. When the list has two or more nodes, we need to traverse the whole node and then delete the last node.

Delete at the end in Doubly Linked List

Deletion_at_end(int key){
    struct Node *Ptr = Head;  
    if(Head == NULL)  //If the list is empty
        return;
    if(Ptr->Next == NULL)  //If the list has only one element
    {
        Head->Next = NULL;
        return;
    }
    Ptr->Prev->Next = NULL;
    free(ptr);
}

Deletion after a particular node:

If we know the address of a particular node, we can easily delete the node next to it.
For example, suppose we wish to delete node ‘C’ from the list having nodes: ‘A’, ‘B’, ‘C’ and ‘D’. Then, we will do it as follows:

Deletion from Doubly Linked List

The function will be:

Deletion_after_particular_node(int key){
    struct Node *temp = Head;  
    if(Head == NULL)  //If the list is empty
        return;
    if(temp -> Next == NULL)  //If the list has only 1 node 
        return;   
    while(temp->data != key)  //Traversing the list   
        temp = temp->Next; 
    if(temp->Next->Next == NULL)  //If the node to be deleted is the last node
        temp->Next = NULL;  
    Ptr = temp->Next;  
    temp->Next = Ptr->Next;  
    Ptr->Next->Prev = temp;  
    free(ptr);
}

Time complexity for Deletion operation:

Deletion operationComplexity 
At the beginningO(1)
After a particular nodeO(n)
At the endO(n)

Doubly Linked List as Circular Linked list:

A doubly linked list contains pointers to both the previous and the next node. A circular list does not contain any NULL pointer. In a circular linked list, the ‘Next’ of the last nodes points to the first node of the list.

Combination of a doubly list and a circular list is known as a doubly-circular list. A doubly-circular linked list looks as follows:

Doubly Linked List as Circular Linked list

1. The ‘Next’ pointer of the last node in the doubly-linked list points to the points to the first node in the list.

2. The ‘Prev’ pointer of the first node points to the last node of the linked list.

3. There is no NULL pointer anywhere in the list.

Advantages of a Doubly Linked List:

1. We can traverse a doubly linked list in both forward and backward direction.

2. Traversal in the backward direction makes the deletion operation more efficient. If the pointer to a node is given, we can easily delete the previous node with O’s time complexity O(1).

3. The insertion operation is also more efficient. If the pointer a node is given, we can easily insert a node before that node.

Disadvantages of a Doubly Linked List:

1. A doubly linked list takes more space than a singly list because of the presence of an extra ‘Prev’ pointer at each node.

2. We need to maintain this extra ‘Prev’ pointer while performing all the operations. This increases the space complexity of all the operations performed on a doubly linked list.

Conclusion

The crux of this article is that a doubly linked list has a similar behaviour as a singly list most of the time. However, there are a few cases when a double list performs better than a singly linked list. Insertion and deletion operations are easier and more efficient in a doubly-linked list as compared to a singly linked list. But they are easier at the cost of additional space for the program.

Did you like our efforts? If Yes, please give TechVidvan 5 Stars on Google | Facebook

2 Responses

  1. K john prakash says:

    Excellent but need all those data structures using c and c++ notes. Thanks for ur info

  2. K john prakash says:

    Programmes with explanation

Leave a Reply

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