Skip to content
Home » Traversing

Traversing

✅ Traversing in Linked List

✅ 1. Introduction

A Linked List is a linear data structure where elements are stored in the form of nodes connected by pointers.
To access or process the elements of a linked list, we perform an operation called Traversing.

✅ 2. Definition of Traversing

Traversing in a linked list means visiting each node of the list one by one, starting from the HEAD node and continuing until the last node is reached.

📌 Traversing is required for:

  • Displaying elements
  • Searching an element
  • Counting nodes
  • Performing operations on each node

✅ 3. Concept of Traversing

Since linked lists do not support random access, nodes cannot be accessed directly using index values.
So, traversal must start from the first node (HEAD).

📌 Basic idea:

HEAD → Node1 → Node2 → Node3 → NULL

Traversal order:

Node1 → Node2 → Node3

✅ 4. Traversing in Singly Linked List

✅ Steps Involved

  1. Create a temporary pointer temp
  2. Assign temp = HEAD
  3. Repeat until temp == NULL:
    • Process (display) temp->data
    • Move temp to next node (temp = temp->next)

✅ Algorithm for Traversing Singly Linked List

Algorithm: Traverse_SLL(HEAD)

  1. Start
  2. If HEAD == NULL, print List is empty and Stop
  3. Set temp = HEAD
  4. While temp != NULL
    • Print temp->data
    • temp = temp->next
  5. Stop

✅ Example

Linked List:

HEAD → 10 → 20 → 30 → NULL

Traversal Output:

10 20 30

✅ Time Complexity

✅ O(n) where n is the number of nodes.

✅ 5. Traversing in Circular Linked List

In a Circular Linked List, the last node points back to the first node, so there is no NULL pointer.

✅ Traversing Logic

  1. Start from HEAD
  2. Visit nodes until you reach HEAD again

📌 Representation:

HEAD → 10 → 20 → 30
  ↑                 ↓
  ←←←←←←←←←←←←←←←←←←←

✅ Algorithm for Traversing Circular Linked List

Algorithm: Traverse_CLL(HEAD)

  1. Start
  2. If HEAD == NULL, print List is empty and Stop
  3. Set temp = HEAD
  4. Do
    • Print temp->data
    • temp = temp->next
      While temp != HEAD
  5. Stop

✅ Time Complexity

✅ O(n)

✅ 6. Traversing in Doubly Linked List

In a Doubly Linked List, each node contains two pointers:

  • prev
  • next

✅ Forward Traversing

Start from the first node and move using next pointer.

📌 Example:

NULL ← 10 ↔ 20 ↔ 30 → NULL

Traversal:

10 20 30

✅ Backward Traversing

Start from the last node and move using prev pointer.

📌 Backward Traversal:

30 20 10

✅ Algorithm (Forward Traversing)

Algorithm: Traverse_DLL_Forward(HEAD)

  1. Start
  2. Set temp = HEAD
  3. While temp != NULL
    • Print temp->data
    • temp = temp->next
  4. Stop

✅ Algorithm (Backward Traversing)

  1. Move to last node
  2. Traverse using prev pointer

✅ 7. Important Points

✅ Key points to remember:

  • Traversing always starts from HEAD
  • Linked lists do not allow direct access
  • Temporary pointer is used for traversal
  • Traversing time complexity is O(n)

✅ 8. Applications of Traversing

Traversing is used for:

  • Displaying list elements
  • Searching data
  • Counting number of nodes
  • Updating node values

✅ Conclusion

Traversing in a linked list is the process of visiting each node sequentially from the first node to the last node. Since linked lists do not support direct access, traversal is the only way to access elements, and it takes O(n) time.