Search

Searching a Linked List

To find a value, scan the list until you find it or reach the end:

int search(struct Node *head, int val) {
    struct Node *cur = head;
    while (cur != NULL) {
        if (cur->val == val) return 1;
        cur = cur->next;
    }
    return 0;
}

Return 1 if found, 0 if not.

This is O(n) in the worst case — linked lists have no random access, so there is no shortcut.

Comparison to Arrays

• Array: int a[n] → binary search O(log n) if sorted
• Linked list: must scan linearly O(n), even if sorted

The lack of random access is linked lists' main weakness. Their strength is O(1) insertion/deletion at the front.

Your Task

Implement int search(struct Node *head, int val) that returns 1 if val is in the list, 0 otherwise.