What is a Doubly Linked List in C?

A doubly linked list is a fundamental data structure in C programming that allows traversal in both forward and backward directions. Unlike a singly linked list, where each node points only to the next node, a doubly linked list node contains two pointers: one to the next node and another to the previous node.

What is a Doubly Linked List in C?

A doubly linked list (DLL) consists of nodes where each node has three components:

• Data: Stores the value.
• Next Pointer: Points to the next node in the list.
• Previous Pointer: Points to the previous node in the list.

Unlike singly linked lists (which can be traversed only forward), a DLL can be traversed both forwards and backwards.

Here’s a visual representation:

NULL <- [10] <-> [20] <-> [30] -> NULL

Each node is connected both ways — backward and forward.

Why Use a Doubly Linked List?

Here are some reasons you might choose a doubly linked list:

• Easy to traverse in both directions.
• Deleting a node is faster (especially if you have a pointer to it).
• Inserting nodes is more flexible (e.g., insert before or after a given node).

However, the trade-off is more memory usage (because of the extra pointer) and a bit more complex code.

Structure of a Doubly Linked List Node in C

In C, a node in a doubly linked list can be defined using structures:

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

Here, data holds the value, prev points to the previous node, and next points to the next node.

Basic Operations on Doubly Linked List

1. Insertion

Insertion can occur at various positions:

• At the beginning: Create a new node, set its next to the current head, and update the head’s prev to the new node. Then, update the head to the new node.
• At the end: Traverse to the end of the list, set the last node’s next to the new node, and set the new node’s prev to the last node.
• After a given node: Adjust the next and prev pointers of the new node and its adjacent nodes to insert it in the desired position.

2. Deletion

Deletion involves removing a node and adjusting the pointers of adjacent nodes:

• From the beginning: Update the head to the next node and set its prev to NULL.
• From the end: Traverse to the last node, update the second last node’s next to NULL, and free the last node.
• A specific node: Adjust the next pointer of the previous node and the prev pointer of the next node to bypass the node to be deleted.

3. Traversal

• Forward Traversal: Start from the head and move through each node using the next pointer.
• Backward Traversal: Start from the tail and move through each node using the prev pointer.

Example: Forward and Backward Traversal of Doubly Linked List

#include <stdio.h>
#include <stdlib.h>
 
// Node structure
struct Node {
    int mcqs;
    struct Node* prev;
    struct Node* next;
};
 
// Insert at end
void insertAtEnd(struct Node** head_ref, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->mcqs = data;
    newNode->next = NULL;
 
    if (*head_ref == NULL) {
        newNode->prev = NULL;
        *head_ref = newNode;
        return;
    }
 
    struct Node* temp = *head_ref;
    while (temp->next != NULL)
        temp = temp->next;
 
    temp->next = newNode;
    newNode->prev = temp;
}
 
// Traverse forward
void traverseForward(struct Node* head) {
    printf("Forward Traversal: ");
    while (head != NULL) {
        printf("%d ", head->mcqs);
        head = head->next;
    }
    printf("\n");
}
 
// Traverse backward
void traverseBackward(struct Node* head) {
    if (head == NULL) return;
 
    // Move to last node
    while (head->next != NULL)
        head = head->next;
 
    // Traverse back
    printf("Backward Traversal: ");
    while (head != NULL) {
        printf("%d ", head->mcqs);
        head = head->prev;
    }
    printf("\n");
}
 
int main() {
    struct Node* head = NULL;
 
    // Insert data
    insertAtEnd(&head, 11);
    insertAtEnd(&head, 22);
    insertAtEnd(&head, 33);
    insertAtEnd(&head, 44);
 
    // Display list in both directions
    traverseForward(head);
    traverseBackward(head);
 
    return 0;
}

Output:

Forward Traversal: 11 22 33 44 
Backward Traversal: 44 33 22 11

Explanation:

• The program defines a doubly linked list using a Node structure with data and two pointers (prev and next).
• The insertAtEnd function creates a new node and adds it to the end of the list.
• If the list is empty, the new node becomes the head; otherwise, it’s linked after the last node.
• The traverseForward function prints the list from head to tail using the next pointer.
• The traverseBackward function prints the list from tail to head using the prev pointer.
• The main function inserts four nodes (11, 22, 33, 44) and displays them in forward and backward order.

Advantages of Doubly Linked List

• Ease of Deletion: Deleting a node is more straightforward since we have access to the previous node.
• Flexible Insertion: Can insert nodes more efficiently in certain scenarios.

Disadvantages of Doubly Linked List

• Increased Memory Usage: Each node requires extra memory for the prev pointer.
• Complexity: More complex to implement and manage due to additional pointers.

Use Cases of Doubly Linked List

• Navigation Systems: Allowing forward and backward movement.
• Undo/Redo Functionality: In applications where actions can be reversed.
• Browser History: Navigating back and forth between pages.

Sanfoundry Global Education & Learning Series – 1000 C Tutorials.