Doubly Linked List

A Doubly linked list is a data structure that consists of a set of sequentially linked nodes, each containing two links: one to the next node and another to the previous node. This allows for traversal in both forward and backward directions, making it different from a singly

linked list, which only allows for traversal in one direction.

Representation of a Doubly Linked List

A Doubly Linked List is represented by a series of nodes, where each node contains three fields.

Data: Stores the value of the node.
Previous: A pointer that stores the address of the previous node.
Next: A pointer that stores the address of the next node.

The first node of the list is called the head node, and the last node is called the tail node. The head node's previous pointer is always NULL, and the tail node's next pointer is also NULL. Doubly Linked List Data Structure

Uses of Doubly Linked List

Implementing undo/redo functionality in text editors and graphic design applications.
Implementing navigation in web browsers, where the back and forward buttons allow for traversal in both directions.
Implementing memory management algorithms, such as the LRU cache, which requires fast access to both the least recently used and most recently used data.

Advantages and Disadvantages of Doubly Linked List

Advantages of Doubly Linked List

Allows for traversal in both forward and backward directions.

Insertion and deletion of nodes are efficient.

Can be used to implement stack, queue, and deque data structures.

Disadvantages of Doubly Linked List

Extra space is required for the previous pointers, increasing the memory requirements.

Implementation is more complex than a singly linked list.

Common Doubly Linked List Operations

Add a Node in a Doubly Linked List

To add a new node to the Doubly Linked List, we need to follow the following steps:

Create a new node and set its data value.
Set the next pointer of the new node to the current node's next pointer.
Set the previous pointer of the new node to the current node.
Set the next pointer of the current node to the new node.
If the new node's next pointer is not null, then set the previous pointer of the new node's next node to the new node.

Traverse a Doubly Linked List

To traverse a Doubly Linked List, we can start from the head node and move forward until we reach the last node.

Delete a Node from Doubly Linked List

To delete a node from the Doubly Linked List, we need to follow the following steps:

If the node to be deleted is the head node, then set the head node to the next node.
If the node to be deleted is not the head node, then set the next pointer of the previous node of the node to be deleted to the next node of the node to be deleted.
If the node to be deleted is not the last node, then set the previous pointer of the next node of the node to be deleted to the previous node of the node to be deleted.
Free the memory of the node to be deleted.

Doubly Linked List Implementation Program

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node *prev;
    struct node *next;
};

// Function to add a node at the end of the list
void add_node_end(struct node **head, int data)
{
    struct node *new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = data;
    new_node->next = NULL;

    if (*head == NULL)
    {
        new_node->prev = NULL;
        *head = new_node;
        return;
    }

    struct node *last_node = *head;
    while (last_node->next != NULL)
    {
        last_node = last_node->next;
    }

    last_node->next = new_node;
    new_node->prev = last_node;
}

// Function to traverse the list from head to tail
void traverse_forward(struct node *head)
{
    printf("\nTraversal in forward direction:\n");
    while (head != NULL)
    {
        printf("%d ", head->data);
        head = head->next;
    }
}

// Function to traverse the list from tail to head
void traverse_backward(struct node *tail)
{
    printf("\nTraversal in backward direction:\n");
    while (tail != NULL)
    {
        printf("%d ", tail->data);
        tail = tail->prev;
    }
}

// Function to delete a node with given key
void delete_node(struct node **head, int key)
{
    if (*head == NULL)
    {
        printf("\nList is empty\n");
        return;
    }

    struct node *temp = *head;
    if (temp->data == key)
    {
        *head = temp->next;
        (*head)->prev = NULL;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key)
    {
        temp = temp->next;
    }

    if (temp == NULL)
    {
        printf("\nKey not found in list\n");
        return;
    }

    if (temp->next == NULL)
    {
        temp->prev->next = NULL;
        free(temp);
        return;
    }

    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    free(temp);
}

int main()
{
    struct node *head = NULL;

    // Adding nodes to the list
    add_node_end(&head, 10);
    add_node_end(&head, 20);
    add_node_end(&head, 30);
    add_node_end(&head, 40);
    add_node_end(&head, 50);

    // Traversing the list in forward direction
    traverse_forward(head);

    // Traversing the list in backward direction
    struct node *tail = head;
    while (tail->next != NULL)
    {
        tail = tail->next;
    }
    traverse_backward(tail);

    // Deleting a node with key 30
    delete_node(&head, 30);

    // Traversing the list after deletion
    traverse_forward(head);

    return 0;
}

Output

Traversal in forward direction:
10 20 30 40 50 
Traversal in backward direction:
50 40 30 20 10 
Traversal in forward direction:
10 20 40 50