Structure of a Doubly Linked List - Doubly Linked Lists — Bidirectional Navigation | OneNoughtOne

Data Structures & AlgorithmsDoubly Linked Lists

Doubly Linked Lists — Bidirectional Navigation

LevelIntermediate

Duration55 mins

TopicDoubly Linked Lists

1 / 4

Structure of a Doubly Linked List

Beyond One-Way Streets

You've mastered the singly linked list—a chain of nodes where each node points forward to its successor, like a one-way street through your data. You can traverse from head to tail efficiently, insert at either end, and delete nodes when you have access to their predecessors.

But what happens when you need to go backwards?

Imagine you're building a text editor. Users expect to navigate with both arrow keys—left and right. They expect undo and redo. They expect to select text by dragging in either direction. With a singly linked list representing your document, every backward operation requires starting from the beginning and traversing forward until you reach your target. For a 10,000-character document, going back one character could mean 10,000 traversal steps.

This limitation isn't theoretical—it's a fundamental constraint that makes singly linked lists unsuitable for many real-world applications.

What You Will Learn

By the end of this page, you will understand the complete structural anatomy of a doubly linked list. You'll grasp how dual pointers transform a linear chain into a bidirectional highway, why this architectural decision has profound implications for operations, and how to visualize and reason about doubly linked structures with clarity and precision.

The Fundamental Insight: Nodes That Look Both Ways

The conceptual leap from singly to doubly linked lists is elegantly simple yet structurally profound: give each node the ability to look backwards as well as forwards.

In a singly linked list, each node contains:

Data: The value stored in the node
Next pointer: A reference to the successor node

In a doubly linked list, each node contains:

Data: The value stored in the node
Next pointer: A reference to the successor node
Previous pointer: A reference to the predecessor node

This single addition—the previous pointer—fundamentally transforms the capabilities of the data structure. It's the difference between a one-way street and a two-lane highway.

The Symmetry Principle

A doubly linked list exhibits structural symmetry: from any node, you can reach both its predecessor and its successor in O(1) time. This symmetry is not merely aesthetic—it's the foundation for all the operational advantages doubly linked lists provide.

Why this matters architecturally:

The addition of a single pointer per node creates what we might call local bidirectional awareness. Each node becomes a waypoint that knows its position relative to both neighbors, rather than a stepping stone that only knows where to go next.

This local awareness cascades into global capabilities:

Reverse traversal: Walk from tail to head without restarting
Efficient deletion: Remove any node without needing access to its predecessor
Cursor operations: Move forward and backward through data with equal ease
Window navigation: Slide viewing windows in either direction

The previous pointer doesn't just add one capability—it unlocks an entire category of operations that were previously impossible or prohibitively expensive.

Anatomy of a Doubly Linked Node

Let's examine the internal structure of a doubly linked list node with the precision it deserves. Understanding this anatomy is essential for visualizing operations, reasoning about edge cases, and implementing robust solutions.

The Three Components:

Every doubly linked list node contains exactly three components, each with a distinct responsibility:

Node Components

•Data Field: Stores the actual value or payload. This can be a primitive type (integer, character), a reference to a complex object, or even another data structure. The data field is the reason for the node's existence—the pointers exist only to organize access to this data.
•Next Pointer: A reference to the subsequent node in the sequence. For the tail node, this pointer is null (or points to a sentinel, which we'll discuss later). The next pointer enables forward traversal and maintains the logical ordering of the list.
•Previous Pointer: A reference to the preceding node in the sequence. For the head node, this pointer is null (or points to a sentinel). The previous pointer enables backward traversal and provides the bidirectional capability that distinguishes doubly linked lists.

DoublyLinkedNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Represents a node in a doubly linked list.
 * Each node maintains references to both its predecessor and successor,
 * enabling bidirectional traversal through the list.
 */
class DoublyLinkedNode<T> {
    /** The data payload stored in this node */
    data: T;
    
    /** Reference to the next node in the sequence (null if this is the tail) */
    next: DoublyLinkedNode<T> | null;
    
    /** Reference to the previous node in the sequence (null if this is the head) */
    prev: DoublyLinkedNode<T> | null;
    
    constructor(data: T) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}
 
// Example: Creating nodes and establishing links
const nodeA = new DoublyLinkedNode<string>("A");
const nodeB = new DoublyLinkedNode<string>("B");
const nodeC = new DoublyLinkedNode<string>("C");
 
// Establish forward links
nodeA.next = nodeB;
nodeB.next = nodeC;
 
// Establish backward links - this is what makes it "doubly" linked
nodeB.prev = nodeA;
nodeC.prev = nodeB;
 
// Now we can traverse in either direction:
// Forward:  A → B → C
// Backward: C → B → A

Memory Layout Intuition

Each node in a doubly linked list occupies more memory than its singly linked counterpart. The exact overhead depends on your platform's pointer size (typically 4 bytes on 32-bit systems, 8 bytes on 64-bit systems). For a 64-bit system, each node carries an additional 8-byte overhead for the previous pointer. This cost is per-node, so it scales linearly with list size.

The List-Level Structure

While individual nodes form the building blocks, the list structure itself manages these nodes and provides the interface for all operations. Understanding this management layer is crucial for implementing and reasoning about doubly linked lists correctly.

Essential List Properties:

A well-designed doubly linked list maintains several key properties at the list level:

List-Level Properties

•Head Pointer: A reference to the first node in the list. This is your entry point for forward traversal. When the list is empty, the head is null (or points to a sentinel).
•Tail Pointer: A reference to the last node in the list. This enables O(1) access to the end of the list for append operations and backward traversal. When the list is empty, the tail is null (or points to a sentinel).
•Size/Length: An optional but recommended counter tracking the number of nodes. Maintaining this count allows O(1) size queries without traversal.

DoublyLinkedList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * A doubly linked list implementation that maintains head, tail, and size.
 * This structure enables O(1) access to both ends and O(1) size queries.
 */
class DoublyLinkedList<T> {
    /** Reference to the first node in the list */
    private head: DoublyLinkedNode<T> | null;
    
    /** Reference to the last node in the list */
    private tail: DoublyLinkedNode<T> | null;
    
    /** Number of nodes currently in the list */
    private size: number;
    
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    /** Returns true if the list contains no elements */
    isEmpty(): boolean {
        return this.size === 0;
    }
    
    /** Returns the number of elements in the list */
    getSize(): number {
        return this.size;
    }
    
    /** Returns the first node (or null if empty) */
    getHead(): DoublyLinkedNode<T> | null {
        return this.head;
    }
    
    /** Returns the last node (or null if empty) */
    getTail(): DoublyLinkedNode<T> | null {
        return this.tail;
    }
}

The Structural Invariants:

A correctly maintained doubly linked list preserves several critical invariants that must hold after every operation:

Bidirectional Consistency: If node A's next points to node B, then node B's prev must point to node A. This symmetry is sacred—violating it creates a corrupted data structure.
Boundary Conditions: The head's prev pointer is null (no predecessor exists). The tail's next pointer is null (no successor exists).
Empty List State: When the list is empty, both head and tail are null, and size is zero.
Single Element State: When the list contains exactly one element, head and tail point to the same node, and that node's prev and next are both null.
Size Accuracy: The size counter accurately reflects the number of nodes in the list at all times.

Invariant Violations Are Catastrophic

If you ever break the bidirectional consistency invariant (A.next = B but B.prev ≠ A), your data structure becomes silently corrupted. Forward traversal will show one sequence of nodes; backward traversal will show another. This is one of the most insidious bugs in linked list implementations—always verify both directions when modifying links.

Visual Mental Model: The Chain Metaphor

To internalize doubly linked list operations, you need a clear mental model. Let's build one using the metaphor of a physical chain with interconnected links.

The Singly Linked Model: Imagine a chain where each link has a hook on one side only. You can follow the chain forward by grabbing each hook in sequence, but if you want to go backward, you must return to the start and traverse forward again.

The Doubly Linked Model: Now imagine each link has hooks on both sides—front and back. You can grab any link and move in either direction. The chain becomes a highway with lanes going both ways.

Visualizing the Structure:

structural-visualization

Diagram

DOUBLY LINKED LIST STRUCTURE
=============================
 
List Object:
┌──────────────────────────────────────────────────────────────────┐
│  head ─────────────────────────────────┐                         │
│                                        │                         │
│  tail ────────────────────────────────────────────────┐          │
│                                        │              │          │
│  size: 3                               ▼              ▼          │
└────────────────────────────────────────┼──────────────┼──────────┘
                                         │              │
                                         ▼              ▼
Nodes:
         ┌──────────┐    ┌──────────┐    ┌──────────┐
 null ◄──┤   prev   │◄───┤   prev   │◄───┤   prev   │
         ├──────────┤    ├──────────┤    ├──────────┤
         │  data: A │    │  data: B │    │  data: C │
         ├──────────┤    ├──────────┤    ├──────────┤
         │   next   ├───►│   next   ├───►│   next   ├──► null
         └──────────┘    └──────────┘    └──────────┘
              ▲                               ▲
              │                               │
            HEAD                            TAIL
 
 
KEY OBSERVATIONS:
─────────────────
• Each node has pointers in BOTH directions
• Head's prev pointer is null (no predecessor)
• Tail's next pointer is null (no successor)
• The list object maintains direct access to both ends
 
TRAVERSAL PATHS:
────────────────
Forward:   HEAD → A → B → C → null
Backward:  TAIL → C → B → A → null

The Critical Insight: Every Link is Bidirectional

Notice how each connection in the diagram is actually two separate arrows pointing in opposite directions. This isn't redundant—it's the fundamental architectural choice that enables bidirectional navigation.

When you see:

nodeA.next = nodeB
nodeB.prev = nodeA

You're establishing a single logical link with two physical pointers. This duality is the essence of doubly linked lists. The two pointers must always agree about their relationship—if they don't, the structure is broken.

Drawing Helps

When implementing doubly linked list operations, always draw the before and after states. Include both prev and next pointers for every node involved. This simple practice catches pointer manipulation errors before they become bugs. Professional engineers who work with linked structures routinely sketch diagrams—it's not a beginner's crutch, it's a professional practice.

Structural Comparison: Singly vs Doubly Linked

To truly understand when doubly linked lists are appropriate, you must have crystal-clear mental models of both structures and their differences. Let's examine them side by side:

Structural Comparison: Singly vs Doubly Linked Lists
Aspect	Singly Linked List	Doubly Linked List
Pointers per Node	1 (next only)	2 (next and prev)
Memory per Node	data + 1 pointer	data + 2 pointers
Forward Traversal	Yes, from any node	Yes, from any node
Backward Traversal	No (requires restart from head)	Yes, from any node
Access to Predecessor	Requires O(n) search from head	O(1) via prev pointer
Deletion Complexity	O(1) if predecessor known	O(1) always (node is self-sufficient)
Insertion Before Node	Requires predecessor reference	Directly possible via prev
Implementation Complexity	Simpler (fewer pointers to manage)	More complex (maintain both pointers)

Singly Linked: What You Can't Do Efficiently

•Traverse backward from a given node
•Delete a node given only that node's reference
•Insert before a node without its predecessor
•Implement efficient cursor movement in both directions
•Build undo/redo functionality naturally

Doubly Linked: What You Gain

•O(1) backward traversal from any node
•True O(1) deletion with just the node reference
•O(1) insertion before any given node
•Natural support for bidirectional cursor/iterator
•Foundation for complex structures like deques

The Trade-off Is Real

Doubly linked lists are not universally better than singly linked lists. They use more memory, require more careful pointer management, and introduce more opportunities for bugs. If your use case only requires forward traversal and you're memory-constrained, a singly linked list may be the superior choice. Engineering is about choosing the right tool for the specific constraints you face.

Edge Cases and Boundary Conditions

The structural elegance of doubly linked lists comes with increased responsibility for handling edge cases correctly. The more pointers you manage, the more boundary conditions you must consider.

Critical Edge Cases to Master:

Edge Cases Requiring Special Handling

•Empty List: Both head and tail are null. Any operation must first check for this state and handle it appropriately—typically by creating a new node that becomes both head and tail.
•Single Element: Head and tail point to the same node. Deletion removes the only element and returns the list to empty state. The single node's prev and next are both null.
•Operation at Head: When inserting or deleting at the head, you must update both the head pointer AND the new head's prev pointer (setting it to null).
•Operation at Tail: When inserting or deleting at the tail, you must update both the tail pointer AND the new tail's next pointer (setting it to null).
•Two Elements: After one deletion, you may transition from a general case to a single-element case. Both head and tail must be updated to point to the remaining node.

edge-case-patterns
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Demonstrates structural states at different list sizes.
 * Understanding these states is essential for correct implementations.
 */
 
// STATE 1: Empty List
// head = null, tail = null, size = 0
let emptyList = new DoublyLinkedList<number>();
console.log(emptyList.isEmpty()); // true
console.log(emptyList.getHead()); // null
console.log(emptyList.getTail()); // null
 
// STATE 2: Single Element
// head = node, tail = node (same reference!)
// node.prev = null, node.next = null
let singleList = new DoublyLinkedList<number>();
singleList.addFirst(42);
// Now: head.data = 42, head === tail
// head.prev = null, head.next = null
 
// STATE 3: Two Elements
// head ≠ tail
// head.next = tail, tail.prev = head
// head.prev = null, tail.next = null
singleList.addLast(99);
// Now: head.data = 42, tail.data = 99
// head.next = tail, tail.prev = head
 
// STATE 4: Many Elements
// Standard case with internal nodes
// Only head has prev = null
// Only tail has next = null
// All internal nodes have both prev and next pointing to valid nodes

The Single-Element Trap

The most common bug in doubly linked list implementations occurs when deleting the second-to-last element. Developers often update the tail correctly but forget to also set the new tail's next pointer to null—or forget to update head when it should now equal tail. Always trace through your logic with exactly two elements in the list.

The Sentinel Node Pattern (Preview)

Many production implementations of doubly linked lists employ sentinel nodes (also called dummy nodes) to eliminate edge cases. This is an advanced technique worth understanding at a structural level.

The Idea: Instead of using null to indicate "no predecessor" or "no successor," create permanent dummy nodes at the head and tail that never contain real data and are never removed.

The Benefits:

Every real node always has both a valid prev and next pointer
Head operations become identical to internal operations
Tail operations become identical to internal operations
No null checks needed for prev/next in standard operations

sentinel-structure

Diagram

DOUBLY LINKED LIST WITH SENTINELS
==================================
 
               ┌────────────┐    ┌──────────┐    ┌──────────┐    ┌────────────┐
NULL ◄─────────┤  SENTINEL  │◄───┤   prev   │◄───┤   prev   │◄───┤  SENTINEL  │
               │   (HEAD)   │    ├──────────┤    ├──────────┤    │   (TAIL)   │
               │  no data   │    │  data: A │    │  data: B │    │  no data   │
               ├────────────┤    ├──────────┤    ├──────────┤    ├────────────┤
               │    next    ├───►│   next   ├───►│   next   ├───►│    next    │──────► NULL
               └────────────┘    └──────────┘    └──────────┘    └────────────┘
 
 
EMPTY LIST WITH SENTINELS:
──────────────────────────
 
               ┌────────────┐                    ┌────────────┐
NULL ◄─────────┤  SENTINEL  │◄───────────────────┤  SENTINEL  │
               │   (HEAD)   │                    │   (TAIL)   │
               │  no data   │                    │  no data   │
               ├────────────┤                    ├────────────┤
               │    next    ├───────────────────►│    next    │──────► NULL
               └────────────┘                    └────────────┘
 
• Head sentinel's prev is always null
• Tail sentinel's next is always null
• Real data exists only between sentinels
• Sentinels are never removed

Sentinels Trade Memory for Simplicity

Sentinel nodes add a small constant memory overhead (two extra nodes per list) in exchange for significantly simpler code with fewer branches. This trade-off is almost always worthwhile in practice. Many language standard library implementations use sentinels for their linked list structures.

Summary: The Doubly Linked Structure

We've established a comprehensive understanding of doubly linked list structure. Let's consolidate the key concepts:

Key Structural Concepts

•Dual-Pointer Nodes: Each node contains data plus two pointers—next and prev—enabling bidirectional navigation.
•Structural Symmetry: The relationship between any two adjacent nodes is represented by two pointers that must always agree (A.next = B implies B.prev = A).
•List-Level Management: The list maintains head and tail pointers for O(1) access to both ends, plus an optional size counter.
•Boundary Conditions: Head's prev is null, tail's next is null. These boundaries define the list's extent.
•Edge Cases: Empty, single-element, and two-element lists require special handling in most operations.
•Sentinel Pattern: Dummy nodes at both ends can eliminate null checks and simplify implementation.

What's Next:

Now that you understand the anatomy of a doubly linked list, we'll dive deeper into the mechanics of the previous and next pointers. You'll learn exactly how to manipulate these pointers during insertions, deletions, and traversals—the fundamental operations that bring this structure to life.

Page Complete

You now have a solid mental model of doubly linked list structure. You understand the node anatomy, list-level management, key invariants, boundary conditions, and the sentinel pattern. This foundation prepares you for mastering pointer manipulation in the next page.

1 / 4

Loading learning content...

Data Structures & AlgorithmsDoubly Linked Lists

Doubly Linked Lists — Bidirectional Navigation

LevelIntermediate

Duration55 mins

TopicDoubly Linked Lists

1 / 4

Structure of a Doubly Linked List

Beyond One-Way Streets

But what happens when you need to go backwards?

This limitation isn't theoretical—it's a fundamental constraint that makes singly linked lists unsuitable for many real-world applications.

What You Will Learn

The Fundamental Insight: Nodes That Look Both Ways

The conceptual leap from singly to doubly linked lists is elegantly simple yet structurally profound: give each node the ability to look backwards as well as forwards.

In a singly linked list, each node contains:

Data: The value stored in the node
Next pointer: A reference to the successor node

In a doubly linked list, each node contains:

Data: The value stored in the node
Next pointer: A reference to the successor node
Previous pointer: A reference to the predecessor node

This single addition—the previous pointer—fundamentally transforms the capabilities of the data structure. It's the difference between a one-way street and a two-lane highway.

The Symmetry Principle

Why this matters architecturally:

This local awareness cascades into global capabilities:

Reverse traversal: Walk from tail to head without restarting
Efficient deletion: Remove any node without needing access to its predecessor
Cursor operations: Move forward and backward through data with equal ease
Window navigation: Slide viewing windows in either direction

The previous pointer doesn't just add one capability—it unlocks an entire category of operations that were previously impossible or prohibitively expensive.

Anatomy of a Doubly Linked Node

The Three Components:

Every doubly linked list node contains exactly three components, each with a distinct responsibility:

Node Components

•Data Field: Stores the actual value or payload. This can be a primitive type (integer, character), a reference to a complex object, or even another data structure. The data field is the reason for the node's existence—the pointers exist only to organize access to this data.
•Next Pointer: A reference to the subsequent node in the sequence. For the tail node, this pointer is null (or points to a sentinel, which we'll discuss later). The next pointer enables forward traversal and maintains the logical ordering of the list.
•Previous Pointer: A reference to the preceding node in the sequence. For the head node, this pointer is null (or points to a sentinel). The previous pointer enables backward traversal and provides the bidirectional capability that distinguishes doubly linked lists.

DoublyLinkedNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Represents a node in a doubly linked list.
 * Each node maintains references to both its predecessor and successor,
 * enabling bidirectional traversal through the list.
 */
class DoublyLinkedNode<T> {
    /** The data payload stored in this node */
    data: T;
    
    /** Reference to the next node in the sequence (null if this is the tail) */
    next: DoublyLinkedNode<T> | null;
    
    /** Reference to the previous node in the sequence (null if this is the head) */
    prev: DoublyLinkedNode<T> | null;
    
    constructor(data: T) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}
 
// Example: Creating nodes and establishing links
const nodeA = new DoublyLinkedNode<string>("A");
const nodeB = new DoublyLinkedNode<string>("B");
const nodeC = new DoublyLinkedNode<string>("C");
 
// Establish forward links
nodeA.next = nodeB;
nodeB.next = nodeC;
 
// Establish backward links - this is what makes it "doubly" linked
nodeB.prev = nodeA;
nodeC.prev = nodeB;
 
// Now we can traverse in either direction:
// Forward:  A → B → C
// Backward: C → B → A

Memory Layout Intuition

The List-Level Structure

Essential List Properties:

A well-designed doubly linked list maintains several key properties at the list level:

List-Level Properties

•Head Pointer: A reference to the first node in the list. This is your entry point for forward traversal. When the list is empty, the head is null (or points to a sentinel).
•Tail Pointer: A reference to the last node in the list. This enables O(1) access to the end of the list for append operations and backward traversal. When the list is empty, the tail is null (or points to a sentinel).
•Size/Length: An optional but recommended counter tracking the number of nodes. Maintaining this count allows O(1) size queries without traversal.

DoublyLinkedList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * A doubly linked list implementation that maintains head, tail, and size.
 * This structure enables O(1) access to both ends and O(1) size queries.
 */
class DoublyLinkedList<T> {
    /** Reference to the first node in the list */
    private head: DoublyLinkedNode<T> | null;
    
    /** Reference to the last node in the list */
    private tail: DoublyLinkedNode<T> | null;
    
    /** Number of nodes currently in the list */
    private size: number;
    
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    /** Returns true if the list contains no elements */
    isEmpty(): boolean {
        return this.size === 0;
    }
    
    /** Returns the number of elements in the list */
    getSize(): number {
        return this.size;
    }
    
    /** Returns the first node (or null if empty) */
    getHead(): DoublyLinkedNode<T> | null {
        return this.head;
    }
    
    /** Returns the last node (or null if empty) */
    getTail(): DoublyLinkedNode<T> | null {
        return this.tail;
    }
}

The Structural Invariants:

A correctly maintained doubly linked list preserves several critical invariants that must hold after every operation:

Bidirectional Consistency: If node A's next points to node B, then node B's prev must point to node A. This symmetry is sacred—violating it creates a corrupted data structure.
Boundary Conditions: The head's prev pointer is null (no predecessor exists). The tail's next pointer is null (no successor exists).
Empty List State: When the list is empty, both head and tail are null, and size is zero.
Single Element State: When the list contains exactly one element, head and tail point to the same node, and that node's prev and next are both null.
Size Accuracy: The size counter accurately reflects the number of nodes in the list at all times.

Invariant Violations Are Catastrophic

Visual Mental Model: The Chain Metaphor

To internalize doubly linked list operations, you need a clear mental model. Let's build one using the metaphor of a physical chain with interconnected links.

Visualizing the Structure:

structural-visualization

Diagram

DOUBLY LINKED LIST STRUCTURE
=============================
 
List Object:
┌──────────────────────────────────────────────────────────────────┐
│  head ─────────────────────────────────┐                         │
│                                        │                         │
│  tail ────────────────────────────────────────────────┐          │
│                                        │              │          │
│  size: 3                               ▼              ▼          │
└────────────────────────────────────────┼──────────────┼──────────┘
                                         │              │
                                         ▼              ▼
Nodes:
         ┌──────────┐    ┌──────────┐    ┌──────────┐
 null ◄──┤   prev   │◄───┤   prev   │◄───┤   prev   │
         ├──────────┤    ├──────────┤    ├──────────┤
         │  data: A │    │  data: B │    │  data: C │
         ├──────────┤    ├──────────┤    ├──────────┤
         │   next   ├───►│   next   ├───►│   next   ├──► null
         └──────────┘    └──────────┘    └──────────┘
              ▲                               ▲
              │                               │
            HEAD                            TAIL
 
 
KEY OBSERVATIONS:
─────────────────
• Each node has pointers in BOTH directions
• Head's prev pointer is null (no predecessor)
• Tail's next pointer is null (no successor)
• The list object maintains direct access to both ends
 
TRAVERSAL PATHS:
────────────────
Forward:   HEAD → A → B → C → null
Backward:  TAIL → C → B → A → null

The Critical Insight: Every Link is Bidirectional

When you see:

nodeA.next = nodeB
nodeB.prev = nodeA

Drawing Helps

Structural Comparison: Singly vs Doubly Linked

To truly understand when doubly linked lists are appropriate, you must have crystal-clear mental models of both structures and their differences. Let's examine them side by side:

Structural Comparison: Singly vs Doubly Linked Lists
Aspect	Singly Linked List	Doubly Linked List
Pointers per Node	1 (next only)	2 (next and prev)
Memory per Node	data + 1 pointer	data + 2 pointers
Forward Traversal	Yes, from any node	Yes, from any node
Backward Traversal	No (requires restart from head)	Yes, from any node
Access to Predecessor	Requires O(n) search from head	O(1) via prev pointer
Deletion Complexity	O(1) if predecessor known	O(1) always (node is self-sufficient)
Insertion Before Node	Requires predecessor reference	Directly possible via prev
Implementation Complexity	Simpler (fewer pointers to manage)	More complex (maintain both pointers)

Singly Linked: What You Can't Do Efficiently

•Traverse backward from a given node
•Delete a node given only that node's reference
•Insert before a node without its predecessor
•Implement efficient cursor movement in both directions
•Build undo/redo functionality naturally

Doubly Linked: What You Gain

•O(1) backward traversal from any node
•True O(1) deletion with just the node reference
•O(1) insertion before any given node
•Natural support for bidirectional cursor/iterator
•Foundation for complex structures like deques

The Trade-off Is Real

Edge Cases and Boundary Conditions

The structural elegance of doubly linked lists comes with increased responsibility for handling edge cases correctly. The more pointers you manage, the more boundary conditions you must consider.

Critical Edge Cases to Master:

Edge Cases Requiring Special Handling

•Empty List: Both head and tail are null. Any operation must first check for this state and handle it appropriately—typically by creating a new node that becomes both head and tail.
•Single Element: Head and tail point to the same node. Deletion removes the only element and returns the list to empty state. The single node's prev and next are both null.
•Operation at Head: When inserting or deleting at the head, you must update both the head pointer AND the new head's prev pointer (setting it to null).
•Operation at Tail: When inserting or deleting at the tail, you must update both the tail pointer AND the new tail's next pointer (setting it to null).
•Two Elements: After one deletion, you may transition from a general case to a single-element case. Both head and tail must be updated to point to the remaining node.

edge-case-patterns
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Demonstrates structural states at different list sizes.
 * Understanding these states is essential for correct implementations.
 */
 
// STATE 1: Empty List
// head = null, tail = null, size = 0
let emptyList = new DoublyLinkedList<number>();
console.log(emptyList.isEmpty()); // true
console.log(emptyList.getHead()); // null
console.log(emptyList.getTail()); // null
 
// STATE 2: Single Element
// head = node, tail = node (same reference!)
// node.prev = null, node.next = null
let singleList = new DoublyLinkedList<number>();
singleList.addFirst(42);
// Now: head.data = 42, head === tail
// head.prev = null, head.next = null
 
// STATE 3: Two Elements
// head ≠ tail
// head.next = tail, tail.prev = head
// head.prev = null, tail.next = null
singleList.addLast(99);
// Now: head.data = 42, tail.data = 99
// head.next = tail, tail.prev = head
 
// STATE 4: Many Elements
// Standard case with internal nodes
// Only head has prev = null
// Only tail has next = null
// All internal nodes have both prev and next pointing to valid nodes

The Single-Element Trap

The Sentinel Node Pattern (Preview)

The Idea: Instead of using null to indicate "no predecessor" or "no successor," create permanent dummy nodes at the head and tail that never contain real data and are never removed.

The Benefits:

Every real node always has both a valid prev and next pointer
Head operations become identical to internal operations
Tail operations become identical to internal operations
No null checks needed for prev/next in standard operations

sentinel-structure

Diagram

DOUBLY LINKED LIST WITH SENTINELS
==================================
 
               ┌────────────┐    ┌──────────┐    ┌──────────┐    ┌────────────┐
NULL ◄─────────┤  SENTINEL  │◄───┤   prev   │◄───┤   prev   │◄───┤  SENTINEL  │
               │   (HEAD)   │    ├──────────┤    ├──────────┤    │   (TAIL)   │
               │  no data   │    │  data: A │    │  data: B │    │  no data   │
               ├────────────┤    ├──────────┤    ├──────────┤    ├────────────┤
               │    next    ├───►│   next   ├───►│   next   ├───►│    next    │──────► NULL
               └────────────┘    └──────────┘    └──────────┘    └────────────┘
 
 
EMPTY LIST WITH SENTINELS:
──────────────────────────
 
               ┌────────────┐                    ┌────────────┐
NULL ◄─────────┤  SENTINEL  │◄───────────────────┤  SENTINEL  │
               │   (HEAD)   │                    │   (TAIL)   │
               │  no data   │                    │  no data   │
               ├────────────┤                    ├────────────┤
               │    next    ├───────────────────►│    next    │──────► NULL
               └────────────┘                    └────────────┘
 
• Head sentinel's prev is always null
• Tail sentinel's next is always null
• Real data exists only between sentinels
• Sentinels are never removed

Sentinels Trade Memory for Simplicity

Summary: The Doubly Linked Structure

We've established a comprehensive understanding of doubly linked list structure. Let's consolidate the key concepts:

Key Structural Concepts

•Dual-Pointer Nodes: Each node contains data plus two pointers—next and prev—enabling bidirectional navigation.
•Structural Symmetry: The relationship between any two adjacent nodes is represented by two pointers that must always agree (A.next = B implies B.prev = A).
•List-Level Management: The list maintains head and tail pointers for O(1) access to both ends, plus an optional size counter.
•Boundary Conditions: Head's prev is null, tail's next is null. These boundaries define the list's extent.
•Edge Cases: Empty, single-element, and two-element lists require special handling in most operations.
•Sentinel Pattern: Dummy nodes at both ends can eliminate null checks and simplify implementation.

What's Next:

Page Complete

1 / 4