Searching in Linked List

To find a value in an unsorted singly linked list, start at head and walk forward, comparing each data until you match or run off the end. In the worst case you visit every node—O(n) time and O(1) extra space (just the iterator pointer).

C program (return pointer to node, or `NULL`)

The list is built with insert_begin exactly as in insert at beginning. The search function returns a pointer to the first node whose data equals key, or NULL if none match. main prints the list, runs two searches, then frees the list.

search does not modify the list.
If duplicates exist, only the first match is returned.

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

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

struct Node *insert_begin(struct Node *head, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return head;

    newNode->data = data;
    newNode->next = head;
    return newNode;
}

/* First node with data == key, or NULL. */
struct Node *search(struct Node *head, int key)
{
    struct Node *cur = head;
    while (cur != NULL) {
        if (cur->data == key)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

void print_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void free_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

int main(void)
{
    struct Node *head = NULL;

    head = insert_begin(head, 30);
    head = insert_begin(head, 20);
    head = insert_begin(head, 10);

    print_list(head);   /* 10 20 30 */

    struct Node *p = search(head, 20);
    if (p != NULL)
        printf("found %d\n", p->data);

    struct Node *q = search(head, 99);
    if (q == NULL)
        printf("not found\n");

    free_list(head);
    return 0;
}

Program output

10 20 30
found 20
not found

Overall program flow

Step	Operation	`head` points to	Notes
1	`head = NULL`	`NULL`	Empty list
2	`head = insert_begin(head, 30)`	Node with data `30`	List: `30`
3	`head = insert_begin(head, 20)`	Node `20` → node `30`	`20 30`
4	`head = insert_begin(head, 10)`	Node `10` → `20` → `30`	`10 20 30`
5	`print_list(head)`	`0x3000`	Output line: `10 20 30`
6	`search(head, 20)`	Unchanged	Returns pointer to node `20` (`0x2000`); prints `found 20`
7	`search(head, 99)`	Unchanged	Returns `NULL`; prints `not found`
8	`free_list(head)`	All nodes freed	List destroyed

Each `search` call in detail

Call 1: search(0x3000, 10)

Step	Operation	Variable	Value
1	`cur = head`	`cur`	`0x3000`
2	`cur->data == 10`	—	True → `return cur` (`0x3000`)

Key 10 is at the head—one comparison.

Call 2: search(0x3000, 20)

Step	Operation	Variable	Value
1	`cur = head`	`cur`	`0x3000` (data `10`)
2	Compare `10` vs `20`	—	Not equal; `cur = cur->next`
3	`cur` advances	`cur`	`0x2000` (data `20`)
4	Match	return value	`0x2000`

Two comparisons to reach the middle node.

Call 3: search(0x3000, 99)

Step	Operation	Variable	Value
1–3	Walk `10`, `20`, `30`	`cur`	`0x3000` → `0x2000` → `0x1000`
4	After last node	`cur`	`NULL`
5	`while` exits	return	`NULL`

Worst case for this list: three comparisons, then failure.

Memory layout (example addresses)

List in heap (same as insert_begin example)

Address	Node	`data`	`next`	Points to
`0x3000`	`n1` (head)	10	`0x2000`	`n2`
`0x2000`	`n2`	20	`0x1000`	`n3`
`0x1000`	`n3`	30	`NULL`	nowhere

Visual representation

head (0x3000)
   │
   ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ data: 10     │    │ data: 20     │    │ data: 30     │
│ next: 0x2000 ┼───→│ next: 0x1000 ┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘
     n1                   n2                   n3
  (inserted last)     (inserted 2nd)      (inserted first)

Detailed step-by-step: call 2 (search key `20`)

Inside search when head is 0x3000 and key is 20:

Line	Code	Before	After
1	`struct Node *cur = head;`	`head = 0x3000`	`cur = 0x3000`
2	`while (cur != NULL)`	`cur = 0x3000`	Enter loop
3	`if (cur->data == key)`	`10 == 20` false	Skip `return`
4	`cur = cur->next;`	`cur` was `0x3000`	`cur = 0x2000`
5	`while` / `if` again	`20 == 20` true	`return cur` (`0x2000`)

Complexity summary

Operation	Time	Extra space
`search`	`O(n)` worst case (full walk)	`O(1)`
`insert_begin`	`O(1)`	`O(1)` per new node
`print_list`	`O(n)`	`O(1)`
`free_list`	`O(n)`	`O(1)`
Whole program (build + print + search + free)	`O(n)`	`O(n)` nodes stored in the list

The key takeaway is that linear search on a linked list cannot skip ahead without extra structure: you follow next pointers, so the worst case is O(n) time for n nodes.

If the list is sorted, you can still only scan sequentially in a plain SLL—O(n)—unless you add another structure (e.g. skip list) or copy into an array for binary search.