4.3 ~50 min medium

Doubly Linked List

Each node points both forward and backward. You can walk in both directions and delete a node knowing only its address, at the cost of one extra pointer per node.

Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.

02Mental model

A train: every carriage is coupled to the one in front and the one behind. You can walk through the train in either direction, and to unhook a carriage you only need that carriage, because it knows both neighbours.

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

We usually keep both head and tail, which makes inserting and deleting at either end O(1).

Updating both directions

Every insert or delete updates up to four pointers. A safe order for inserting n between A and B:

n->prev = A; n->next = B; (the new node first; nothing is lost yet)
A->next = n; B->prev = n;

For deleting cur: cur->prev->next = cur->next; and cur->next->prev = cur->prev;, and check for nullptr at the head and the tail.

When to use it

Browser back/forward history, music playlists (previous/next), undo/redo, and any “delete this node now” situation. Pay the extra pointer when you need to move backwards.

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

Delete a middle node and watch two arrows change. Then print backward from the tail.

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

doubly-linked-list.cpp60 lines · C++17

Compiler ExplorerRun OnlineGDB

#include <iostream>
using namespace std;

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

void insertFront(DNode*& head, DNode*& tail, int x) {
    DNode* n = new DNode{x, nullptr, head};
    if (head != nullptr) head->prev = n;
    else tail = n;
    head = n;
}

void insertEnd(DNode*& head, DNode*& tail, int x) {
    DNode* n = new DNode{x, tail, nullptr};
    if (tail != nullptr) tail->next = n;
    else head = n;
    tail = n;
}

void deleteValue(DNode*& head, DNode*& tail, int x) {
    DNode* cur = head;
    while (cur != nullptr && cur->data != x) cur = cur->next;
    if (cur == nullptr) return;
    if (cur->prev) cur->prev->next = cur->next;
    else head = cur->next;
    if (cur->next) cur->next->prev = cur->prev;
    else tail = cur->prev;
    delete cur;
}

void printForward(DNode* head) {
    for (DNode* c = head; c != nullptr; c = c->next) cout << c->data << " ";
    cout << "\n";
}

void printBackward(DNode* tail) {
    for (DNode* c = tail; c != nullptr; c = c->prev) cout << c->data << " ";
    cout << "\n";
}

int main() {
    DNode* head = nullptr;
    DNode* tail = nullptr;
    insertEnd(head, tail, 10);
    insertEnd(head, tail, 20);
    insertEnd(head, tail, 30);
    insertFront(head, tail, 5);
    cout << "forward:  "; printForward(head);
    cout << "backward: "; printBackward(tail);
    deleteValue(head, tail, 20);   // middle
    deleteValue(head, tail, 30);   // tail
    cout << "after deletes: "; printForward(head);
    cout << "tail is now " << tail->data << "\n";
    while (head) deleteValue(head, tail, head->data);
    cout << "empty: " << (head == nullptr && tail == nullptr ? "yes" : "no") << "\n";
}

#include <iostream>
using namespace std;

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

void insertFront(DNode*& head, DNode*& tail, int x) {
    DNode* n = new DNode{x, nullptr, head};
    if (head != nullptr) head->prev = n;
    else tail = n;
    head = n;
}

void insertEnd(DNode*& head, DNode*& tail, int x) {
    DNode* n = new DNode{x, tail, nullptr};
    if (tail != nullptr) tail->next = n;
    else head = n;
    tail = n;
}

void deleteValue(DNode*& head, DNode*& tail, int x) {
    DNode* cur = head;
    while (cur != nullptr && cur->data != x) cur = cur->next;
    if (cur == nullptr) return;
    if (cur->prev) cur->prev->next = cur->next;
    else head = cur->next;
    if (cur->next) cur->next->prev = cur->prev;
    else tail = cur->prev;
    delete cur;
}

void printForward(DNode* head) {
    for (DNode* c = head; c != nullptr; c = c->next) cout << c->data << " ";
    cout << "\n";
}

void printBackward(DNode* tail) {
    for (DNode* c = tail; c != nullptr; c = c->prev) cout << c->data << " ";
    cout << "\n";
}

int main() {
    DNode* head = nullptr;
    DNode* tail = nullptr;
    insertEnd(head, tail, 10);
    insertEnd(head, tail, 20);
    insertEnd(head, tail, 30);
    insertFront(head, tail, 5);
    cout << "forward:  "; printForward(head);
    cout << "backward: "; printBackward(tail);
    deleteValue(head, tail, 20);   // middle
    deleteValue(head, tail, 30);   // tail
    cout << "after deletes: "; printForward(head);
    cout << "tail is now " << tail->data << "\n";
    while (head) deleteValue(head, tail, head->data);
    cout << "empty: " << (head == nullptr && tail == nullptr ? "yes" : "no") << "\n";
}

Expected output

forward:  5 10 20 30 
backward: 30 20 10 5 
after deletes: 5 10 
tail is now 10
empty: yes

05Complexity

Insert / delete at front or end (with tail)	O(1)
Delete a node you already have a pointer to	O(1): no need to find prev
Search / delete by value	O(n)
Traverse backward	O(n): impossible in a singly list without extra memory
Extra space	O(n), with 2 pointers per node

The trade-off: more memory and more pointers to update (4 instead of 2 on insert), in exchange for two-way movement.

06Watch

Introduction to Doubly Linked List

mycodeschool · 7:12

Why this one: A short intro to the node structure and insert/print in both directions.

Watched

Linked List: Implementation in C/C++

mycodeschool · 13:58

Why this one: Revisit the singly version first if the pointer updates feel shaky.

Watched

Original class slides (Python, by the course's lecture authors):Linked List

07Exam lens

Likely questions

Write the node structure of a doubly linked list.
Write a function to insert a node at the front of a doubly linked list.
Write a function to delete a given node from a doubly linked list.
Compare singly and doubly linked lists.

Common mistakes

Updating next but forgetting prev (or the reverse). Each insert or delete touches both directions.
Forgetting cur->next->prev when cur->next is nullptr (deleting the tail) → crash.
Not updating tail when deleting the last node.

08Quick check

1.Deleting node cur from the middle requires:
2.Main advantage over a singly linked list?
3.In a list 5 ⇄ 10 ⇄ 20 with tail at 20, after inserting 30 at the end, tail->prev->data is…

09Practice

🟢 Trace by hand

Start empty. insertFront 10, insertEnd 20, insertFront 5, delete 10. Write all prev and next pointers at the end.

Show answer

Final list: 5 ⇄ 20.

5: prev = null, next = 20
20: prev = 5, next = null
head = 5, tail = 20

🟡 Implement it

Write insertAfter(DNode* node, int x) that inserts a new node right after node (update the tail if needed).

Hint

Four pointers to set (n->prev, n->next, node->next, and the old next's prev). Do the new node's pointers first.

Solution

void insertAfter(DNode*& tail, DNode* node, int x) {
    DNode* n = new DNode{x, node, node->next};
    if (node->next) node->next->prev = n;
    else tail = n;
    node->next = n;
}

🔴 Solve problems

Design Linked List mediumleetcode.com
Hint
Implement it again, doubly linked, with dummy head AND dummy tail. All the edge cases vanish.
Palindrome Linked List easyleetcode.com
Hint
With prev pointers you could walk from both ends. With a singly list, use fast & slow pointers and reverse the second half (see Level Up).

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

I can write the DNode struct.
I can insert at the front and end, updating prev, next, head and tail.
I can delete any node, including the head and tail.
I can compare singly and doubly linked lists.

0/4 ticked

My notes

View as Markdown · Chapter cheat sheet