The singly or linear linked list comes with a limitation. You can traverse in only one direction. You can read nodes starting from first to the last by updating a pointer with location of next node. What if you want to move backward and forward from any location you are currently at?? You do such a thing with the back and next buttons in your browser. Well to meet such a need, you can use a doubly linked list instead of a linear linked list.
What is a Doubly Linked List?
This is a special kind of linked list in which two-way traversal can be done. Every node contains two pointers to store locations of next and previous nodes. These two pointers allow traversing to previous node or next node from any given node. Each node of this linked list is thus created with following components
- DATA- information to be stored in the node
- NEXT- Pointer to store location of next node of the current node
- PREV- Pointer to store location of previous node of the current node
The NEXT pointer of the last node of a doubly linked list contains NULL to indicate termination of the doubly linked list while traversing forward.
The PREV pointer of the first node of a doubly linked list contains NULL to indicate termination of the doubly linked list while traversing backward.
FIRST pointer is used to store the location of first node and LAST pointer is used to store the location of last node.
Traversing a 2-way Linked List
Traversal from first to last node, last to first node and from any node to next or previous node is possible. For the convenience of traversing from the beginning or end of a doubly linked list two pointers are used to identify two ends of the linked list. Since both ways traversal is allowed in such a linked list, so it also called a 2-way linked list.
To traverse a linked list in forward direction, start with FIRST pointer and follow each node’s NEXT pointer to move to its next node. Traversal completes when the pointer used for traversal gets a NULL value.
To traverse a linked list in backward direction, start with LAST pointer and follow each node’s PREV pointer to move to previous node. Traversal completes when the pointer used for traversal gets a NULL value.
For any two nodes to be neighbors or adjacent to each other the following condition is to be valid. The adjacent nodes identified by pointers PTRA and PTRB in this example
PREV[PTRB]= PTRA and NEXT[PTRA]=PTRB