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.
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:
To traverse this list in the backward direction, follow these steps:
Let's apply these steps to the example doubly linked list:
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.