Skip to content
Home » Searching Circular Linked List

Searching Circular Linked List

✅ Searching in Circular Linked List

✅ 1. Introduction

A Circular Linked List (CLL) is a linked list in which the last node points back to the first node, forming a circle.
Unlike singly linked lists, there is no NULL pointer at the end.

Because of this circular nature, special care is required while searching to avoid infinite looping.

✅ 2. Definition of Searching

Searching in a Circular Linked List is the process of finding a node that contains a given key value by traversing the list in a circular manner.

Searching continues until:

  • The element is found, or
  • The traversal reaches the starting node again

✅ 3. Concept of Searching in Circular Linked List

Consider the following circular linked list:

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

If we want to search 30, traversal will be:

10 → 20 → 30 (FOUND)

Traversal must stop when HEAD is reached again, otherwise it will loop infinitely.

✅ 4. Steps Involved in Searching

  1. Check if the list is empty (HEAD == NULL)
  2. Start traversal from HEAD
  3. Compare key with current node data
  4. If found → stop
  5. Move to next node
  6. Stop when current node becomes HEAD again

✅ 5. Algorithm for Searching in Circular Linked List

Algorithm: Search_CLL(HEAD, KEY)

  1. Start
  2. If HEAD == NULL, print List is empty and Stop
  3. Set temp = HEAD
  4. Set pos = 1
  5. Do
    • If temp->data == KEY
      • Print Element found at position pos
      • Stop
    • temp = temp->next
    • pos = pos + 1
      While temp != HEAD
  6. Print Element not found
  7. Stop

✅ 6. Example

Circular Linked List:

HEAD → 5 → 15 → 25 → 35
  ↑                         ↓
  ←←←←←←←←←←←←←←←←←←←←←←←←←←←

Search for 25:

Traversal:

  • 5 → not match
  • 15 → not match
  • 25 → match ✅

Output:

Element found at position 3

✅ 7. Time Complexity

  • Best Case: O(1) (element found at first node)
  • Worst Case: O(n) (element found at last node or not found)
  • Average Case: O(n)

📌 Where n is the number of nodes.

✅ 8. Advantages of Searching in Circular Linked List

✅ Benefits:

  • Can start searching from any node
  • No NULL pointer issues
  • Useful in circular data processing

❌ 9. Limitations

  • Must handle loop termination carefully
  • Slightly more complex than singly linked list
  • Still sequential search (no random access)

✅ Conclusion

Searching in a circular linked list is done by linear traversal, starting from the head node and stopping when the traversal reaches the head again. Though it offers circular traversal, the time complexity remains O(n).