8 Essential Data Structures for Embedded Programming

Introduction

Data structures are ways of organizing and storing data to enable efficient operations on that data. They have broad and varied applications in computer science and software engineering. Nearly every program or software system uses data structures. They are foundational to computer science and software engineering and are commonly tested in technical interviews. This article briefly explains eight common data structures every developer should know.

1. Arrays

An array is a fixed-size structure that holds items of the same data type. It can be an array of integers, floats, strings, or even arrays (for example, two-dimensional arrays). Arrays are indexed, which allows random access.

Common array operations:

Traversal: iterate over all elements, for example to print them.
Insertion: insert one or more elements into the array.
Deletion: remove elements from the array.
Search: find elements by value or by index.
Update: change the value of an element at a given index.

Typical applications:

Basis for other structures such as array lists, heaps, hash tables, vectors, and matrices.
Used by sorting algorithms such as insertion sort, quicksort, bubble sort, and merge sort.

2. Linked Lists

A linked list is a sequential structure composed of nodes that are linked together. Data must be accessed sequentially; random access is not possible. Linked lists provide a simple, flexible representation for dynamic collections.

Common types of linked lists:

Singly linked list — nodes can be traversed only in the forward direction.
Doubly linked list — nodes can be traversed forward and backward.
Circular linked list — the previous pointer of the head points to the tail, and the next pointer of the tail points to the head.

Common linked list operations:

Search: linear search to find a node with key k and return a pointer to it.
Insertion: insert a key into the linked list.
Deletion: remove an element from the linked list.

Typical applications:

Symbol table management in compilers.
Switching between applications (for example Alt-Tab can be implemented with a circular linked list).

3. Stacks

A stack is a LIFO (last-in, first-out) structure commonly found in many programming environments.

Core stack operations:

Push: insert an element onto the top of the stack.
Pop: remove and return the element from the top of the stack.

Typical applications:

Expression evaluation (for example, the shunting-yard algorithm for parsing and evaluating arithmetic expressions).
Implementing function call behavior in recursion.

4. Queues

A queue is a FIFO (first-in, first-out) structure commonly used in programming.

Core queue operations:

Enqueue: insert an element at the end of the queue.
Dequeue: remove an element from the front of the queue.

Typical applications:

Thread management in multithreaded systems.
Implementing queuing systems such as priority queues.

5. Hash Tables

A hash table stores key-value pairs and supports efficient lookup when the key is known.

Hash function:

A special function called a hash function (h) maps keys to indices to address issues with direct addressing.

Typical applications:

Database indexing.
Implementing associative arrays (maps).
Implementing set data structures.

6. Trees

A tree is a hierarchical structure where data is organized in levels and linked together.

Typical applications:

Binary trees: used for expression parsing and evaluation.
Binary search trees: used in many search applications with frequent insertions and deletions.

7. Heaps

A heap is a special binary-tree-based structure where parent and child node values are compared and arranged according to heap properties.

Typical applications:

Implementing priority queues, since priority values can be ordered by heap properties.
Supporting queue operations with O(log n) time complexity using a heap.