Embedded C

Linked Lists

A linked list is nothing more than a struct holding a pointer to another struct of its own type — the entire data structure is built from that one self-referential idea. Embedded code reaches for arrays far more often than linked lists, for reasons that connect directly back to Dynamic Memory, but the pattern itself shows up constantly once memory pools enter the picture.

Quick reference

What it is: A chain of nodes, each holding data plus a pointer to the next (and sometimes previous) node.
Mental model: A scavenger hunt — each clue (node) only tells you where the next one is, and you can't skip ahead without following the chain from wherever you're currently standing.
Key numbers: O(1) insert/delete at a known position; O(n) to reach an arbitrary element by index — the opposite trade-off from an array.
Reach for it when: The maximum size genuinely isn't known ahead of time, or elements need to be inserted/removed from the middle frequently — otherwise, an array wins on both simplicity and embedded-friendliness.

The self-referential node

struct node {
    int data;
    struct node *next;   // a struct pointing to another struct of its own type
};

Singly linked

Each node points only forward. Traversal is one-directional; inserting at the head is O(1), but inserting anywhere else requires walking the list from the head first.

struct node *push_front(struct node *head, int value) {
    struct node *n = malloc(sizeof(*n));
    n->data = value;
    n->next = head;     // new node points at the old head
    return n;            // caller's head pointer now becomes this node
}

Doubly linked

Each node carries both next and prev, enabling backward traversal and O(1) removal of a node whose address is already known, without needing to find its predecessor first — at the cost of one extra pointer per node and twice as many pointer updates to get right on every insert/delete.

struct dnode {
    int data;
    struct dnode *next;
    struct dnode *prev;
};

Circular

The last node's next points back to the first node instead of NULL — there's no "end" to reach. Useful for anything that logically repeats: a simple round-robin scheduler's task list, or cycling through a fixed set of I/O channels in a loop that never actually terminates.

Same node struct, three different link patterns — the choice is purely about what the traversal needs to do, not a different data structure underneath.

Linked lists vs. arrays

	Array	Linked list
Random access	O(1)	O(n)
Insert/delete at known position	O(n) (shifting)	O(1)
Memory layout	Contiguous — cache-friendly	Scattered — poor cache locality
Size	Fixed at compile time (or costly resize)	Grows one node at a time
Allocation	Usually one static block	Usually one allocation per node

That last row is the one that matters most for embedded: a linked list built with raw malloc() per node inherits every problem from Dynamic Memory — fragmentation, non-deterministic timing, allocation failure. This is why embedded code favors arrays whenever the maximum size is known ahead of time, and reserves linked lists for cases where nodes are drawn from a pre-sized static pool rather than the raw heap.

Real-world applications

RTOS ready/blocked task lists — built from pre-allocated task control blocks threaded together by pointers, never malloc'd per task — see RTOS.
Free-list allocators — the memory-pool alternative to raw malloc (see Dynamic Memory) is, underneath, a singly linked list of free blocks threaded through the pool's own unused memory — no separate bookkeeping structure needed.
Round-robin I/O scanning — a circular linked list of channels or devices to poll in sequence is a natural fit for "there's no last one, just keep going."

Gotchas

Field notes

Overwriting a node's next pointer before saving it elsewhere loses the rest of the list permanently — a very easy mistake during insertion/deletion.
Freeing a node without saving its next pointer first leaks the entire remainder of the list, since nothing else references it anymore.
An accidental cycle in what should be a linear list — or mishandling a circular list's stopping condition — turns a traversal into an infinite loop, since there's no NULL to naturally stop at.