What are Traverse and Search Linked Lists- C Programming Training Institute In Hyderabad

🚀 Learn BLE on Linux (BlueZ) – Programming Part 1

Hands-on Bluetooth Low Energy course. Special price: ₹399

Enroll Now on Udemy →
💬 Need help or career guidance? Ask us!Contact Us →

Free C Programming Course · Structure and Union · Lecture 29

Traverse and Search Linked Lists

Walk every node with one pointer, count and sum values, and search for a key. Practical lessons from our free C tutorial and free embedded C course.

Once you have a list, the first things you want to do are look at every node and find a particular value. Both tasks use the same idea: a helper pointer that hops from node to node. In this lecture of our free C programming course you will learn to traverse and search a linked list in C, write small reusable functions for it, and handle the empty-list case that trips up many beginners in embedded C programming.

What You Will Learn

  • How traversal visits each node exactly once
  • Why you walk with a copy of the pointer and keep start safe
  • How to write print, count and sum functions
  • How to search and return a pointer to the matching node
  • How the same code handles an empty list
  • Mistakes that cause infinite loops and crashes

Prerequisites

You should know the node structure with info and link, the role of the start pointer, and the arrow operator. The previous lecture covers all of this.

Traversal: Visit Every Node Once

Traversal means accessing each node exactly once, in order. The recipe has three steps:

  1. Create a helper pointer and make it point where start points.
  2. While the helper is not NULL, use the node it points to.
  3. Move the helper to the next node by copying that node’s link into it.
for (ptr = start; ptr != NULL; ptr = ptr->link)
    printf("%d -> ", ptr->info);
The helper pointer hops along the chain
step 1: ptr = startnode 12
step 2: ptr = ptr->linknode 30
step 3: ptr = ptr->linknode 45
step 4: ptr = ptr->linknode 8
step 5: ptr = ptr->linkNULL, loop ends

Never move start itself

If you advance start during traversal, you lose the address of the first node and cannot get back. Use a separate walker, or in a function that receives start by value, remember that the caller’s copy stays untouched anyway.

Handy Helpers: Print, Count, Sum

Instead of repeating loops everywhere, wrap them in small functions. Passing the list as const struct node * tells the reader, and the compiler, that these functions only look and never modify.

static void list_print(const struct node *start)
{
    const struct node *ptr;

    for (ptr = start; ptr != NULL; ptr = ptr->link)
        printf("%d -> ", ptr->info);
    printf("NULL\n");
}

static int list_count(const struct node *start)
{
    int n = 0;

    while (start != NULL) {
        n++;
        start = start->link;
    }
    return n;
}

static long list_sum(const struct node *start)
{
    long s = 0;

    for (; start != NULL; start = start->link)
        s += start->info;
    return s;
}

Here list_count() advances its own parameter start. That is fine because the parameter is a private copy of the caller’s pointer; the caller’s variable does not change.

Searching a Linked List

Searching is traversal with a question asked at each node: is this the value I want? We stop at the first match or when we fall off the end. Returning a pointer to the matching node is more useful than just yes or no, because the caller can then read or modify that node.

static struct node *list_find(struct node *start, int key)
{
    while (start != NULL && start->info != key)
        start = start->link;
    return start;           /* NULL when not found */
}

Pay attention to the order inside the condition: start != NULL is checked before start->info. C evaluates && left to right and stops early, so the node is never touched when the pointer is NULL. Swap the two tests and the program crashes on a missing key.

Search for 45: stop at the first match
12 ≠ 45→30 ≠ 45→45 = 45return this node
Search for 99: all four fail, reach NULL, return NULL

Complete Program: Build and Run

To keep this lecture about reading a list, the program links four nodes that live in an ordinary array. Creating nodes dynamically comes next lecture. Save the code as list_walk.c.

#include <stdio.h>

struct node {
    int info;
    struct node *link;
};

static void list_print(const struct node *start)
{
    const struct node *ptr;
    for (ptr = start; ptr != NULL; ptr = ptr->link)
        printf("%d -> ", ptr->info);
    printf("NULL\n");
}

static int list_count(const struct node *start)
{
    int n = 0;
    while (start != NULL) { n++; start = start->link; }
    return n;
}

static struct node *list_find(struct node *start, int key)
{
    while (start != NULL && start->info != key)
        start = start->link;
    return start;
}

static long list_sum(const struct node *start)
{
    long s = 0;
    for (; start != NULL; start = start->link)
        s += start->info;
    return s;
}

int main(void)
{
    struct node pool[4] = {
        { 12, &pool[1] },
        { 30, &pool[2] },
        { 45, &pool[3] },
        { 8,  NULL }
    };
    struct node *start = &pool[0];
    struct node *hit;

    list_print(start);
    printf("count = %d\n", list_count(start));
    printf("sum   = %ld\n", list_sum(start));

    hit = list_find(start, 45);
    if (hit)
        printf("found 45, next node holds %d\n", hit->link->info);

    hit = list_find(start, 99);
    printf("find 99 -> %s\n", hit ? "found" : "not found");

    printf("empty list count = %d\n", list_count(NULL));
    return 0;
}
$ gcc -Wall -Wextra -o list_walk list_walk.c
$ ./list_walk

Expected output:

12 -> 30 -> 45 -> 8 -> NULL
count = 4
sum   = 95
found 45, next node holds 8
find 99 -> not found
empty list count = 0

The empty list needs no special case

The last line passes NULL as the whole list. Because every loop begins with a != NULL test, zero iterations run and the answer is correctly 0. Writing functions this way means one piece of code handles empty, one-node and long lists alike.

A subtle danger in this demo

In find 45 we read hit->link->info. That works because 45 is not the last node. If we had searched for 8, hit->link would be NULL and the same line would crash. Always check a link before following it a second time.

Cost of Traversal and Search

OperationWork doneNotes
Print / count / sumvisits all n nodesalways n steps
Search, key present1 to n stepsaverage about n/2 for random keys
Search, key absentn stepsmust reach NULL to be sure
Access k-th nodek stepsno direct indexing

Linear search is acceptable for short lists, which is typical in embedded systems such as a handful of registered callbacks. For thousands of entries, consider a different structure.

Real-World Uses

  • Finding the connection entry for a given device address in a list of active BLE connections.
  • Searching a list of registered timers for the one that matches an id before cancelling it.
  • Counting pending events to report queue depth over a debug UART.
  • Summing buffer lengths along a chain of packet fragments to learn the full message size.

Common Mistakes

  • Forgetting to advance. A loop without ptr = ptr->link never ends.
  • Testing the value before NULL. Always test the pointer first.
  • Using = instead of ==. if (ptr->info = key) overwrites data and is almost always true.
  • Stopping one node early. A condition like ptr->link != NULL skips the last node when you wanted to visit it. Use it only when you really need the final node’s address.
  • Cyclic lists. If a bug makes the last link point back into the chain, traversal loops forever.

Best Practices

  • Return a pointer from search functions, and document that NULL means not found.
  • Mark read-only functions with const.
  • Keep traversal loops tiny; do the heavy work in a separate function.
  • In interrupt-shared lists, disable the interrupt or lock before walking.

Suggested Images for This Lecture

Image ideaALT text
Pointer hopping across nodes step by steptraverse linked list in C step by step free C programming course
Search path for found and not found casessearch linked list in C free C tutorial diagram
Terminal output of list_walkembedded C programming linked list traversal output free embedded C course

Key Takeaways

  • Traverse with a walker: start it at the head, stop at NULL, advance with ptr = ptr->link.
  • Check the pointer for NULL before looking inside the node.
  • A search function returns the node pointer, or NULL if the key is absent.
  • Loops that start with a NULL test handle empty lists automatically.

Conclusion

Traversal is the foundation of every linked list operation: counting, searching, inserting at a position and deleting all begin by walking the chain. With three or four lines you can reach any node, and with a careful NULL test you can do it safely. In the final lecture of this section of our free C programming course we will create nodes dynamically and insert them at the beginning, at the end and after a chosen node, then finish with a quiz and interview questions to test what you have learned.

Frequently Asked Questions

How do you traverse a linked list in C?

Set a pointer to the start, loop while it is not NULL, process the node, and move the pointer to the node’s link.

Why use a separate pointer to traverse?

Moving start itself would lose the address of the first node. A separate walker keeps start intact.

What should a search function return?

A pointer to the matching node, or NULL when the value is not found.

What is the time complexity of searching a linked list?

It is linear, proportional to the number of nodes, because each node must be checked in order.

How does traversal handle an empty list?

If the start pointer is NULL the loop body never runs, so count returns 0 and print shows only NULL.

Why check ptr != NULL before ptr->info?

Reading a member through a NULL pointer crashes the program. The && operator stops evaluating as soon as the first test fails.

Almost There: Insert Nodes Next

The next lecture builds lists dynamically and ends with a quiz and interview questions.

💬 Need help or career guidance? Ask us!Contact Us →

1 Comment

Leave a Reply

Your email address will not be published. Required fields are marked *

×

🚀 BLE on Linux (BlueZ)

Hands-on course. Only ₹399

Enroll Now →