Search for a Value in Linked List in DSA C++

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: Found the value we are searching for

Result:

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

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

bool searchValue(Node* head, int target) {
    Node* curr = head; // start at head
    while (curr != nullptr) { // traverse until end
        if (curr->data == target) {
            return true; // found value
        }
        curr = curr->next; // move to next node
    }
    return false; // value not found
}

int main() {
    // create linked list 1->2->3->null
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);

    int target = 2;
    bool found = searchValue(head, target);
    if (found) {
        cout << "Value " << target << " found in the list" << endl;
    } else {
        cout << "Value " << target << " not found in the list" << endl;
    }

    // free memory
    Node* curr = head;
    while (curr != nullptr) {
        Node* next = curr->next;
        delete curr;
        curr = next;
    }
    return 0;
}

Node* curr = head; // start at head

initialize current pointer to head to start traversal

while (curr != nullptr) { // traverse until end

loop through nodes until reaching end of list

if (curr->data == target) {

check if current node's data matches target value

return true; // found value

stop search and return true when value found

curr = curr->next; // move to next node

advance current pointer to next node to continue search

return false; // value not found

return false if reached end without finding value

Output

Value 2 found in the list

Complexity Analysis

Time: O(n) because we may need to check each node once until we find the value or reach the end

Space: O(1) because we only use a few pointers 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 one by one

Edge Cases

empty list

search returns false immediately because head is null

DSA C++

while (curr != nullptr) {

value at head node

search returns true immediately without traversing further

DSA C++

if (curr->data == target) {

value not in list

search traverses entire list and returns false

DSA C++

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 traversal checking each node until found or end reached.

Common Mistakes

Mistake: Not checking for null before accessing node data, causing runtime errors
Fix: Always check if current node is not null before accessing its data

Mistake: Stopping search too early without checking all nodes
Fix: Continue traversal until value found or list ends

Summary

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

Use when you need to check if a value exists 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 add a new node at the end of the list

B. To find if a specific value exists in the list

C. To delete the first node of the list

D. To reverse the order of nodes in the list

Solution

1. Step 1: Understand the search operation

   Searching in a linked list means checking each node to see if it contains the value we want.

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 a specific value exists in the list -> Option B

4. Quick Check:

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

Hint: Search means check each node for the value [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 syntax to start traversing a singly linked list in C++?

easy

A. Node* current = new Node();

B. Node current = head;

C. Node current = new Node();

D. Node* current = head;

Solution

1. Step 1: Understand pointer usage in linked lists

   In C++, linked list nodes are accessed via pointers, so we use a pointer variable to traverse.

2. Step 2: Identify correct pointer initialization

   We set a pointer 'current' to point to the head node to start traversal: Node* current = head;

3. Final Answer:

   Node* current = head; -> Option D

4. Quick Check:

   Use pointer to start traversal = Node* current = head; [OK]

Hint: Use pointer to traverse linked list starting at head [OK]

Common Mistakes:

• Using object instead of pointer for traversal
• Creating a new node instead of using existing head
• Not initializing traversal pointer correctly

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

struct Node {
  int data;
  Node* next;
};

Node* head = new Node{10, nullptr};
head->next = new Node{20, nullptr};
head->next->next = new Node{30, nullptr};

Node* current = head;
int searchValue = 20;
bool found = false;
while (current != nullptr) {
  if (current->data == searchValue) {
    found = true;
    break;
  }
  current = current->next;
}
if (found) std::cout << "Value found";
else std::cout << "Value not found";

medium

A. Value not found

B. Compilation error

C. Value found

D. Runtime error

Solution

1. Step 1: Trace the linked list nodes and values

   The list has nodes with values 10 -> 20 -> 30. We search for 20.

2. Step 2: Check the search loop logic

   The loop checks each node's data. When it reaches node with 20, found becomes true and loop breaks.

3. Final Answer:

   Value found -> Option C

4. Quick Check:

   20 exists in list, so output = "Value found" [OK]

Hint: Check each node's data until match or end [OK]

Common Mistakes:

• Forgetting to update current pointer
• Using wrong comparison operator
• Not breaking loop after finding value

4. Identify the error in the following code that searches for a value in a linked list:

Node* current = head;
int searchValue = 15;
while (current->next != nullptr) {
  if (current->data == searchValue) {
    std::cout << "Found";
    break;
  }
  current = current->next;
}
if (current == nullptr) std::cout << "Not Found";

medium

A. The loop condition skips checking the last node

B. The searchValue variable is not initialized

C. The current pointer is not updated inside the loop

D. The output statements are missing semicolons

Solution

1. Step 1: Analyze the loop condition

   The loop runs while current->next is not nullptr, so it stops before the last node.

2. Step 2: Understand impact on search

   The last node's data is never checked, so if the value is there, it will be missed.

3. Final Answer:

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

4. Quick Check:

   Loop must check all nodes including last [OK]

Hint: Loop on current != nullptr to check all nodes [OK]

Common Mistakes:

• Using current->next != nullptr instead of current != nullptr
• Not checking last node's data
• Incorrectly handling nullptr checks

5. You want to search for a value in a singly linked list and return its position (1-based index). Which approach correctly implements this?

int searchPosition(Node* head, int value) {
  int pos = 1;
  Node* current = head;
  while (current != nullptr) {
    if (current->data == value) return pos;
    current = current->next;
    pos++;
  }
  return -1;
}

hard

A. Returns the position of value or -1 if not found

B. Returns true if value found, false otherwise

C. Returns the last node's data always

D. Returns 0 if value is found at head

Solution

1. Step 1: Understand the function logic

   The function starts position at 1 and traverses nodes, checking data against value.

2. Step 2: Check return values

   If value matches, it returns current position; if not found, returns -1.

3. Final Answer:

   Returns the position of value or -1 if not found -> Option A

4. Quick Check:

   Function returns index or -1 if missing [OK]

Hint: Return index on match, else -1 after full traversal [OK]

Common Mistakes:

• Returning boolean instead of position
• Starting position count at 0 instead of 1
• Not returning -1 when value not found