Traverse Singly Linked Lists

Introduction to Traversing Singly Linked Lists

Traversing a singly linked list involves visiting each node in the list in sequence to perform actions or retrieve data. This operation is fundamental for various linked list manipulations, including searching, updating, and displaying elements.

---

Step-by-Step Process

Consider a singly linked list with the following structure:

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

To traverse this list, 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).

Let's apply these steps to the example 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

class SinglyLinkedList:
    def __init__(self):
        self.head = None

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

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

# Example usage:
linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
print("Traversal of the linked list:")
linked_list.traverse()  # Output: 1 -> 2 -> 3 -> 4 -> None

This Python program defines a singly linked list with methods for appending nodes and traversing the list. The traverse method visits each node and prints its value in sequence.