Search for a Value in Linked List in DSA Go

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 -> [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 -> [2 ↑] -> 3 -> null

Why: Keep looking because current node is not the target

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

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

Why: Found the value we were searching for

Result:

head -> 1 -> [2] -> 3 -> null; value 2 found

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	value int
	next  *Node
}

func search(head *Node, target int) bool {
	curr := head
	for curr != nil {
		if curr.value == target {
			return true
		}
		curr = curr.next
	}
	return false
}

func main() {
	node3 := &Node{value: 3, next: nil}
	node2 := &Node{value: 2, next: node3}
	node1 := &Node{value: 1, next: node2}

	found := search(node1, 2)
	fmt.Printf("List: 1 -> 2 -> 3 -> null\n")
	fmt.Printf("Search for 2: %v\n", found)
}

curr := head

start from the first node

for curr != nil {

traverse nodes until end of list

if curr.value == target {

check if current node has the target value

return true

stop and report found

curr = curr.next

move to next node to continue search

return false

value not found after full traversal

Output

List: 1 -> 2 -> 3 -> null

Search for 2: true

Complexity Analysis

Time: O(n) because we may need to check each node once until we find the value or reach the end

Space: O(1) because we only use a pointer to traverse without extra storage

vs Alternative: Compared to searching in an array, linked list search is similar in time but slower for random access since we must go node by node

Edge Cases

empty list

search returns false immediately because there are no nodes

DSA Go

for curr != nil {

value at head node

search returns true immediately at first check

DSA Go

if curr.value == target {

value not in list

search traverses entire list and returns false

DSA Go

return false

When to Use This Pattern

When you need to find if a value exists in a linked list, use linear traversal checking each node until found or end.

Common Mistakes

Mistake: Stopping search too early without checking all nodes
Fix: Continue traversal until node is nil or value is found

Mistake: Not handling empty list (nil head) causing errors
Fix: Check for nil head by starting traversal only if head is not nil

Summary

It checks each node one by one to find if a value exists in the linked list.

Use it when you want to know if a linked list contains a specific value.

The key is to move through nodes step-by-step 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 reverse the order of nodes in the list

B. To add a new node at the end of the list

C. To delete the first node of the list

D. To find if a specific value exists in the 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 a specific value exists in the list -> Option D

4. Quick Check:

   Search means find value presence = To find if a specific value exists in the list [OK]

Hint: Search means look for a value in nodes [OK]

Common Mistakes:

• Confusing search with insertion or deletion
• Thinking search changes the list structure
• Assuming search reverses the list

2. Which of the following Go code snippets correctly checks if a linked list node's value equals the target value val?

easy

A. if current.val = val { return true }

B. if current.value == val { return true }

C. if current.value := val { return true }

D. if current.value != val { return true }

Solution

1. Step 1: Identify correct equality check syntax in Go

   Use double equals (==) to compare values, not single equals (=) or :=.

2. Step 2: Check the field name and comparison logic

   Assuming node field is 'value', 'current.value == val' correctly compares values.

3. Final Answer:

   if current.value == val { return true } -> Option B

4. Quick Check:

   Use '==' for comparison in Go [OK]

Hint: Use '==' to compare values, not '=' or ':=' [OK]

Common Mistakes:

• Using '=' instead of '==' for comparison
• Using ':=' inside if condition incorrectly
• Checking inequality instead of equality

3. What will be the output of the following Go code that searches for value 5 in a linked list?

type Node struct {
    value int
    next  *Node
}

func search(head *Node, val int) bool {
    current := head
    for current != nil {
        if current.value == val {
            return true
        }
        current = current.next
    }
    return false
}

// List: 1 -> 3 -> 5 -> 7 -> nil
head := &Node{1, &Node{3, &Node{5, &Node{7, nil}}}}
fmt.Println(search(head, 5))

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Trace the search function through the list

   It checks nodes 1, 3, then 5. When it finds 5, it returns true immediately.

2. Step 2: Confirm no errors occur

   Code is correct and will print true because 5 exists in the list.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Value 5 found in list = true [OK]

Hint: Stop search when value found, else false [OK]

Common Mistakes:

• Assuming search returns false if value is in list
• Thinking code causes panic due to nil pointer
• Confusing output with string instead of boolean

4. Identify the bug in this Go function that searches for a value in a linked list:

func search(head *Node, val int) bool {
    current := head
    for current.next != nil {
        if current.value == val {
            return true
        }
        current = current.next
    }
    return false
}

medium

A. Loop condition misses checking the last node

B. Comparison uses '=' instead of '=='

C. Function returns true even if value not found

D. Variable 'current' is not initialized

Solution

1. Step 1: Analyze the loop condition

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

2. Step 2: Understand impact on search

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

3. Final Answer:

   Loop condition misses checking the last node -> Option A

4. Quick Check:

   Loop must check all nodes including last [OK]

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

Common Mistakes:

• Using current.next != nil instead of current != nil
• Forgetting to check last node's value
• Misreading loop condition as correct

5. Given a linked list where nodes may contain duplicate values, how would you modify the search function to return the count of occurrences of a target value val instead of just true/false?
Choose the correct approach.

hard

A. Return true immediately when first node.value == val is found

B. Use recursion to return true if any node.value == val

C. Traverse all nodes, increment count when node.value == val, return count

D. Stop traversal when node.value != val is found

Solution

1. Step 1: Understand requirement to count all occurrences

   We must check every node because duplicates can appear anywhere.

2. Step 2: Modify search to count matches

   Traverse all nodes, increase count each time node.value equals val, then return count.

3. Final Answer:

   Traverse all nodes, increment count when node.value == val, return count -> Option C

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
• Returning boolean instead of count
• Ignoring duplicates in list