Search for a Value in Linked List in DSA Go - Execution Trace

Concept Flow - Search for a Value in Linked List

Start at head node

↓

Check if current node is null?

Yes→Value not found, stop

No↓

Compare current node value with target

↓

Return found

↩Back to check if current node is null

Start from the first node, check each node's value. If it matches the target, stop and return found. Otherwise, move to the next node until the list ends.

Execution Sample

DSA Go

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

This code searches for a target value in a linked list by checking each node one by one.

Execution Table

Step	Operation	Current Node Value	Comparison with Target (3)	Pointer Changes	Visual State
1	Start at head	1	1 == 3? No	current -> node with value 1	1 -> 2 -> 3 -> 4 -> null
2	Move to next node	2	2 == 3? No	current -> node with value 2	1 -> 2 -> 3 -> 4 -> null
3	Move to next node	3	3 == 3? Yes	current -> node with value 3	1 -> 2 -> 3 -> 4 -> null
4	Return found	3	Match found	Stop	1 -> 2 -> 3 -> 4 -> null

💡 Value 3 found at step 3, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
current	head (value 1)	node with value 1	node with value 2	node with value 3	node with value 3

Key Moments - 3 Insights

Why do we check if current is nil before comparing values?

Because if current is nil, it means we've reached the end of the list and there is no node to check. This is shown in execution_table step 1 where the loop condition current != nil is checked before comparing values.

What happens if the target value is not in the list?

The loop will continue moving current to next nodes until current becomes nil (end of list). Then the function returns false. This is implied by the exit condition in the concept flow and the exit_note in execution_table.

Why do we move current to current.next after each comparison?

To check the next node in the list. Without moving current, we would check the same node repeatedly causing an infinite loop. This is shown in execution_table steps 2 and 3 where pointer changes move current forward.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of current at step 2?

A Node with value 2

B Node with value 1

C Node with value 3

D nil

💡 Hint

Check the 'Pointer Changes' column at step 2 in execution_table.

At which step does the search find the target value 3?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Look at the 'Comparison with Target (3)' column for the first 'Yes' match.

If the target was 5 (not in list), what would happen to current pointer?

A Stops at node with value 4

B Stays at head node

C Moves to nil after last node

D Moves to node with value 3 and stops

💡 Hint

Refer to concept_flow where current moves until it becomes nil if target not found.

Concept Snapshot

Search in Linked List:
- Start at head node
- While current node not nil:
  - Compare node value with target
  - If match, return found
  - Else move to next node
- If end reached, return not found

Full Transcript

This concept shows how to search for a value in a linked list. We start at the head node and check if the current node is nil. If not, we compare the current node's value with the target. If they match, we stop and return found. Otherwise, we move to the next node and repeat. If we reach the end of the list without finding the target, we return not found. The execution table traces each step, showing the current node, comparisons, pointer moves, and the list state. Key moments clarify why we check for nil before comparing, what happens if the target is missing, and why we move the pointer forward. The visual quiz tests understanding of pointer positions and stopping conditions.

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