A doubly linked list is a data structure that extends the concept of a singly linked list by allowing each node to maintain references to both its preceding node (called the "previous" or "prev" node) and its succeeding node (called the "next" node). This bidirectional linkage enables traversal in both directions—forward and backward—making certain operations more efficient compared to a singly linked list.
Each node in a doubly linked list consists of three components:
-
Data (or Payload): This holds the actual information or value stored in the node.
-
Next Pointer (or Next Reference): This is a reference to the next node in the sequence.
-
Previous Pointer (or Prev Reference): This is a reference to the previous node in the sequence.
Here's a visual representation of a doubly linked list:
First Node Second Node Third Node Last Node
+------+ +------+ +------+ +------+ +------+ +------+
| Data | | Data | | Data | | Data | | Data | | Data |
+------+ +------+ +------+ +------+ +------+ +------+
| Prev |<->| Prev |<->| Prev |<->| Prev |<->| Prev | ... <-> | Prev |
+------+ +------+ +------+ +------+ +------+ +------+
| Next |<->| Next |<->| Next |<->| Next |<->| Next | | Null |
+------+ +------+ +------+ +------+ +------+ +------+
In this representation, each node has both a "prev" pointer and a "next" pointer. The first node's "prev" pointer is null because it doesn't have a preceding node, and the last node's "next" pointer is null because it doesn't have a succeeding node.
Operations on a doubly linked list include insertion, deletion, traversal in both directions, and searching for specific elements. While a doubly linked list requires more memory to store the additional "prev" pointers, it offers advantages in terms of easier traversal in both directions compared to a singly linked list.
