WikiGalaxy
Traversal in Doubly Linked List
Understanding Traversal:
Traversal in a doubly linked list means visiting each node in the list once to perform some operation (like printing the data). In a doubly linked list, each node has pointers to both the next and the previous nodes, allowing traversal in both forward and backward directions.
Forward Traversal:
This involves moving from the head of the list to the end, visiting each node along the way. The traversal uses the 'next' pointer of each node.
Backward Traversal:
This involves moving from the end of the list back to the head, visiting each node along the way. The traversal uses the 'prev' pointer of each node.
Step 1: Start at the Head Node
[Head] <-> [Node1] <-> [Node2] <-> [Node3] <-> [Tail]
Step 2: Move Forward using 'next'
[Head] -> [Node1] -> [Node2] -> [Node3] -> [Tail]
Step 3: Move Backward using 'prev'
[Tail] <- [Node3] <- [Node2] <- [Node1] <- [Head]
Step 4: End when reaching Null
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
}
}
public class DoublyLinkedList {
Node head;
// Forward Traversal
void printForward() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
}
// Backward Traversal
void printBackward() {
Node current = head;
if (current == null) return;
// Move to the end of the list
while (current.next != null) {
current = current.next;
}
// Traverse backwards
while (current != null) {
System.out.print(current.data + " ");
current = current.prev;
}
}
}
Detailed Explanation:
In the forward traversal, we start from the head and keep moving to the next node until we reach null. In backward traversal, we first move to the end of the list by following the 'next' pointers and then traverse back to the head using the 'prev' pointers.
Console Output:
Forward: 1 2 3 4 Backward: 4 3 2 1
