Doubly Linked Lists

A doubly linked list extends the singly linked list by giving every node a second pointer, prev, that points back to the previous node. This extra pointer costs a small amount of memory per node, but it unlocks backward traversal and much cheaper removal of a node when you already have a pointer to it.

The Node Structure

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

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

Why Bother with a Second Pointer?

Backward traversal — you can walk from any node toward the head without restarting from the front.
O(1) removal given a node pointer — a singly linked list needs the previous node to unlink a target node, which normally means an O(n) search for it; a doubly linked list already has that pointer stored on the node itself.
Easier insertion before a given node — you do not need a separate pass to find its predecessor.

Operation	Singly Linked	Doubly Linked
Traverse forward	O(n)	O(n)
Traverse backward	Not possible directly	O(n)
Remove a node you have a pointer to	O(n) — must find its predecessor	O(1) — predecessor is node->prev
Memory per node	One pointer	Two pointers

Inserting at the Head

Node *create_node(int value) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(EXIT_FAILURE);
    }
    node->data = value;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

void push_front(Node **head, int value) {
    Node *node = create_node(value);
    node->next = *head;

    if (*head != NULL) {
        (*head)->prev = node; /* old head's prev must point back at the new node */
    }

    *head = node;
}

Warning

Every insertion or removal in a doubly linked list touches two links, not one. Forgetting to update the prev pointer on the neighboring node (as with (*head)->prev = node above) leaves the list in an inconsistent state — forward traversal may look fine while backward traversal is broken.

Inserting at the Tail

void push_back(Node **head, int value) {
    Node *node = create_node(value);

    if (*head == NULL) {
        *head = node;
        return;
    }

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

    current->next = node;
    node->prev = current;
}

Deleting a Node (Given a Pointer to It)

This is where the doubly linked list shines: since the node already knows both its neighbors, removal does not require searching for the previous node at all.

void delete_node(Node **head, Node *target) {
    if (target->prev != NULL) {
        target->prev->next = target->next;
    } else {
        *head = target->next; /* target was the head */
    }

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

    free(target);
}

Note

Compare this to the singly linked list's delete_value, which had to walk the list from the head just to find the previous node. Here, if you already hold target (perhaps found earlier during a search), removal is O(1) because target->prev and target->next give you both neighbors directly.

Traversing Backward

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

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

Full Compilable Example

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

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

Node *create_node(int value) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(EXIT_FAILURE);
    }
    node->data = value;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

void push_back(Node **head, int value) {
    Node *node = create_node(value);
    if (*head == NULL) {
        *head = node;
        return;
    }
    Node *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = node;
    node->prev = current;
}

Node *find_tail(Node *head) {
    if (head == NULL) return NULL;
    Node *current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    return current;
}

void delete_node(Node **head, Node *target) {
    if (target->prev != NULL) {
        target->prev->next = target->next;
    } else {
        *head = target->next;
    }
    if (target->next != NULL) {
        target->next->prev = target->prev;
    }
    free(target);
}

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

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

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

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

    push_back(&head, 1);
    push_back(&head, 2);
    push_back(&head, 3);

    print_forward(head);              /* 1 <-> 2 <-> 3 <-> NULL */
    print_backward(find_tail(head));  /* 3 <-> 2 <-> 1 <-> NULL */

    delete_node(&head, head->next);   /* remove the node holding 2 */
    print_forward(head);              /* 1 <-> 3 <-> NULL */

    free_list(head);
    return 0;
}

Example

Bash

$ ./dlist

1 <-> 2 <-> 3 <-> NULL
3 <-> 2 <-> 1 <-> NULL
1 <-> 3 <-> NULL

Tip

Many real-world data structures, including the sliding-window deque and the LRU cache, are built on top of a doubly linked list precisely because of its O(1) arbitrary-node removal property.

Summary

A doubly linked node stores next AND prev pointers.
Backward traversal and O(1) removal (given a node pointer) are the main advantages over a singly linked list.
Every insert/delete must carefully update both neighboring links, or the list becomes inconsistent.
The extra prev pointer costs memory per node in exchange for these capabilities.