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 list and where

Step 1: Start at the first node with value 1

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

Why: We begin searching from the start of the list

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

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

Why: Value not found yet, so we continue to next node

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

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

Why: Found the value we are searching for

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* create_node(int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = value;
    new_node->next = NULL;
    return new_node;
}

// Function to search for a value in the linked list
int search_value(Node* head, int target) {
    Node* current = head; // start at head
    while (current != NULL) { // while not end of list
        if (current->data == target) {
            return 1; // found the value
        }
        current = current->next; // move to next node
    }
    return 0; // value not found
}

// Function to print the linked list
void print_list(Node* head, int highlight) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == highlight) {
            printf("[%d ↑] -> ", current->data); // highlight found node
        } else {
            printf("[%d] -> ", current->data);
        }
        current = current->next;
    }
    printf("null\n");
}

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

    int target = 2;
    int found = search_value(head, target);

    print_list(head, found ? target : -1);
    if (found) {
        printf("Value %d found in the list\n", target);
    } else {
        printf("Value %d not found in the list\n", target);
    }

    // Free memory
    Node* current = head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }

    return 0;
}

Node* current = head; // start at head

initialize current pointer to start of list

while (current != NULL) { // while not end of list

loop through nodes until end

if (current->data == target) {

check if current node has target value

return 1; // found the value

stop search and report found

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

advance to next node to continue search

Output

[1] -> [2 ↑] -> [3] -> null

Value 2 found in the list

Complexity Analysis

Time: O(n) because in 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 arrays, linked list search is similar O(n), but linked lists do not allow direct access so traversal is necessary

Edge Cases

Empty list (head is NULL)

Search immediately returns not found

DSA C

while (current != NULL) {

Value not in list

Search traverses entire list and returns not found

DSA C

while (current != NULL) {

Value at head node

Search finds value immediately and returns found

DSA C

if (current->data == target) {

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 current node is NULL before accessing data
Fix: Always check current != NULL in the loop condition before accessing current->data

Summary

Searches through a linked list to find if a value exists.

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

The key is to check each node one by one 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 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