Search for a Value in Linked List in DSA Javascript - 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

↓

Found value, stop

↩Back to check if current node is 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 Javascript

function search(head, target) {
  let current = head;
  while (current !== null) {
    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 from head to end.

Execution Table

Step	Operation	Current Node Value	Pointer Changes	Visual State
1	Start at head	3	current = head (3)	3 -> 7 -> 10 -> 15 -> null
2	Compare current.value with target (7)	3	current = current.next (7)	3 -> 7 -> 10 -> 15 -> null
3	Compare current.value with target (7)	7	Found target, stop	3 -> 7 -> 10 -> 15 -> null

💡 Found target value 7 at step 3, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3 (End)
current	head (3)	3	7	7
target	7	7	7	7

Key Moments - 3 Insights

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

Because if current is null, it means we've reached the end of the list and the value is not found. This is shown in step 2 where we move current to next before comparing.

What happens if the target value is at the head node?

The search finds the value immediately at step 1 and stops without moving to next nodes. This is shown by comparing current.value with target right after starting.

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

To move forward in the list and check the next node. This is shown in step 2 where current changes from 3 to 7 after the first comparison.

Visual Quiz - 3 Questions

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

A 10

B 3

C 7

D null

💡 Hint

Check the 'Current Node Value' column at step 2 in the execution table.

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

A Step 3

B Step 1

C Step 2

D Search never stops

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns to see when the target is found.

If the target was 15 instead of 7, what would happen at step 2?

A Current would move to node with value 10

B Search would stop at node with value 3

C Current would move to node with value 7

D Search would find target at node with value 7

💡 Hint

Refer to how current moves to next node when value does not match, as shown in step 2.

Concept Snapshot

Search in Linked List:
- Start at head node
- Check if current node is null (end)
- Compare current node 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 the current node is null. If not, we compare the current node's value with the target. If they match, we stop and return true. Otherwise, we move to the next node and repeat. If we reach the end (null) without finding the target, we return false. The execution table tracks each step, the current node's value, pointer changes, and the visual state of the list. Variable tracker shows how the current pointer moves through the list. Key moments clarify why we check for null before comparing, what happens if the target is at the head, and why we move current to next after each check. The quiz tests understanding of these steps and pointer movements.

Practice

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

easy

A. To find if the value exists in the list

B. To add a new node at the end

C. To delete the first node

D. To reverse the linked list

Solution

1. Step 1: Understand the search operation

   Searching in a linked list 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 list, not to modify the list.

3. Final Answer:

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

4. Quick Check:

   Search means find value presence = C [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 searching a linked list in JavaScript if head is the first node?

easy

A. let current = null;

B. let current = head;

C. let current = head.next.next;

D. let current = head.value;

Solution

1. Step 1: Understand the starting point of search

   Search starts from the first node, so we assign the first node to a variable to traverse.

2. Step 2: Choose the correct assignment

   Assigning head to current lets us start from the first node and move forward.

3. Final Answer:

   let current = head; -> Option B

4. Quick Check:

   Start search at head node = B [OK]

Hint: Start search at head node with let current = head [OK]

Common Mistakes:

• Starting at null means no nodes to check
• Skipping nodes by starting at head.next.next
• Assigning value instead of node reference

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

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

function search(head, target) {
  let current = head;
  while (current !== null) {
    if (current.value === target) {
      return true;
    }
    current = current.next;
  }
  return false;
}

console.log(search(head, 10));
console.log(search(head, 20));

medium

A. true\ntrue

B. false\ntrue

C. true\nfalse

D. false\nfalse

Solution

1. Step 1: Trace search for value 10

   Nodes are 5 -> 10 -> 15. The search finds 10 in the second node and returns true.

2. Step 2: Trace search for value 20

   20 is not in the list, so the loop ends and returns false.

3. Final Answer:

   true\nfalse -> Option C

4. Quick Check:

   10 found = true, 20 not found = false [OK]

Hint: Return true if found, else false after full traversal [OK]

Common Mistakes:

• Returning false too early
• Not updating current to next node
• Confusing value with node reference

4. Identify the error in the following search function for a linked list:

function search(head, target) {
  let current = head;
  while (current.next !== null) {
    if (current.value === target) {
      return true;
    }
    current = current.next;
  }
  return false;
}

medium

A. It does not check the last node's value

B. It uses incorrect variable names

C. It returns true too early

D. It never updates current

Solution

1. Step 1: Analyze the 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

   The last node's value is never checked because loop ends early, so search may miss target at last node.

3. Final Answer:

   It does not check the last node's value -> Option A

4. Quick Check:

   Loop misses last node check = D [OK]

Hint: Loop until current is null, not current.next [OK]

Common Mistakes:

• Using current.next !== null instead of current !== null
• Forgetting to check last node
• Assuming loop covers all nodes

5. Given a linked list where each node contains a number, how would you modify the search function to return the position (1-based) of the first occurrence of a target value, or -1 if not found?

hard

A. Reverse the list before searching for the value

B. Return true if value found; else false

C. Count total nodes first; then search for value

D. Initialize a position counter at 1; traverse nodes; return position if value matches; else -1

Solution

1. Step 1: Add a position counter starting at 1

   Initialize a variable to track the current node's position as you traverse the list.

2. Step 2: Traverse and compare values

   For each node, check if its value matches the target. If yes, return the current position.

3. Step 3: Return -1 if not found

   If traversal ends without finding the target, return -1 to indicate absence.

4. Final Answer:

   Initialize a position counter at 1; traverse nodes; return position if value matches; else -1 -> Option D

5. Quick Check:

   Position tracking with traversal = A [OK]

Hint: Track position while searching; return position or -1 [OK]

Common Mistakes:

• Returning boolean instead of position
• Not updating position counter
• Reversing list unnecessarily