Skip to content
Home » Searching in Singly Linked List

Searching in Singly Linked List

✅ Searching in Singly Linked List

✅ 1. Introduction

Searching in a Singly Linked List means finding whether a given element (key value) is present in the list or not, and if present, determining its position.

Since a singly linked list does not support random access, searching is done by sequential traversal starting from the HEAD node.

✅ 2. Definition of Searching

Searching is the process of locating a specific node in the linked list by comparing the given key with the data stored in each node.

📌 Searching continues until:

  • The element is found, or
  • The end of the list (NULL) is reached

✅ 3. Concept of Searching in Singly Linked List

A singly linked list has nodes connected in one direction only:

HEAD → 10 → 20 → 30 → 40 → NULL

If we want to search 30, traversal is done as:

10 → 20 → 30 (FOUND)

✅ 4. Steps Involved in Searching

  1. Start from HEAD
  2. Compare key with node->data
  3. If match found → stop search
  4. Else move to next node
  5. Repeat until NULL is reached

✅ 5. Algorithm for Searching in Singly Linked List

Algorithm: Search_SLL(HEAD, KEY)

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

✅ 6. Example

Linked List:

HEAD → 10 → 20 → 30 → 40 → NULL

Search for 30

Traversal:

  • Compare with 10 → No
  • Compare with 20 → No
  • Compare with 30 → Yes (Found)

✅ Output:

Element found at position 3

✅ 7. Time Complexity of Searching

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

📌 Where n is the number of nodes.

✅ 8. Advantages of Searching in Linked List

✅ Benefits:

  • Simple implementation
  • No need of sorted data
  • Works for dynamic data size

✅ 9. Limitations

❌ Disadvantages:

  • Searching is slower compared to arrays
  • No binary search possible (no indexing)

✅ Conclusion

Searching in a singly linked list is performed by sequential traversal from the first node to the last node. Since there is no direct access, the time complexity is O(n). Linear search is the only practical method used in singly linked lists.