Free Lists and Reuse
Track and recycle blocks.
Free Lists and Reuse is a free C Academy lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Beyond the Bump Allocator
To free individual blocks and reuse them, we need bookkeeping. A free list is a linked list of available blocks the allocator searches before grabbing fresh memory.
Each block carries a header so the allocator can find its size and link to the next block in the chain.
Block Header with a Link
We extend the header with a next pointer and a free flag. Together these turn our pool into a navigable list of blocks.
The payload follows immediately after the header in memory.
typedef struct block {
size_t size; /* payload bytes */
int free; /* 1 if reusable */
struct block *next; /* next block in pool */
} block_t;Initializing One Big Free Block
At startup the whole pool is one giant free block. As allocations happen we split it; as frees happen we mark blocks reusable.
The head of the list is this initial block covering the entire arena.
static unsigned char pool[4096];
static block_t *head;
void heap_init(void) {
head = (block_t *)pool;
head->size = sizeof(pool) - sizeof(block_t);
head->free = 1;
head->next = NULL;
}First-Fit Search
The simplest reuse strategy is first-fit: walk the list and return the first free block large enough. It is fast and tends to keep small blocks near the front.
Alternatives are best-fit (smallest sufficient block) and worst-fit, trading speed for fragmentation behavior.
block_t *first_fit(size_t size) {
for (block_t *b = head; b; b = b->next)
if (b->free && b->size >= size)
return b;
return NULL;
}Allocating from a Free Block
Once we find a fit, we mark it used and return the pointer just after its header. For now we hand over the whole block; splitting comes in the next lesson.
The returned pointer is block + 1, hiding the header from the caller.
void *my_alloc(size_t size) {
block_t *b = first_fit(size);
if (!b) return NULL;
b->free = 0;
return (void *)(b + 1);
}Freeing a Block
To free, step back from the user pointer to its header and flip the free flag. The block is now eligible for reuse on the next search.
Recovering the header from the payload is the same one-step pointer trick we saw earlier.
void my_free(void *p) {
if (!p) return;
block_t *b = (block_t *)p - 1;
b->free = 1;
}Coalescing Adjacent Free Blocks
Freeing alone leaves the pool full of small free blocks. Coalescing merges a freed block with the next block if it is also free, rebuilding larger contiguous regions.
This combats external fragmentation so future large requests can still be satisfied.
void coalesce(block_t *b) {
if (b->next && b->next->free) {
b->size += sizeof(block_t) + b->next->size;
b->next = b->next->next;
}
}A Runnable Free-List Demo
This complete program initializes a pool, allocates two blocks, frees the first, then reuses it for a smaller request, proving the free list works.
#include <stdio.h>
#include <stddef.h>
typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;
void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }
int main(void){
heap_init();
int *a = my_alloc(sizeof(int));
*a = 7;
printf("a=%d free=%d\n", *a, head->free);
my_free(a);
printf("after free: free=%d\n", head->free);
return 0;
}The Cost of Searching
A single linked free list means allocation is O(n) in the number of blocks. With many allocations this becomes slow.
Real allocators use segregated free lists (bins by size) or trees to make the search close to O(1). The principle of reuse stays the same.
/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */Double Free and Corruption
Marking a block free twice, or writing past a block's size, corrupts neighboring headers. The next search then follows a garbage next pointer and crashes.
This is why memory bugs in C are so dangerous: the allocator's own metadata lives right beside your data.
Putting Reuse Together
A working free-list allocator needs initialization, a fit strategy, allocate, free, and coalescing. With these, memory cycles through the pool instead of growing forever.
The remaining refinement is splitting oversized blocks and honoring alignment, the subject of the final lesson.
Quick Check
Think about what keeps a free list from fragmenting badly.
Recap
A free list links blocks via headers so individual allocations can be freed and reused. First-fit search finds a block, freeing flips a flag, and coalescing merges neighbors to fight fragmentation.
Linear search is O(n); production allocators bin by size for speed. Next we add splitting and alignment.
Frequently asked questions
Is the “Free Lists and Reuse” lesson free?
Yes — the full text of “Free Lists and Reuse” is free to read here on the web, and the C Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C Academy course, upgrade to CoddyKit PRO.
What will I learn in “Free Lists and Reuse”?
Track and recycle blocks. You practise C Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start C Academy?
No prior experience is required. C Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Free Lists and Reuse” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this C Academy lesson?
Yes. Every C Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- How malloc Works
- A Simple Bump Allocator
- Free Lists and Reuse
- Alignment and Splitting