Linked List Lab and Quiz- Best C Programming Course

🚀 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 35

Linked List Lab and Quiz

Build a malloc-free event queue on a static node pool, the way embedded C programming is done on small microcontrollers, then test yourself with a quiz and interview questions.

This final lecture on linked lists in our free C programming course turns theory into a hands-on lab. You have learned to insert, delete and create nodes with malloc(). Many real devices cannot afford that. A free C tutorial that stops at the heap would leave you unprepared for C programming for embedded systems, where RAM is measured in kilobytes and timing must be predictable. So here you will keep exactly the same pointer logic but take every node from a fixed array. The lecture ends with a multiple-choice quiz and a set of interview questions with short answers.

What You Will Learn

  • Why embedded firmware often avoids malloc() and free()
  • How a free-list of nodes inside a static array works
  • How to build an O(1) FIFO queue with head and tail pointers
  • The classic bug of forgetting to reset the tail pointer
  • Check your understanding with a quiz and common interview questions

Prerequisites

You should have completed the head insertion, insert after node, delete node and create list lectures. Knowledge of stdint.h types (uint8_t, uint16_t) from the earlier data types chapter of this free embedded C course is helpful.

Why Embedded C Programming Avoids the Heap

ConcernHeap (malloc/free)Static pool
TimingVaries, depends on heap stateConstant, a couple of pointer moves
FragmentationPossible after many alloc/free cyclesImpossible, all nodes same size
Failure modeReturns NULL at runtime, hard to testKnown capacity, easy to test
Memory useAllocator metadata per blockExactly array size, visible in the map file
Interrupt safetyUsually not safe in an ISRCan be made safe with a short critical section

Safety standards used in automotive and medical firmware often forbid dynamic allocation after start-up for precisely these reasons. A static pool gives you linked-list flexibility without any of the above risks.

Lab Design: Event Queue on a Node Pool

Imagine an ADC interrupt that must hand samples to the main loop. Each event carries a channel id and a 16-bit sample. We want first-in-first-out order, constant-time push and pop, and a hard capacity of four events. Two linked lists share one array:

  • The free-list chains the nodes nobody is using. Getting a node pops the free-list head; returning one pushes it back. These are exactly the head insertion and head deletion you already know.
  • The queue holds live events with a head pointer for pop and a tail pointer for push. Because we hold a tail, pushing at the end needs no walk.

Initial state: four pool nodes, all on the free-list, queue empty

free_head→pool[0]→pool[1]→pool[2]→pool[3]→NULL
q_headNULLq_tailNULL

After three pushes: nodes moved from free-list to queue

q_head→id 1→id 2→id 3q_tailpoints at id 3
free_head→pool[3]→NULL

The tail pointer trap

When queue_pop() removes the last remaining node, the head becomes NULL naturally. But the tail still points at the node you just recycled. The next push would then write into q_tail->next, which is a node now sitting on the free-list. The queue and free-list silently corrupt each other. The fix is one line: when the head becomes NULL, set the tail to NULL too. Similarly, push must handle the empty case by setting the head as well as the tail.

Interview favourite: “What can go wrong when you delete the last node of a queue implemented with head and tail pointers?” Answer: the tail is left dangling unless you reset it.

Complete Static Pool Queue Program

Everything lives in a global array, so there is no malloc(). The program pushes three events, pops one, pushes two more so all four pool nodes are in use, then tries a sixth push that fails because the pool is exhausted. Finally it drains the queue and shows that pushing works again afterwards.

#include <stdio.h>
#include <stdint.h>
#include <stddef.h>

#define POOL_SIZE 4

typedef struct event {
    uint8_t  id;
    uint16_t sample;
    struct event *next;
} event_t;

static event_t  pool[POOL_SIZE];   /* all nodes live here - no malloc */
static event_t *free_head;         /* list of unused nodes */
static event_t *q_head, *q_tail;   /* list of queued events */

static void pool_init(void)
{
    free_head = NULL;
    for (int i = POOL_SIZE - 1; i >= 0; i--) {
        pool[i].next = free_head;
        free_head = &pool[i];
    }
    q_head = q_tail = NULL;
}

static event_t *pool_get(void)
{
    event_t *n = free_head;
    if (n != NULL)
        free_head = n->next;       /* pop from the free list */
    return n;
}

static void pool_put(event_t *n)
{
    n->next = free_head;           /* push back onto the free list */
    free_head = n;
}

static int queue_push(uint8_t id, uint16_t sample)
{
    event_t *n = pool_get();
    if (n == NULL)
        return -1;                 /* pool exhausted */
    n->id = id;
    n->sample = sample;
    n->next = NULL;
    if (q_tail == NULL)
        q_head = n;                /* queue was empty */
    else
        q_tail->next = n;
    q_tail = n;
    return 0;
}

static int queue_pop(uint8_t *id, uint16_t *sample)
{
    event_t *n = q_head;
    if (n == NULL)
        return -1;
    *id = n->id;
    *sample = n->sample;
    q_head = n->next;
    if (q_head == NULL)
        q_tail = NULL;             /* removed the last node: reset the tail too */
    pool_put(n);
    return 0;
}

int main(void)
{
    uint8_t id;
    uint16_t sample;

    pool_init();

    queue_push(1, 512);
    queue_push(2, 760);
    queue_push(3, 301);

    if (queue_pop(&id, &sample) == 0)
        printf("pop: id=%u sample=%u\n", id, sample);

    queue_push(4, 999);
    queue_push(5, 123);
    if (queue_push(6, 456) != 0)
        printf("push id=6 failed: pool exhausted\n");

    while (queue_pop(&id, &sample) == 0)
        printf("pop: id=%u sample=%u\n", id, sample);

    if (queue_push(7, 42) == 0)
        printf("push id=7 ok after drain\n");
    return 0;
}

Build and run

gcc -std=c11 -Wall -Wextra -g -fsanitize=address,undefined -o ll_pool ll35.c
./ll_pool

Expected output:

pop: id=1 sample=512
push id=6 failed: pool exhausted
pop: id=2 sample=760
pop: id=3 sample=301
pop: id=4 sample=999
pop: id=5 sample=123
push id=7 ok after drain

Walk through the trace

  • Three pushes use three of four pool nodes. The first pop returns id 1 (FIFO) and recycles its node.
  • Pushing ids 4 and 5 uses the recycled node and the last free node, so four events are queued: 2, 3, 4, 5.
  • Pushing id 6 fails: the free-list is empty. A real driver would count dropped events or raise a flag.
  • Draining prints 2, 3, 4, 5 in arrival order. After the drain every node is back on the free-list, so id 7 fits again.

Lab extensions to try

  • Add a counter of dropped events and print it at the end.
  • Change POOL_SIZE to 2 and predict the output before running.
  • Add a function that returns the number of queued events by walking the list, then compare with a counter kept in a variable.
  • Think about interrupt safety: which lines would need interrupts disabled if an ISR pushes while main pops?

Best Practices and Performance for Embedded Linked Lists

  • Size the pool from worst-case burst rate multiplied by worst-case consumer latency, then add margin.
  • Never keep a pointer to a node after returning it to the pool.
  • For single-producer, single-consumer queues, a ring buffer is even cheaper; use a list when items are different sizes or must be re-ordered or removed from the middle.
  • Keep critical sections (interrupts disabled) as short as the two or three pointer moves they protect.

Quiz: Test Your Linked List Knowledge

Choose the best answer for each question, then compare with the answer key below.

Q1. What is the correct order to insert a new node at the head of a list?

  1. head = fresh; fresh->next = head;
  2. fresh->next = head; head = fresh;
  3. fresh->next = NULL; head = fresh;
  4. head->next = fresh; head = fresh;

Q2. A function void add(node_t *head, int v) assigns head = new_node. What happens in the caller?

  1. The caller’s head is updated
  2. The caller’s head is unchanged
  3. The program always crashes
  4. The new node is freed automatically

Q3. Which two statements insert fresh after prev?

  1. prev->next = fresh; fresh->next = prev->next;
  2. fresh->next = prev->next; prev->next = fresh;
  3. fresh->next = prev; prev->next = fresh;
  4. prev = fresh; fresh->next = prev;

Q4. What must you do to delete the first node of a list properly?

  1. free(head) only
  2. Save head in a temporary, set head to head->next, then free the temporary
  3. Set head to NULL
  4. free(head->next)

Q5. What is the time complexity of appending to a list that has only a head pointer?

  1. O(1)
  2. O(log n)
  3. O(n)
  4. O(n squared)

Q6. Why is reading dead->next after free(dead) wrong?

  1. It is a compile error
  2. It is undefined behaviour because the memory no longer belongs to you
  3. It always returns NULL
  4. It is fine on microcontrollers

Q7. In a head-and-tail queue, what must you do when pop removes the last node?

  1. Nothing
  2. Set tail to NULL as well
  3. Set head to tail
  4. Call free on the tail twice

Q8. Which is a benefit of a static node pool?

  1. No fragmentation and predictable timing
  2. Unlimited capacity
  3. No need for pointers
  4. Faster compile time

Answer Key

Q1: B. Q2: B. Q3: B. Q4: B. Q5: C. Q6: B. Q7: B. Q8: A.

Linked List Interview Questions and Answers

QuestionShort answer
What is a self-referential structure?A structure that contains a pointer to its own type, which lets nodes chain together.
Array versus linked list: when do you prefer a list?When you insert or remove often and cannot afford to shift elements, or sizes are not known in advance. Arrays win on random access and cache behaviour.
How do you insert at the head?Set the new node’s next to the old head, then move head to the new node. O(1).
How do you delete a node given only a pointer to it, not the previous node?Copy the next node’s data into it and unlink the next node. It does not work for the last node and breaks anyone who holds a pointer to the next node.
Why pass a pointer to pointer to a list function?So the function can change the caller’s head variable, since C passes by value.
What is a memory leak in the context of lists?Nodes that were allocated but become unreachable without free() being called, for example by overwriting head.
What is a dangling pointer?A pointer to memory that has already been freed.
Why use a tail pointer?To make append O(1). You must keep it updated when the list becomes empty or non-empty.
Why do embedded systems avoid malloc?Non-deterministic timing, fragmentation, and failure paths that are hard to test.
What is a free-list?A linked list of unused nodes from which allocations are served in O(1) and to which freed nodes return.
How would you detect a cycle in a linked list?Use two pointers, one moving one step and one moving two. If they ever meet, there is a cycle.
How would you find the middle node in one pass?Move a slow pointer one step and a fast pointer two steps; when fast reaches the end, slow is at the middle.
How do you reverse a singly linked list?Walk once, keeping prev, curr and next; flip curr->next to prev at each step, then return prev as the new head.

Summary and Conclusion

  • The same pointer rules (link the new node forward first, bypass before freeing) hold on every platform.
  • A static pool plus a free-list gives you a linked list with no heap.
  • With a tail pointer, always reset it when the queue becomes empty.
  • Run small tests with sanitizers on your PC before porting to hardware.

Congratulations on finishing the linked list section of this free C programming course. You can now create, insert, delete, search and reason about singly linked lists, and apply them to embedded C programming problems. Keep practising by solving the reverse, middle and cycle questions above on your own.

Frequently Asked Questions

What is the difference between a linked list on the heap and on a static pool?

The pointer logic is identical. Only the source of nodes changes: malloc versus taking a node from a pre-allocated array.

Can I use a linked list inside an interrupt handler?

Yes, if operations are short and shared pointers are protected by a critical section or a lock-free design. Never call malloc in an ISR.

Why does my queue crash after becoming empty and refilling?

Most likely the tail pointer was not reset to NULL when the last node was removed.

Is a singly linked list or a ring buffer better for embedded work?

A ring buffer is simpler for fixed-size items between one producer and one consumer. A list is better when you must insert or remove in the middle.

How do I choose the pool size?

Estimate the largest burst of events that can arrive before the consumer runs, then add a safety margin.

Where can I find more free embedded C course lectures?

Follow the course index of this free C tutorial series; new lectures are added chapter by chapter.

Finished the Linked List Lectures

Revisit the quiz in a few days without looking at the answers, then try the extensions in the lab.

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

2 Comments

Leave a Reply

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

© 2026 embeddedpathashala.com - WordPress Video Theme by WPEnjoy
×

🚀 BLE on Linux (BlueZ)

Hands-on course. Only ₹399

Enroll Now →