C Doubly Linked Lists

A doubly linked list is a chain of dynamically allocated nodes where each node stores a piece of data plus two pointers: one to the next node and one to the previous node. Unlike a singly linked list, which can only be walked in one direction, a doubly linked list can be traversed forward and backward, and a node can be removed in constant time once you have a pointer to it, without having to search for its predecessor. This makes doubly linked lists the backbone of many real-world structures, such as text editor undo buffers, LRU caches, and deque implementations.

Overview / How it works

Every node in a doubly linked list is a small struct containing the payload and two self-referential pointers:

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

Each node is allocated individually on the heap with malloc, so the nodes are not contiguous in memory the way an array’s elements are. The list itself is usually represented by a head pointer (the first node) and, optionally, a tail pointer (the last node) to make appends and backward traversal efficient without walking the whole list first.

The two pointers per node are what give the structure its power and its cost. The power: from any node you can move in either direction, and deleting a node only requires patching its two neighbors’ pointers — you never need to “look back” the way you do in a singly linked list. The cost: every node uses extra memory for the second pointer, and every insertion or deletion has twice as many pointer assignments to get right, which is exactly where most bugs creep in.

Conceptually, a doubly linked list of 30, 20, 10 looks like this:

NULL <- [30] <-> [20] <-> [10] -> NULL
        prev/next   prev/next   prev/next

The head node’s prev is NULL and the tail node’s next is NULL. These two NULL pointers mark the boundaries of the list, and checking for them correctly is the single most important habit when writing doubly linked list code.

Syntax

There is no special C keyword for a doubly linked list — you build it from a self-referential struct and a set of functions that manipulate pointers. The general shape of every list operation is:

struct Node* createNode(int data);                              // allocate + init one node
struct Node* insertAtHead(struct Node *head, int data);          // add to the front
void insertAtEnd(struct Node **head, struct Node **tail, int d); // add to the back
void deleteNode(struct Node **head, struct Node **tail, int v);  // remove by value
void printForward(struct Node *head);                            // walk head -> tail
void printBackward(struct Node *tail);                           // walk tail -> head

Part	Meaning
struct Node *prev	Pointer to the previous node, or NULL if this is the head
struct Node *next	Pointer to the next node, or NULL if this is the tail
struct Node **head	Pointer-to-pointer, needed so a function can change which node the caller’s head variable points to
malloc(sizeof(struct Node))	Allocates one node’s worth of memory on the heap
free(node)	Releases a node’s memory once it is unlinked from the list

Examples

Example 1: Building a list with head insertion and traversing both ways

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

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

struct Node* createNode(int data) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

struct Node* insertAtHead(struct Node *head, int data) {
    struct Node *newNode = createNode(data);
    newNode->next = head;
    if (head != NULL) {
        head->prev = newNode;
    }
    return newNode;
}

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

void printBackward(struct Node *tail) {
    struct Node *current = tail;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->prev != NULL) {
            printf(" <-> ");
        }
        current = current->prev;
    }
    printf("\n");
}

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

    head = insertAtHead(head, 10);
    head = insertAtHead(head, 20);
    head = insertAtHead(head, 30);

    printf("Forward:  ");
    printForward(head);

    struct Node *tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }

    printf("Backward: ");
    printBackward(tail);

    struct Node *current = head;
    while (current != NULL) {
        struct Node *toFree = current;
        current = current->next;
        free(toFree);
    }

    return 0;
}

Output:

Forward:  30 <-> 20 <-> 10
Backward: 10 <-> 20 <-> 30

Each call to insertAtHead creates a new node, points its next at the current head, and — crucially — updates the old head’s prev to point back at the new node. Because the same list is walked in both directions and produces mirrored output, you can see that the prev and next pointers are consistent with each other.

Example 2: Appending and deleting by value

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

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

struct Node* createNode(int data) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

void insertAtEnd(struct Node **head, struct Node **tail, int data) {
    struct Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        *tail = newNode;
        return;
    }
    newNode->prev = *tail;
    (*tail)->next = newNode;
    *tail = newNode;
}

void deleteNode(struct Node **head, struct Node **tail, int value) {
    struct Node *current = *head;
    while (current != NULL && current->data != value) {
        current = current->next;
    }
    if (current == NULL) {
        printf("Value %d not found\n", value);
        return;
    }
    if (current->prev != NULL) {
        current->prev->next = current->next;
    } else {
        *head = current->next;
    }
    if (current->next != NULL) {
        current->next->prev = current->prev;
    } else {
        *tail = current->prev;
    }
    free(current);
}

void printForward(struct Node *head) {
    struct Node *current = head;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL) printf(" -> ");
        current = current->next;
    }
    printf("\n");
}

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

    insertAtEnd(&head, &tail, 10);
    insertAtEnd(&head, &tail, 20);
    insertAtEnd(&head, &tail, 30);
    insertAtEnd(&head, &tail, 40);

    printf("Before deletion: ");
    printForward(head);

    deleteNode(&head, &tail, 30);
    printf("After deleting 30: ");
    printForward(head);

    deleteNode(&head, &tail, 10);
    printf("After deleting 10: ");
    printForward(head);

    deleteNode(&head, &tail, 99);

    struct Node *current = head;
    while (current != NULL) {
        struct Node *toFree = current;
        current = current->next;
        free(toFree);
    }

    return 0;
}

Output:

Before deletion: 10 -> 20 -> 30 -> 40
After deleting 30: 10 -> 20 -> 40
After deleting 10: 20 -> 40
Value 99 not found

This example maintains both head and tail pointers via double pointers (struct Node **) so that insertAtEnd and deleteNode can update the caller’s variables. deleteNode handles four cases implicitly: deleting the only node, deleting the head, deleting the tail, and deleting a middle node — by checking whether prev and next are NULL before dereferencing them.

Example 3: Keeping a list sorted as you insert (student scores)

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

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

struct Node* createNode(int data) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

struct Node* insertSorted(struct Node *head, int data) {
    struct Node *newNode = createNode(data);

    if (head == NULL || data <= head->data) {
        newNode->next = head;
        if (head != NULL) {
            head->prev = newNode;
        }
        return newNode;
    }

    struct Node *current = head;
    while (current->next != NULL && current->next->data < data) {
        current = current->next;
    }

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

    return head;
}

void printForward(struct Node *head) {
    struct Node *current = head;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL) printf(", ");
        current = current->next;
    }
    printf("\n");
}

int main(void) {
    struct Node *head = NULL;
    int scores[] = {72, 55, 91, 68, 84, 55};
    int n = sizeof(scores) / sizeof(scores[0]);

    for (int i = 0; i < n; i++) {
        head = insertSorted(head, scores[i]);
    }

    printf("Sorted ascending: ");
    printForward(head);

    struct Node *tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }

    printf("Sorted descending: ");
    struct Node *current = tail;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->prev != NULL) printf(", ");
        current = current->prev;
    }
    printf("\n");

    current = head;
    while (current != NULL) {
        struct Node *toFree = current;
        current = current->next;
        free(toFree);
    }

    return 0;
}

Output:

Sorted ascending: 55, 55, 68, 72, 84, 91
Sorted descending: 91, 84, 72, 68, 55, 55

insertSorted walks forward from the head only until it finds the correct spot, then splices the new node in using both prev and next pointers. Because the list stays sorted, printing it backward from the tail (found once by walking to the end) automatically produces the descending order — a nice demonstration of why keeping a tail pointer, or at least being able to find it cheaply, matters.

Under the hood

When you call malloc(sizeof(struct Node)), the operating system’s heap allocator carves out a block of memory just big enough for one data, one prev, and one next. Nothing guarantees that consecutively created nodes sit next to each other in memory — each one could be anywhere in the heap. That is precisely why the pointers exist: they are the only thing tying the nodes together into a sequence.

A pointer assignment like newNode->next = current->next; simply copies a memory address (a number) from one struct field into another; it does not copy or move any node. Insertion and deletion are therefore O(1) once you already hold a pointer to the relevant node, because they only rewire a fixed number of addresses — no shifting of elements the way an array insertion would require.

Traversal, by contrast, is O(n): to reach the k-th node you must follow next k times starting from head (or prev from tail), because there is no arithmetic shortcut like array indexing (arr[k]) for a linked structure. This is the central trade-off of linked lists versus arrays: cheap insert/delete, expensive random access.

Common Mistakes

Mistake 1 — forgetting to update the neighbor’s back-pointer. It is easy to fix next pointers and forget prev, silently corrupting backward traversal.

// Wrong: only relinks next, leaves current->next->prev dangling
current->prev->next = current->next;
free(current);

// Correct: also fix the following node's prev pointer
current->prev->next = current->next;
if (current->next != NULL) {
    current->next->prev = current->prev;
}
free(current);

Mistake 2 — freeing a node before reading the pointer you need next. If you free(current) and then use current->next, you dereference freed memory (undefined behavior).

// Wrong: uses current after it has been freed
free(current);
current = current->next;

// Correct: save the next pointer first
struct Node *next = current->next;
free(current);
current = next;

Mistake 3 — not special-casing the head or tail during deletion. Assuming every node has a non-NULL prev and next crashes when deleting the first or last node, because dereferencing NULL->next is undefined behavior.

Best Practices

• Always check malloc‘s return value before writing into a new node.
• Maintain a tail pointer if you frequently append or need backward traversal, so you don’t have to walk the whole list to find the end.
• When deleting, update both the previous node’s next and the next node’s prev (guarding each with a NULL check).
• Save the pointer you need for the next iteration before calling free on the current node.
• Free every node before the program exits, or before the list variable goes out of scope, to avoid memory leaks.
• Write small helper functions (insertAtHead, insertAtEnd, deleteNode) instead of duplicating pointer-juggling logic throughout your program.
• Use struct Node **head (a pointer to the head pointer) in any function that must be able to change what the caller’s head variable points to.

Practice Exercises

• Write a function struct Node* reverseList(struct Node *head) that reverses a doubly linked list in place by swapping each node’s prev and next pointers, and returns the new head (the old tail).
• Write a function int search(struct Node *head, int value) that returns 1 if a value exists in the list and 0 otherwise, then extend it to return the zero-based index of the first match, or -1 if not found.
• Extend Example 2’s deleteNode into a freeList(struct Node *head) function that frees every remaining node, then call it at the end of a program that builds a 5-node list and deletes two nodes from the middle.

Summary

• A doubly linked list node stores data plus prev and next pointers, allowing traversal in both directions.
• The head node’s prev and the tail node’s next are always NULL — checking for them correctly is essential.
• Insertion and deletion are O(1) once you have a pointer to the target node, because only pointers are rewired, not data shifted.
• Traversal and search are O(n), since each node must be reached by following pointers from a known starting point.
• Deleting a node requires patching up to two neighbors and freeing the node’s memory in the right order to avoid dangling pointers and leaks.
• Keeping a tail pointer alongside head makes appends and backward traversal efficient.