Traverse Doubly Linked Lists

Traversing Doubly Linked Lists

Traversing a doubly linked list involves visiting each node in the list in sequence to perform actions or retrieve data. This operation can be performed in both forward and backward directions due to the bidirectional nature of doubly linked lists.

---

Step-by-Step Process

Consider a doubly linked list with the following structure:

Head <-> 1 <-> 2 <-> 3 <-> 4 <-> None

To traverse this list in the forward direction, follow these steps:

1. Start at the Head: Begin traversal at the head of the list, which is the first node.
2. Visit the Current Node: Perform any required action on the current node, such as printing its value.
3. Move to the Next Node: Update the current node to the next node in the sequence by following the reference to the next node.
4. Repeat: Continue this process until you reach the end of the list (i.e., a node with a reference to None).

To traverse this list in the backward direction, follow these steps:

1. Start at the Tail: Begin traversal at the tail of the list, which is the last node.
2. Visit the Current Node: Perform any required action on the current node, such as printing its value.
3. Move to the Previous Node: Update the current node to the previous node in the sequence by following the reference to the previous node.
4. Repeat: Continue this process until you reach the beginning of the list (i.e., a node with a reference to None).

Let's apply these steps to the example doubly linked list:

• Start at the Head (node with value 1).
• Visit the current node (print 1).
• Move to the next node (node with value 2).
• Visit the current node (print 2).
• Move to the next node (node with value 3).
• Visit the current node (print 3).
• Move to the next node (node with value 4).
• Visit the current node (print 4).
• Move to the next node (None), end traversal.

---

Python Program to Implement Traversal

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def traverse_forward(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    def traverse_backward(self):
        current = self.tail
        while current:
            print(current.data, end=" <-> ")
            current = current.prev
        print("None")

# Example usage:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.append(4)
print("Forward traversal of the doubly linked list:")
dll.traverse_forward()  # Output: 1 <-> 2 <-> 3 <-> 4 <-> None
print("Backward traversal of the doubly linked list:")
dll.traverse_backward()  # Output: 4 <-> 3 <-> 2 <-> 1 <-> None

This Python program defines a doubly linked list with methods for appending nodes and traversing the list in both forward and backward directions. The traverse_forward method visits each node from head to tail, while the traverse_backward method visits each node from tail to head.