Doubly Linked List Structure and Node Design
What you'll learn: How doubly linked lists extend singly linked lists by adding backward navigation through previous pointers.
The Core Idea
In a singly linked list, each node only points forward to the next node—like a one-way street. A doubly linked list allows two-way traffic: each node has two pointers, one pointing to the next node and another pointing to the previous node.
Think of it like a train where each car is connected to both the car in front and the car behind. You can walk forward through the train or backward—whichever direction you need.
Node Structure
A doubly linked list node contains three parts:
- Data: The value stored in the node
- Next pointer: Points to the next node in the list
- Previous pointer: Points to the previous node in the list
Node structure:
┌──────┬──────┬──────┐
│ prev │ data │ next │
└──────┴──────┴──────┘
Bidirectional Navigation
The key advantage is bidirectional traversal. From any node, you can move forward or backward through the list. This makes certain operations more efficient:
- Deleting a node when you only have a pointer to it (no need to search from the head for the previous node)
- Traversing backward from the tail
- Implementing undo/redo functionality
The Tradeoff
The cost? Each node requires extra memory for the previous pointer, and operations must maintain two links instead of one. When you insert or delete, you must update both the next and previous pointers correctly to maintain the bidirectional chain.
Key Takeaway: Doubly linked lists use nodes with both next and previous pointers, enabling efficient two-way traversal at the cost of extra memory and slightly more complex pointer management.