Complete C implementations of a dynamic array, linked list, stack, queue, hash table and binary search tree, with notes on ownership, complexity and pitfalls.
C has arrays, structs and pointers, and nothing else: no built-in list, map or set. Every other data structure is built from these pieces, and the programmer decides how memory is allocated, who owns it and when it is freed. That is more work than in a language with a standard library of containers, but it gives full control over layout and cost.
This page shows compact, correct versions of the structures you meet most, each with its complexity. The pattern is the same: a struct that holds the state, an init/create function, operations that take a pointer to the struct, and a free/destroy function.
#include<stdio.h>#include<stdlib.h>typedefstruct{int*items;size_t length;size_t capacity;} IntVec;staticvoidvec_init(IntVec *v){
v->items =NULL;
v->length =0;
v->capacity =0;}/* Amortized O(1): the capacity doubles when full. Returns 0 on success. */staticintvec_push(IntVec *v,int value){if(v->length == v->capacity){size_t new_capacity = v->capacity ==0?4: v->capacity *2;int*bigger =realloc(v->items, new_capacity *sizeof*bigger);if(bigger ==NULL){return-1;/* old block is still valid */}
v->items = bigger;
v->capacity = new_capacity;}
v->items[v->length++]= value;return0;}/* The same structure is a stack: push at the end, pop from the end. */staticintvec_pop(IntVec *v,int*out){if(v->length ==0){return-1;}*out = v->items[--v->length];return0;}staticvoidvec_free(IntVec *v){free(v->items);vec_init(v);}intmain(void){
IntVec v;vec_init(&v);for(int i =1; i <=10; i++){vec_push(&v, i * i);}printf("length=%zu capacity=%zu\n", v.length, v.capacity);int top;printf("popped:");while(vec_pop(&v,&top)==0&& top >30){printf(" %d", top);}printf("\nremaining length=%zu\n", v.length);vec_free(&v);return0;}
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.
C
Singly linked list and queue
#include<stdio.h>#include<stdlib.h>typedefstructNode{int value;structNode*next;} Node;typedefstruct{
Node *head;/* dequeue from the head */
Node *tail;/* enqueue at the tail: O(1) */size_t size;} Queue;staticintenqueue(Queue *q,int value){
Node *node =malloc(sizeof*node);if(node ==NULL){return-1;}
node->value = value;
node->next =NULL;if(q->tail !=NULL){
q->tail->next = node;}else{
q->head = node;}
q->tail = node;
q->size++;return0;}staticintdequeue(Queue *q,int*out){if(q->head ==NULL){return-1;}
Node *old = q->head;*out = old->value;
q->head = old->next;if(q->head ==NULL){
q->tail =NULL;}free(old);
q->size--;return0;}/* Reverse the list in place by re-pointing every next. */staticvoidreverse(Queue *q){
Node *prev =NULL;
Node *cur = q->head;
q->tail = q->head;while(cur !=NULL){
Node *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;}
q->head = prev;}staticvoidprint_queue(const Queue *q){for(const Node *n = q->head; n !=NULL; n = n->next){printf("%d ", n->value);}printf("(size %zu)\n", q->size);}intmain(void){
Queue q ={};for(int i =1; i <=5; i++){enqueue(&q, i *10);}print_queue(&q);int v =0;if(dequeue(&q,&v)==0){printf("dequeued %d\n", v);}reverse(&q);print_queue(&q);while(dequeue(&q,&v)==0){/* drain and free every node */}printf("empty: head is %s\n", q.head ==NULL?"NULL":"set");return0;}
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.
C
Hash table with chaining and a binary search tree
#include<stdio.h>#include<stdlib.h>#include<string.h>/* ---------- hash table: string -> int, separate chaining ---------- */#defineBUCKETS8typedefstructEntry{char*key;int value;structEntry*next;} Entry;typedefstruct{
Entry *buckets[BUCKETS];} Table;staticsize_thash(constchar*s){/* djb2 */size_t h =5381;while(*s !='\0'){
h = h *33+(unsignedchar)*s++;}return h % BUCKETS;}staticinttable_set(Table *t,constchar*key,int value){size_t i =hash(key);for(Entry *e = t->buckets[i]; e !=NULL; e = e->next){if(strcmp(e->key, key)==0){
e->value = value;/* update existing key */return0;}}
Entry *e =malloc(sizeof*e);if(e ==NULL){return-1;}
e->key =malloc(strlen(key)+1);if(e->key ==NULL){free(e);return-1;}strcpy(e->key, key);
e->value = value;
e->next = t->buckets[i];
t->buckets[i]= e;return0;}staticconstint*table_get(const Table *t,constchar*key){for(const Entry *e = t->buckets[hash(key)]; e !=NULL; e = e->next){if(strcmp(e->key, key)==0){return&e->value;}}returnNULL;}staticvoidtable_free(Table *t){for(size_t i =0; i < BUCKETS; i++){
Entry *e = t->buckets[i];while(e !=NULL){
Entry *next = e->next;free(e->key);free(e);
e = next;}
t->buckets[i]=NULL;}}/* ---------- binary search tree of ints ---------- */typedefstructTree{int value;structTree*left,*right;} Tree;static Tree *tree_insert(Tree *root,int value){if(root ==NULL){
Tree *node =calloc(1,sizeof*node);if(node !=NULL){
node->value = value;}return node;}if(value < root->value){
root->left =tree_insert(root->left, value);}elseif(value > root->value){
root->right =tree_insert(root->right, value);}return root;}staticvoidtree_print(const Tree *root){/* in-order: sorted */if(root !=NULL){tree_print(root->left);printf("%d ", root->value);tree_print(root->right);}}staticvoidtree_free(Tree *root){if(root !=NULL){tree_free(root->left);tree_free(root->right);free(root);}}intmain(void){
Table t ={};constchar*words[]={"apple","pear","fig","apple","fig","apple"};for(size_t i =0; i <6; i++){constint*count =table_get(&t, words[i]);table_set(&t, words[i], count ==NULL?1:*count +1);}constchar*query[]={"apple","fig","pear","kiwi"};for(size_t i =0; i <4; i++){constint*c =table_get(&t, query[i]);if(c !=NULL){printf("%s -> %d\n", query[i],*c);}else{printf("%s -> not found\n", query[i]);}}table_free(&t);
Tree *root =NULL;int values[]={50,30,70,20,40,60,80,30};for(size_t i =0; i <8; i++){
root =tree_insert(root, values[i]);}printf("sorted: ");tree_print(root);printf("\n");tree_free(root);return0;}
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.
Ownership. Decide who frees what. Containers that store pointers should either own the pointed-to data (and free it) or document that they do not. The hash table above copies keys so it owns them.
realloc safely. Assign its result to a temporary pointer, as vec_push does; assigning straight to the old pointer leaks the block on failure.
Check every allocation, and free partially built structures on failure. See malloc and realloc.
Initialize with {} (C23) or = {0} so pointers start NULL; calloc does the same for heap memory.
Recursive trees can overflow the stack when unbalanced; use a loop or a balanced tree for large inputs.
Generic containers in C use void * plus an element size, or macros that generate a typed version; both lose some type safety. See void pointers.
Memory errors are the common bug: leaks, double free, use after free. Run these structures under Valgrind or sanitizers.
Array-based structures (vector, ring buffer, binary heap) usually beat pointer-based ones in speed because of cache locality.