Search for a Value in Linked List in DSA C#

Mental Model

We look at each item in the list one by one until we find the value or reach the end.

Analogy: Like flipping through pages of a book to find a specific word, checking each page in order.

head -> 1 -> 2 -> 3 -> null
           ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, search for value 2

Goal: Find if the value 2 exists in the linked list

Step 1: Start at the head node with value 1

head -> [curr->1] -> 2 -> 3 -> null

Why: We begin searching from the first node

Step 2: Check if current node value 1 equals 2; it does not, move to next node

head -> 1 -> [curr->2] -> 3 -> null

Why: Value not found yet, continue to next node

Step 3: Check if current node value 2 equals 2; it does, stop search

head -> 1 -> [curr->2] -> 3 -> null

Why: Found the value we were searching for

Result:

head -> 1 -> [curr->2] -> 3 -> null
Value 2 found in the list

Annotated Code

DSA C#

using System;

public class Node
{
    public int Value;
    public Node Next;

    public Node(int value)
    {
        Value = value;
        Next = null;
    }
}

public class LinkedList
{
    public Node Head;

    public LinkedList()
    {
        Head = null;
    }

    public void AddLast(int value)
    {
        if (Head == null)
        {
            Head = new Node(value);
            return;
        }
        Node curr = Head;
        while (curr.Next != null)
        {
            curr = curr.Next; // advance curr to next node
        }
        curr.Next = new Node(value); // add new node at end
    }

    public bool Search(int target)
    {
        Node curr = Head;
        while (curr != null)
        {
            if (curr.Value == target)
                return true; // found target value
            curr = curr.Next; // move to next node
        }
        return false; // reached end without finding
    }

    public void PrintList()
    {
        Node curr = Head;
        while (curr != null)
        {
            Console.Write(curr.Value);
            if (curr.Next != null)
                Console.Write(" -> ");
            curr = curr.Next;
        }
        Console.WriteLine(" -> null");
    }
}

public class Program
{
    public static void Main()
    {
        LinkedList list = new LinkedList();
        list.AddLast(1);
        list.AddLast(2);
        list.AddLast(3);

        list.PrintList();

        int searchValue = 2;
        bool found = list.Search(searchValue);
        Console.WriteLine(found ? $"Value {searchValue} found in the list" : $"Value {searchValue} not found in the list");
    }
}

while (curr.Next != null) { curr = curr.Next; // advance curr to next node }

advance curr to last node to add new node at end

if (curr.Value == target) return true; // found target value

check if current node holds the target value

curr = curr.Next; // move to next node

advance curr to next node to continue search

Output

1 -> 2 -> 3 -> null

Value 2 found in the list

Complexity Analysis

Time: O(n) because in worst case we check each node once until we find the value or reach the end

Space: O(1) because we only use a few variables regardless of list size

vs Alternative: Compared to arrays, linked list search is similar O(n) but no direct index access; arrays allow direct access but shifting is costly

Edge Cases

empty list

search returns false immediately because head is null

DSA C#

while (curr != null)

value not in list

search traverses entire list and returns false

DSA C#

while (curr != null)

value at head node

search finds value immediately and returns true

DSA C#

if (curr.Value == target)

When to Use This Pattern

When you need to find if a value exists in a linked list, use linear search by checking nodes one by one because linked lists do not support direct access.

Common Mistakes

Mistake: Not checking if the current node is null before accessing its value
Fix: Always check 'curr != null' in the loop condition before accessing curr.Value

Summary

Searches the linked list nodes one by one to find a target value.

Use when you need to check if a value exists in a linked list.

The key is to move through nodes sequentially until you find the value or reach the end.

Practice

1. What is the main purpose of searching for a value in a linked list?

easy

A. To add a new node at the end

B. To find if the value exists in the list

C. To delete the first node

D. To reverse the linked list

Solution

1. Step 1: Understand the search operation

   Searching means checking each node to see if it contains the target value.

2. Step 2: Identify the goal of searching

   The goal is to find whether the value exists anywhere in the linked list.

3. Final Answer:

   To find if the value exists in the list -> Option B

4. Quick Check:

   Search = Find value presence [OK]

Hint: Search means checking nodes for the value [OK]

Common Mistakes:

• Confusing search with insertion or deletion
• Thinking search changes the list
• Assuming search returns the node position always

2. Which of the following is the correct C# syntax to start traversing a linked list from its head node named head?

easy

A. Node current => head;

B. Node current == head;

C. Node current = head;

D. Node current <- head;

Solution

1. Step 1: Understand variable assignment syntax in C#

   To assign a reference, use single equals sign =.

2. Step 2: Check each option for correct assignment

   Node current = head; uses =, which is correct. Others use invalid operators.

3. Final Answer:

   Node current = head; -> Option C

4. Quick Check:

   Assignment uses = in C# [OK]

Hint: Use single = for assignment in C# [OK]

Common Mistakes:

• Using == instead of = for assignment
• Using invalid operators like => or <-
• Confusing assignment with comparison

3. What will be the output of the following C# code snippet?

class Node {
  public int data;
  public Node next;
  public Node(int d) { data = d; next = null; }
}

Node head = new Node(5);
head.next = new Node(10);
head.next.next = new Node(15);

Node current = head;
bool found = false;
while (current != null) {
  if (current.data == 10) {
    found = true;
    break;
  }
  current = current.next;
}
Console.WriteLine(found);

medium

A. NullReferenceException

B. False

C. Compilation error

D. True

Solution

1. Step 1: Trace the linked list nodes and search loop

   The list has nodes with data 5 -> 10 -> 15. The loop checks each node's data for 10.

2. Step 2: Check when the value 10 is found

   At second node, data is 10, so found becomes true and loop breaks.

3. Final Answer:

   True -> Option D

4. Quick Check:

   Value 10 found = True [OK]

Hint: Stop loop when value found, print true [OK]

Common Mistakes:

• Forgetting to break loop after finding value
• Printing current.data instead of found
• Null pointer errors if next not checked

4. Identify the error in the following code that searches for a value in a linked list:

Node current = head;
while (current.next != null) {
  if (current.data == 20) {
    Console.WriteLine("Found");
    break;
  }
  current = current.next;
}

medium

A. It skips checking the last node

B. It causes infinite loop

C. It throws NullReferenceException immediately

D. It never enters the loop

Solution

1. Step 1: Analyze the loop condition

   The loop runs while current.next != null, so it stops before last node.

2. Step 2: Understand impact on search

   The last node's data is never checked, so search may miss the value if it's there.

3. Final Answer:

   It skips checking the last node -> Option A

4. Quick Check:

   Loop condition misses last node [OK]

Hint: Use current != null to check all nodes [OK]

Common Mistakes:

• Using current.next != null instead of current != null
• Assuming last node is checked automatically
• Not handling empty list (head null)

5. Given a linked list where nodes may contain duplicate values, how can you modify the search to return the count of occurrences of a target value x instead of just checking presence?

hard

A. Traverse all nodes, increment count when node.data == x, then return count

B. Stop at first occurrence and return 1

C. Use recursion to find only the last occurrence

D. Delete nodes with value x and return total nodes left

Solution

1. Step 1: Understand the need to count all occurrences

   Since duplicates exist, we must check every node to count all matches.

2. Step 2: Traverse entire list and count matches

   Loop through each node, increment a counter when node.data equals x, then return the count.

3. Final Answer:

   Traverse all nodes, increment count when node.data == x, then return count -> Option A

4. Quick Check:

   Count all matches by full traversal [OK]

Hint: Count matches by checking every node [OK]

Common Mistakes:

• Stopping search after first match
• Using recursion incorrectly for counting
• Modifying list during search unintentionally