Search for a Value in Linked List in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a linked list?

A linked list is a chain of nodes where each node holds data and a link (pointer) to the next node. It is like a treasure hunt where each clue leads to the next one.

beginner

How do you search for a value in a linked list?

Start from the first node and check each node's data one by one until you find the value or reach the end of the list.

beginner

What does it mean if the search reaches the end of the linked list without finding the value?

It means the value is not present in the linked list.

intermediate

Why can't we use direct indexing to search in a linked list like in an array?

Because linked lists do not store elements in continuous memory locations, so we must follow links from one node to the next.

intermediate

What is the time complexity of searching a value in a linked list?

The time complexity is O(n), where n is the number of nodes, because you may need to check each node once.

What is the first step when searching for a value in a linked list?

A Jump to the middle node

B Start from the last node

C Start from the head node

D Sort the list first

Searching always starts from the head (first) node in a linked list.

If the value is not found in the linked list, what will the search function return?

A Pointer to the last node

B NULL or equivalent

C The head node

D The value itself

If the value is not found, the search returns NULL to indicate absence.

Why is searching in a linked list slower than in an array?

A Because linked lists use pointers and no direct indexing

B Because arrays have more memory

C Because linked lists are sorted

D Because linked lists store duplicate values

Linked lists require following pointers node by node, unlike arrays which allow direct access.

What happens if you try to access a node beyond the last node in a linked list?

A You get NULL or no node

B You get the first node again

C You get an error but still continue

D You get a random node

The last node points to NULL, so accessing beyond it returns NULL.

Which of these is a correct way to check each node's value during search?

A Compare node's pointer with target value

B Compare node's next pointer with target value

C Compare node's address with target value

D Compare node's data with target value

We compare the data stored in the node to the value we are searching for.

Explain step-by-step how to search for a value in a linked list.

Think of walking through a chain checking each link.

Describe why searching in a linked list takes longer than in an array.

Compare walking through a chain vs jumping directly to a position.

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