# 4.3 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.

Chapter: Linked Lists · ~50 min · medium
URL: https://dsa.fetehadin.com/learn/doubly-linked-list

## Mental 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.

```cpp
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`:

1. `n->prev = A; n->next = B;` (the new node first; nothing is lost yet)
2. `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.

## C++ code: doubly-linked-list.cpp

```cpp
#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:

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

## Complexity

| Case | Cost |
| --- | --- |
| 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 |

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.

## Videos

- [Introduction to Doubly Linked List](https://youtu.be/JdQeNxWCguQ) (mycodeschool): A short intro to the node structure and insert/print in both directions.
- [Linked List: Implementation in C/C++](https://youtu.be/vcQIFT79_50) (mycodeschool): Revisit the singly version first if the pointer updates feel shaky.

## Exam 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.

## Quick check

1. Deleting node `cur` from the middle requires:
   A. `cur->prev->next = cur->next;` only
   B. `cur->next->prev = cur->prev;` only
   C. both of the above, then `delete cur`
   D. `delete cur` only
   Answer: C. Both neighbours must skip over cur.

2. Main advantage over a singly linked list?
   A. Less memory
   B. Traversal in both directions and O(1) delete given the node
   C. Faster search
   D. Random access
   Answer: B. It knows its own predecessor.

3. In a list 5 ⇄ 10 ⇄ 20 with tail at 20, after inserting 30 at the end, `tail->prev->data` is…
   A. 10
   B. 20
   C. 30
   D. 5
   Answer: B. 30 is now tail; its prev is 20.

## Practice

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

Solution:

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.

```cpp
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;
}
```


**Problems:**

- [Design Linked List](https://leetcode.com/problems/design-linked-list/) (medium). Hint: Implement it again, doubly linked, with dummy head AND dummy tail. All the edge cases vanish.
- [Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/) (easy). 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).

## Mastery checklist

- [ ] 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.