Linux Kernel Data Structures: Linked Lists, Queues, Maps, and Red‑Black Trees with Practical C Examples

The Linux kernel relies on a set of fundamental data structures to manage processes, files, memory, and other resources efficiently. Core structures include the doubly linked list ( struct list_head) defined in include/linux/list.h, the byte‑oriented queue ( kfifo) in include/linux/kfifo.h, the IDR mapping ( struct idr) in include/linux/idr.h, and the self‑balancing red‑black tree ( struct rb_node) in include/linux/rbtree.h.

Linked List

Linux uses a circular doubly linked list where each node contains only two pointers ( next and prev). The list node is embedded inside user structures, allowing generic operations without storing user data in the list itself. Important macros are:

#define list_entry(ptr, type, member) container_of(ptr, type, member)

#define list_for_each_entry(pos, head, member) ...

Example code shows how to allocate objects, initialize the list with INIT_LIST_HEAD, add nodes with list_add or list_add_tail, iterate with list_for_each_entry, move nodes, and delete them using list_del.

kfifo Queue

The kfifo API provides a lock‑protected circular buffer for byte streams. Functions such as kfifo_alloc, kfifo_put, kfifo_get, and kfifo_free manage allocation, enqueue, dequeue, and cleanup. The article includes a kernel module that allocates a FIFO, inserts four student structures, and demonstrates reading them back.

IDR Mapping

IDR implements a fast integer‑to‑pointer mapping using a layered bitmap tree. Key functions are idr_pre_get (reserve space), idr_get_new / idr_get_new_above (allocate a new ID), idr_find (lookup), idr_remove (delete), and idr_destroy (cleanup). Sample code creates an IDR, inserts four student objects, removes one, and iterates over the remaining entries.

Red‑Black Tree (rbtree)

Linux’s rbtree is a self‑balancing binary search tree used throughout the kernel (e.g., VMA management, I/O schedulers). The core structures are struct rb_node and struct rb_root. Nodes embed struct rb_node and are accessed via container_of. The API provides insertion ( rb_link_node + rb_insert_color), deletion ( rb_erase), search, and iteration ( rb_first, rb_next, etc.). The article also describes cached roots ( rb_root_cached) and augmented trees for interval queries, with example callbacks for maintaining subtree maximum values.

Overall, the article serves as a comprehensive tutorial for developers who need to read, understand, and use Linux kernel data structures in their own modules, offering both conceptual explanations and ready‑to‑use C implementations.