Doubly Linked Lists Explained

A doubly linked list is a linked list where each node stores two pointers: one to the next node and one to the previous node. That extra backward link lets you walk the list in either direction and, more importantly, delete any node you already hold in O(1) time, without first searching for its predecessor.

What the extra pointer buys you

In a singly linked list, to delete a node you must know the node before it so you can re-route the next pointer around the deleted node. Finding that predecessor takes a walk from the head — O(n). A doubly linked list already stores a prev pointer in every node, so given any node you can immediately reach both its neighbours and splice it out in constant time.

You also gain two-way traversal: you can iterate from head to tail using next, or from tail to head using prev. Many implementations keep both a head and a tail pointer for this reason.

Building a doubly linked list

#include <iostream>
using namespace std;

// Each node links to both its neighbours.
struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};

// Insert a value at the front. Returns the new head. O(1).
Node* insertAtHead(Node* head, int value) {
    Node* node = new Node(value);
    node->next = head;            // new node points forward to old head
    if (head != nullptr) {
        head->prev = node;        // old head points back to new node
    }
    return node;                  // new node is the head
}

// Delete a node we already hold, in O(1).
// Returns the (possibly new) head of the list.
Node* deleteNode(Node* head, Node* target) {
    if (target->prev != nullptr) {
        target->prev->next = target->next; // skip target going forward
    } else {
        head = target->next;               // target was the head
    }
    if (target->next != nullptr) {
        target->next->prev = target->prev; // skip target going backward
    }
    delete target;                         // free the memory
    return head;
}

void printForward(Node* head) {
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        cout << cur->data << " <-> ";
    }
    cout << "null" << endl;
}

int main() {
    Node* head = nullptr;
    head = insertAtHead(head, 30);
    head = insertAtHead(head, 20);
    head = insertAtHead(head, 10);
    printForward(head);                 // 10 <-> 20 <-> 30 <-> null
    head = deleteNode(head, head->next); // delete the node holding 20
    printForward(head);                 // 10 <-> 30 <-> null
    return 0;
}

The deletion logic touches only the target and its two neighbours, so it is genuinely O(1) once you have the node — something a singly linked list cannot promise.

Costs and trade-offs

The price is one extra pointer per node and more bookkeeping: every insert and delete must keep both next and prev consistent. Get one wrong and the chain breaks.

Where they are used

Doubly linked lists power structures where you remove elements from arbitrary positions cheaply: LRU caches (move-to-front, evict-from-back), browser history (back and forward), text editors, and the underlying nodes of many standard library list types. The two-way structure is also the natural backbone for a deque-style container.

Common mistakes

• Updating only one direction. When you insert or delete, both the forward and backward links of the affected nodes must change. Updating next but forgetting prev silently corrupts the list.
• Null neighbour assumptions. The head has no prev and the tail has no next. Always guard against null before dereferencing a neighbour.
• Double-free on delete. Deleting a node and then traversing through a stale pointer to it causes crashes. Re-link first, free last, and stop using the freed pointer.
• Ignoring the tail pointer. If you maintain a tail for O(1) back-end operations, remember to update it when you delete the last node.

Keep learning

Compare this with the simpler singly linked list, see how these nodes back a queue, and browse the full DSA hub for the bigger picture.

Want to build these structures with instructor support in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.