1. 为什么还要从零手写数据结构：先回答“值不值”

这两年我陆续把好几个项目的核心模块从脚本语言重写回 C，最大的感触不是性能数字好看，而是思路被迫变得特别清楚。C 语言没有现成的HashMap、没有链表库、没有自动扩容的数组，你手里只有指针、结构体和一块你得自己负责的内存。当团队里有人问我“现在 Python 一个字典就解决了，你折腾这些干嘛”，我就知道对方大概率没经历过性能排查查到深夜的场景——或者说，没体会过真正“掌控”一个数据结构是什么样的感觉。

所谓“ C 语言的优雅回归”，并不是复古，而是回到数据结构本身。现代语言的标准库里塞满了经过千锤百炼的容器，拿来就用确实方便，但也正因为太方便，大部分开发者对“表是怎么存下来的”“扩容时发生了什么”“哈希冲突会带来什么恶果”毫无感知。一旦数据量跨过某个阈值，线上问题会先于你的认知到来。

手写数据结构的第一个直接价值，是你终于能在面试或方案评审时底气十足地聊“均摊复杂度”。第二个价值更实际：当你需要定制内存布局、控制缓存命中率、在嵌入式或协议栈场景里塞入一个零依赖的容器，你只有自己能写。第三个价值偏长期，写 C 的过程会把你对数据在内存里如何排列、指针如何流转的理解钉进肌肉记忆，这对排查任何语言的疑难杂症都有帮助。

但这篇文章不是帮你应付面试的面经，也不打算做一本完整的“C 语言容器说明书”。我选择了几种最常见、也最能体现设计思路的数据结构：动态数组、双链表、哈希表、二叉搜索树。从零开始写，能写多优雅就写多优雅，同时把每一步的设计理由、边界条件、内存管理约定都讲透。

提示：如果你刚接触 C 不久，建议先掌握指针、结构体和内存分配的基本用法，再来读这篇。如果你已经写过一些 C，那么这篇文章里提到的坑和取舍，值得你对照自己的实现检查一遍。

2. 开工前的三件准备：环境、思路与约法三章

2.1 编译环境与工程骨架

我习惯用 GCC 加一个简单的 Makefile 起步，开-Wall -Wextra -g -fsanitize=address。其中-fsanitize=address是保命选项，内存越界、释放后使用这类问题一跑就原形毕露。开发阶段不开它，等于闭着眼睛骑车上高速。

每个数据结构我都会拆成一对文件，比如array.c和array.h，头文件里只放公开接口和不透明类型声明，结构体定义留在.c文件里。这是个容易被忽略但非常重要的决定：使用者看不到内部布