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

Concept Flow - Search for a Value in Linked List

Start at head node

↓

Check if current node is None?

Yes→Value not found, stop

No↓

Compare current node value with target

↓

Value found, stop

↩Back to check None

Start from the head node, check each node's value. If it matches the target, stop. If not, move to the next node until the end.

Execution Sample

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def search(head, target):
    current = head
    while current:
        if current.val == target:
            return True
        current = current.next
    return False

This code searches for a target value in a linked list by checking each node from head to end.

Execution Table

Step	Operation	Current Node Value	Comparison with Target	Pointer Changes	Visual State
1	Start at head	3	3 == 5? No	current -> Node(3)	3 -> 7 -> 10 -> 5 -> None
2	Move to next node	7	7 == 5? No	current -> Node(7)	3 -> 7 -> 10 -> 5 -> None
3	Move to next node	10	10 == 5? No	current -> Node(10)	3 -> 7 -> 10 -> 5 -> None
4	Move to next node	5	5 == 5? Yes	current -> Node(5)	3 -> 7 -> 10 -> 5 -> None
5	Value found	5	Stop search	current stays	3 -> 7 -> 10 -> 5 -> None

💡 Value found at step 4, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
current	Node(3)	Node(3)	Node(7)	Node(10)	Node(5)	Node(5)
target	5	5	5	5	5	5

Key Moments - 3 Insights

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

Because if current is None, it means we've reached the end of the list and there are no more nodes to check. This is shown in execution_table step 1 where the loop condition is evaluated before comparison.

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

The loop moves through all nodes until current becomes None, then returns False. This is implied by the exit condition in the concept flow and would be shown if the target was not found.

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

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

Visual Quiz - 3 Questions

Look at the execution table, what is the value of current at step 3?

A Node with value 5

B Node with value 7

C Node with value 10

D None

💡 Hint

Check the 'Current Node Value' column at step 3 in the execution_table.

At which step does the search stop because the value is found?

A Step 2

B Step 4

C Step 5

D Step 3

💡 Hint

Look for the row where 'Comparison with Target' is '5 == 5? Yes'.

If the target was 8 instead of 5, what would happen in the execution table?

A Search would continue until current becomes None and then stop

B Search would stop at step 4

C Search would find value at step 3

D Search would stop immediately at step 1

💡 Hint

Refer to the concept_flow and key_moments about what happens when value is not found.

Concept Snapshot

Search for a value in a linked list:
- Start at head node
- Check if current node is None (end)
- Compare current node's value with target
- If match, stop and return True
- Else move to next node
- If end reached without match, return False

Full Transcript

This visual trace shows how to search for a value in a linked list. We start at the head node and check if it is None to avoid errors. Then we compare the current node's value with the target. If they match, we stop and return True. If not, we move to the next node and repeat. If we reach the end of the list (current is None) without finding the target, we return False. The execution table tracks each step, showing the current node's value, comparisons, pointer moves, and the linked list's visual state. The variable tracker shows how the current pointer moves through the list. Key moments clarify why we check for None first, what happens if the value is not found, and why we move to the next node each time. The quiz tests understanding of these steps and outcomes.

Practice

1. What does searching for a value in a linked list involve?

easy

A. Sorting the list first then searching for the value

B. Jumping directly to the middle node to find the value

C. Checking each node one by one until the value is found or list ends

D. Using an index to access the value directly

Solution

1. Step 1: Understand linked list traversal

   Linked lists do not have indexes, so we must check nodes one by one from the start.

2. Step 2: Search each node for the value

   We compare the target value with each node's data until we find a match or reach the end.

3. Final Answer:

   Checking each node one by one until the value is found or list ends -> Option C

4. Quick Check:

   Search = Sequential check [OK]

Hint: Traverse nodes sequentially to find the value [OK]

Common Mistakes:

• Assuming direct access by index
• Trying to jump to middle node without traversal
• Sorting before searching in linked list

2. Which of the following is the correct way to start searching for a value in a singly linked list named head?

easy

A. current = head.next

B. current = head

C. current = None

D. current = head.prev

Solution

1. Step 1: Identify the starting node

   Search starts from the first node, which is referenced by head.

2. Step 2: Assign current pointer correctly

   Set current = head to begin traversal from the first node.

3. Final Answer:

   current = head -> Option B

4. Quick Check:

   Start at head node [OK]

Hint: Always start search from head node [OK]

Common Mistakes:

• Starting from head.next skips first node
• Setting current to None causes no traversal
• Using head.prev in singly linked list (no prev pointer)

3. What will be the output of the following code?

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def search(head, target):
    current = head
    while current:
        if current.data == target:
            return True
        current = current.next
    return False

# Create linked list: 5 -> 10 -> 15 -> None
head = Node(5)
head.next = Node(10)
head.next.next = Node(15)

print(search(head, 10))
print(search(head, 20))

medium

A. True\nFalse

B. False\nTrue

C. True\nTrue

D. False\nFalse

Solution

1. Step 1: Trace search for 10

   Nodes checked: 5 (no), 10 (yes) -> returns True.

2. Step 2: Trace search for 20

   Nodes checked: 5, 10, 15 (none match) -> returns False.

3. Final Answer:

   True\nFalse -> Option A

4. Quick Check:

   10 found, 20 not found [OK]

Hint: Return True immediately when value found [OK]

Common Mistakes:

• Returning False too early
• Not moving to next node correctly
• Confusing True/False outputs

4. Find the error in this search function for a linked list:

def search(head, target):
    current = head
    while current.next:
        if current.data == target:
            return True
        current = current.next
    return False

medium

A. The loop condition should be while current, not while current.next

B. The return False should be inside the loop

C. The function should return the node, not True

D. The current pointer should start at head.next

Solution

1. Step 1: Analyze loop condition

   Using while current.next skips checking the last node.

2. Step 2: Correct loop to include last node

   Change to while current to check all nodes including last.

3. Final Answer:

   The loop condition should be while current, not while current.next -> Option A

4. Quick Check:

   Loop must check all nodes [OK]

Hint: Use while current to include last node in search [OK]

Common Mistakes:

• Stopping before last node
• Returning False too early
• Starting current at head.next skips first node

5. You have a linked list with nodes containing values: 3 -> 7 -> 3 -> 9 -> None. You want to find if value 3 exists and also count how many times it appears. Which approach correctly combines search and count?

hard

A. Use recursion to find first 3, then stop

B. Search for 3 once, then traverse again to count occurrences

C. Sort the list first, then count consecutive 3s

D. Traverse the list once, increment count each time node data equals 3, then check if count > 0

Solution

1. Step 1: Traverse list once counting matches

   Check each node; if data is 3, increase count.

2. Step 2: After traversal, check if count > 0

   If count is more than zero, value 3 exists and count shows occurrences.

3. Final Answer:

   Traverse the list once, increment count each time node data equals 3, then check if count > 0 -> Option D

4. Quick Check:

   Single pass count and check [OK]

Hint: Count while searching in one pass [OK]

Common Mistakes:

• Doing two separate traversals
• Sorting linked list unnecessarily
• Stopping after first find without counting all