Advantages of Doubly Linked List in Data Structure

Introduction

A linked list contains nodes in which each node has a data part and the reference to the next node. Each node in a linked list is connected via links. The operations that can be performed on a linked list are search, insert, delete, traverse, etc. There are various kinds of linked lists like singly link list, doubly link list and circular link list.

In this article, we will see the most used doubly link list and its advantages.

What is a Doubly Linked List?

Doubly linked list is a variation of linked list in which we can move forward and backward. We can define a doubly linked list using the following terms -

• Link: Each link of a linked list can store a data called an element.
• Next: Each link of a linked list contains a link to the next link called Next.
• Prev: Each link of a linked list contains a link to the previous link called Prev.
• LinkedList: A Linked List contains the connection link to the first link called First and to the last link called Last.

An example of a doubly linked list is the tabs in the browser, you can move to any tab forward or backward.

So if a Linked List ⇒ A → B → C
Then a Doubly Linked List ⇒ A ⇆ B ⇆ C

Representation of a Doubly Linked List in Data Structure

A class node is created that contains a data variable to hold the value of a node. A next pointer to store the address of the next linked node in the list.

A prev pointer to store the address of previously linked nodes in the list.

C++ Code

class Node
{
    public:
    int data; // value of a node in linked list 
    Node* next; // Pointer to next node in DLL
    Node* prev; // Pointer to previous node in DLL
};

C Code

struct Node // create a structure for C ll 
{
    int data; // value of a node in linked list 
    struct Node* next; // Pointer to next node in DLL
    struct Node* prev; // Pointer to previous node in DLL
};

Operations on a Doubly Linked List

The following are some various operations that can be performed in a doubly linked list -

• Add a Node in the Front Steps involved -

1. Allocate node
2. Put in the data
3. Make next of new node as head and previous as NULL
4. Change prev of head node to new node
5. Move the head to point to the new node

• Add a Node After a Given Node Steps involved -

1. Check if the given previous node is NULL
2. Allocate new node
3. Put in the data
4. Make next of new node as next of previous node
5. Make the next of previous node as new_node
6. Make previous node as previous of new_node
7. Change previous of new_node's next node

• Add a Node in the End Steps involved -

1. Allocate node and put in the data
2. This new node is going to be the last node, so If the Linked List is empty, then make the new
3. Else traverse till the last node
4. Change the next of last node
5. Make last node as previous of new node

• Add a Node in the End Steps involved -

1. Check if the next_node is NULL or not. If it’s NULL, return from the function because any new node can not be added before a NULL
2. Allocate memory for the new node, let it be called new_node
3. Set the value of data to the new node
4. Set the previous pointer of this new_node as the previous node of the next_node, new_node->prev = next_node->prev
5. Set the previous pointer of the next_node as the new_node.
6. Set the next pointer of this new_node as the next_node.
7. If the previous node of the new_node is not NULL, then set the next pointer of this previous node as new_node.
8. Else, if the prev of new_node is NULL, it will be the new head node.

Code to Demonstrate the Insertion Operations

CPP

#include <bits/stdc++.h>
using namespace std;
class Node // Create a doubly linked list 
{
    public:
    int data; // value of a node 
    Node* next;// next pointer 
    Node* prev;// previous pointer of node 
};


void push(Node** head_ref, int new_data) // insert a node in front of list 
{
    /* 1. allocate node
    Node* new_node = new Node();

    /* 2. put in the data */
    new_node->data = new_data;

    /* 3. Make next of new node as head
    and previous as NULL */
    new_node->next = (*head_ref);
    new_node->prev = NULL;

    /* 4. change prev of head node to new node */
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;

    /* 5. move the head to point to the new node */
    (*head_ref) = new_node;
}


void insertAfter(Node* prev_node, int new_data) // function to insert after a node 
{
    /*1. check if the given prev_node is NULL */
    if (prev_node == NULL)
    {
        cout<<"the given previous node cannot be NULL";
        return;
    }

    /* 2. allocate new node */
    Node* new_node = new Node();

    /* 3. put in the data */
    new_node->data = new_data;

    /* 4. Make next of new node as next of prev_node */
    new_node->next = prev_node->next;

    /* 5. Make the next of prev_node as new_node */
    prev_node->next = new_node;

    /* 6. Make prev_node as previous of new_node */
    new_node->prev = prev_node;

    /* 7. Change previous of new_node's next node */
    if (new_node->next != NULL)
        new_node->next->prev = new_node;
}


void append(Node** head_ref, int new_data) // function to add a new node at the end 
{
    /* 1. allocate node */
    Node* new_node = new Node();

    Node* last = *head_ref; /* used in step 5*/

    /* 2. put in the data */
    new_node->data = new_data;

    /* 3. This new node is going to be the last node, so
        make next of it as NULL*/
    new_node->next = NULL;

    /* 4. If the Linked List is empty, then make the new
        node as head */
    if (*head_ref == NULL)
    {
        new_node->prev = NULL;
        *head_ref = new_node;
        return;
    }

    /* 5. Else traverse till the last node */
    while (last->next != NULL)
        last = last->next;

    /* 6. Change the next of last node */
    last->next = new_node;

    /* 7. Make last node as previous of new node */
    new_node->prev = last;

    return;
}


void printList(Node* node)// function to print the doubly linked list 
{
    Node* last;
    cout<<"\nTraversal in forward direction \n";
    while (node != NULL)
    {
        cout<<" "<<node->data<<" ";
        last = node;
        node = node->next;
    }

    cout<<"\nTraversal in reverse direction \n";
    while (last != NULL) // traverse the list in reverse direction 
    {
        cout<<" "<<last->data<<" ";
        last = last->prev;
    }
}

int main() // Main function
{

    Node* head = NULL; // currently the list is empty 
    append(&head, 6); // insert 6 in the beginning 
    push(&head, 7); // insert 7 before 6 
    push(&head, 1); 

Output:

Created Doubly linked list is: 
Traversal in forward direction 
 1  7  8  6  4 
Traversal in reverse direction 
 4  6  8  7  1 

• Deletion in Doubly Linked List The deletion of nodes can be divided into three categories - head, middle and last node deletion.

Steps to be performed for deletion

1. Let the node be Deleted be D.
2. If the node to be Deleted is the head node, then change the head pointer to the next current head.
3. Set next to previous to D, if previous to D exists.
4. Set prev of next to D, if next to D exists.

CPP Code to Perform Deletion Operation

#include <bits/stdc++.h>
using namespace std;
class Node // create a doubly linked list 
{
    public:
    int data; // value of the node 
    Node* next; // next pointer of the node 
    Node* prev; // previous pointer to the node 
};

void deleteNode(Node** head_ref, Node* del) // function to delete a node in DLL
{
    /* base case */
    if (*head_ref == NULL || del == NULL)
        return;

        if (*head_ref == del)
        *head_ref = del->next;

    if (del->next != NULL)
        del->next->prev = del->prev;

    if (del->prev != NULL)
        del->prev->next = del->next;

    /* Finally, free the memory occupied by del*/
    free(del);
    return;
}

void push(Node** head_ref, int new_data) // function to insert data into the DLL
{

    Node* new_node = new Node();

    /* put in the data */
    new_node->data = new_data;

    new_node->prev = NULL;
    new_node->next = (*head_ref);

    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;

    (*head_ref) = new_node;
}

void printList(Node* node) // function to print the content of the DLL
{
    while (node != NULL) // iterate till the end of DLL 
    {
        cout << node->data << " "; // print node data 
        node = node->next;
    }
}

int main() // main function 
{
    Node* head = NULL; // currently head is NULL 

   // DLL created =  10<->8<->4<->2 
    push(&head, 2);
    push(&head, 4);
    push(&head, 8);
    push(&head, 10);

    cout << "Original Doubly Linked list ";
    printList(head); // print original DLL

    /* delete nodes from the doubly linked list */
    deleteNode(&head, head); 

Output:

Original Doubly Linked list 10 8 4 2 
Modified Doubly Linked list 8 

Advantages of a Doubly Linked List

As we have seen the operations of a DLL, below are the advantages -

• It becomes easier to iterate in both directions.
• Deletion of a particular node is easy as we have access to the previous node.
• Performing a reverse operation is easy.
• A DLL can grow and shrink dynamically.
• It is beneficial in implementing other data structures like binary trees, hash tables, stacks, etc.
• It provides the flexibility to perform undo/redo operations.
• It can also be used in gaming like playing deck of cards.
• Traversing a DLL in a bidirectional manner is easy as compared to singly linked lists.
• In the operating system, a thread scheduler manages a doubly linked list of all the processes.
• The concept of DLL can be applied in forward and backward navigation areas.

Disadvantages of a Doubly Linked List

• It stores an extra pointer to store the address of previously linked nodes. Hence, it consumes more memory when compared to a singly linked list.
• Due to extra pointers more time is required in handling the overhead.
• We can't randomly access elements in a doubly linked list.

Conclusion

A doubly linked list has three parts: the data, next and a previous pointer. We can perform various operations on a doubly linked list like add a node in front, add a node in last, delete a node in front, delete a node in the lost, insert a node after a given node, insert a node before a given node, etc.

The main benefit of a doubly linked list is its iteration in backward and forward direction. Also a DLL can shrink dynamically. Doubly linked list examples are - a music playlist in which songs can be changed by moving backward and forward, the undo and redo functionality in a word file, etc.

Reference: Scaler Topics