🚀 Learn BLE on Linux (BlueZ) – Programming Part 1
Hands-on Bluetooth Low Energy course. Special price: ₹399
Enroll Now on Udemy →Linked List Basics in C
Understand nodes, the start pointer and the NULL terminator, and see when a linked list beats an array. Part of our free C tutorial and free embedded C course.
A linked list in C is a chain of small records, called nodes, where every node knows the address of the next one. It is the first dynamic data structure most students meet, and it appears constantly in embedded C programming: in RTOS kernels, in driver queues and in protocol stacks. In this lecture of our free C programming course you will build a three-node list by hand, read it back, and learn exactly why this structure exists.
What You Will Learn
- The two problems with storing a list in an array
- The anatomy of a node: information part and link part
- Why a single start pointer controls the whole list
- How an empty list and the last node are represented
- How to create linked nodes with
malloc()and release them withfree() - A fair table comparing arrays and linked lists
Prerequisites
Read the previous lecture on self referential structures first, and be comfortable with malloc(), free() and pointer dereferencing from the Pointers chapter of this free C tutorial.
Why Not Just Use an Array?
An array is the simplest way to keep a collection, but it has two weaknesses that show up quickly in real projects.
- Fixed capacity. You must choose the size in advance. If you reserve room for 100 entries and only 10 arrive, 90 slots of precious RAM sit idle. If 101 arrive, you have an overflow.
- Costly insertion and deletion. To put a new element in the middle, every element after it must shift one place. Removing one means shifting the others back to close the gap.
A linked list attacks both problems. It allocates one node at a time, so memory use follows the real number of entries. And it inserts or removes a node by changing a couple of pointers, with no shifting of data at all.
Anatomy of a Node
Each node has two parts: the information part that carries your data, and the link part that carries the address of the next node. The link of the very last node is NULL, which tells every loop that the chain has ended.
struct node {
int info; /* the data we store */
struct node *link; /* address of the next node, or NULL */
};
The Start Pointer: Your Only Handle
Nodes of a linked list are scattered through memory. They are not neighbours the way array elements are, so there is no array name to index from. Instead you keep one pointer, conventionally called start or head, that holds the address of the first node. Every operation begins there and follows links onward. If you lose this pointer without freeing the list, you lose the whole list and leak its memory.
struct node *start = NULL; /* an empty list */
An empty list is simply start == NULL. There is no special “empty” node.
Building a List by Hand
Before writing helper functions, build a three-node list the slow way so every pointer movement is visible. We allocate each node with malloc(), fill in its data, then connect the nodes in order.
#include <stdio.h>
#include <stdlib.h>
struct node {
int info;
struct node *link;
};
int main(void)
{
struct node *start = NULL;
struct node *n1, *n2, *n3;
printf("empty list? %s\n", start == NULL ? "yes" : "no");
n1 = malloc(sizeof *n1);
n2 = malloc(sizeof *n2);
n3 = malloc(sizeof *n3);
if (!n1 || !n2 || !n3) {
fprintf(stderr, "out of memory\n");
return 1;
}
n1->info = 7; n1->link = n2;
n2->info = 14; n2->link = n3;
n3->info = 21; n3->link = NULL;
start = n1;
printf("empty list? %s\n", start == NULL ? "yes" : "no");
printf("first = %d\n", start->info);
printf("second = %d\n", start->link->info);
printf("third = %d\n", start->link->link->info);
printf("third->link is %s\n",
start->link->link->link == NULL ? "NULL" : "not NULL");
free(n3);
free(n2);
free(n1);
return 0;
}
$ gcc -Wall -Wextra -o list_basic list_basic.c
$ ./list_basic
Expected output:
empty list? yes
empty list? no
first = 7
second = 14
third = 21
third->link is NULL
Walking through the code
malloc(sizeof *n1)asks for exactly one node. Usingsizeof *n1instead ofsizeof(struct node)keeps the line correct even if you later rename the type.- The checks for
NULLmatter. On a small microcontroller heap,malloc()can really fail. - Each
linkis set to the next node, and the last one toNULL. start = n1hands the list over to the single handle that represents it.start->link->inforeads “the info of the node that start’s link points to”, which is the second node.- We free the nodes at the end. Every
malloc()needs a matchingfree().
start. Free a node before reading its link and you read freed memory. The correct pattern, shown in a later lecture, is to save the next pointer first.
Array Versus Linked List
| Feature | Array | Linked list |
|---|---|---|
| Size | Fixed at compile time (or at allocation) | Grows and shrinks one node at a time |
| Memory layout | Contiguous block | Scattered nodes joined by pointers |
| Access element k | Instant: a[k] | Walk k links from the start |
| Insert or delete in the middle | Shift many elements | Change one or two pointers |
| Extra memory per element | None | One pointer per node |
| Cache friendliness | Excellent | Poor, nodes may be far apart |
| Typical embedded use | Lookup tables, buffers | Queues, task lists, event chains |
Choose honestly
A linked list is not “better” than an array. If you know the size and mostly read by index, an array wins on speed and simplicity. Reach for a list when the count is unpredictable or when records are frequently inserted and removed.
Real-World Uses in Embedded Systems
- RTOS scheduler. Ready tasks and blocked tasks are kept on lists so the kernel can move a task between them by relinking.
- Protocol stacks. Network and Bluetooth buffers are chained so a packet can grow header by header without copying.
- Linux kernel. Its core list type chains device and driver objects. Understanding plain linked lists makes that code readable later.
- Event queues. Interrupt handlers append events that the main loop removes one by one.
Common Mistakes
- Forgetting to set the last link to NULL. A garbage link makes your loop run off into random memory.
- Losing start. Overwriting
startbefore saving it leaves the nodes unreachable and leaked. - Not checking malloc. A
NULLresult dereferenced is an instant crash. - Using a node after free(). The memory may be reused by something else.
- Casting malloc in C. Not needed in C and can hide a missing include. Plain
malloc(sizeof *p)is cleaner.
Performance and Safety Notes
- Each node costs the data plus one pointer, plus allocator overhead. On tiny heaps, overhead can be larger than your data.
- Repeated allocation and release can fragment a small heap. Many embedded projects use a fixed pool of nodes instead.
- If an interrupt and the main loop share a list, protect it. A half-finished pointer update seen by an interrupt can corrupt the chain.
Suggested Images for This Lecture
| Image idea | ALT text |
|---|---|
| Chain of nodes with start pointer | linked list in C start pointer and nodes free C programming course |
| Array versus linked list memory layout | array vs linked list free embedded C course comparison |
| Terminal output of list_basic | free C tutorial linked list program output embedded C programming |
Key Takeaways
- A node = information part + link part; the last link is
NULL. - One
startpointer is the only way into the list; an empty list isstart == NULL. - Lists grow node by node and insert without shifting data, but cannot jump to element k directly.
- Always check
malloc()and alwaysfree()what you allocate.
Conclusion
You now know what a linked list is, how a node is laid out, and why a single start pointer is enough to control the whole chain. You also have an honest picture of when to choose a list or an array in embedded C programming. In the next lecture of this free C programming course we will put that start pointer to work: walking every node, counting, summing and searching for a value.
Frequently Asked Questions
What is a linked list in C?
A linked list is a sequence of nodes, each holding data and a pointer to the next node, with the last pointer set to NULL.
Why do we need a start pointer?
Nodes are not stored side by side, so the only way to reach the list is through the address of its first node, which the start pointer holds.
How do I know a linked list is empty?
If the start pointer equals NULL, the list has no nodes.
Is a linked list faster than an array?
Not for reading by index; arrays are faster there. Lists are faster for inserting and removing in the middle because no data shifts.
Can I use linked lists without malloc on a microcontroller?
Yes. Link nodes taken from a static array or a fixed pool. The pointer logic is the same.
What happens if I forget to free the nodes?
The memory leaks. On a long-running embedded device this eventually exhausts the heap.
Next in the Free C Programming Course
Traverse the list, count nodes and search for a value.

1 Comment