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.