Introduction to Doubly Linked List (DLL)

This lesson is the starting point for doubly linked lists in C: how they extend the singly linked idea with a backward link, what a DLL node looks like, how memory and traversal differ from SLL, and when the extra pointer per node is worth it. Later DLL lessons cover insert, delete, and complexity in code.

1) What is a doubly linked list?

A doubly linked list (DLL) is still a linear sequence of nodes, like a singly linked list. The difference is that each node stores two pointers: one to the next node and one to the previous node. That lets you walk the list forward and backward from any node without rescanning from the head.

Programs often keep a head pointer to the first node and sometimes a tail pointer to the last node for O(1) access to both ends. The first node’s prev and the last node’s next are usually NULL in a non-circular DLL (a circular variant can link them into a ring—see Types of Linked List for the big picture).

2) DLL vs singly linked list (mental model)

In an SLL, each node only knows “who is next.” To remove the last node, or to insert before a node you only have a handle to, you often need an extra scan to find the predecessor. In a DLL, node->prev is that predecessor (when it exists), which simplifies many operations at the cost of one more pointer per node and more pointer updates when you splice nodes in or out.

Memory picture: singly vs doubly (same values 10 → 20 → 30)

Arrows show next; dashed lines show prev (conceptually):

SINGLY (one direction per node)
  head
    │
    ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ data: 10     │    │ data: 20     │    │ data: 30     │
│ next ────────┼───→│ next ────────┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘

DOUBLY (forward + backward)
  head                                              tail (optional)
    │                                                  │
    ▼                                                  ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ prev: NULL   │←──→│ prev         │←──→│ prev         │
│ data: 10     │    │ data: 20     │    │ data: 30     │
│ next ────────┼───→│ next ────────┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘

3) What is a node in a DLL?

A node in a doubly linked list holds the data plus struct Node *prev and struct Node *next. The first node has prev == NULL; the last has next == NULL in the usual open-chain layout.

Minimal doubly linked node in C

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

Every insert or delete must update both neighbors’ pointers—easy to get wrong in C, so the later lessons walk through patterns step by step.

4) Real-life examples of doubly linked lists

Anywhere you need easy forward and backward movement along a sequence, a DLL (or a structure with the same idea) is a natural fit:

• Browser back / forward — history is often modeled as a list you can traverse in both directions.
• Music players — “previous track” and “next track” without scanning from the start.
• LRU caches — many implementations pair a hash map with a DLL to move entries to the “most recently used” side in O(1).
• Kernel and library internals — e.g. per-CPU run lists, deque-like structures built from intrusive DLL nodes.

If you only ever walk forward, an SLL may suffice; when backward navigation or removal given only a node pointer matters, DLLs are a common choice.

5) SLL vs DLL (quick comparison)

Same abstract sequence; different trade-offs. Exact Big-O for insert/delete depends on whether you already hold pointers to the right nodes (see DLL Time Complexity and Time Complexity (Linked List)).

For a focused head-to-head lesson, open SLL vs DLL when you are ready.

6) Advantages of doubly linked lists

• Bidirectional traversal — Navigate forward and backward in constant time per step.
• Easier deletion / insertion near a known node — prev avoids searching for the predecessor on a singly linked chain.
• Natural for deque-like APIs — Push/pop at both ends is straightforward with head and tail.
• Building blocks for advanced structures — e.g. LRU lists, some graph adjacency representations.

7) Disadvantages of doubly linked lists

• Extra memory — One more pointer per node vs SLL; matters for small payloads.
• More bookkeeping — Every splice updates up to four pointer ends (two nodes × two directions); bugs show up as subtle list corruption.
• Still no O(1) access by index — Finding the k-th element is still a linear walk unless you add extra structure.
• Cache behavior — Like any linked structure, nodes may be scattered on the heap compared to a tight array.

Choose DLL when backward links or symmetric operations justify the overhead; stay with SLL when a single direction is enough and memory is tight.