The Doubly Linked List: A Two-Way Chain

The Doubly Linked List: A Two-Way Chain

A regular (singly) linked list is a chain of boxes, where each box only knows about the next box. This one-way design causes a problem: if you are standing at one box and want to go backward, you can't. You would have to start from the very beginning of the list and walk forward again. That wastes time. The doubly linked list is a clever fix for this.

What is a doubly linked list?

A doubly linked list is a chain of boxes (we call each box a node) that stores data in order. The nodes are not lined up neatly in memory; they sit at random spots and are connected by links. The list is also dynamic, which simply means it can grow or shrink while the program runs.

The big difference is this: each node stores two links instead of one.

• A link to the next node (the one in front of it).
• A link to the previous node (the one behind it).

Because every node knows both its neighbors, you can walk through the list in both directions — forward and backward. That is why we call it *bidirectional*. Think of a train where every carriage is connected to the carriage in front of it *and* the carriage behind it, so you can walk either way through the train.

A small example list looks like this: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5. The very first node is called the head, and the very last node is called the tail.

Why is this useful? (Advantages)

1. You can travel both ways. You can go from the head to the tail, and also from the tail back to the head. A singly linked list can only go one way.

2. Insertion is fast. Suppose someone hands you a node and says "insert a new value just before this one." In a doubly linked list, the node already knows who its previous neighbor is, so you can slot in the new node right away. You don't need to search from the start to find the node behind it.

3. Deletion is fast. The same idea applies to removing nodes. If you are given a node's address, you can insert or delete in O(1) time and O(1) space — meaning the work takes the same tiny, fixed amount of effort no matter how long the list is. The key reason: *insertion and deletion before the given node do not require traversal.* You never have to walk the list to find the previous node, because the node already remembers it.

A worked example: deleting the node before a given node

Let's delete a node from the list 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ↔ 6. Imagine someone points to node 5 and calls it the given node. We want to remove node 4, which sits just before it.

• Step 1 — Get the previous node. Because node 5 stores a backward link, we can *instantly* reach node 4. We call this prev. No searching needed — this is the magic of the second link.
• Step 2 — Update the pointer of the previous node. Node 3 (the node before 4) should now point forward to node 6 instead of to node 4. We re-route that forward link so it skips over 4.
• Step 3 — Update the pointer of the next node. Node 6 should now point backward to node 3 instead of to node 4. We re-route that backward link too.
• Step 4 — Delete the given node. Node 4 is now completely bypassed — nothing points to it anymore. We can safely remove it and free its memory.

The result is the clean list 1 ↔ 2 ↔ 3 ↔ 6. Notice that nodes 3 and 6 are now directly connected in both directions. Removing the node took just a few pointer changes, with no walking through the list.

The trade-offs (Limitations)

Nothing comes for free. The doubly linked list pays a small price for its extra power:

• Extra memory. Every node must store one more link (the backward one). Across thousands of nodes, that adds up to noticeably more memory than a singly linked list.
• More complicated to manage. Because there are two links per node, the programmer has more pointers to keep correct. Every time you insert or delete, you must update *both* the forward and backward links. Forget one, and the chain breaks.

In short: a doubly linked list trades a little extra memory and care for the big benefit of moving and editing in both directions quickly. It is the natural upgrade to use when a singly linked list's one-way design slows you down.