Search for a Value in Linked List in DSA Javascript

Mental Model

We look at each item in the list one by one until we find the value or reach the end.

Analogy: Like checking each book on a shelf from left to right to find a specific title.

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

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null, search value: 2

Goal: Find if the value 2 exists in the linked list

Step 1: start at head node with value 1

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

Why: We begin searching from the first node

Step 2: compare current node value 1 with search value 2; not equal, move to next node

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

Why: Value not found yet, so check next node

Step 3: compare current node value 2 with search value 2; found match

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

Why: Found the value we are searching for

Result:

head -> 1 -> [curr->2] -> 3 -> null
Result: true (value found)

Annotated Code

DSA Javascript

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

class LinkedList {
  constructor() {
    this.head = null;
  }

  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let curr = this.head;
    while (curr.next) {
      curr = curr.next; // advance curr to next node
    }
    curr.next = newNode; // link new node at the end
  }

  search(value) {
    let curr = this.head;
    while (curr) {
      if (curr.value === value) {
        return true; // found the value
      }
      curr = curr.next; // move to next node
    }
    return false; // value not found
  }
}

// Driver code
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
const searchValue = 2;
console.log(list.search(searchValue));

while (curr) {

iterate through each node until end

if (curr.value === value) {

check if current node holds the search value

curr = curr.next;

advance to next node to continue search

Output

true

Complexity Analysis

Time: O(n) because in the worst case we check each node once until we find the value or reach the end

Space: O(1) because we only use a few variables regardless of list size

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

Edge Cases

empty list

search returns false immediately because head is null

DSA Javascript

while (curr) {

value at head node

search returns true immediately on first check

DSA Javascript

if (curr.value === value) {

value not in list

search traverses entire list and returns false

DSA Javascript

return false; // value not found

When to Use This Pattern

When you need to find if a value exists in a linked list, use linear search by checking nodes one by one until found or end.

Common Mistakes

Mistake: Not moving to the next node inside the loop, causing infinite loop
Fix: Add 'curr = curr.next;' inside the while loop to advance the pointer

Mistake: Checking for value after moving pointer, missing head node check
Fix: Check current node's value before moving to next node

Summary

Searches for a specific value by checking each node in the linked list one by one.

Use when you need to find if a value exists in a linked list without extra data structures.

The key is to start at the head and move through nodes 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 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