🚀 Learn BLE on Linux (BlueZ) – Programming Part 1
Hands-on Bluetooth Low Energy course. Special price: ₹399
Enroll Now on Udemy →Reverse Linked List Code
Free C programming course: write, run and test the iterative reverse function, apply it in an embedded sensor lab, then check yourself with a quiz and interview questions.
In the last lecture you learned the idea behind reversing a list: save, flip, advance. Now we turn that idea into working code and prove it works by running it. This lecture finishes the linked list section of our free C programming course. You will write the reverse linked list in C function, trace its output, solve a small embedded C programming lab that replays sensor readings in arrival order, and close with a quiz and interview questions. It is the kind of practice a good free embedded C course should give you before a job interview.
What You Will Learn
- How to write the iterative
reverse_list()function in C - How to read a step-by-step trace of the pointers
- How to test empty, single-node and multi-node lists
- How to use reversal to turn a stack-like list into arrival order
- How to check your code with AddressSanitizer
- Quiz questions and interview questions on linked lists
Prerequisites
- The previous lecture on the three-pointer reversal logic
- Insertion, traversal and freeing a linked list
The reverse_list Function
Here is the idea in code. The four statements inside the loop are exactly the four moves from the last lecture, in the same order.
void reverse_list(struct node **head)
{
struct node *prev = NULL;
struct node *cur = *head;
struct node *next;
while (cur != NULL) {
next = cur->next; /* 1. save the rest */
cur->next = prev; /* 2. flip the arrow */
prev = cur; /* 3. advance prev */
cur = next; /* 4. advance cur */
}
*head = prev; /* old last node is the new first */
}
One pass of the loop
The function takes struct node **head because the head must change: the old last node becomes the first. A function that took only struct node *head could reverse the arrows but would leave the caller’s head pointing at what is now the last node.
A Complete Test Program With Trace
This program builds the list 8, 21, 34, 55, prints it, reverses it, prints it again, then reverses once more to prove that two reversals restore the original. A printf inside the loop shows each pass.
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
static struct node *make_node(int value, struct node *next)
{
struct node *n = malloc(sizeof *n);
if (n == NULL) {
perror("malloc");
exit(EXIT_FAILURE);
}
n->value = value;
n->next = next;
return n;
}
static void print_list(const char *label, const struct node *head)
{
printf("%-8s:", label);
for (; head != NULL; head = head->next)
printf(" %d", head->value);
printf("\n");
}
void reverse_list(struct node **head)
{
struct node *prev = NULL;
struct node *cur = *head;
struct node *next;
int step = 1;
while (cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
printf("step %d: prev=%d cur=%s\n", step++, prev->value,
cur ? "next node" : "NULL");
}
*head = prev;
}
int main(void)
{
struct node *head = make_node(8, make_node(21, make_node(34, make_node(55, NULL))));
struct node *next;
print_list("before", head);
reverse_list(&head);
print_list("after", head);
reverse_list(&head);
print_list("again", head);
while (head != NULL) {
next = head->next;
free(head);
head = next;
}
return 0;
}
Build and run
gcc -std=c17 -Wall -Wextra -fsanitize=address,undefined -o reverse_demo reverse_demo.c
./reverse_demo
Expected output
before : 8 21 34 55
step 1: prev=8 cur=next node
step 2: prev=21 cur=next node
step 3: prev=34 cur=next node
step 4: prev=55 cur=NULL
after : 55 34 21 8
step 1: prev=55 cur=next node
step 2: prev=34 cur=next node
step 3: prev=21 cur=next node
step 4: prev=8 cur=NULL
again : 8 21 34 55
Read the trace against the table from the last lecture. After step 4, cur is NULL and prev is 55, so *head = prev makes 55 the first node. The sanitizer reported nothing, which means no leak and no invalid access.
Why reversing twice is a good test
A correct reversal is its own inverse. If the second call does not bring back the original order, some arrow was flipped wrongly. This is a cheap self-check you can add to any test.
Edge Case Checklist
| Input | Expected | Why it works |
|---|---|---|
| NULL list | head stays NULL | Loop never runs, prev is NULL |
| One node | Same single node | Node points to NULL, becomes head |
| Two nodes 1, 2 | 2, 1 | Two passes swap the arrows |
| Four nodes | Fully reversed | Shown in the trace |
Embedded Lab: Replay ADC Readings in Order
Problem. An interrupt handler records each ADC sample by pushing it at the front of a list, because front insertion is O(1) and fast. The main loop wants to process samples oldest first. Use reversal once, then process.
#include <stdio.h>
#include <stdlib.h>
struct reading {
int sample;
struct reading *next;
};
static void push_front(struct reading **head, int sample)
{
struct reading *r = malloc(sizeof *r);
if (r == NULL) {
perror("malloc");
exit(EXIT_FAILURE);
}
r->sample = sample;
r->next = *head;
*head = r;
}
static void reverse(struct reading **head)
{
struct reading *prev = NULL, *cur = *head, *next;
while (cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
*head = prev;
}
static void show(const char *label, const struct reading *r)
{
printf("%s:", label);
for (; r != NULL; r = r->next)
printf(" %d", r->sample);
printf("\n");
}
int main(void)
{
struct reading *head = NULL;
int adc[] = {512, 530, 498, 505, 540};
size_t i;
for (i = 0; i < sizeof adc / sizeof adc[0]; i++)
push_front(&head, adc[i]);
show("newest first", head);
reverse(&head);
show("oldest first", head);
while (head != NULL) {
struct reading *n = head->next;
free(head);
head = n;
}
return 0;
}
newest first: 540 505 498 530 512
oldest first: 512 530 498 505 540
Why this pattern is popular
Prepending is cheaper than appending on a singly linked list, so firmware often prepends in a time-critical path and reverses once in a relaxed context. One O(n) reversal replaces an O(n) walk on every insert.
Common Mistakes and Troubleshooting
| Mistake | Symptom | Fix |
|---|---|---|
Forgetting *head = prev | Printing shows only the old first node | Update head after the loop |
Taking struct node *head by value | Caller sees a broken list | Use a double pointer |
Setting cur->next = prev before saving next | List shrinks to one node | Save first |
| Infinite loop when printing | First node points to itself | Start prev as NULL |
Dereferencing cur after the loop | Null pointer crash | Use prev after the loop |
Best Practices and Performance
- Reversal is O(n) time and O(1) space; avoid reversing inside a tight loop.
- Prefer the iterative version in embedded code; recursion costs stack per node.
- Always run linked list code once under AddressSanitizer.
- In interrupt context, keep list work short; do the reversal in the main loop.
Key Takeaways
- Four statements in a loop reverse a singly linked list.
- The head must be updated through a double pointer.
- Two reversals restore the original list: a handy test.
- Prepend now, reverse later is a common embedded pattern.
Chapter Quiz: Linked Lists in C
Try each question first, then open the answer.
- What does an empty singly linked list look like?
Answer
The head pointer is NULL.
- Why does
push_front()takestruct node **?Answer
It must change the caller’s head pointer, and C passes pointers by value.
- What is the time cost of adding at the front, and at the back without a tail pointer?
Answer
Front is O(1). Back is O(n) because we walk to the last node.
- In
insert_after(), which assignment must come first:n->next = cur->nextorcur->next = n?Answer
n->next = cur->next, otherwise the rest of the list is lost.
- When deleting the first node, what is the value of
prev?Answer
NULL, so the code updates *head instead of prev->next.
- What is wrong with
free(p); p = p->next;?Answer
It reads a field of freed memory. Save p->next before freeing.
- Why must
cur != NULLcome beforecur->value != valuein a loop condition?Answer
&& stops at the first false test, so the null check prevents a null dereference.
- What does
find_position()return for a missing value in our program?Answer
0, because valid positions start at 1.
- Which three pointers are used to reverse a list?
Answer
prev, cur and next.
- Why does
prevstart as NULL in reversal?Answer
The old first node becomes the last and must point to NULL.
- After the reversal loop ends, where does
headpoint?Answer
To prev, the old last node.
- What is the space complexity of iterative reversal?
Answer
O(1): only three pointer variables.
Practice Challenges
- Add menu choice 7 to the complete program that calls
reverse_list()and then shows the list. - Write
count_nodes()that returns the length of a list. - Write
remove_all()that deletes every node equal to a given value. - Write
insert_sorted()that keeps a list in ascending order. - Find the middle node of a list using two pointers, one moving twice as fast.
Interview Questions on Linked Lists
1. How do you reverse a singly linked list?
Walk the list with prev, cur and next pointers: save cur->next, point cur->next at prev, move prev and cur forward, and finally set head to prev. It takes O(n) time and O(1) space.
2. Array versus linked list: when would you choose each?
An array gives O(1) random access and is cache friendly. A linked list gives cheap insertion and deletion when you already hold a pointer, and grows without copying. For fixed-size data on small devices, arrays are usually better.
3. How do you detect a loop in a linked list?
Use two pointers, one moving one step and one moving two steps. If they ever meet, there is a loop.
4. How do you find the middle node in one pass?
Move a slow pointer one step and a fast pointer two steps. When the fast one reaches the end, the slow one is at the middle.
5. How do you delete a node when you only have a pointer to it?
For a node that is not last, copy the next node’s data into it and unlink the next node. This does not work for the last node and changes node identity, so it is a trick, not a general method.
6. What are the cases when deleting from a singly linked list?
First node, middle node, last node, and value not found. A trailing prev pointer lets one piece of code cover the first three.
7. Why pass a pointer to the head pointer?
So the function can change which node is first, as in push_front, delete of the first node, and reversal.
8. How do you avoid memory leaks with a linked list?
Free every node you remove, free the whole list before exit, save next before freeing, and test with valgrind or AddressSanitizer.
9. What is the advantage of a doubly linked list?
You can move in both directions and delete a node given only a pointer to it, at the cost of an extra pointer per node.
10. Why is a linked list often avoided in embedded systems?
Each node adds pointer overhead, dynamic allocation can fragment memory or fail, and pointer chasing hurts cache behaviour. Static pools or arrays are common alternatives.
11. How would you merge two sorted linked lists?
Compare the front nodes of both lists, attach the smaller to the result, advance that list, and repeat. Attach the remaining list at the end.
12. What does a dangling pointer mean, and how can it appear in list code?
It is a pointer to memory that was freed. It appears when you use a node pointer after calling free on it.
Conclusion
You have now built a complete linked list toolkit in C: creation, insertion at three places, deletion, display, search, cleanup and reversal. You also practised the habits that matter for real firmware: checking allocations, drawing pointer diagrams and testing edge cases. Keep going with this free C tutorial series, and use these functions as the base for stacks, queues and more advanced structures in your journey through C programming for embedded systems.
Frequently Asked Questions
Can I reverse a linked list without a third pointer?
Not safely for a singly linked list. The third pointer holds the rest of the list while you flip the arrow.
Does reversing change the memory addresses of nodes?
No. Nodes stay where they are; only the next pointers change.
Why prepend and then reverse instead of appending directly?
Prepending is O(1), appending is O(n) without a tail pointer. One reversal at the end is cheaper than many walks.
How do I test my reverse function quickly?
Reverse twice and compare with the original, and test the empty and single-node lists.
Is this course free for students?
Yes. EmbeddedPathashala offers this free C programming course and other free embedded systems, Linux kernel and device driver courses to all learners.
Finish Strong: Free C Programming Course
Practise the challenges, then move on to the next chapter.

2 Comments