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:

advertisement
  • 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.

Free 30-Day Java Certification Bootcamp is Live. Join Now!

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:

advertisement
  • 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.

If you wish to look at all C Tutorials, go to C Tutorials.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.