Doubly Linked List in Data Structure

We have already seen the singly linked list in our previous article. A doubly linked list is a complex version of a singly linked list. Unlike a singly linked list, a doubly-linked list has each node pointed to its next node as well as its previous node.

Let us consider the same example as the previous article. Suppose you are inside a train. You can move from any coach to any coach because each coach has a two-way link to its next coach and to its previous coach.

Similarly, in a doubly-linked list, each node is connected to its previous node and next node making the accessibility very easy in comparison to a singly linked list.

In this article, we are going to learn about doubly-linked lists, types, and how to perform some often used operations on a doubly linked list.

Doubly linked list

A doubly linked list is a complex version of a singly linked list where each node contains a pointer to its previous node as well as the next node. Each node in the doubly linked list has three parts, the first part points to the previous node, the middle part contains the data and the last part points to the next node. 

Memory representation of Doubly Linked List

Operations on doubly linked list

• Insert: adding a new node to the existing doubly linked list.
• Delete: removing a node from the existing doubly linked list.
• Search: finding a node containing the search data in the existing doubly linked list. 
• Display: display the existing doubly linked list.

Creating node in Doubly Linked List

C program to create a node in a doubly-linked list:

struct node   
{  
    struct node *prev;  //NULL for first node
    int data;                 // data to store in node
    struct node *next;   //NULL for last node
}

Traversing a doubly linked list

Visit each node from start to end one by one.

void printList(struct Node* n)
{
    while (n != NULL) {
        printf(" %d ", n->data);
        n = n->next;
    }
}

Adding node in Doubly Linked List

1. Adding node at the beginning in Doubly Linked List

Point the next pointer of the new node to the first node and point the previous pointer of the current first node to the new node. Point previous of new node to NULL. The new node is now the first node of the linked list.

void insertAtBegin(node *new) 
{
     new->next = head;
     head -> previous = new;
     head = new;
 }

2. Adding node at the end in Doubly Linked List

To add the node in the last position, point the next pointer of the last node to the new node and point the previous pointer of the new node to the current last node. Point the next of the new node to null.

Void AddAtEnd(node *new)
{
     while (last -> next != NULL)
          last = last -> next;
     last -> next = new;
     new -> previous = last;
     new -> next = NULL;
}

3. Adding node at a specific position in Doubly Linked List

If you want to add a node at the nth position, point the next pointer of the new node to the (n+1)th node and point the previous pointer of the new node to (n-1)th node. After that, point the next of (n-1)th node and previous of (n+1)th node to the new node. 

Void AddAtPosition(node *new, node *prev)
{
    new -> next = prev-> next;
     new -> previous = prev;
    (previous -> next) -> previous = new;
     prev -> next= new;
}

Deleting node in Doubly Linked List

1. Delete node at the beginning of Doubly Linked List

Point the next pointer of the first node and the previous pointer of the second node to null.

void DeleteAtFirst()
{
     Node *temp  = *head;   
     head = temp -> next;
     head -> previous = NULL;
     free(temp);  
}

2. Delete node at the end of Doubly Linked List

Point next pointer of the second last node and previous pointer of the last node to null.

void DeleteAtLast()
{
     Node *ptr, *ptr1;
     ptr = head;
     while (ptr -> next != NULL)
     {
          ptr1 = ptr;
          ptr = ptr -> next;
     }
     ptr1 -> next =NULL;
     free ptr;   
}

3. Delete node at any position in Doubly Linked List

If you want to delete the node at the nth position, point the next of (n-1)th to (n+1)th node and point the previous of (n+1)th node to the(n-1)th node. Point previous and next of nth node to null.

void DeleteAtPosition(int pos)  
{  
    struct node *ptr,*ptr1;   
    ptr=head;  
    for(i=0;i<pos;i++)  
    {  
        ptr1 = ptr;       
        ptr = ptr->next;  
    }  
    ptr1 ->next = ptr -> next; 
    ptr1 -> next -> previous = ptr1; 
    free(ptr);   
}

Searching node in Doubly Linked List

Traverse from either the head of the doubly linked list or from the tale of the doubly linked list and compare the search element to every node. If found, return true else return false.

Boolean flag= false;
bool search(struct Node* head, int x)
{
    struct Node* current = head;
    while (current != NULL)
    {
        if (current->key == x)
          {
            flag = true;
            break;
    }
}
    return flag;
}

Display

Start Traversing from the head of the doubly linked list and keep on returning each node.

void display(struct Node* disp)
{
    while (disp != NULL) 
{
        printf(" %d ", disp -> data);
        disp = disp -> next;
    }
}

Implementation of doubly linked list in C

#include <stdio.h>
#include <stdlib.h>
  
struct Node
 {
    int data;
    struct Node* next;
    struct Node* previous;
};
  
int main()
{
    struct Node* Node1 = NULL;
    struct Node* Node2 = NULL;
    struct Node* Node3 = NULL;
  
    
   Node1 = (struct Node*)malloc(sizeof(struct Node));
   Node2 = (struct Node*)malloc(sizeof(struct Node));
   Node3 = (struct Node*)malloc(sizeof(struct Node));
  
     
    Node1 -> data = 1; 
    Node1 -> next = Node2; 
    Node1 -> previous = NULL;  
       
    Node2 -> data = 2;
    Node2 -> next = Node3;
    Node2 -> previous = Node1; 
     
    Node3 -> data = 3; 
    Node3 -> next = NULL;
    Node3 -> previous = Node2;

    display(Node1);
    return 0;
}

void display(struct Node* disp)
{
    while (disp != NULL) 
{
        printf(" %d ", disp -> data);
        disp = disp -> next;
    }
}

Implementation of doubly linked list in Python

class Node:
    def __init__(self, data):
        self.data = data  
        self.next = None 
        self.previous = None 
  
class SinglyLinkedList:    
    def __init__(self):
        self.head = None
    
    def DisplayList(self):
        temp = self.head
        while (temp):
            print (temp.data)
            temp = temp.next
  
if __name__=='__main__':
  
    dll = SinglyLinkedList()
  
    dll.head = Node(“DATA”)
    Node2 = Node(“FLAIR”)
    Node3 = Node(“DLL”)
  
    dll.head.next = Node2; 
    Node2.next = Node3; 
 
    dll.head.previous = None;
    Node2.previous = dll.head;
    Node3.previous = Node2;
 
    dll.DisplayList()

Doubly linked list implementation in C++

#include <bits/stdc++.h>
using namespace std;
  
class Node {
public:
    string data;
    Node* next;
    Node* previous;
};
  
void displayList(Node* n)
{
    while (n != NULL)
 {
        cout << n -> data << " ";
        n = n -> next;
    }
}
 
int main()
{
    Node* Node1 = NULL;
    Node* Node2 = NULL;
    Node* Node3 = NULL;
  
    Node1 = new Node();
    Node2 = new Node();
    Node3 = new Node();
  
    Node1 -> data = “DATA”; 
    Node1 -> next = Node2; 
    Node1 -> previous = NULL;
  
    Node2 -> data = “FLAIR”; 
    Node2 -> next = Node3;
    Node2 -> previous = Node1;
  
    Node3 -> data = “DLL”; 
    Node3 -> next = NULL;
    Node3 -> previous = Node2;
  
    displayList(Node1);
  
    return 0;
}

Implementation of doubly linked list in Java

public class DoublyLinkedList {
    Node head; 
 
    static class Node {
        String data;
        Node next;
        Node previous;
        
        Node(String str)
        {
            data = str;
            next = null;
        } 
    }
  
    
    public void displayList()
    {
        Node n = head;
        while (n != null) 
        {
            System.out.print(n.data + " ");
            n = n.next;
        }
    }
  
    public static void main(String[] args)
    {
        
        DoublyLinkedList dllist = new DoublyLinkedList();
  
        Node Node1 = new Node("DATA");        
        Node Node2 = new Node("FLAIR");
        Node Node3 = new Node("DLL");
 
        dllist.head = Node1;
  
        dllist.head.next = Node2; 
        Node2.next = Node3; 
 
        Node2.previous = Node1;
        Node3.previous = Node2;
  
        dllist.displayList();
    }
}

Advantages of Doubly linked list

• Both forward and backward traversing is possible.
• Insert and Delete operations are highly efficient as compared to the singly linked list.

Disadvantages of Doubly linked list

• Every node requires large memory blocks since it has a previous pointer too. This makes it a little memory inefficient. 

Singly-linked list Vs Doubly linked list

Conclusion

A doubly linked list is a more efficient version of a singly linked list. Although it requires more memory, Insert and delete operations are carried out in constant time complexity.

Here we also learned the step-by-step procedure for insertion and deletion of nodes at different positions in an already existing doubly linked list.