Source: https://mokxi.com/teachers/plans/embedded-data-structures
Updated: 2026-11-19

Lesson plan

# Data structures without malloc lesson plan

The containers firmware really uses, every byte fixed at build time: ring buffers, pools, intrusive lists, bitsets, state tables and heaps. Ends with an event queue that runs a space shooter.

4 chapters, 7 lessons, about 5 hours, on the Arduino Uno R3. Every lesson runs in the browser, with nothing to install.

Start a class from this course

The unit

## Objectives and materials

### By the end, students can

- A ring buffer for events and a pool of bullets, with no heap.
- Lists threaded through the objects, and sixteen answers in two bytes.
- A game run by a table, and a heap that knows what is due next.
- Everything in one event queue: Mokxi Invaders.

### Materials for the whole unit

- Arduino Uno R3
- Full-size breadboard
- LED x 3
- Pushbutton
- Resistor x 3

Every part is already on the simulator’s bench, so there is nothing to buy or hand out. The counts are the most any one lesson uses, if you build it on real breadboards too.

Chapter 1. About 1 h 20 min

## Queues and pools

A ring buffer for events and a pool of bullets, with no heap.

Lesson | Time | What students do

Ring buffers A fixed-size queue that never moves its data: free-running uint8_t indices, a power-of-two mask, what full means, and button presses queued for a game tick. | 40 min

- Run it: a queue in an array
- Full is full
- Free-running indices
- Fire!
- A bigger ring

Fixed pools Every bullet the game will ever have, made at build time: a free list threaded through the slots, alloc and release in a few instructions, and what happens when it runs dry. | 40 min

- Run it: a pool of bullets
- The free list
- Give it back
- Out of bullets
- A bigger magazine

### Materials

- Arduino Uno R3
- Full-size breadboard
- LED x 3
- Pushbutton
- Resistor x 3

### Check for understanding

Each student finishes "Fixed pools" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "A bigger magazine".

Chapter 2. About 1 h 25 min

## Links and bits

Lists threaded through the objects, and sixteen answers in two bytes.

Lesson | Time | What students do

Intrusive lists Enemies that carry their own next pointer: lists that cost no memory, moving a node between lists with two pointer writes, and unlinking with a pointer to a pointer. | 40 min

- Run it: a fleet on a list
- Unlink with a pointer to a pointer
- Respawn, and the cost
- Shoot them down
- Reinforcements

Bitsets Sixteen invaders in one uint16_t: test, set and clear a bit, count them with Kernighan's trick, and shoot the lowest one with v & (v - 1). | 45 min

- Run it: a wave in one number
- Count the ones
- Test one bit
- What it saves
- Shoot the lowest
- A full wave

### Materials

- Arduino Uno R3
- Full-size breadboard
- LED x 3
- Pushbutton
- Resistor x 3

### Check for understanding

Each student finishes "Bitsets" on their own, without opening the hints. The simulator checks 6 of its 6 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "A full wave".

Chapter 3. About 1 h 25 min

## Rules and order

A game run by a table, and a heap that knows what is due next.

Lesson | Time | What students do

State tables A game's TITLE, PLAYING, PAUSED and GAMEOVER rules as one NEXT[state][event] table: transitions that are data, entry actions, and changing a rule by editing one cell. | 40 min

- Run it: the rules in 12 bytes
- Press to play
- Pause and resume
- Three hits and out
- Instant retry

Priority queues A binary min-heap of timed game events in an 8-slot array: the tree with no pointers, sift up and down, swap counts, and time comparisons that survive the wrap. | 45 min

- Run it: soonest first
- A tree with no pointers
- Sift up, sift down
- Time that wraps
- Shields up
- Something sooner

### Materials

- Arduino Uno R3
- Full-size breadboard
- LED x 3
- Pushbutton
- Resistor x 3

### Check for understanding

Each student finishes "Priority queues" on their own, without opening the hints. The simulator checks 6 of its 6 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Something sooner".

Chapter 4. About 55 min

## Boss

Everything in one event queue: Mokxi Invaders.

Lesson | Time | What students do

Boss: an event queue for a game Mokxi Invaders with no malloc: a button interrupt and a heap of timers feed one ring of events, handled by a table of state functions, with a bullet pool and a bitset wave. | 55 min

- Run it: Mokxi Invaders
- One queue for everything
- Fire
- Clear the wave
- Let them land
- Hard mode
- Make it yours

### Materials

- Arduino Uno R3
- Full-size breadboard
- LED x 3
- Pushbutton
- Resistor x 3

### Check for understanding

Each student finishes "Boss: an event queue for a game" on their own, without opening the hints. The simulator checks 7 of its 7 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Make it yours".

Your class

## Teach this unit as a class

Start a class from this course and its 7 lessons are assigned in one go, in order. Students join with a six-character code or printed login cards, and each one’s work comes back to you.

The class tools are free for 30 days for one class of up to 20 students, with no card. The lessons themselves are free either way.

Start a class from this course See the demo class

More units

## Other lesson plans

Electronics basics 20 lessons, about 10 h. Embedded on the Arduino Uno 16 lessons, about 12 h. Embedded on the ESP32-C3 13 lessons, about 11 h. Embedded on the Raspberry Pi Pico 7 lessons, about 6 h. Build your own fight stick 5 lessons, about 4 h. Embedded on the STM32F411 6 lessons, about 6 h. C++ on a board 13 lessons, about 10 h. Digital logic and memory 4 lessons, about 4 h. Interactive devices on the Uno 9 lessons, about 8 h. From gates to a computer 23 lessons, about 16 h. Build a claw machine 8 lessons, about 6 h. Every unit All the courses as ready-made units, on the teachers page.
