Doubly Linked List in C – Insert, Delete, and Traverse Both Ways

A doubly linked list in C extends the singly linked list by giving each node two pointers: one to the next node (next) and one to the previous node (prev). This bidirectional linkage lets you traverse the list in either direction and delete a node in O(1) given only a pointer to that node — without needing to find its predecessor first.

Singly vs Doubly Linked List

Node Structure

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

NULL ←[prev|5|next]↔[prev|10|next]↔[prev|20|next]↔[prev|30|next]→ NULL
       ↑head                                          ↑tail

Doubly Linked List Program in C

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

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

typedef struct {
    Node *head;
    Node *tail;
} DList;

/* ── Node creation ─────────────────────────────────────────── */
static Node *createNode(int val)
{
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) { fprintf(stderr, "malloc failed\n"); exit(1); }
    n->data = val;
    n->prev = n->next = NULL;
    return n;
}

/* ── Insert at front — O(1) ────────────────────────────────── */
void insertFront(DList *list, int val)
{
    Node *n = createNode(val);
    if (list->head == NULL) {
        list->head = list->tail = n;
    } else {
        n->next = list->head;
        list->head->prev = n;
        list->head = n;
    }
}

/* ── Insert at end — O(1) with tail pointer ─────────────────── */
void insertEnd(DList *list, int val)
{
    Node *n = createNode(val);
    if (list->tail == NULL) {
        list->head = list->tail = n;
    } else {
        n->prev = list->tail;
        list->tail->next = n;
        list->tail = n;
    }
}

/* ── Delete a node given a pointer to it — O(1) ─────────────── */
void deleteNode(DList *list, Node *node)
{
    if (node == NULL) return;
    if (node->prev != NULL)
        node->prev->next = node->next;
    else
        list->head = node->next;   /* deleting head */

    if (node->next != NULL)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;   /* deleting tail */

    free(node);
}

/* ── Delete by value — O(n) search + O(1) delete ────────────── */
int deleteByValue(DList *list, int val)
{
    Node *curr;
    for (curr = list->head; curr != NULL; curr = curr->next) {
        if (curr->data == val) {
            deleteNode(list, curr);
            return 1;   /* found and deleted */
        }
    }
    return 0;   /* not found */
}

/* ── Forward traversal — O(n) ──────────────────────────────── */
void displayForward(DList *list)
{
    Node *curr;
    printf("Head → ");
    for (curr = list->head; curr != NULL; curr = curr->next)
        printf("%d → ", curr->data);
    printf("NULL\n");
}

/* ── Backward traversal — O(n) ─────────────────────────────── */
void displayBackward(DList *list)
{
    Node *curr;
    printf("NULL ← ");
    for (curr = list->tail; curr != NULL; curr = curr->prev)
        printf("%d ← ", curr->data);
    printf("Head\n");
}

/* ── Free all nodes — O(n) ─────────────────────────────────── */
void freeList(DList *list)
{
    Node *curr = list->head, *next;
    while (curr != NULL) {
        next = curr->next;
        free(curr);
        curr = next;
    }
    list->head = list->tail = NULL;
}

int main(void)
{
    DList list;
    list.head = list.tail = NULL;

    insertEnd(&list, 10);
    insertEnd(&list, 20);
    insertEnd(&list, 30);
    insertFront(&list, 5);

    printf("Forward:  "); displayForward(&list);
    printf("Backward: "); displayBackward(&list);

    /* Delete by value */
    if (deleteByValue(&list, 20))
        printf("Deleted 20\n");
    printf("Forward:  "); displayForward(&list);

    /* Delete head */
    if (deleteByValue(&list, 5))
        printf("Deleted 5 (head)\n");
    printf("Forward:  "); displayForward(&list);
    printf("Backward: "); displayBackward(&list);

    freeList(&list);
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra -o doublylist doublylist.c
./doublylist

Sample Output

Forward:  Head → 5 → 10 → 20 → 30 → NULL
Backward: NULL ← 30 ← 20 ← 10 ← 5 ← Head
Deleted 20
Forward:  Head → 5 → 10 → 30 → NULL
Deleted 5 (head)
Forward:  Head → 10 → 30 → NULL
Backward: NULL ← 30 ← 10 ← Head

Step-by-Step Trace — Deleting Node 20

Before: [5]↔[10]↔[20]↔[30]
              ↑prev  ↑curr  ↑next

curr = node(20)
curr→prev = node(10)   → node(10)→next = node(20)→next = node(30)
curr→next = node(30)   → node(30)→prev = node(20)→prev = node(10)
free(curr)

After: [5]↔[10]↔[30]   node(20) freed ✓

Compare with singly linked list deletion: to delete node(20) in a singly linked list, you would have to traverse from head to find the predecessor (node(10)) first — O(n). In a doubly linked list, the predecessor is already stored in curr->prev — O(1).

How the Implementation Works

• DList struct (head + tail): keeping a tail pointer makes insertEnd O(1) instead of O(n). Backward traversal starts from tail without needing a full forward pass.
• deleteNode(DList *, Node *): takes a direct pointer to the node — O(1). Four pointer updates cover all cases: node is in the middle, is the head (no prev), or is the tail (no next).
• deleteByValue: O(n) search + O(1) delete. In practice, if you already have a pointer to a node (e.g., in an LRU cache map), you can skip the search entirely.
• Initialise prev = next = NULL: the createNode helper sets both to NULL. Forgetting to NULL prev leaves a dangling pointer on the first node (which should have prev == NULL).

Time and Space Complexity

What This Program Teaches

• Bidirectional linkage: maintaining both prev and next pointers doubles insertion/deletion pointer work but enables O(1) delete-by-pointer — the key advantage over singly linked lists
• Head and tail boundary cases: every insert/delete must check whether the node being added or removed is the head, the tail, or in the middle — three distinct code paths for each
• Struct-of-pointers pattern: wrapping head and tail in a DList struct instead of using two separate global variables keeps the API clean and supports multiple independent lists

Where Doubly Linked Lists Are Used

• Browser history — back/forward navigation through previously visited pages
• LRU cache — O(1) delete-by-pointer + a hash map gives O(1) cache eviction
• Deque (double-ended queue) — insert and remove from both ends in O(1)
• Text editors — undo/redo where each state is a node with prev=undo, next=redo

Related Programs

• Singly Linked List in C — one pointer per node, simpler structure
• Queue Using Linked List in C
• Stack Using Linked List in C
• Binary Search Tree in C

As an Amazon Associate we earn from qualifying purchases.

Recommended Book

Structures and pointers — the building blocks of doubly linked lists — are covered in chapters 5 and 6 of The C Programming Language by Kernighan & Ritchie. Also on Amazon.com.