🚀 Learn BLE on Linux (BlueZ) – Programming Part 1
Hands-on Bluetooth Low Energy course. Special price: ₹399
Enroll Now on Udemy →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:
- Create a helper pointer and make it point where
startpoints. - While the helper is not
NULL, use the node it points to. - 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);
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.
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
| Operation | Work done | Notes |
|---|---|---|
| Print / count / sum | visits all n nodes | always n steps |
| Search, key present | 1 to n steps | average about n/2 for random keys |
| Search, key absent | n steps | must reach NULL to be sure |
| Access k-th node | k steps | no 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->linknever 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 != NULLskips 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
NULLmeans 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 idea | ALT text |
|---|---|
| Pointer hopping across nodes step by step | traverse linked list in C step by step free C programming course |
| Search path for found and not found cases | search linked list in C free C tutorial diagram |
| Terminal output of list_walk | embedded 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 withptr = ptr->link. - Check the pointer for
NULLbefore looking inside the node. - A search function returns the node pointer, or
NULLif the key is absent. - Loops that start with a
NULLtest 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.

1 Comment