Data Structure Selection for Embedded Systems Questions

This topic covers selecting and implementing data structures that are optimized for constrained embedded environments. Candidates should demonstrate understanding of fixed size arrays versus dynamic structures, preallocation and memory pooling, statically allocated linked lists with preallocated nodes, circular buffers and ring queues, and fixed size heap strategies. The description also includes compact representations such as bit packing and pointerless or index based designs to reduce metadata overhead. Important considerations include memory layout, alignment, and padding effects on usable memory, cache locality, fragmentation, and the space time trade offs that influence choice of structure. Candidates should reason about deterministic allocation and time complexity for real time constraints, overhead of dynamic allocation, strategies to minimize fragmentation, and techniques to guarantee safe behavior under interrupts and concurrent access. Practical skills include designing memory efficient variants of common data structures, estimating memory usage, choosing representations that fit a fixed budget, and explaining why one structure is preferable to another given specific hardware limits.

MediumTechnical

93 practiced

Design an index-based singly-linked list in C that uses 16-bit indices to reference nodes inside a statically allocated array. Provide struct definitions and explain insert, delete, and iteration operations, and explain why index-based lists are safer for ROM relocation than pointer-based lists.

Sample Answer

**Approach (brief)** Use 16-bit indices instead of pointers. Keep a statically allocated pool array of nodes; index 0 reserved as NULL. Maintain a free-list of indices for allocation. This is common in embedded systems where ROM/flash relocation or position-independent data is required.

**Structs / definitions**

#include <stdint.h>
#define MAX_NODES 256
typedef uint16_t idx_t;        /* 0 == NULL */

typedef struct {
    uint16_t value;           /* payload (example) */
    idx_t next;               /* index of next node */
} node_t;

typedef struct {
    node_t pool[MAX_NODES];   /* pool[0] unused */
    idx_t head;               /* list head index */
    idx_t free_head;          /* free list head index */
} list_t;

**Init**- Build free list linking indices 1..MAX_NODES-1, set head = 0.

**Insert (at front)**- Pop an index from free_head (O(1)); set pool[i].value; pool[i].next = head; head = i.- If free_head == 0 => pool exhausted.

**Delete (by index or value)**- To delete first matching value: iterate keeping prev index; when found, if prev==0 set head = pool[i].next else pool[prev].next = pool[i].next; push i onto free_head (O(1) for push).- Deleting by index is similar and avoids search.

**Iteration**- For(idx = head; idx != 0; idx = pool[idx].next) { process pool[idx].value; }

**Why safer for ROM relocation**- Pointers encode absolute addresses; if the data section is relocated (copied from ROM into RAM at different base), stored absolute pointers become invalid. Indices are offsets/IDs into a known array and remain valid regardless of base address because code uses pool base + index to compute address at runtime. This makes structures position-independent and robust for bootloaders, firmware updates, or memory remapping.

**Complexity & notes**- Insert/delete at head: O(1). Search/delete by value: O(n).- Reserve index 0 as NULL. Ensure atomic updates if used in ISRs or multi-context code. Keep pool size within memory limits.

EasyTechnical

103 practiced

You have 32KB RAM and must store 100 sensor records. Each record contains a 16-byte payload, a 4-byte timestamp, and a 4-byte pointer for next in a linked list. Calculate the memory required for the pointer-based list including simple alignment assumptions, propose a pointerless indexed layout using 16-bit indices, compute savings, and note alignment/padding costs.

MediumTechnical

75 practiced

How can you guarantee deterministic worst-case allocation time in an embedded system? Describe specific designs or allocator choices (e.g., slab, fixed-pool) and explain constraints and trade-offs when allocations are required from different priority contexts including high-priority ISRs.

MediumTechnical

76 practiced

Implement in C a fixed-size object pool for N identical objects allocated at compile time. Provide API: pool_init, pool_alloc, pool_free. Allocation and free must be O(1) without using malloc/free. Show data structures and brief code sketches and describe how to make pool_alloc safe for use in an ISR.

Sample Answer

**Approach (brief)** Use a free-list of fixed objects stored in an array allocated at compile time. pool_alloc/pop and pool_free/push are O(1) by taking/returning head of a singly-linked lock-free stack (or by disabling interrupts for ISR-safety on simple MCUs).

**Data structures**- Array of N objects (object storage)- Array of next indices (or next pointer inside each object)- head index (int) or pointer

**Code sketch (compile-time N)**

#include <stdint.h>
#define N  16
typedef struct { uint8_t data[32]; int next; } Obj;

static Obj pool[N];
static int free_head;

void pool_init(void){
    for(int i=0;i<N-1;i++) pool[i].next = i+1;
    pool[N-1].next = -1;
    free_head = 0;
}

void* pool_alloc(void){
    int idx = free_head;
    if(idx < 0) return NULL;
    free_head = pool[idx].next;
    return &pool[idx];
}

void pool_free(void* p){
    int idx = ((Obj*)p) - pool;
    pool[idx].next = free_head;
    free_head = idx;
}

**ISR-safety / concurrency**- Simple MCU: wrap pool_alloc/pool_free with critical sections (disable/restore interrupts) to make them atomic:

irq_disable();
... modify free_head ...
irq_restore();

- Multi-core or preemptive RTOS: use a lock-free atomic compare-and-swap on head (store index with version/tag) or a mutex provided by RTOS.- Ensure pointer validity and double-free protection if needed (add magic/tag).

**Complexity & notes**- O(1) alloc/free, no malloc. Memory fixed at compile time. - For safety add bounds checks, optional debug bitmaps, and alignment as needed for the object type.

EasyTechnical

102 practiced

List reasons to prefer arrays over linked lists in embedded systems. Include memory overhead, cache locality, traversal cost, fragmentation risk, and static bounds. Provide concrete examples where arrays are significantly better and where linked lists remain the right choice.

Sample Answer

**Direct answer (summary)** Arrays are usually preferable in embedded systems because they have lower memory overhead, far better cache locality, cheaper traversal and indexing, lower fragmentation risk, and allow fixed/static bounds (no malloc). Linked lists are still right when you need O(1) mid-list inserts/removals with unpredictable counts or when objects have widely varying lifetimes and you use a safe fixed-size pool.

**Why arrays win (details)**

- Memory overhead - Each linked-list node needs at least one pointer (4 bytes on 32-bit). For many small elements that doubles/triples RAM usage compared to a packed array of structs.

- Cache locality & performance - Arrays store elements contiguously → prefetching + fewer cache misses. Traversing an array is orders of magnitude faster than chasing pointers on small MCUs with small caches.

- Traversal cost / access patterns - Random access O(1) with index vs O(n) for linked lists. Traversal over arrays benefits DMA, memcpy, and vectorized operations.

- Fragmentation risk - Dynamic node allocation fragments the heap on constrained flash/RAM systems. Static arrays (or ring buffers) avoid malloc/free entirely.

- Static bounds & safety - Fixed-size arrays can be allocated in .bss/stack, enabling deterministic memory usage and easier timing/stack analysis for RTOS and safety certifications.

**Concrete examples**- Arrays significantly better: sensor sample buffer (circular buffer of 1024 samples), TCP packet buffer pool for DMA descriptors, lookup tables in firmware—lower RAM, predictable timing, and DMA-friendly.- Linked lists better: event subscriber lists where handlers are registered/unregistered frequently and count is small but dynamic; sparse free-list management using a preallocated pool of nodes when element sizes/number are unknown but heap is avoided.

**Practical rule** Prefer static arrays or fixed pools in embedded code for predictability and performance. Use linked lists only when insertion/deletion semantics justify pointer overhead and either use a fixed node pool or rigorous memory-control to avoid fragmentation.

Unlock Full Question Bank

Get access to hundreds of Data Structure Selection for Embedded Systems interview questions and detailed answers.

Join thousands of developers preparing for their dream job.