为什么我把链表换成了动态数组C语言 DArray 实战拆解【免费下载链接】learn-c-the-hard-way-lecturesAll of the code from Learn C The Hard Way, each project, plus the presentation slides used in the videos.项目地址: https://gitcode.com/gh_mirrors/le/learn-c-the-hard-way-lectures前阵子线上服务频繁卡顿我翻遍日志最后发现元凶居然是列表操作——几千个节点逐个遍历、反复插入删除把性能拖垮了。同事看了一眼代码丢给我一句你为什么不用动态数组这句话让我重新翻开了《Learn C The Hard Way》里第 34 讲ex34/lecture.md它讲的就是这个叫 DArray 的动态数组结构。这篇文章把我踩过的坑和悟出来的道理完整讲给你听。先弄明白DArray 到底是什么样的座位想象一间电影院。动态数组就是把座位一排排整齐排好每把椅子紧挨着下一把。你要找第 5 排 8 号座直接数过去就行一步到位。链表则像一支乱糟糟的队伍每个人只知道自己后面跟着谁你要找队伍里的第 100 个人只能从队头开始一个个问过去。DArray 的底层就是一块连续的内存里面装的是一堆void*指针。听起来抽象看代码就懂了// 一个极简的动态数组骨架 // 核心思路底层是一块连续内存装的是 void* 指针 // 这样任何类型的数据都能往里塞代价是类型你得自己管 typedef struct { void **slots; // 连续内存里的座位们 int capacity; // 当前总共有多少个座位 int used; // 已经坐了多少个人 } DArray;想取第i个元素slots[i]直接命中O(1) 搞定。链表想做到这一点得从头指针出发走 i 步这就是两者最根本的分水岭。扩容电影院临时加座位的艺术座位坐满了怎么办动态数组的做法是临时加一排重新申请一块更大的内存把所有人挪过去再把老座位还回去。这一步叫expand也是整篇文章最值得玩味的地方。《Learn C The Hard Way》的作者在讲座里留了个彩蛋他实现扩容用的是固定增量300而不是教科书里常见的翻倍*2static int DArray_expand(DArray *da) { // 座位不够了就得加座。 // 这里用固定增量 300 而不是翻倍 // 理由翻倍会造成大量用不上的空座位 // 白白吃掉内存性能却没什么提升。 int new_cap da-capacity 300; void **fresh realloc(da-slots, new_cap * sizeof(void *)); if (!fresh) return -1; // realloc 失败会返回 NULL必须先检查 da-slots fresh; da-capacity new_cap; return 0; }你可能会问翻倍不是能减少扩容次数、摊薄拷贝成本吗作者的实测结论是翻倍省下的那点拷贝时间远抵不上它浪费的内存。尤其当你只存几千个元素时翻倍策略可能让你多备出一整倍的空位。当然这只是一个观点——讲座的 Extra Credit 里也建议你自己写测试去验证。这个别迷信教科书的态度我觉得比结构本身更值钱。数组还是链表一张表帮你拍板选择困难症犯了我平时就靠这张表做决策使用场景动态数组 (DArray)链表 (List)随机访问按下标取元素✅ O(1)直接命中❌ O(n)要遍历在头部插入/删除❌ 全员搬家O(n)✅ 只动指针O(1)排序✅ 随机访问快排归并随便上❌ 冒泡都写得想哭大容量存储✅ 每个元素只多一个指针❌ 每个节点都有一堆指针开销分割、合并❌ 要拷贝整段数据✅ 改几个指针完事少量元素❌ 预分配空位浪费内存✅ 用多少造多少一句话总结你更常读选数组你更常插选链表。没有万能结构只有合不合适。三个翻车现场我全踩过现场一malloc 不检查直接开用新手写malloc从来不看返回值仿佛内存永远够用。但一旦分配失败拿到 NULL 还继续读写就是段错误 诡异崩溃二选一。老手的习惯是每个分配点都查一次返回值代码丑一点没关系稳。现场二off-by-one边界全错capacity和used这两个数一个管总座位一个管已用座位。扩容的时机、下标的边界稍微算错一格不是漏了最后一个元素就是写穿了缓冲区。空数组、满数组、恰好差一个这三种情况值得专门写测试用例盯死。现场三被人用扩容耗死动态数组扩容要拷贝整块内存。如果攻击者不停插入再删除、再插入再删除就能反复触发扩容把你的 CPU 和内存拖垮——这就是教科书说的拒绝服务。解决方案之一扩容策略做保守设计像作者那样用固定增量让单次扩容的成本可控、可预测。两个额外视角vector 与内存侦探学完 DArray 再看 C 的std::vector你会发现它俩本质是同一个东西连续存储、自动扩容、随机访问。区别在于 vector 把扩容策略、内存回收、类型安全都封装好了而你用 C 手写 DArray等于把 vector 的内脏翻出来看了一遍。看得懂内脏的人用起封装才不心虚。排查内存问题时推荐一个侦探工具valgrind。一行命令就能帮你抓出忘了 free 的块和越界读写valgrind --leak-checkfull ./my_darray_testDArray 的销毁按理说只需要两步先free掉slots这块连续内存再free结构体本身——比链表挨个释放节点痛快多了。但如果你忘了第一步valgrind 会毫不留情地给你标红。用它跑一遍胜过你盯着代码猜半天。三个小实验今晚就能上手光看不练假把式。这里有三个递进的小实验跑完你就真正拥有了 DArray改扩容策略把代码里的 300改成* 2用clock()计时插入 10 万个元素对比两者耗时和内存峰值看看作者的断言是否成立。链表大乱斗把同样的 10 万次头部插入分别跑在 DArray 和 List 上感受一下 O(n) 与 O(1) 的真实差距。实现归并排序给 DArray 写一个归并排序。等你写完就会发现——正是因为能随机访问这些排序算法才有用武之地这也是第 35 讲ex35/lecture.md要展开的故事。写代码最爽的时刻莫过于亲手验证一个别人说不行的东西。去把座位排好吧万一你发现翻倍策略更适合你的场景呢【免费下载链接】learn-c-the-hard-way-lecturesAll of the code from Learn C The Hard Way, each project, plus the presentation slides used in the videos.项目地址: https://gitcode.com/gh_mirrors/le/learn-c-the-hard-way-lectures创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考