Singly Linked List – Search Operation

Linked Lists

Contents

IntroExamplePseudocodeExamplesTimeSpace

Search Operation in Singly Linked List

Searching node with value 35 in the singly linked list.

Searching in a singly linked list means traversing the list from the head and checking each node's value until we either find the target value or reach the end of the list.

Since a singly linked list does not support direct indexing like an array, we must move node by node using the next pointers.

Visual Example

Suppose we have a list:

We want to search for value 35. The traversal should move through nodes until it finds this value.

Step-by-Step Search for 35

  1. Start at the head node (value 5).
  2. Compare with target: 5 ≠ 35, move to next node.
  3. Compare 15 ≠ 35, move to next.
  4. Compare 25 ≠ 35, move to next.
  5. Compare 35 == 35, target found!

If the value is not found even after reaching the end, we return null or indicate that the value is not in the list.

Complete Pseudocode: Search Value in Singly Linked List

This pseudocode shows how to search for a specific value in a singly linked list and return its index if found.

function search(head, target):
    curr = head
    index = 0

    while curr != null:
        if curr.val == target:
            return index
        curr = curr.next
        index += 1

    return -1

Let’s understand each part of the code step by step.

function search(head, target):
    curr = head
    index = 0

Explanation: We start by defining the function and initializing two things — curr to walk through the list and index to track position.

    while curr != null:
        if curr.val == target:
            return index

Explanation: We use a loop to visit every node. If the value of the current node matches the target, we return its index.

        curr = curr.next
        index += 1

Explanation: If the current node doesn’t match, we move to the next node and increment the index.

    return -1

Explanation: If we reach the end of the list and haven’t found the value, we return -1 to show that it’s not present.

Singly Linked List Search Operation Examples

The following examples demonstrate how to search for a value in a singly linked list.

Initial List Search Value Result Explanation
[10, 20, 30, 40, 50] 30 Found at index 2 Start from head and traverse each node. Match found at index 2.
[5, 15, 25, 35] 35 Found at index 3 Last element matches the search value. Traversed till end to find match.
[1, 2, 3] 10 Not Found Reached end of list without finding the value. Return not found.
[] 10 Not Found List is empty. Nothing to search. Return not found.

Time Complexity of Singly Linked List Search Operation

Search Case Time Complexity Explanation
Search for Head Node O(1) If the target value is at the head, we find it immediately without traversal.
Search for Middle Node O(n) We may have to traverse approximately half the list to locate the value.
Search for Tail Node or Missing Node O(n) In the worst case, we traverse the entire list either to find the last node or determine that the value doesn't exist.

Space Complexity of Singly Linked List Search Operation

Search Case Space Complexity Explanation
Any Search Operation O(1) We use a constant number of variables (like a pointer) to traverse and check each node. No extra space is used regardless of list size.

Key Concepts

  • Linear traversal: Start from the head and visit each node one by one until the desired value is found or the end is reached.
  • Early termination: If the value is found early (e.g., at the head), traversal stops immediately.
  • Empty list: Always check if the list is empty to avoid null reference errors.
  • Searching in a singly linked list is sequential — there's no direct access to middle or end nodes.

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...