Doubly Linked List Explained with C Program

📋 Blogger Post — Doubly Linked List Explained with C Program

Click the button to copy the full post HTML, or copy individual code blocks below.

What is a Doubly Linked List?

A Doubly Linked List (DLL) is a linear data structure made up of a sequence of nodes where each node contains three parts:

prev — a pointer to the previous node
data — the actual value stored in the node
next — a pointer to the next node

Unlike a Singly Linked List where traversal is only possible in one direction (forward), a doubly linked list allows traversal in both directions — forward and backward — because each node knows about both its predecessor and its successor.

💡 Key Point: The prev pointer of the first node (head) is always NULL, and the next pointer of the last node (tail) is always NULL.

📊 Doubly Linked List Diagram

NULL ←

⇄

→ NULL

Each node has a prev pointer, a data field, and a next pointer.

Singly Linked List vs Doubly Linked List

Before diving into the implementation, it's important to understand the key differences between a singly and doubly linked list:

Feature	Singly Linked List	Doubly Linked List
Pointers per node	1 (next only)	2 (prev + next)
Traversal direction	Forward only	Forward & Backward
Memory usage	Less	More (extra prev pointer)
Deletion complexity	Needs previous node reference	Easy — node has prev pointer
Insertion complexity	O(1) at head	O(1) at head or tail
Reverse traversal	Not possible	Possible directly
Implementation	Simple	Slightly complex

Node Structure of a Doubly Linked List in C

In C, each node of a doubly linked list is represented using a struct with three members: a prev pointer, a data field, and a next pointer. Here is how we define the node:

C Language — Node Structure

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

// Node structure for Doubly Linked List
struct Node {
    int          data;   // stores the value
    struct Node* prev;   // pointer to previous node
    struct Node* next;   // pointer to next node
};

// Helper: create a new node
struct Node* createNode(int value) {
    struct Node* newNode =
        (struct Node*) malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

🔍 Note: We use malloc() to dynamically allocate memory for each new node on the heap. Always check if malloc() returns NULL to handle memory allocation failure gracefully.

Operations on a Doubly Linked List

A doubly linked list supports the following fundamental operations:

Operation	Description	Time Complexity
Insert at Beginning	Add a new node before the head	O(1)
Insert at End	Add a new node after the tail	O(n) / O(1) with tail ptr
Insert at Position	Add a node at a given index	O(n)
Delete at Beginning	Remove the head node	O(1)
Delete at End	Remove the tail node	O(n) / O(1) with tail ptr
Delete by Value	Find and remove a specific node	O(n)
Forward Traversal	Print list from head to tail	O(n)
Backward Traversal	Print list from tail to head	O(n)
Search	Find a node with a given value	O(n)
Length	Count total number of nodes	O(n)

1. Insert a Node at the Beginning

To insert a node at the beginning, we create a new node, set its next to point to the current head, update the current head's prev to point to the new node, and then move the head pointer to the new node.

This operation is very efficient because no traversal is needed — it always runs in O(1) time.

C Language — Insert at Beginning

// Insert a new node at the beginning of the DLL
void insertAtBeginning(struct Node** head, int value) {
    struct Node* newNode = createNode(value);

    if (*head == NULL) {
        // List is empty — new node becomes the head
        *head = newNode;
        return;
    }

    // Link new node to the current head
    newNode->next        = *head;
    (*head)->prev        = newNode;

    // Move head to the new node
    *head = newNode;

    printf("Inserted %d at beginning.\n", value);
}

2. Insert a Node at the End

To insert at the end, we traverse the list until we reach the last node (where next == NULL), then attach the new node after it. The new node's prev is set to the last node, and the last node's next is updated to point to the new node.

C Language — Insert at End

// Insert a new node at the end of the DLL
void insertAtEnd(struct Node** head, int value) {
    struct Node* newNode = createNode(value);

    if (*head == NULL) {
        // List is empty — new node is the first node
        *head = newNode;
        printf("Inserted %d at end.\n", value);
        return;
    }

    // Traverse to the last node
    struct Node* curr = *head;
    while (curr->next != NULL) {
        curr = curr->next;
    }

    // Attach new node after the last node
    curr->next    = newNode;
    newNode->prev = curr;

    printf("Inserted %d at end.\n", value);
}

3. Insert a Node at a Given Position

To insert at a specific position, we traverse to the node just before the desired position, then re-link the prev and next pointers of the surrounding nodes to include the new node. Position is 1-based (position 1 = beginning).

C Language — Insert at Position

// Insert a new node at a specific position (1-based index)
void insertAtPosition(struct Node** head, int value, int pos) {
    if (pos <= 1) {
        insertAtBeginning(head, value);
        return;
    }

    struct Node* curr = *head;
    for (int i = 1; i < pos - 1 && curr != NULL; i++) {
        curr = curr->next;
    }

    if (curr == NULL) {
        printf("Position out of range.\n");
        return;
    }

    struct Node* newNode  = createNode(value);
    struct Node* nextNode = curr->next;

    // Connect new node
    newNode->prev = curr;
    newNode->next = nextNode;

    // Update surrounding nodes
    curr->next = newNode;
    if (nextNode != NULL) {
        nextNode->prev = newNode;
    }

    printf("Inserted %d at position %d.\n", value, pos);
}

4. Delete a Node from the Doubly Linked List

Deletion in a doubly linked list is more straightforward than in a singly linked list because we can access the previous node directly via the prev pointer — no need to track the predecessor manually during traversal.

🔹 Delete at Beginning

C Language — Delete at Beginning

// Delete the first node (head) of the DLL
void deleteAtBeginning(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty. Nothing to delete.\n");
        return;
    }

    struct Node* temp = *head;
    printf("Deleted: %d from beginning.\n", temp->data);

    *head = (*head)->next;  // move head forward

    if (*head != NULL) {
        (*head)->prev = NULL;  // new head's prev = NULL
    }

    free(temp);
}

🔹 Delete at End

C Language — Delete at End

// Delete the last node (tail) of the DLL
void deleteAtEnd(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty. Nothing to delete.\n");
        return;
    }

    struct Node* curr = *head;

    // Traverse to the last node
    while (curr->next != NULL) {
        curr = curr->next;
    }

    printf("Deleted: %d from end.\n", curr->data);

    if (curr->prev != NULL) {
        // Disconnect second-to-last node from the tail
        curr->prev->next = NULL;
    } else {
        // Only one node existed
        *head = NULL;
    }

    free(curr);
}

🔹 Delete by Value

C Language — Delete by Value

// Delete the first node that contains the given value
void deleteByValue(struct Node** head, int value) {
    if (*head == NULL) {
        printf("List is empty.\n");
        return;
    }

    struct Node* curr = *head;

    // Search for the node
    while (curr != NULL && curr->data != value) {
        curr = curr->next;
    }

    if (curr == NULL) {
        printf("Value %d not found in list.\n", value);
        return;
    }

    // Bypass the node to delete
    if (curr->prev != NULL) {
        curr->prev->next = curr->next;
    } else {
        *head = curr->next;  // deleting the head node
    }

    if (curr->next != NULL) {
        curr->next->prev = curr->prev;
    }

    printf("Deleted node with value: %d\n", value);
    free(curr);
}

5. Traversal — Forward and Backward

One of the biggest advantages of a doubly linked list is the ability to traverse it in both directions. Forward traversal starts at the head and follows next pointers. Backward traversal starts at the tail and follows prev pointers.

C Language — Forward & Backward Traversal

// Forward traversal: head → tail
void traverseForward(struct Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }
    printf("Forward:  NULL <- ");
    struct Node* curr = head;
    while (curr != NULL) {
        printf("%d <-> ", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

// Backward traversal: tail → head
void traverseBackward(struct Node* head) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }

    // First, reach the tail
    struct Node* curr = head;
    while (curr->next != NULL) {
        curr = curr->next;
    }

    // Then traverse backward using prev pointers
    printf("Backward: NULL <- ");
    while (curr != NULL) {
        printf("%d <-> ", curr->data);
        curr = curr->prev;
    }
    printf("NULL\n");
}

6. Search and Length

C Language — Search & Length

// Search for a value — returns position (1-based) or -1
int search(struct Node* head, int value) {
    struct Node* curr = head;
    int pos = 1;

    while (curr != NULL) {
        if (curr->data == value) {
            printf("Found %d at position %d.\n", value, pos);
            return pos;
        }
        curr = curr->next;
        pos++;
    }

    printf("Value %d not found in the list.\n", value);
    return -1;
}

// Returns the number of nodes in the DLL
int getLength(struct Node* head) {
    int count = 0;
    struct Node* curr = head;
    while (curr != NULL) {
        count++;
        curr = curr->next;
    }
    return count;
}

Complete Doubly Linked List Program in C

Below is the full, self-contained C program that combines all operations — node creation, insertion at beginning/end/position, deletion at beginning/end/by value, forward and backward traversal, search, and length — in a single runnable file.

C Language — Complete Doubly Linked List Program

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

/* ── Node structure ── */
struct Node {
    int          data;
    struct Node* prev;
    struct Node* next;
};

/* ── Create a new node ── */
struct Node* createNode(int value) {
    struct Node* n = (struct Node*) malloc(sizeof(struct Node));
    if (!n) { printf("Memory error!\n"); exit(1); }
    n->data = value;
    n->prev = n->next = NULL;
    return n;
}

/* ── Insert at beginning ── */
void insertBegin(struct Node** head, int val) {
    struct Node* n = createNode(val);
    if (*head) { n->next = *head; (*head)->prev = n; }
    *head = n;
    printf("Inserted %d at beginning.\n", val);
}

/* ── Insert at end ── */
void insertEnd(struct Node** head, int val) {
    struct Node* n = createNode(val);
    if (!*head) { *head = n; printf("Inserted %d at end.\n", val); return; }
    struct Node* c = *head;
    while (c->next) c = c->next;
    c->next = n; n->prev = c;
    printf("Inserted %d at end.\n", val);
}

/* ── Insert at position (1-based) ── */
void insertPos(struct Node** head, int val, int pos) {
    if (pos <= 1) { insertBegin(head, val); return; }
    struct Node* c = *head;
    for (int i = 1; i < pos - 1 && c; i++) c = c->next;
    if (!c) { printf("Position out of range.\n"); return; }
    struct Node* n = createNode(val);
    struct Node* nx = c->next;
    n->prev = c; n->next = nx;
    c->next = n;
    if (nx) nx->prev = n;
    printf("Inserted %d at position %d.\n", val, pos);
}

/* ── Delete at beginning ── */
void deleteBegin(struct Node** head) {
    if (!*head) { printf("List is empty.\n"); return; }
    struct Node* t = *head;
    printf("Deleted %d from beginning.\n", t->data);
    *head = t->next;
    if (*head) (*head)->prev = NULL;
    free(t);
}

/* ── Delete at end ── */
void deleteEnd(struct Node** head) {
    if (!*head) { printf("List is empty.\n"); return; }
    struct Node* c = *head;
    while (c->next) c = c->next;
    printf("Deleted %d from end.\n", c->data);
    if (c->prev) c->prev->next = NULL;
    else *head = NULL;
    free(c);
}

/* ── Delete by value ── */
void deleteValue(struct Node** head, int val) {
    struct Node* c = *head;
    while (c && c->data != val) c = c->next;
    if (!c) { printf("Value %d not found.\n", val); return; }
    if (c->prev) c->prev->next = c->next; else *head = c->next;
    if (c->next) c->next->prev = c->prev;
    printf("Deleted node with value %d.\n", val);
    free(c);
}

/* ── Forward traversal ── */
void forwardTraversal(struct Node* head) {
    printf("Forward:  NULL <-> ");
    while (head) { printf("%d <-> ", head->data); head = head->next; }
    printf("NULL\n");
}

/* ── Backward traversal ── */
void backwardTraversal(struct Node* head) {
    if (!head) { printf("List is empty.\n"); return; }
    struct Node* c = head;
    while (c->next) c = c->next;
    printf("Backward: NULL <-> ");
    while (c) { printf("%d <-> ", c->data); c = c->prev; }
    printf("NULL\n");
}

/* ── Search ── */
int search(struct Node* head, int val) {
    int pos = 1;
    while (head) {
        if (head->data == val) {
            printf("Found %d at position %d.\n", val, pos);
            return pos;
        }
        head = head->next; pos++;
    }
    printf("Value %d not found.\n", val);
    return -1;
}

/* ── Length ── */
int length(struct Node* head) {
    int cnt = 0;
    while (head) { cnt++; head = head->next; }
    return cnt;
}

/* ── Free all nodes ── */
void freeList(struct Node** head) {
    struct Node* c = *head;
    while (c) {
        struct Node* nx = c->next;
        free(c);
        c = nx;
    }
    *head = NULL;
}

/* ════════════════════════════════════════
   MAIN — Demo of all operations
   ════════════════════════════════════════ */
int main() {
    struct Node* head = NULL;

    printf("=== Doubly Linked List in C ===\n\n");

    // Insertions
    printf("-- Insertions --\n");
    insertEnd(&head, 10);
    insertEnd(&head, 20);
    insertEnd(&head, 30);
    insertEnd(&head, 40);
    insertBegin(&head, 5);
    insertPos(&head, 25, 4);

    printf("\n-- Traversal --\n");
    forwardTraversal(head);
    backwardTraversal(head);

    printf("\nList length: %d\n", length(head));

    printf("\n-- Search --\n");
    search(head, 25);
    search(head, 99);

    printf("\n-- Deletions --\n");
    deleteBegin(&head);
    deleteEnd(&head);
    deleteValue(&head, 25);

    printf("\n-- Final List --\n");
    forwardTraversal(head);
    printf("List length: %d\n", length(head));

    freeList(&head);
    printf("\nAll memory freed successfully.\n");

    return 0;
}

📤 Expected Output

Output

=== Doubly Linked List in C ===

-- Insertions --
Inserted 10 at end.
Inserted 20 at end.
Inserted 30 at end.
Inserted 40 at end.
Inserted 5 at beginning.
Inserted 25 at position 4.

-- Traversal --
Forward:  NULL <-> 5 <-> 10 <-> 20 <-> 25 <-> 30 <-> 40 <-> NULL
Backward: NULL <-> 40 <-> 30 <-> 25 <-> 20 <-> 10 <-> 5 <-> NULL

List length: 6

-- Search --
Found 25 at position 4.
Value 99 not found.

-- Deletions --
Deleted 5 from beginning.
Deleted 40 from end.
Deleted node with value 25.

-- Final List --
Forward:  NULL <-> 10 <-> 20 <-> 30 <-> NULL
List length: 3

All memory freed successfully.

Bonus: Reverse a Doubly Linked List in C

Reversing a doubly linked list is a commonly asked interview question. The idea is simple — for every node, swap its prev and next pointers. After processing all nodes, the head pointer is updated to the last node (which is now the new first node).

C Language — Reverse a Doubly Linked List

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

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

struct Node* createNode(int v) {
    struct Node* n = (struct Node*) malloc(sizeof(struct Node));
    n->data = v; n->prev = n->next = NULL; return n;
}

void insertEnd(struct Node** h, int v) {
    struct Node* n = createNode(v);
    if (!*h) { *h = n; return; }
    struct Node* c = *h;
    while (c->next) c = c->next;
    c->next = n; n->prev = c;
}

void printList(struct Node* h) {
    printf("List: NULL <-> ");
    while (h) { printf("%d <-> ", h->data); h = h->next; }
    printf("NULL\n");
}

// Reverse the doubly linked list by swapping prev and next of every node
void reverseList(struct Node** head) {
    struct Node* curr = *head;
    struct Node* temp = NULL;

    // Swap prev and next for every node
    while (curr != NULL) {
        temp        = curr->prev;
        curr->prev = curr->next;
        curr->next = temp;
        curr        = curr->prev;  // move to what was next
    }

    // Update head to the last processed node (new first node)
    if (temp != NULL) {
        *head = temp->prev;
    }
}

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

    insertEnd(&head, 10);
    insertEnd(&head, 20);
    insertEnd(&head, 30);
    insertEnd(&head, 40);

    printf("Before reversing:\n");
    printList(head);

    reverseList(&head);

    printf("After reversing:\n");
    printList(head);

    return 0;
}

📤 Output

Output

Before reversing:
List: NULL <-> 10 <-> 20 <-> 30 <-> 40 <-> NULL
After reversing:
List: NULL <-> 40 <-> 30 <-> 20 <-> 10 <-> NULL

Real-World Applications of Doubly Linked List

Doubly linked lists are used in many real-world systems where bidirectional access, easy deletion, and dynamic sizing are required:

🌐 Browser Navigation
The forward and back history in web browsers is implemented using a doubly linked list — each page has a link to both the previous and next page.

↩️ Undo / Redo Feature
Applications like MS Word and VS Code maintain a doubly linked list of actions — undo moves backward, redo moves forward.

🎵 Music Playlists
Music players implement playlists as a doubly linked list — previous song and next song buttons traverse in both directions.

🧠 LRU Cache
The Least Recently Used cache eviction policy uses a doubly linked list combined with a hash map for O(1) insertion and deletion.

🖥️ Operating System Scheduler
OS task schedulers use doubly linked lists to manage the process queue and efficiently insert/remove processes.

📖 Text Editors
Text editors maintain the document as a doubly linked list of lines so that inserting and deleting lines is efficient in both directions.

Time & Space Complexity Analysis

Here is the complete complexity analysis for all doubly linked list operations:

Operation	Time Complexity	Space Complexity	Notes
Insert at Beginning	O(1)	O(1)	No traversal needed
Insert at End	O(n)	O(1)	O(1) with tail pointer
Insert at Position	O(n)	O(1)	Traversal to position
Delete at Beginning	O(1)	O(1)	No traversal needed
Delete at End	O(n)	O(1)	O(1) with tail pointer
Delete by Value	O(n)	O(1)	Search + delete
Forward Traversal	O(n)	O(1)	Visit every node once
Backward Traversal	O(n)	O(1)	Go to tail first
Search	O(n)	O(1)	Linear scan
Reverse	O(n)	O(1)	Swap prev/next in-place
Space per Node	—	O(1)	data + prev + next
Total Space (n nodes)	—	O(n)	n nodes on heap

⚠️ Memory Note: Each node in a doubly linked list uses more memory than a singly linked list node because of the extra prev pointer. On a 64-bit system, each pointer is 8 bytes, so each DLL node uses 8 (data) + 8 (prev) + 8 (next) = 24 bytes minimum.

Conclusion

In this tutorial, we covered the Doubly Linked List data structure completely with working C programs:

✅ We understood the structure of a DLL node — prev, data, next
✅ We compared Singly vs Doubly Linked List with a detailed table
✅ We implemented Insert at Beginning, End, and Position
✅ We implemented Delete at Beginning, End, and by Value
✅ We wrote both Forward and Backward Traversal functions
✅ We implemented Search and Length functions
✅ We built a complete, self-contained full DLL program in C
✅ We solved the Reverse a DLL bonus interview problem
✅ We explored all real-world applications of doubly linked lists
✅ We analyzed Time & Space Complexity for every operation

The Doubly Linked List is a powerful and flexible data structure. Its bidirectional traversal capability makes it far more versatile than a singly linked list in many practical scenarios like browser history, undo/redo systems, and LRU caches.

📌 What's Next? After mastering Doubly Linked Lists, explore Circular Linked Lists, Binary Trees, and Hash Maps to continue your data structures journey!

✅ Copied to clipboard!

Doubly linked list explained with c program.