1. 鏈表 (Linked Lists)

• 單向鏈表 vs 雙向鏈表
  • struct list_head 標準實現
  • 內核鏈表API：LIST_HEAD(), list_add(), list_del()
• 環形鏈表
  • 通過list_head自動形成環狀結構
• 安全考慮
  • 并發訪問保護（自旋鎖/RCU）

2. 隊列 (Queues)

• kfifo實現
  • 無鎖環形緩沖區
  • 生產者-消費者模型
• API示例：

  DECLARE_KFIFO(name, size);
  kfifo_put(fifo, data);
  kfifo_get(fifo, &data);
  

3. 映射 (Maps)

• IDR機制
  • 整數ID到指針的映射
  • 替代方案：XArray（新內核）
• 紅黑樹
  • struct rb_root 實現
  • O(log n) 查找復雜度

4. 二叉樹 (Binary Trees)

• 紅黑樹特性：
  • 自平衡二叉樹
  • 內核實現：lib/rbtree.c
• 使用場景：
  • 虛擬內存區域管理
  • 調度器deadline隊列

5. 位圖 (Bitmaps)

• 內核位操作：
  • set_bit(), clear_bit()
  • 原子位操作版本
• 應用場景：
  • CPU掩碼（cpumask）
  • 內存頁管理

6. 其他數據結構

• 哈希表：
  • hlist_head 實現
  • 網絡協議棧大量使用
• 基數樹(radix tree)：
  • 頁緩存核心數據結構
  • 已被XArray逐步替代

性能考量

1. 緩存友好性（局部性原理）
2. 鎖粒度優化
3. 內存預分配策略
4. 算法復雜度分析