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

Concept Flow - Search for a Value in Linked List

Start at head node

↓

Is current node null?

Yes→Value not found, stop

No↓

Check if current node value == target

↓

Value found, stop

↓

Is current node null?

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

Execution Sample

DSA Java

Node current = head;
while (current != null) {
  if (current.value == target) {
    return true;
  }
  current = current.next;
}
return false;

This code searches each node in the linked list for the target value and returns true if found, false otherwise.

Execution Table

Step	Operation	Current Node Value	Pointer Changes	Visual State
1	Start at head	3	current -> Node(3)	3 -> 7 -> 10 -> 15 -> null
2	Check if current.value == target(10)	3	No pointer change	3 -> 7 -> 10 -> 15 -> null
3	Move to next node	7	current -> Node(7)	3 -> 7 -> 10 -> 15 -> null
4	Check if current.value == target(10)	7	No pointer change	3 -> 7 -> 10 -> 15 -> null
5	Move to next node	10	current -> Node(10)	3 -> 7 -> 10 -> 15 -> null
6	Check if current.value == target(10)	10	No pointer change	3 -> 7 -> 10 -> 15 -> null
7	Value found, stop	10	No pointer change	3 -> 7 -> 10 -> 15 -> null

💡 Value 10 found at step 6, search stops.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7 (End)
current	Node(3)	Node(7)	Node(10)	Node(10)

Key Moments - 3 Insights

Why do we check if current is null before accessing current.value?

Because if current is null, it means we've reached the end of the list and there is no node to check. Accessing current.value when current is null would cause an error. See execution_table step 2 where the check happens before value comparison.

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

The loop continues moving current to next nodes until current becomes null, meaning the end of the list is reached without finding the target. Then the function returns false. This is implied by the exit condition in the concept flow.

Why do we move current to current.next after each failed check?

Because we need to check every node in the list one by one. Moving current to current.next advances the search to the next node. See execution_table steps 3 and 5 where current pointer changes to next nodes.

Visual Quiz - 3 Questions

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

A Node with value 7

B Node with value 10

C Node with value 15

D null

💡 Hint

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

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

A Step 7

B Step 4

C Step 6

D Step 8

💡 Hint

Look for the row where 'Value found, stop' appears in the 'Operation' column.

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

A It would stop at Node(15)

B It would jump back to head

C It would become null after Node(15)

D It would point to Node(10)

💡 Hint

Refer to the concept_flow where the search continues until current is null if value not found.

Concept Snapshot

Search for a value in a linked list:
- Start at head node
- Check current node's value
- If matches target, stop and return true
- Else move to next node
- Repeat until end (null) reached
- Return false if not found

Full Transcript

To search for a value in a linked list, start at the head node. Check if the current node is null; if yes, the value is not found and stop. If not null, compare the current node's value with the target. If they match, stop and return true. Otherwise, move to the next node and repeat the process. Continue until the value is found or the list ends. This process ensures every node is checked one by one.

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 delete the first node

C. To find if the value exists in the list

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 is present or not in the linked list.

3. Final Answer:

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

4. Quick Check:

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

Hint: Search means check nodes for value presence [OK]

Common Mistakes:

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

2. Which of the following is the correct way to start traversing a linked list in Java to search for a value target?

easy

A. Node current = head; while(current != null) { if(current.data == target) break; current = current.next; }

B. Node current = null; while(current != head) { if(current.data == target) break; current = current.next; }

C. Node current = head; while(current.next != null) { if(current.data == target) break; current = current.next; }

D. Node current = head.next; while(current != null) { if(current.data == target) break; current = current.next; }

Solution

1. Step 1: Initialize traversal from head node

   Traversal must start from the head node to check all nodes including the first.

2. Step 2: Loop until current is null

   Loop continues while current is not null to cover all nodes.

3. Final Answer:

   Node current = head; while(current != null) { if(current.data == target) break; current = current.next; } -> Option A

4. Quick Check:

   Start at head and loop till null = Node current = head; while(current != null) { if(current.data == target) break; current = current.next; } [OK]

Hint: Start at head; loop while node not null [OK]

Common Mistakes:

• Starting traversal from null or head.next
• Looping until current.next is null misses last node
• Using wrong loop condition causing errors

3. What will be the output of the following code snippet if the linked list contains nodes with values 3 -> 5 -> 7 -> null and we search for value 5?

Node current = head;
boolean found = false;
while(current != null) {
  if(current.data == 5) {
    found = true;
    break;
  }
  current = current.next;
}
System.out.println(found);

medium

A. false

B. null

C. Compilation error

D. true

Solution

1. Step 1: Traverse nodes checking for value 5

   Nodes checked in order: 3 (no), 5 (yes), loop breaks and found = true.

2. Step 2: Print the found variable

   Since value 5 is found, found is true, so output is true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Value 5 found = true [OK]

Hint: If value found, print true; else false [OK]

Common Mistakes:

• Assuming output is node data instead of boolean
• Thinking loop misses the value 5
• Confusing true/false output

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 == target) {
    System.out.println("Found");
    break;
  }
  current = current.next;
}

medium

A. It causes a null pointer exception

B. It misses checking the last node

C. It never breaks the loop

D. It prints "Found" multiple times

Solution

1. Step 1: Analyze loop condition

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

2. Step 2: Check if last node is checked

   Since last node's next is null, last node is never checked for target value.

3. Final Answer:

   It misses checking the last node -> Option B

4. Quick Check:

   Loop condition excludes last node = misses last node check [OK]

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

Common Mistakes:

• Using current.next != null instead of current != null
• Assuming last node is checked
• Ignoring possibility of missing target at last node

5. Given a singly linked list where each node contains an integer, write a method to return the index (0-based) of the first occurrence of a target value. If the value is not found, return -1. Which approach correctly implements this search?

hard

A. Traverse from head, increment index each step, return index if found, else -1 after loop

B. Traverse from head, return node data if found, else return null

C. Traverse from tail backwards, return index if found, else 0

D. Traverse from head, increment index only when value matches, return index or -1

Solution

1. Step 1: Traverse from head with index counter

   Start at head, keep an index starting at 0, check each node's data.

2. Step 2: Return index if value matches, else -1 after full traversal

   If node data equals target, return current index; if not found after loop, return -1.

3. Final Answer:

   Traverse from head, increment index each step, return index if found, else -1 after loop -> Option A

4. Quick Check:

   Index search = traverse + count + return index or -1 [OK]

Hint: Count nodes from head; return index on match, else -1 [OK]

Common Mistakes:

• Returning node data instead of index
• Traversing from tail in singly linked list (not possible)
• Incrementing index only on match causing wrong count