Doubly Linked List in C (Bidirectional Traversal)

A doubly linked list links nodes bidirectionally with next and prev pointers. Learn how to perform O(1) node removals, bidirectional traversals, and pointer updates in C.

A doubly linked list enhances the singly linked list by equipping each node with two pointers: prev and next. This bidirectional chaining allows traversal in both forward and reverse directions and makes deleting arbitrary nodes an O(1) operation when a pointer to the node is already known.

Because each node maintains two pointer references, updating the list requires carefully sequencing four pointer assignments to avoid breaking the chain. A broken pointer chain can orphan downstream nodes, causing severe memory leaks.

Doubly linked lists form the architectural foundation for LRU caches, browser history stacks, and OS scheduler runqueues where rapid bidirectional navigation and node removal are required.

Interactive Runnable C Implementation

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

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

DNode* insertHead(DNode *head, int val) {
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    newNode->data = val;
    newNode->prev = NULL;
    newNode->next = head;
    if (head != NULL) head->prev = newNode;
    return newNode;
}

void printForward(DNode *head) {
    DNode *curr = head;
    while (curr != NULL) {
        printf("%d <-> ", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

void freeDList(DNode *head) {
    DNode *curr = head;
    while (curr != NULL) {
        DNode *temp = curr;
        curr = curr->next;
        free(temp);
    }
}

int main() {
    DNode *head = NULL;
    head = insertHead(head, 300);
    head = insertHead(head, 200);
    head = insertHead(head, 100);

    printf("Doubly Linked List: ");
    printForward(head);

    freeDList(head);
    return 0;
}

Open example in compiler

Expected Output

Doubly Linked List: 100 <-> 200 <-> 300 <-> NULL