很多人学数据结构都有一个共同体验纸上的链表画得明明白白方块加箭头清清爽爽一坐到编辑器前不是段错误就是内存泄漏。我见过不止一个同学能把“数组和链表的区别”背得滚瓜烂熟真让他写一个带析构函数的链表类手指放在键盘上半天落不下去。这种割裂感并不罕见根源在于我们把“数据结构”当成了概念知识而不是工程能力。数据结构从来不是一套名词解释它是“存储布局访问规则操作算法”的三位一体不落到指针、内存和C的类设计这一层永远只是纸面功夫。所以我想按这个思路整理一份实操笔记默认你有一点C基础知道类和指针是什么剩下的我们从数组、链表、栈、队列一路写到树和哈希表每个结构都先讲清楚它到底在解决什么“访问问题”再给出可以直接复现的C实现思路最后把那些教材不会写、却一定会遇到的坑挑出来讲透。不管你是正在学数据结构的学生还是工作里需要手写容器的工程师应该都能找到对自己有用的东西。1. 数据结构到底在解决什么问题访问方式才是核心竞争力1.1 数据不是一堆散沙它有形状先问一个最基础的问题为什么我们需要数组、链表这些东西因为真实世界里要处理的数据天然有形状。一个班级的名单是线性的一个公司的组织架构是树状的一张地铁图是图状的。程序在内存里处理这些数据不能把它们打成散沙之后再用暴力搜索而是要让存储结构去贴合数据的形状让访问效率变得可控。这就是数据结构的第一个价值它决定了你访问数据的路径和代价。同样是“找到第三本书”在书架上做是O(1)的“走到第三个格子”在一根铁链上做是O(n)的“从头数三个环”同样是“在第二本书和第三本书之间插一本”在连续的书架上要往后挪一排书在铁链上只需要把链环重新扣一下。数据结构没有绝对的优劣它本质上是一组代价的取舍选型就是选择一组你最愿意承受的代价。1.2 ADT把“接口”和“实现”分开概念层面的数据结构其实说的是抽象数据类型ADT。ADT里最重要的思想是用户只依赖操作不依赖存储。栈只暴露push、pop、top这些操作至于底层是用数组还是链表调用方根本不需要知道。这就像你去餐厅点餐只需要看菜单不需要知道后厨用的什么灶更不用关心那道菜是几个厨师配合炒出来的。C的class天然适合做这件事。public方法是菜单private成员和后厨做法都被藏起来。只要公开接口不变昨天内部用vector今天换成deque调用方代码一行不用改。这也是为什么STL里的stack、queue是“容器适配器”而不是“容器”——它们没有发明新的存储结构只是把deque、list这些现成容器包成受限接口。理解了ADT你再看STL的适配器源码很快就会明白它们到底在干什么。1.3 选结构的三把尺子把概念转成实现之前先建立一个选型框架。我平时掂量一个数据结构时主要看三件事。第一访问模式是什么——读多还是写多是不是按下标访问需不需要有序遍历第二数据规模量级如何——几百条还是几百万条某些O(n)操作在几百条时完全无感几百万条就是灾难第三要不要保证有序性——无序哈希虽然快但需要有序输出时还是要回到树。这三个问题回答完多数情况下容器选择已经定了一大半。后面每个章节都会用到这几把尺子。它们不神秘核心就一句话一个数据结构只有在匹配你真实访问模式时才谈得上“好”否则再高级的结构也是负担。我先把这个判断框架放在这等讲到哈希表和红黑树的取舍时你还会回来验证它。2. 数组与链表两种存储哲学两条实现路线2.1 数组的“高贵”与代价数组是最朴素的结构但很多人没意识到它的快速来自哪里。因为它把元素连续摆在内存里a[i]的地址可以按 base i * sizeof(T) 直接算出来一次加法一次访存天然就是O(1)。这个特性链表给不了。而且连续内存对CPU缓存极度友好遍历数组时硬件预取器会拼命帮你提前加载这在现代计算机上带来的收益往往比算法复杂度本身更明显。代价呢保持连续性是一件“贵”的事情。在数组中间插入一个元素要把它后面的元素全部往后挪在头部插入就是全员平移。删除同理。另一个隐藏代价是扩容用vector时容量不够就要申请一块更大的内存、把旧元素搬过去、释放旧内存。一次扩容是O(n)的但只要按1.5倍或2倍扩容把多次扩容的成本摊到每次push_back上均摊下来就是O(1)。如果每次只多申请1个位置最后一次扩容要把前面所有元素都拷贝一遍均摊就变成O(n)那就不划算了。2.2 链表灵活的背后是内存所有权问题链表用“每个节点存好下一个节点的地址”来换取插入删除的灵活性代价是随机访问要顺着指针走。手写链表真正让人头疼的不是画图而是内存所有权——谁拥有这个节点谁来释放释放顺序错了就是悬垂指针漏了就是内存泄漏。我写链表时习惯用一个虚拟头节点dummy它不存有效数据但能让头插和中间插共用同一套插入逻辑省掉“是不是空链表”“是不是头节点”这一堆特判。删除节点时也极有用你不再需要单独处理“删除的是不是第一个节点”这种边界。删除节点有一个固定顺序先摘链再释放。先把前驱节点的next指到待删节点的后继然后再delete那个节点本身顺序反了前驱节点就成了悬垂指针。这个顺序看起来简单但我在代码评审里见过太多次写反的情况因为它属于那种“你不踩一次崩就记不住”的错误。2.3 用还是不用谈谈缓存和局部性讲完原理落到工程选型上。事实是现代C程序里数组vector的出场率碾压链表list不是因为链表不经典而是因为内存局部性。链表节点分散在堆上每一次next都是一次随机访存缓存命中率低数组连续访问下一个元素大概率已经在缓存里。所以很多“看起来该用链表”的场景实测下来vector反而更快这个反直觉结论是真的。什么时候才该认真考虑链表我总结过你已经持有某个节点的迭代器需要在它旁边频繁插入删除或者你需要元素的地址稳定、不被扩容搬走或者你在做并发容器需要在节点层面做细粒度控制。否则先写vector用性能分析工具说话这比拍脑袋定结构可靠得多。把两种结构的常用代价放在一张表里方便随时查阅。维度数组vector链表list随机访问O(1)O(n)已知位置插入/删除O(n)要搬元素O(1)未知位置插入/删除O(n)要先找位置O(n)要先找位置内存布局连续缓存友好分散缓存不友好扩容/重建偶发O(n)均摊O(1)无地址稳定性扩容后失效稳定3. 用C把栈和队列写成有“性格”的类3.1 栈的本质是一种访问纪律栈和队列都属于受限线性表它们在数组或链表之上额外规定了一组“只允许怎么访问”的规则。栈的规则是后进先出LIFO——只能从同一端压入和弹出就像一叠盘子你永远只接触最上面那只。递归的函数调用栈、编辑器里的撤销、表达式求值、括号匹配背后都是这个纪律。因为栈是“规则”而不是“存储”它底层用什么容器都行。理解这一点很重要面试里写“用数组实现栈”和“用链表实现栈”答案是同一个类的两种内脏。重点在于类对外暴露的push、pop、top这三个接口以及它对边界行为的定义。3.2 用模板写一个栈接口性格自己定建议直接用模板把它写成通用的。一个最简单的、基于vector的栈长这样template typename T class Stack { public: void push(const T value) { m_data.push_back(value); } void pop() { if (!m_data.empty()) { m_data.pop_back(); } } T top() { return m_data.back(); // 空栈时是未定义行为 } bool empty() const { return m_data.empty(); } private: std::vectorT m_data; };注意几个设计决策。pop()的返回类型是void不是T——因为如果返回弹出元素必然先拷贝一份T再删除T可能是个很重的对象还可能拷贝抛异常。这正是STL的pop不返回元素的原因。top()在空栈时调用的行为是未定义行为我在注释里写清楚了。你当然可以改成抛异常或者返回std::optional但不管选哪条都要在接口注释里写死让调用方知道边界在哪。这种“接口性格”是自研数据结构最容易被忽略的部分。3.3 队列与循环数组绕圈的数学队列是先进先出FIFO。如果直接拿vector当队列出队时erase(0)会让所有元素前移是O(n)。经典解法是循环数组用head和tail两个下标标记队头队尾入队tail加1出队head加1下标满了就通过取模“绕回”开头。取模运算本质上就是让下标在时钟面上走圈。判满的时候有两种流派。一种浪费一个槽位用 (tail 1) % capacity head 判满一种单独维护一个size变量用 size capacity 判满。我更推荐后者因为不用留空洞代码也更直观template typename T class CircularQueue { public: explicit CircularQueue(size_t capacity) : m_data(capacity), m_head(0), m_tail(0), m_size(0) {} bool push(const T value) { if (m_size m_data.size()) { return false; // 队列已满 } m_data[m_tail] value; m_tail (m_tail 1) % m_data.size(); m_size; return true; } bool pop() { if (m_size 0) { return false; } m_head (m_head 1) % m_data.size(); --m_size; return true; } private: std::vectorT m_data; size_t m_head; size_t m_tail; size_t m_size; };循环队列在操作系统缓冲区、生产者消费者模型里出现频率很高因为它是定长数组、不需要动态扩容、也没有游标之外的额外内存分配。如果用链表实现队列那就是head出队、tail入队思路同样自然。说到底队列也是一层“规则”底层容器完全可以根据场景换。4. 递归、树与二叉树把层次关系写进代码4.1 递归是归纳法不只是“自己调用自己”讲到树绕不开递归。很多人把递归理解成“自己调用自己”这只是表面。递归的本质是数学归纳法先有基线条件再假定“规模小一点的问题已经能解决”用这个结果构造出当前规模的答案。写递归最忌讳上来就写递推式、不写终止条件——那样的代码要么死循环要么爆栈。举个最简单的例子求二叉树高度。基线条件是空树高度为0递推关系是当前节点的高度等于1加上左右子树高度的较大值。代码短到不能再短struct Node { int value; Node* left; Node* right; Node(int v) : value(v), left(nullptr), right(nullptr) {} }; int height(Node* root) { if (root nullptr) { return 0; } return 1 std::max(height(root-left), height(root-right)); }递归背后是有代价的。每次调用都会在调用栈上压一个新栈帧递归深度等于树高。对于一棵平衡树深度是O(log n)没问题但如果树退化成一条链递归深度就等于节点数几万层就能把栈压爆。后面讲平衡树的时候你会发现“控制树高”不只是为了复杂度好看还为了能让这种递归写法安全地跑完。4.2 二叉搜索树让“比较”变成“方向”二叉搜索树BST的核心规则只有一条左子树所有节点都比根小右子树所有节点都比根大。有了这条规则查找、插入都可以沿着一条路径走平均O(log n)。它本质上把“比较大小”这件事转化成了“向左走还是向右走”的方向选择。插入的逻辑也很清晰注意递归的返回值直接写回当前节点的指针字段Node* insert(Node* root, int value) { if (root nullptr) { return new Node(value); } if (value root-value) { root-left insert(root-left, value); } else if (value root-value) { root-right insert(root-right, value); } return root; }真正劝退入门者的是删除操作。BST删除一个节点分三种情况叶子节点直接delete只有一个孩子把孩子提上来顶替自己的位置有两个孩子最麻烦——要找到中序后继右子树里最左边的节点用它的值覆盖当前节点再去右子树里删掉那个后继。为什么非要找后继因为中序后继在删除后依然能让整棵树保持左小右大的性质而且它一定最多只有一个孩子删除它就退化成前两种情况。这个思路我当年也绕了很久现在回想核心就是“合并问题、降维处理”。4.3 平衡问题BST的“平均”与“意外”有一个必须直面的现实BST的复杂度是平均意义下的。如果数据总是按升序插入比如1、2、3、4……每插入一个都成为当前最大节点树就会一路往右偏最终退化成一条链表。这时查找复杂度从O(log n)掉到O(n)树的美感荡然无存。为了解决这个问题才出现了AVL树、红黑树。AVL用严格平衡因子控制左右子树高度差不超过1红黑树用颜色规则做近似平衡插入删除时需要旋转的次数更少所以工程实现和实际性能通常更优。你平时用的std::map、std::set底层就是红黑树。理解到这层就够了平衡结构存在的意义是把“树高有保证”从平均变成确定让所有的O(log n)承诺真正成立。5. 哈希表再快也有边界散列思维与容器选型5.1 哈希让任意key也能变成下标数组按下标访问是O(1)但现实世界里大多数key是字符串、对象没有天然下标。哈希表的核心就是让key也能变成“下标”用一个哈希函数把任意key散列成整数再通过取模映射到数组的某个桶里。只要桶够多、分布够均匀绝大多数访问就是一次计算加一次访存这就是哈希表O(1)的理论来源。代价是空间的浪费和冲突的处理。两个不同key映射到同一个桶叫哈希冲突。处理冲突主要有两种思路链地址法和开放寻址法。链地址法最简单每个桶挂一条链表冲突了就往后挂开放寻址法在桶里找下一个空位缓存更友好但删除时要打删除标记实现细节更多。哈希表还有一个关键参数叫负载因子也就是元素总数除以桶数。负载因子太高冲突变多太低空间浪费。标准库实现会在负载因子超过临界值时rehash重新申请更多桶把已有元素全部重新散列。这次rehash是O(n)的所以高频插入前提前reserve桶数是有价值的优化。5.2 手写一个极简哈希表到底在练什么我不建议你直接去实现一个生产级哈希表但手写一个简化版值得做因为它能把散列、冲突、rehash这些概念全部串起来。下面这个版本只是为了看清结构桶用vector嵌套list插入和查询都只要三步算哈希、找桶、在桶里线性找key。template typename K, typename V class SimpleHashMap { public: explicit SimpleHashMap(size_t bucketCount 16) : m_buckets(bucketCount) {} void set(const K key, const V value) { size_t index std::hashK{}(key) % m_buckets.size(); for (auto kv : m_buckets[index]) { if (kv.first key) { kv.second value; return; } } m_buckets[index].push_back({key, value}); } bool get(const K key, V outValue) const { size_t index std::hashK{}(key) % m_buckets.size(); for (const auto kv : m_buckets[index]) { if (kv.first key) { outValue kv.second; return true; } } return false; } private: std::vectorstd::liststd::pairK, V m_buckets; };调试这个类的时候我建议你打印一下每个桶的链表长度。如果出现一两个桶特别长、其他桶基本空着多半是哈希函数选得不好而不是代码有bug。工程里我自己给自定义类型写哈希时习惯用多个字段的哈希值做异或和移位混合避免直接把几个整数相加——那种哈希会让相似对象扎堆冲突率直线上升。5.3 哈希再快也有边界哈希表在“按key找value”这个场景确实近乎无敌但它有一个基本缺陷无序。你无法遍历它得到有序序列也无法做范围查询比如查出所有大于某个值的key。这些操作哈希表做不了树结构才擅长。所以工程选型从来不是“哈希更先进”而是看访问模式。简单给个经验法则只要需要有序性或者范围查询就选基于树的容器map/set只要做存在性判断或精确查找优先哈希容器unordered_map/ unordered_set如果数据量很小几百条以内线性扫描甚至可能超过所有结构因为它的常数小、缓存友好。你要是观察过真实代码会发现很多“性能优化”最后都是在减少不必要的容器操作而不是换一个更高级的容器。哈希和树各有各的边界用对位置才是关键。6. 自己实现数据结构时最值得警惕的三个“坑”6.1 浅拷贝与double free裸指针类最容易踩的坑如果你用裸指针写链表或者树节点一定绕不开资源所有权问题。C默认的拷贝构造函数是浅拷贝两个对象会指向同一块堆内存。头一个对象析构时把那一串节点delete了第二个对象析构时再delete一遍直接double free崩溃。解决办法是所谓的“三法则”如果类里有裸指针资源就需要同时自定义拷贝构造、拷贝赋值运算符和析构函数。以链表为例拷贝构造要逐节点复制整条链让两个对象各自拥有一份拷贝赋值要先释放已有资源再逐节点复制析构则要沿链一个个释放。这个道理看起来简单但很多人直到线上程序时不时崩一次才真正理解“深拷贝”三个字是什么意思。如果你不想写这些繁琐的代码有两个选择用std::shared_ptr管理节点让所有权交给引用计数或者干脆别用裸指针容器直接以STL容器为底座。自己的项目怎么顺手怎么来。但作为学习我强烈建议你用裸指针完整写一遍链表因为只有亲手处理过double free才会对RAII和所有权这两个概念建立真正的肌肉记忆。6.2 迭代器失效vector扩容与遍历时删除的经典现场迭代器失效是另一个经典大坑。最典型的是vector的扩容当你push_back导致容量不够时vector会重新申请内存并搬移元素旧内存上的迭代器、指针、引用全部失效。你手头明明持有“1号元素”的迭代器扩容完它可能指向一段已经释放的内存再用就出问题。更隐蔽的是遍历时删除。很多人写删除元素的循环会习惯性像这样写std::vectorint v {1, 2, 2, 3}; for (auto it v.begin(); it ! v.end(); it) { if (*it 2) { v.erase(it); } }这段代码在erase之后继续使用it而且it会让迭代器跳过删除后的下一个元素。正确的写法是利用erase返回的迭代器std::vectorint v {1, 2, 2, 3}; for (auto it v.begin(); it ! v.end(); ) { if (*it 2) { it v.erase(it); } else { it; } }这个细节我在很多初学者代码里反复看到写法差异只有一行行为却天差地别。记住一句话删除操作让当前迭代器失效但会返回指向下一个元素的新迭代器使用返回值更新自己永远不要在失效迭代器上做自增。6.3 正确的打开方式先分析访问模式再谈优化整理到尾我的核心想法就一个数据结构选型是权衡不是比谁名词多。你在决定用哪个容器之前先问自己真实的访问模式是什么。如果是大量精确查找且不关心顺序哈希表会带来质的提升如果需要频繁按序输出和范围查询树容器才合适如果数据量小任何结构在长时间维度上都差不了太多反而代码可读性更重要。我印象里有一个文本索引处理的小例子最初用map存键值对查找速度始终上不去后来换上unordered_map精确查找快了很多但又发现需要有序输出的场景卡了壳。最终方案是同时维护两种视角——unordered_map做快速精确查找另一棵有序树服务范围输出。你看没有哪个结构替你想好一切真正管用的是“按访问模式分别选型、各取所长”这个思路。最后还是建议你动手写。不要直接抄STL拿裸指针写一遍单链表拿定长数组写一遍循环队列再写一个带深拷贝的二叉树然后回头再看std::list和std::deque的源码。你会发现教材里那些“平均复杂度”“边界条件”“内存所有权”全都在实实在在的代码里。数据结构这门课概念只是入口C实现才把你带过河。我后来带过的不少同学都是用一个周末完成从“画图很熟”到“代码能跑”的转变。你写的第一个链表可能会崩好几次但每一次崩溃都在帮你建立对内存的直觉。慢慢来值得的。
