Search for a Value in Linked List in DSA Typescript

Mental Model

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

Analogy: Like flipping through pages of a book to find a specific word, checking each page in order.

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

Dry Run Walkthrough

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

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

Step 1: Start at the head node with value 1

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

Why: We begin searching from the first node

Step 2: Check if current node value (1) equals 2; it does not, move to next node

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

Why: Value not found yet, continue to next node

Step 3: Check if current node value (2) equals 2; it does, stop search

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

Why: Value found, no need to continue

Result:

head -> 1 -> [curr->2] -> 3 -> null
Value 2 found in the list

Annotated Code

DSA Typescript

class ListNode {
  value: number;
  next: ListNode | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

function searchLinkedList(head: ListNode | null, target: number): boolean {
  let curr = head;
  while (curr !== null) {
    if (curr.value === target) {
      return true; // found the target value
    }
    curr = curr.next; // move to next node
  }
  return false; // reached end without finding
}

// Driver code
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

const target = 2;
const found = searchLinkedList(head, target);
console.log(found ? `Value ${target} found in the list` : `Value ${target} not found in the list`);

while (curr !== null) {

keep checking nodes until we reach the end

if (curr.value === target) {

check if current node has the target value

return true; // found the target value

stop search and report success

curr = curr.next; // move to next node

advance to next node to continue search

return false; // reached end without finding

target not found after full traversal

Output

Value 2 found in the list

Complexity Analysis

Time: O(n) because we may need to check every node once

Space: O(1) because we only use a single pointer variable

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

Edge Cases

empty list

search returns false immediately

DSA Typescript

while (curr !== null) {

value at head node

search finds value immediately and returns true

DSA Typescript

if (curr.value === target) {

value not in list

search traverses entire list and returns false

DSA Typescript

return false; // reached end without finding

When to Use This Pattern

When you need to find if a value exists in a linked list, use linear search by checking each node one by one.

Common Mistakes

Mistake: Not checking if the current node is null before accessing its value
Fix: Always check 'curr !== null' in the loop condition before accessing 'curr.value'

Summary

Searches each node in the linked list to find a target value.

Use when you need to check presence of a value in a linked list.

The key is to move node by node 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 reverse the linked list

B. To find if the value exists in the list

C. To delete the first node

D. To add a new node at the end

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 B

4. Quick Check:

   Search means find value presence [OK]

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

Common Mistakes:

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

2. Which of the following is the correct way to start searching a linked list in TypeScript?

easy

A. let current = new Node();

B. let current = tail;

C. let current = null;

D. let current = head;

Solution

1. Step 1: Identify the starting point of search

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

2. Step 2: Check each option

   let current = head; correctly initializes current to head. let current = tail; starts at tail which is incorrect for forward search. let current = null; sets current to null, meaning no start. let current = new Node(); creates a new node, unrelated to searching.

3. Final Answer:

   let current = head; -> Option D

4. Quick Check:

   Search starts at head node [OK]

Hint: Always start search from head node [OK]

Common Mistakes:

• Starting search from tail instead of head
• Initializing current to null before search
• Creating a new node instead of using existing nodes

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

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    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: Node | null, target: number): boolean {
  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\nfalse

B. false\ntrue

C. true\ntrue

D. false\nfalse

Solution

1. Step 1: Trace search for value 10

   The list nodes are 5 -> 10 -> 15. Searching for 10 finds it at the second node, so returns true.

2. Step 2: Trace search for value 20

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

3. Final Answer:

   true\nfalse -> Option A

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 true for values not in list
• Stopping search too early
• Confusing output order

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

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

medium

A. The loop condition misses checking the last node

B. The function should return a number instead of boolean

C. The current variable should be initialized to null

D. The function should use a for loop instead of while

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: Understand impact on search

   If the target is in the last node, it will not be checked, causing incorrect false result.

3. Final Answer:

   The loop condition misses checking the last node -> Option A

4. Quick Check:

   Loop must check all nodes including last [OK]

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

Common Mistakes:

• Using current.next !== null instead of current !== null
• Returning wrong data type
• Incorrect initialization of current

5. Given a singly linked list with possible duplicate values, how can you modify the search function to return the count of occurrences of a target value instead of just true/false?

function countOccurrences(head: Node | null, target: number): number {
  // Your code here
}

hard

A. Return 1 if target found once, else 0

B. Stop at first match and return true

C. Traverse all nodes, increment count when value matches, return count

D. Use recursion without counting matches

Solution

1. Step 1: Understand the requirement

   We need to count how many times the target appears, so we must check every node.

2. Step 2: Plan the traversal and counting

   Initialize a count to zero, traverse all nodes, increment count when node value equals target, then return count.

3. Final Answer:

   Traverse all nodes, increment count when value matches, return count -> Option C

4. Quick Check:

   Count all matches, not just presence [OK]

Hint: Count matches during full traversal, then return count [OK]

Common Mistakes:

• Stopping search after first match
• Returning boolean instead of count
• Not traversing entire list