Skip to content
Tutorials Center
My learning

Topics

C Reference ยท Concepts and Tools

Data structures in C

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.

Try it

C Dynamic array and stack

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

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

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.

Complexity at a glance

Structure Access Search Insert Delete Notes
Array / dynamic array O(1) O(n) O(1) amortized at end, O(n) middle O(n) Contiguous, cache friendly.
Singly linked list O(n) O(n) O(1) at head (or tail with a tail pointer) O(1) given the previous node One allocation per node.
Stack top only O(1) O(1) Dynamic array or list.
Queue front only O(1) O(1) List with tail pointer or a ring buffer.
Hash table O(1) average, O(n) worst O(1) average O(1) average Needs a good hash and resizing; iteration order is arbitrary.
Binary search tree O(log n) balanced, O(n) degenerate same same Self-balancing variants (AVL, red-black) guarantee O(log n).
Heap (array) O(1) min/max O(n) O(log n) O(log n) Priority queues.

Usage notes

  • 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.