# 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:

**Start at the Head**: Begin traversal at the head of the list, which is the first node.**Visit the Current Node**: Perform any required action on the current node, such as printing its value.**Move to the Next Node**: Update the current node to the next node in the sequence by following the reference to the next node.**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:

**Start at the Tail**: Begin traversal at the tail of the list, which is the last node.**Visit the Current Node**: Perform any required action on the current node, such as printing its value.**Move to the Previous Node**: Update the current node to the previous node in the sequence by following the reference to the previous node.**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.