Searching a Linked List

Welcome to the next lesson on linked lists. In our previous session, you mastered list traversal by implementing a printList function. This involved starting at the head and following the next pointers until you reached the end of the list.

Today, we'll build directly on that foundation. Your goal is to implement a function to search for a value within a linked list. This is one of the most common operations you'll perform. The logic will feel very familiar, as it's essentially a traversal with an added conditional check inside the loop. By the end of this lesson, you will be able to write a function that can determine if a specific value exists within a list and locate it.

1. The Search Algorithm

Finding an element in a linked list is like looking for a specific book on a single shelf. You start at one end and check each book, one by one, until you either find the one you're looking for or you reach the end of the shelf.

The algorithm for searching is a straightforward modification of the traversal algorithm you've already learned:

1. Start at the beginning: Create a temporary pointer, let's call it current, and initialize it to point to the head of the list.
2. Check if we're done: Start a while loop that continues as long as current is not NULL.
3. Compare values: Inside the loop, check if the data in the current node (current->data) matches the target value you're searching for.
4. Handle a match: If the values match, you've found the element. You can stop searching and return a signal indicating success.
5. Move to the next node: If the values do not match, advance the current pointer to the next node: current = current->next.
6. Handle a non-match: If the loop finishes (meaning current became NULL), you have traversed the entire list without finding the target value. You should return a signal indicating failure.

The following image provides a great visual for this process, showing how a pointer moves through the list, comparing the data at each node to the target value (in this case, 60).

2. Implementation: Two Common Approaches

When implementing a search function, a key design choice is what to return. There are two very common and useful approaches.

Approach 1: Returning a Pointer to the Node

One powerful approach is to have the search function return a pointer to the node that contains the value, if found. If the value is not found after traversing the entire list, the function returns NULL. This is particularly useful because it not only tells you if the element exists but also where it is, allowing the calling code to perform further operations on that node (like deleting it, which we'll cover later).

Let's watch a short video that implements exactly this logic.

Here is the C code for a function, let's call it findNode, that implements this pointer-based return strategy:

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

// Assume the standard node struct definition
struct node {
    int data;
    struct node *next;
};

/*
 * Searches for a node with a given value in a linked list.
 * head: A pointer to the first node of the list.
 * value: The integer value to search for.
 * Returns: A pointer to the first node containing the value, or NULL if not found.
 */
struct node* findNode(struct node *head, int value) {
    struct node *current = head; // Start at the head

    while (current != NULL) { // Loop until the end of the list
        if (current->data == value) {
            return current; // Found it! Return a pointer to this node.
        }
        current = current->next; // Move to the next node
    }

    return NULL; // Value not found in the list
}

Approach 2: Returning a Boolean (true/false)

Sometimes, you don't need to know where the element is, you just need a simple "yes" or "no" answer. In these cases, returning a boolean value is a cleaner and more direct solution. C has a standard library for this, <stdbool.h>, which provides the bool type and the constants true and false.

The following resource provides a full, runnable program that implements a search function returning a bool.

The search function from the article looks like this:

#include <stdbool.h> // Include this header for boolean types

// ... (node struct definition) ...

/*
 * Checks whether a value x is present in the linked list.
 * head: A pointer to the first node of the list.
 * x: The integer value to search for.
 * Returns: true if the value is found, false otherwise.
 */
bool search(struct node* head, int x) {
    struct node* current = head; // Start at the head
    while (current != NULL) {
        if (current->key == x) { // Note: the article uses 'key' instead of 'data'
            return true; // Found it!
        }
        current = current->next;
    }
    return false; // Traversed the whole list, not found.
}

Which approach you choose depends entirely on what you need to do with the result. Both are correct and widely used.

3. A Recursive Perspective

Given your familiarity with recursion from earlier in the course, it's worth noting that search can also be implemented recursively. This can lead to very elegant code.

The logic is:

1. Base Case 1: If the list is empty (head == NULL), the value cannot be found. Return false.
2. Base Case 2: If the data in the current head node matches the key, the value has been found. Return true.
3. Recursive Step: If neither base case is met, the result of the search is the result of searching the rest of the list (head->next).

You can see a full implementation of this in the "Recursive Solution" section of the GeeksforGeeks article (LINK) you just reviewed. The recursive approach has the same O(n) time complexity but uses O(n) auxiliary space for the function call stack, whereas the iterative approach uses O(1) space.

4. Your Turn: Practice Searching

Now it's time to put this into practice. Let's write a main function to test our search capability.

Exercise:
Complete the main function below. You will need to:

1. Implement a search function that returns a bool. You can copy or adapt the one from the GeeksforGeeks article.
2. Use the provided insertAtHead function to build a small list.
3. Call your search function twice: once for a value you know is in the list, and once for a value that is not.
4. Print a message indicating whether each value was found.

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

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

// Function to add a node at the start of the list
void insertAtHead(struct node **head_ref, int new_data) {
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// TODO: Implement your boolean search function here
// bool search( ... ) { ... }

int main() {
    struct node *head = NULL;

    // Build the list: 40 -> 30 -> 20 -> 10 -> NULL
    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtHead(&head, 30);
    insertAtHead(&head, 40);

    int value_to_find_1 = 30; // This value is in the list
    int value_to_find_2 = 99; // This value is NOT in the list

    // TODO: Call search for value_to_find_1 and print the result
    
    // TODO: Call search for value_to_find_2 and print the result

    return 0;
}

Is 30 in the list? Yes
Is 99 in the list? No

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

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

void insertAtHead(struct node **head_ref, int new_data) {
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// Boolean search function
bool search(struct node* head, int value) {
    struct node* current = head;
    while (current != NULL) {
        if (current->data == value) {
            return true;
        }
        current = current->next;
    }
    return false;
}

int main() {
    struct node *head = NULL;

    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtHead(&head, 30);
    insertAtHead(&head, 40);

    int value_to_find_1 = 30;
    int value_to_find_2 = 99;

    // Search for a value that exists
    if (search(head, value_to_find_1)) {
        printf("Is %d in the list? Yes\n", value_to_find_1);
    } else {
        printf("Is %d in the list? No\n", value_to_find_1);
    }

    // Search for a value that does not exist
    if (search(head, value_to_find_2)) {
        printf("Is %d in the list? Yes\n", value_to_find_2);
    } else {
        printf("Is %d in the list? No\n", value_to_find_2);
    }

    return 0;
}

Conclusion

Congratulations! You have successfully implemented one of the most essential linked list operations. By combining the traversal pattern with a simple conditional check, you can now efficiently locate data within your list.

Key Takeaways:

• Searching a linked list builds directly on the traversal algorithm: iterate from the head to NULL using a temporary pointer.
• The core addition is an if statement inside the loop to compare the current node's data with a target value.
• A search function can be designed to return different types of values based on the need. Common choices include a pointer to the found node (or NULL) or a simple boolean (true/false).
• In the worst-case scenario (the value is at the end or not in the list), you must visit every node. This gives searching a time complexity of O(n), where 'n' is the number of nodes in the list.

Preview of the Next Lesson:
Searching for a node is often the first step in a more complex operation. In our next lesson, we will tackle one such operation: implementing a function to delete a node with a specific value. You will see that to delete a node, you must first find it, making today's lesson a critical prerequisite.