EMBEDDED DSA

Linked Lists

Every list variant, written for embedded C rather than for a whiteboard: singly and doubly linked, circular lists and sentinels that delete the boundary cases, the intrusive form kernels and firmware actually use, static pools and free lists for systems without malloc, reversal and cycle detection, and an honest account of when an array is the better answer.

Reviewed 2026-08-223,439 words

What a linked list is, and what it costs

A linked list stores each element in its own node, and each node holds a pointer to the next one. Nothing is contiguous; the order is carried entirely by the pointers. That single decision buys O(1) insertion and removal anywhere you already have a pointer, and it costs random access, cache locality, and one pointer of memory per element. Almost every property of every list variant follows from that trade.

How it is built

A node is a struct holding a value and a pointer to the next node. The final node's pointer is null.
The list itself is just a pointer to the first node - the head. An empty list is a null head.
Reaching element n costs n pointer dereferences, because there is no arithmetic relationship between node addresses.
Inserting or removing at a known position is a couple of pointer writes, with no shifting of anything else.
Each node costs the value plus one pointer, plus allocator overhead and alignment padding if allocated individually.

Design procedure

Choose a list when you insert and remove often at positions you already hold, and rarely index by number.
Choose an array when you index, iterate hot loops, or care about cache behaviour, which on a cached core is most of the time.
Always traverse with an explicit null test; there is no length to compare against unless you maintain one.
Keep a count if you need the length often, because computing it is a full traversal every time.
Draw the pointer updates before writing them; almost every list bug is an assignment ordering mistake.

Key terms

Node: One element: the payload plus the link or links to its neighbours.
Head: Pointer to the first node. A null head is the empty list.
Tail: The last node, whose next pointer is null. Often cached to make append O(1).
Traversal: Walking the list by following next pointers until null.
Locality: Whether elements sit near each other in memory. Arrays have it; lists generally do not.

Worked example

The structure, and the honest cost comparison:

  typedef struct Node {
      int value;
      struct Node *next;      // the tag is required here: the
  } Node;                     // typedef does not exist yet inside

  Node *head = NULL;          // empty list

  for (Node *n = head; n != NULL; n = n->next)
      visit(n->value);

  operation           array        linked list
  ---------------------------------------------
  index [i]           O(1)         O(n)
  insert at front     O(n)         O(1)
  insert after p      O(n)         O(1)
  remove at p         O(n)         O(1)  (doubly)
  search              O(n)         O(n)
  memory per element  sizeof(T)    sizeof(T) + pointer + padding
  cache behaviour     sequential   a miss per node, typically

On a Cortex-M7 with a data cache, iterating 1000 scattered nodes can be an
order of magnitude slower than iterating 1000 contiguous ints, even though
both are O(n). The complexity column is not the whole story.

Common pitfalls

The singly linked list: insert, remove, and the ordering that matters

The singly linked list is the base case: one link per node, forward traversal only. Every operation is a small number of pointer assignments, and every classic bug is those assignments in the wrong order. Writing them out explicitly, once, is worth more than any amount of description - the correct sequences are short and the incorrect ones lose the rest of the list.

How it is built

Insert at front: point the new node at the current head, then move the head to the new node. That order, never the reverse.
Insert after a node p: point the new node at p->next, then point p->next at the new node.
Remove after p: save p->next, point p->next past it, then free the saved one.
Removing the head is a special case because there is no preceding node to update - which is what the pointer-to-pointer technique eliminates.
Append is O(n) unless a tail pointer is maintained, since the last node must be found by walking.

Design procedure

Write the new node's links before touching any existing node's links; the list stays valid at every step.
Save any pointer you are about to overwrite if you still need it afterwards.
Handle the empty list and the single-element list explicitly, or use a technique that removes the special case.
After removing a node, do not read it again; if it was freed, the pointer is dangling immediately.
Test with zero, one and two elements. Almost every list bug lives in exactly those cases.

Key terms

Singly linked: One pointer per node, forward only. No way to reach the predecessor.
Head insertion: Adding at the front. O(1) and the natural operation for a stack.
Tail pointer: A cached pointer to the last node, making append O(1) instead of O(n).
Dangling pointer: A pointer to memory that has been freed or reused.
Lost list: What happens when the head is overwritten before the new node points at the old one.

Worked example

The four operations, and the ordering that destroys the list:

  // insert at front - CORRECT
  n->next = head;
  head = n;

  // insert at front - WRONG
  head = n;               // the old head is now unreachable
  n->next = head;         // n points at ITSELF

  // insert after p
  n->next = p->next;
  p->next = n;

  // remove after p
  Node *dead = p->next;
  if (dead) {
      p->next = dead->next;
      free(dead);         // only AFTER unlinking
  }

Removing by value, with the head special case visible:

  Node *prev = NULL, *cur = head;
  while (cur && cur->value != key) { prev = cur; cur = cur->next; }
  if (cur) {
      if (prev) prev->next = cur->next;
      else      head       = cur->next;   // the special case
      free(cur);
  }

And the same thing with no special case at all, which is the version worth
learning:

  Node **link = &head;                 // pointer to the POINTER
  while (*link && (*link)->value != key)
      link = &(*link)->next;
  if (*link) {
      Node *dead = *link;
      *link = dead->next;              // works for the head too
      free(dead);
  }

The indirect version has no prev, no branch, and no way to get the head case
wrong, because the head is just another pointer to update.

Common pitfalls

Doubly linked lists: paying a pointer to remove in O(1)

A doubly linked list adds a previous pointer to each node. That costs one pointer per element and buys two things: backward traversal, and the ability to remove a node given only that node - no search for its predecessor. In practice the second is the reason to use one, because it is what makes an O(1) remove genuinely O(1) rather than O(1) after an O(n) search.

How it is built

Each node holds prev and next. The first node's prev is null and the last node's next is null.
Removing node n is four assignments: fix n->prev->next and n->next->prev, with a null check on each end.
Insertion requires updating four pointers as well, in an order that keeps the list traversable throughout.
The null checks at each end are what a sentinel node removes, at the cost of one extra node's storage.
Memory cost is the payload plus two pointers - on a 32-bit target, eight bytes of overhead per element.

Design procedure

Update the new node's own pointers first, then the neighbours' pointers into it.
Guard every neighbour access with a null check, or use a sentinel so there are no ends.
Keep both head and tail pointers so that insertion and removal at either end are O(1).
Set removed pointers to null after unlinking, so a later accidental use faults instead of corrupting.
Consider whether you actually need backward traversal; if not, a singly linked list with the pointer-to-pointer idiom is cheaper.

Key terms

Doubly linked: Two pointers per node, forward and backward.
Unlink: Removing a node by making its neighbours point past it.
Sentinel: A dummy node that is always present, removing the null checks at the ends.
O(1) removal: Removing a node given only a pointer to it, which requires the prev link.
Overhead ratio: Pointer bytes against payload bytes. Two pointers around a 4-byte int is 200% overhead.

Worked example

Unlink, with the ends handled:

  typedef struct DNode {
      int value;
      struct DNode *prev, *next;
  } DNode;

  void unlink(DNode **head, DNode **tail, DNode *n) {
      if (n->prev) n->prev->next = n->next;
      else         *head        = n->next;    // n was first
      if (n->next) n->next->prev = n->prev;
      else         *tail        = n->prev;    // n was last
      n->prev = n->next = NULL;               // fail loudly later
  }

  Four assignments, two branches, no search. That is the whole
  reason the prev pointer exists.

Insert before an existing node:

  void insert_before(DNode **head, DNode *at, DNode *n) {
      n->next = at;                // n's own links first
      n->prev = at->prev;
      if (at->prev) at->prev->next = n;
      else          *head         = n;
      at->prev = n;
  }

What the overhead actually looks like on a 32-bit MCU:

  struct { int v; }                       4 bytes
  singly:  { int v; Node *next; }         8 bytes  (100% overhead)
  doubly:  { int v; Node *prev, *next; } 12 bytes  (200% overhead)

For 1000 elements that is 4 kB against 12 kB. On a 64 kB part, the choice of
list variant is a fifth of your RAM.

Common pitfalls

Circular lists and sentinel nodes: deleting the special cases

Most linked-list bugs are in the boundary cases - the empty list, the first node, the last node. Two structural changes remove them rather than handling them. A circular list has no ends: the last node points back to the first. A sentinel is a permanent dummy node that is always present, so there is always a node before and after any real one. Together they turn branchy code into straight-line code, which is why the Linux kernel's list is built this way.

How it is built

In a circular doubly linked list every node has a non-null prev and next, always, including when it is the only node.
A sentinel head node belongs to the list itself rather than to any element; the empty list is the sentinel pointing at itself.
Insert and remove need no null checks and no head special case, because there are no ends and the head is never a node.
Traversal terminates by returning to the sentinel rather than by finding null, so the loop condition changes shape.
The cost is one node's worth of memory and the discipline of never treating the sentinel as an element.

Design procedure

Initialise the sentinel pointing at itself; that single line is the entire empty-list representation.
Write insert and remove with no branches, and check them against the empty and single-element cases to confirm none are needed.
Terminate every traversal at the sentinel, not at null, and never dereference the sentinel's payload.
Use the same routine for insert-at-front and insert-at-back by choosing which side of the sentinel to insert on.
Keep the sentinel embedded in the list struct rather than allocated, so an empty list needs no allocation at all.

Key terms

Circular list: The last node links back to the first, so there is no null terminator.
Sentinel: A permanent non-element node, so every real node has neighbours.
Branch-free: Code with no conditionals. Here it means insert and remove need no null checks.
Self-referential init: head.next = head.prev = &head - the empty circular list.
list_head: The Linux kernel's name for this structure, embedded in every listed object.

Worked example

The whole implementation, with no special cases anywhere:

  typedef struct List { struct List *prev, *next; } List;

  static inline void list_init(List *l) { l->prev = l->next = l; }

  static inline void list_add(List *node, List *after) {
      node->next       = after->next;
      node->prev       = after;
      after->next->prev = node;
      after->next       = node;
  }

  static inline void list_del(List *node) {
      node->prev->next = node->next;
      node->next->prev = node->prev;
      node->prev = node->next = node;
  }

  Count the branches: zero. list_del works on the only node in a
  list, on the first, on the last, identically - because in a
  circular list with a sentinel those are all the same situation.

  List head;
  list_init(&head);                 // empty: head points at itself
  bool empty = (head.next == &head);

  list_add(&item, &head);           // insert at FRONT
  list_add(&item, head.prev);       // insert at BACK - same routine

  for (List *p = head.next; p != &head; p = p->next)
      ...                           // stops at the sentinel

Compare against the non-circular remove, which needed four branches and a
head pointer. Same operation, same complexity, and nothing left to get wrong.

Common pitfalls

Intrusive lists: the form embedded C actually uses

In the textbook list, the node owns the data: it holds a value or a pointer to one. In an intrusive list, the data owns the node: the link struct is a member of your object, and the list threads through objects that already exist. This is the dominant form in kernels and firmware because it requires no allocation to add something to a list, an object can be on several lists at once, and there is no separate node to keep in sync with the thing it points at.

How it is built

The object embeds a link member: struct Task { ...; List link; }. The list connects the link members.
Given a pointer to the link, the containing object is recovered by subtracting the member's offset - the container_of idiom.
Adding to a list allocates nothing, because the link is already part of an object that exists.
One object can carry several link members and therefore be on several lists simultaneously, with no duplication.
offsetof from stddef.h provides the offset portably, so container_of needs no compiler extension beyond a cast.

Design procedure

Embed a link member in the object rather than defining a node type that points at it.
Define a container_of macro once and use it at every point where a link is turned back into an object.
Give each list its own link member with a descriptive name when an object belongs to more than one.
Remember the object's lifetime is now the list's concern: freeing an object still on a list corrupts that list.
Initialise every link member when the object is created, so an unlisted object is distinguishable from a listed one.

Key terms

Intrusive list: The link is a member of the object rather than the object being pointed at by a node.
container_of: Recovering the containing struct from a pointer to one of its members.
offsetof: The standard macro giving a member's byte offset within its struct.
Multiple membership: One object on several lists at once, via several link members.
Zero-allocation: Adding to a list without allocating, because the link already exists.

Worked example

The pattern, and the macro that makes it work:

  #define container_of(ptr, type, member) \
      ((type *)((char *)(ptr) - offsetof(type, member)))

  typedef struct {
      uint32_t id;
      uint8_t  priority;
      List     ready_link;      // for the ready queue
      List     timer_link;      // AND for the timer list
  } Task;

  List ready_queue;
  list_init(&ready_queue);

  Task t = { .id = 1, .priority = 3 };
  list_add(&t.ready_link, &ready_queue);     // no malloc

  for (List *p = ready_queue.next; p != &ready_queue; p = p->next) {
      Task *task = container_of(p, Task, ready_link);
      run(task);
  }

Why this dominates firmware:

  non-intrusive:  add to a list = allocate a node, may FAIL,
                  and now two objects must be kept in sync
  intrusive:      add to a list = four pointer writes, cannot fail,
                  no allocator involved at all

And the same task sits on the ready queue and the timer list at once, through
two different link members, with one copy of the task.

Common pitfalls

Lists without malloc: static pools and free lists

Most firmware cannot use malloc: it fragments, its worst-case timing is unbounded, and running out at hour 300 is not an acceptable failure mode. The replacement is a static pool - a fixed array of nodes allocated at compile time - plus a free list threading the unused ones together. Allocation becomes popping the free list head, and freeing becomes pushing onto it, both O(1), both deterministic, and both incapable of fragmenting.

How it is built

The pool is a static array of node objects, so all the memory exists at link time and appears in the map file.
The free list uses the nodes' own next pointers, so the bookkeeping costs nothing beyond what the nodes already have.
Allocation is: take the head of the free list, advance the head, return the node. A null head means the pool is exhausted.
Freeing is: push the node onto the front of the free list. Neither operation searches or coalesces.
The capacity is fixed and visible, which is the point - exhaustion is a known, testable condition rather than a runtime surprise.

Design procedure

Size the pool from the worst case and assert that the worst case is what you think it is.
Initialise the free list once at startup by threading every node together in a loop.
Always check the allocation for null and define what the system does when the pool is empty - drop, block, or fault.
Protect both operations against interrupt preemption if an ISR allocates, since both are read-modify-write on the head.
Track a high-water mark in development so the real peak usage is measured rather than assumed.

Key terms

Static pool: A fixed array of objects allocated at compile time and reused.
Free list: The unused nodes linked together, using their own pointer fields.
Fragmentation: Free memory split into pieces too small to use. Impossible with fixed-size nodes.
High-water mark: The peak number of nodes ever in use. The number that sizes the pool.
Deterministic allocation: Constant-time allocation with a known bound. What malloc cannot promise.

Worked example

A complete pool allocator, in about fifteen lines:

  #define POOL_SIZE 32
  static Node pool[POOL_SIZE];
  static Node *free_list;
  static uint8_t in_use, peak;

  void pool_init(void) {
      free_list = NULL;
      for (int i = 0; i < POOL_SIZE; i++) {
          pool[i].next = free_list;      // thread them together
          free_list    = &pool[i];
      }
  }

  Node *pool_alloc(void) {
      Node *n = free_list;
      if (!n) return NULL;               // exhausted: a real state
      free_list = n->next;
      if (++in_use > peak) peak = in_use;
      n->next = NULL;
      return n;
  }

  void pool_free(Node *n) {
      n->next   = free_list;
      free_list = n;
      in_use--;
  }

What this buys over malloc:

  malloc:  variable time, can fragment, can fail at any point in a
           300-hour run, heap size hard to bound
  pool:    constant time, cannot fragment, capacity known at link
           time, exhaustion is testable on the bench

If an ISR allocates, both functions must run with interrupts disabled - each
is a read-modify-write on free_list, and a preemption between the read and
the write hands the same node to two owners.

Common pitfalls

The classic algorithms: reversal, cycle detection, merge

Three algorithms come up constantly, in interviews and in real code, and each teaches something structural. Reversal is pure pointer manipulation with no extra memory. Floyd's cycle detection finds a loop in constant space using two pointers at different speeds. Merging two sorted lists is the operation that makes merge sort the natural sort for a linked list, because it needs no random access.

How it is built

Reversal walks the list once, reversing each link, keeping three pointers: previous, current and the saved next.
Floyd's algorithm advances one pointer by one node and another by two; if they ever meet, there is a cycle.
The meeting point is not the cycle start; restarting one pointer at the head and advancing both by one finds that.
Merging two sorted lists repeatedly takes the smaller head, which is O(n + m) with no allocation and no shifting.
Merge sort on a list is O(n log n) with O(1) extra space, unlike on an array, because splicing needs no scratch buffer.

Design procedure

For reversal, save next before overwriting current->next, or the rest of the list is lost immediately.
For cycle detection, advance the fast pointer twice with a null check between the two steps.
Use a dummy head node when merging, so the first element needs no special case.
Split a list for merge sort with the same slow/fast technique, which finds the midpoint in one pass.
Test every one of these on empty, single-element and two-element lists, where all the edge cases live.

Key terms

In-place reversal: Reversing links without allocating anything. O(n) time, O(1) space.
Floyd's algorithm: Tortoise and hare cycle detection in constant space.
Cycle: A node reachable from itself. Makes any naive traversal loop forever.
Dummy head: A temporary node during construction, so appending never special-cases the first element.
Splice: Moving nodes between lists by rewriting pointers rather than copying data.

Worked example

All three, complete:

  Node *reverse(Node *head) {
      Node *prev = NULL;
      while (head) {
          Node *next = head->next;   // SAVE first, always
          head->next = prev;         // reverse this link
          prev = head;
          head = next;
      }
      return prev;                   // the new head
  }

  bool has_cycle(Node *head) {
      Node *slow = head, *fast = head;
      while (fast && fast->next) {
          slow = slow->next;
          fast = fast->next->next;   // twice as fast
          if (slow == fast) return true;
      }
      return false;                  // fast reached the end
  }

  Node *merge(Node *a, Node *b) {
      Node dummy = {0}, *tail = &dummy;
      while (a && b) {
          if (a->value <= b->value) { tail->next = a; a = a->next; }
          else                      { tail->next = b; b = b->next; }
          tail = tail->next;
      }
      tail->next = a ? a : b;        // whichever still has nodes
      return dummy.next;
  }

Why Floyd's works: if there is a cycle, the fast pointer enters it and gains
one position per step on the slow pointer, so the gap closes by one each
iteration and they must eventually coincide. If there is no cycle, fast
reaches null first. Constant space, single pass.

And why merge sort suits lists: merging needs only the two heads, never a
random index, so the whole sort runs in O(1) extra space. On an array the
same algorithm needs a scratch buffer as large as the input.

Common pitfalls

Choosing a list, and the honest alternative

The linked list is the structure most likely to be chosen for the wrong reason. Its complexity table looks excellent, and on modern hardware its constant factors are poor enough that an array often wins the same workload outright. The useful skill is knowing the handful of cases where a list is genuinely right - and recognising that on a microcontroller those cases are more common than on a desktop, because the reasons are different.

How it is built

A list wins when you hold the position already, elements are large, or stable addresses matter across insertions.
An array wins when you index, iterate, or care about cache behaviour, which covers most traversal-heavy code.
On a cached core the constant factor can be an order of magnitude, because each node is potentially a cache miss.
On a small microcontroller with no cache the gap narrows, and the list's real advantage is that it needs no contiguous block and never has to grow.
An intrusive list on a static pool is often the right answer where a dynamic array would need a reallocation that cannot fail.

Design procedure

Ask first whether you index by position; if you do, stop and use an array.
Ask whether you already hold a pointer at the point of insertion or removal; if not, the O(1) claim does not apply.
Ask whether element addresses must stay valid across insertions, which arrays cannot promise once they grow.
On a constrained target, prefer an intrusive list over a growable array when a reallocation failure would be unrecoverable.
Measure before optimising the choice; for small n an array wins nearly everything regardless of the complexity table.

Key terms

Constant factor: The real cost hidden inside big-O. Where lists lose to arrays on cached hardware.
Pointer stability: Whether an element's address survives other insertions. Lists give it; growable arrays do not.
Contiguity: Needing one unbroken block of memory. Arrays require it; lists never do.
Amortised growth: A growable array's doubling strategy, which is O(1) on average and O(n) at each reallocation.
Cache miss: A memory access not served by cache. Roughly the cost of many arithmetic instructions.

Worked example

When each is right, concretely:

  USE A LIST
    an RTOS ready queue - tasks move between queues constantly,
    always by a pointer already held, and never by index
    a free list of fixed-size buffers - O(1) push and pop, no search
    a timer list kept in expiry order - insert at a found position

  USE AN ARRAY
    a sample buffer walked front to back every cycle
    a lookup table indexed by an enum
    anything with fewer than about 100 elements, where the cache
    behaviour dominates the complexity entirely

The measurement that surprises people, summing 1000 ints:

  contiguous array   one cache line fetch per 8 elements,
                     hardware prefetch works
  linked list        potentially one cache miss PER NODE,
                     prefetch cannot predict the next address

  Both are O(n). On a Cortex-M7 with a data cache the array can be
  roughly an order of magnitude faster.

But on a Cortex-M0 with no cache and 8 kB of RAM, that argument disappears and
a different one takes over: a growable array needs one contiguous block and a
reallocation that can fail, while an intrusive list on a static pool needs
neither. Same structure, different reason, and the reason is what should drive
the choice.

Linked Lists

What a linked list is, and what it costs

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

The singly linked list: insert, remove, and the ordering that matters

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Doubly linked lists: paying a pointer to remove in O(1)

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Circular lists and sentinel nodes: deleting the special cases

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Intrusive lists: the form embedded C actually uses

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Lists without malloc: static pools and free lists

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

The classic algorithms: reversal, cycle detection, merge

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

Choosing a list, and the honest alternative

How it is built

Design procedure

Key terms

Worked example

Common pitfalls

More in Embedded DSA