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

Start from the head node, check each node's value. If it matches the target, stop. Otherwise, move to the next node until the list ends.

Execution Sample

DSA C

Node* current = head;
while (current != NULL) {
  if (current->value == target) {
    return current;
  }
  current = current->next;
}
return NULL;

This code searches each node in the linked list for the target value and returns the node if found, else NULL.

Execution Table

Step	Operation	Current Node Value	Pointer Changes	Visual State
1	Start at head	3	current = head (3)	[3] -> [5] -> [7] -> NULL
2	Compare current value with target (5)	3	No pointer change	[3] -> [5] -> [7] -> NULL
3	Move to next node	5	current = current->next (5)	[3] -> [5] -> [7] -> NULL
4	Compare current value with target (5)	5	No pointer change	[3] -> [5] -> [7] -> NULL
5	Value matches target	5	Stop search	[3] -> [5] -> [7] -> NULL

💡 Value 5 found at step 5, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5
current	head (3)	3	5	5
target	5	5	5	5

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 without finding the value. Checking NULL first prevents errors when accessing current->value. See execution_table step 2.

What happens if the value is not in the list?

The loop continues moving current to next nodes until current becomes NULL, then the search stops returning NULL. This is shown by the exit condition in the concept flow.

Why do we move current to current->next after each failed comparison?

To check the next node in the list. Without moving forward, the search would get stuck on the same node. See execution_table step 3.

Visual Quiz - 3 Questions

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

A 3

B 7

C 5

D NULL

💡 Hint

Check the 'Pointer Changes' and 'Current Node Value' columns at step 3.

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

A Step 3

B Step 5

C Step 4

D Step 2

💡 Hint

Look for the row where 'Value matches target' and 'Stop search' appear.

If the target was 7 instead of 5, at which step would the value be found?

A Step 6

B Step 3

C Step 5

D Step 4

💡 Hint

Think about how many nodes are checked before finding 7 in the list.

Concept Snapshot

Search in Linked List:
- Start at head node
- While current != NULL:
  - Check if current->value == target
  - If yes, stop and return node
  - Else move to current->next
- If end reached (NULL), value not found

Full Transcript

This visualization shows how to search for a value in a linked list. We start at the head node and check if the current node's value matches the target. If it does, we stop and return the node. If not, we move to the next node and repeat. If we reach the end of the list (NULL) without finding the value, the search ends with no result. The execution table tracks each step, showing the current node's value, pointer changes, and the list's visual state. Key moments clarify why we check for NULL first, what happens if the value is missing, and why we move forward in the list. The quiz tests understanding of pointer positions and stopping conditions.

Practice

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

easy

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

B. To add a new node at the end of 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 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 linked list.

3. Final Answer:

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

4. Quick Check:

   Search = Find value in list [OK]

Hint: Search means look for a value in nodes [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 C?

easy

A. Node* current = head; while(current != NULL) { if(current->data == value) break; current = current->next; }

B. Node* current = NULL; while(current != head) { if(current->data == value) break; current = current->next; }

C. Node* current = head; while(current->next != NULL) { if(current->data == value) break; current = current->next; }

D. Node* current = head; for(int i=0; inext; }

Solution

1. Step 1: Initialize pointer to head

   We start searching from the head node, so current = head is correct.

2. Step 2: Traverse until end or value found

   Loop continues while current is not NULL, checking each node's data.

3. Final Answer:

   Node* current = head; while(current != NULL) { if(current->data == value) break; current = current->next; } -> Option A

4. Quick Check:

   Start at head and loop till NULL [OK]

Hint: Start at head, loop until NULL or value found [OK]

Common Mistakes:

• Initializing current to NULL instead of head
• Looping until current->next is NULL misses last node
• Using for loop with value as count incorrectly

3. What will be the output of the following code snippet if the linked list contains nodes with values 3 -> 7 -> 10 -> NULL and we search for 7?

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

int search(Node* head, int value) {
  Node* current = head;
  while(current != NULL) {
    if(current->data == value) {
      return 1;
    }
    current = current->next;
  }
  return 0;
}

int main() {
  Node n3 = {10, NULL};
  Node n2 = {7, &n3};
  Node n1 = {3, &n2};
  int found = search(&n1, 7);
  printf("%d", found);
  return 0;
}

medium

A. Compilation error

B. 0

C. 7

D. 1

Solution

1. Step 1: Trace the search function

   The function checks each node's data: 3 (no), 7 (yes), so it returns 1 immediately.

2. Step 2: Understand main output

   Main prints the returned value, which is 1, indicating value found.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   Value found = 1 [OK]

Hint: Returns 1 if found, else 0 [OK]

Common Mistakes:

• Expecting the value itself to be printed
• Confusing return 1 with return 0
• Thinking code causes compilation error

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

int search(Node* head, int value) {
  Node* current = head;
  while(current->next != NULL) {
    if(current->data == value) {
      return 1;
    }
    current = current->next;
  }
  return 0;
}

medium

A. The function returns 1 even if value is not found

B. The pointer current is not initialized

C. The loop condition misses checking the last node

D. The function should return the node pointer instead of int

Solution

1. Step 1: Analyze loop condition

   The loop runs while current->next != NULL, so it stops before last node.

2. Step 2: Consequence of condition

   The last node's data is never checked, so search may miss value at last node.

3. Final Answer:

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

4. Quick Check:

   Loop condition excludes last node [OK]

Hint: Loop until current != NULL to check all nodes [OK]

Common Mistakes:

• Using current->next != NULL instead of current != NULL
• Assuming last node is checked automatically
• Confusing return types

5. Given a linked list with nodes containing values 5 -> 8 -> 12 -> 20 -> NULL, write a function to search for a value and return the position (1-based) if found, or -1 if not found. What will be the output when searching for 12?

hard

A. -1

B. 3

C. 2

D. 4

Solution

1. Step 1: Understand position counting

   Positions start at 1 for head node, increment by 1 for each next node.

2. Step 2: Locate value 12 in list

   Values: 5 (pos 1), 8 (pos 2), 12 (pos 3), so 12 is at position 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Value 12 is third node [OK]

Hint: Count nodes from head until value found [OK]

Common Mistakes:

• Returning zero-based index instead of 1-based
• Returning -1 even if value exists
• Confusing position with value