Search for a Value in Linked List in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after searching for a value in the linked list?

Consider the following C++ code that creates a linked list and searches for a value. What will be printed?

DSA C++

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

bool search(Node* head, int key) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == key) {
            return true;
        }
        current = current->next;
    }
    return false;
}

int main() {
    Node* head = new Node(10);
    head->next = new Node(20);
    head->next->next = new Node(30);

    if (search(head, 20)) {
        std::cout << "Found" << std::endl;
    } else {
        std::cout << "Not Found" << std::endl;
    }
    return 0;
}

A Compilation Error

B Not Found

C Found

D Runtime Error

💡 Hint

Check if the value 20 exists in the linked list nodes.

The linked list contains nodes with values 10, 20, and 30. The search function checks each node's data. Since 20 is present, it returns true and prints 'Found'.

❓ Predict Output

intermediate

What is the output when searching for a missing value?

Given the linked list below, what will be the output when searching for the value 40?

DSA C++

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

bool search(Node* head, int key) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == key) {
            return true;
        }
        current = current->next;
    }
    return false;
}

int main() {
    Node* head = new Node(5);
    head->next = new Node(15);
    head->next->next = new Node(25);

    if (search(head, 40)) {
        std::cout << "Found" << std::endl;
    } else {
        std::cout << "Not Found" << std::endl;
    }
    return 0;
}

A Compilation Error

B Segmentation Fault

C Found

D Not Found

💡 Hint

Check if the value 40 is present in the linked list nodes.

The linked list contains 5, 15, and 25. Since 40 is not in the list, the search returns false and prints 'Not Found'.

🔧 Debug

advanced

What error does this code produce when searching an empty linked list?

Analyze the code below. What error will occur when searching for a value in an empty linked list?

DSA C++

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

bool search(Node* head, int key) {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == key) {
            return true;
        }
        current = current->next;
    }
    return false;
}

int main() {
    Node* head = nullptr;
    if (search(head, 10)) {
        std::cout << "Found" << std::endl;
    } else {
        std::cout << "Not Found" << std::endl;
    }
    return 0;
}

A No error, prints 'Not Found'

B Segmentation Fault

C Compilation Error

D Infinite Loop

💡 Hint

Consider what happens when head is nullptr and the while loop condition.

The search function checks if current is nullptr before accessing data. Since head is nullptr, the loop does not run and returns false safely.

🧠 Conceptual

advanced

How many nodes are checked when searching for a value not present in the list?

If a linked list has 4 nodes and the searched value is not present, how many nodes does the search function check before returning false?

A 4

B 0

C 5

D 3

💡 Hint

The search checks each node until it reaches the end.

The search function visits every node to check its data. For 4 nodes, it checks all 4 before concluding the value is not found.

🚀 Application

expert

What is the output after searching for a value in a circular linked list?

Consider a circular linked list where the last node points back to the head. The search function below is used to find a value. What will happen when searching for 15?

DSA C++

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

bool search(Node* head, int key) {
    Node* current = head;
    if (head == nullptr) return false;
    do {
        if (current->data == key) {
            return true;
        }
        current = current->next;
    } while (current != head);
    return false;
}

int main() {
    Node* head = new Node(10);
    Node* second = new Node(15);
    Node* third = new Node(20);
    head->next = second;
    second->next = third;
    third->next = head; // circular link

    if (search(head, 15)) {
        std::cout << "Found" << std::endl;
    } else {
        std::cout << "Not Found" << std::endl;
    }
    return 0;
}

A Segmentation Fault

B Found

C Infinite Loop

D Not Found

💡 Hint

The search uses a do-while loop to handle circular lists.

The search function uses a do-while loop that stops when it returns to the head. It finds 15 in the second node and returns true, printing 'Found'.

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