1. 两种存储选择背后的根本矛盾想真正理解线性表得先想明白一个问题我们为什么要发明线性表这种数据结构其实答案特别朴素。现实世界里大量数据天生就是一列带顺序的东西——一个班的学生名单一排货架上的商品一天里产生的订单记录。它们有一个共同特征除了第一个元素每个元素都有且只有一个直接前驱除了最后一个元素每个元素都有且只有一个直接后继。这种一对一的逻辑关系就是线性表的本质。计算机要处理这类数据面临一个物理层面的约束内存地址空间是一维的且数据必须落到具体的地址上。于是问题就变成了——如何把逻辑上连续的一串数据映射到物理上有限的内存空间这里出现了两条路线顺序存储顺序表找一块连续的物理内存把数据一个挨一个放进去。逻辑相邻物理上也相邻。链式存储链表不要求物理连续每个节点单独分配用指针把前后节点串起来。逻辑相邻物理上可能千里之外。我在带新人时发现很多人一开始觉得链表高级复杂顺序表简单低级。这个认知多半是反的。顺序表的难点在于管理一块动态内存链表的难点在于指针操作容易出错两者各有一笔难念的经。所以这篇系列开篇我想先把线性表的整体框架立起来再用大量代码把顺序表ArrayList和单链表SingleLinkedList两种实现讲透。静态链表、循环链表、双向链表这些变种放到后面的篇幅去拆。贪多嚼不烂先把地基夯实。2. 线性表的逻辑画像你永远在操作哪五个动作很多教材上来就甩线性表是具有相同数据类型的n个数据元素的有限序列然后把ADT定义一列——InitList、DestroyList、GetElem、LocateElem、ListInsert、ListDelete……看起来是八股文其实它就是一张地图。我建议你自己把这张地图画一遍。想一想作为使用者你对一个线性表的需求本质上就五件事建一个空表往里面塞数据初始化 / 增知道表里有多少数据长度想改某个位置的数据按位访问想知道某个数据出现在哪按值查找把数据插进去或删掉插入 / 删除把这五个动作抽象出来你就得到了线性表的接口契约。至于底层用数组还是用链表那是后面的事。这就是所谓的逻辑结构与物理结构分离。这个概念不夸张地说是整个数据结构的纲领。栈、队列本质上就是受限的线性表它们的实现同样既可以基于数组也可以基于链表。学完今天这两套代码你后面学栈和队列几乎等于白送。3. 顺序表第一课动态数组的扩容博弈3.1 静态数组的尽头容量写死在代码里顺序表最直观的实现就是一个定长数组加一个表示当前长度的变量#define MaxSize 10 typedef struct { int data[MaxSize]; int length; } SeqList;这种写法考试够用工程里几乎没法用——因为一旦数据量超过MaxSize程序直接崩给你看。更难受的是你事先根本不知道数据会来多少。预先开1万块内存数据只来了10条浪费预先开100块数据来了200条更浪费。所以实战里几乎清一色用动态内存容量capacity和当前长度length分开记装不下了就去申请一块更大的内存把旧数据整体搬过去。这正是std::vector的底层思路也是我们要手动实现的核心逻辑。3.2 扩容的为什么均摊分析不是玄学扩容策略听起来简单但里面的门道值得说清楚。假设容量不够了我就多申请一块固定大小的内存比如每次多50个位置。插入10万个元素会发生什么每次插入前都要检查容量不足时执行一次搬迁。你插入得越多搬迁次数越多总开销呈O(n²)级别增长——这在大量插入时是灾难。正确做法是倍增扩容容量不够时新容量翻倍常见系数是1.5到2之间。这样做的数学背景是均摊分析——虽然单次扩容可能搬动大量元素但由于扩容次数呈对数级减少均摊到每次插入上的代价约等于O(1)。一个简单的经验容量用乘法增长而不是加法增长。选2还是1.5是个经典工程选择题。2倍简单粗暴内存最多浪费一半1.5倍更省内存但计算略复杂。我自己的项目里小规模数据用2倍超大集群里会用1.5减少内存碎片。初学者从2倍起步就够用了。3.3 完整实现带模板的DynamicArray下面给出一份可以直接抄作业的C实现。为了适应不同数据类型用了模板为了支持自动管理内存写了构造、析构、拷贝构造、赋值运算符。#include iostream #include stdexcept template typename T class ArrayList { private: T* data; // 指向动态数组的指针 int capacity; // 当前容量 int size; // 当前元素个数 void resize(int newCapacity) { T* newData new T[newCapacity]; for (int i 0; i size; i) { newData[i] data[i]; // 逐元素拷贝 } delete[] data; // 释放旧内存 data newData; capacity newCapacity; } public: ArrayList() : data(nullptr), capacity(0), size(0) {} ArrayList(const ArrayList other) : data(nullptr), capacity(other.capacity), size(other.size) { data new T[capacity]; for (int i 0; i size; i) { data[i] other.data[i]; } } ArrayList operator(const ArrayList other) { if (this ! other) { // 先清理旧资源再拷贝 delete[] data; capacity other.capacity; size other.size; data new T[capacity]; for (int i 0; i size; i) { data[i] other.data[i]; } } return *this; } ~ArrayList() { delete[] data; }void pushBack(const T value) { if (size capacity) { int newCapacity (capacity 0) ? 1 : capacity * 2; resize(newCapacity); } data[size] value; } void insert(int pos, const T value) { // pos 范围: [0, size] if (pos 0 || pos size) { throw std::out_of_range(insert: pos out of range); } if (size capacity) { int newCapacity (capacity 0) ? 1 : capacity * 2; resize(newCapacity); } // 从后往前搬移元素 for (int i size; i pos; --i) { data[i] data[i - 1]; } data[pos] value; size; } void erase(int pos) { // pos 范围: [0, size-1] if (pos 0 || pos size) { throw std::out_of_range(erase: pos out of range); } // 从前往后搬移元素 for (int i pos; i size - 1; i) { data[i] data[i 1]; } --size; } int find(const T value) const { for (int i 0; i size; i) { if (data[i] value) { return i; } } return -1; } T at(int pos) { if (pos 0 || pos size) { throw std::out_of_range(at: pos out of range); } return data[pos]; } const T at(int pos) const { if (pos 0 || pos size) { throw std::out_of_range(at: pos out of range); } return data[pos]; } int getSize() const { return size; } int getCapacity() const { return capacity; } bool isEmpty() const { return size 0; } void print() const { for (int i 0; i size; i) { std::cout data[i] ; } std::cout std::endl; } };有几个细节必须提一下resize里为什么逐元素拷贝而不是memcpy因为T可能是自定义类型直接按字节拷贝对含指针的类会出双重释放或浅拷贝问题。new T[]会把每个元素依次构造拷贝时用赋值操作最安全。拷贝构造和赋值运算符是必修课如果你不写C编译器会给你生成一个浅拷贝版本两个对象共享同一块data内存。任何一方析构另一方就成了悬挂指针。这是C初学最容易踩的雷。insert的先判位置再扩容顺序很重要。如果先扩容再检查pos万一pos非法白白搬了一次内存。3.4 插入删除的时间账为什么中间插入是O(n)插入操作需要把pos位置及其之后的元素统一向后挪一格。平均而言你插入的位置可能在任意地方所以平均要挪一半的元素复杂度O(n)。删除同理平均挪一半元素向前补齐。这恰恰是教材里说的顺序表随机存取快插入删除慢的来源。两个操作的时间花费都花在了元素搬移上——搬移的次数不是你控制的而是由元素个数和位置分布决定的。4. 单链表第二课把碎片内存串成一条线4.1 为什么要有头节点纯属为了少写if顺序表用数组所有元素住在一栋楼里地址连续链表反着来每个元素自己住一间房房间里放个纸条写着下一个房间在哪。单链表的节点定义再简单不过template typename T struct ListNode { T data; // 数据域 ListNodeT* next; // 指针域指向下一个节点 ListNode(const T val) : data(val), next(nullptr) {} };关键设计在于头节点。头节点有两种理解方式不带头节点head指针直接指向第一个数据节点。空表时head nullptr。带头节点head指向一个不存数据的哨兵节点head-next才指向第一个数据节点。空表时head-next nullptr。后者实战里几乎是标配原因很务实带头节点之后插入和删除的第一个节点跟插入删除中间节点写起来完全一样不用特判。不带头节点的版本里你每次在头部做插入删除都要额外处理head指针本身。这种特判最容易漏而且漏一次就是线上事故级别的bug。4.2 完整实现单链表的增删改查直接看代码。为了保证篇幅不失控我挑最关键的操作讲其余完整代码尽量紧凑。#include iostream #include stdexcept template typename T class SingleLinkedList { private: ListNodeT* head; // 头节点不存数据 int size; public: SingleLinkedList() : head(new ListNodeT(T())), size(0) {}注意一个细节head初始化时哨兵节点也得有个data尽管它永远不会被访问。这里用T()构造了一个临时值占位。如果T没有默认构造函数这里会编译失败解决办法是给哨兵节点单独设计一个不用初始化data的构造版本或者用malloc配合placement new这些属于进阶话题先不展开。~SingleLinkedList() { ListNodeT* cur head; while (cur ! nullptr) { ListNodeT* next cur-next; delete cur; cur next; } } // 头部插入 void pushFront(const T value) { ListNodeT* newNode new ListNodeT(value); newNode-next head-next; head-next newNode; size; } // 尾部插入 void pushBack(const T value) { ListNodeT* newNode new ListNodeT(value); ListNodeT* cur head; while (cur-next ! nullptr) { cur cur-next; } cur-next newNode; size; }pushFront的指针操作顺序是经典中的经典。一定先把新节点的next指向老的头结点再把头节点的next指向新节点。很多人反过来写先把head-next改成newNode然后想给newNode-next赋值时发现老节点已经找不到了。这个顺序我手写代码时每次都会默念一遍先接后链再断前链。// 在第pos个位置从0开始计数插入 void insert(int pos, const T value) { if (pos 0 || pos size) { throw std::out_of_range(insert: pos out of range); } ListNodeT* prev head; for (int i 0; i pos; i) { prev prev-next; } ListNodeT* newNode new ListNodeT(value); newNode-next prev-next; prev-next newNode; size; } // 删除第pos个节点从0开始计数 void erase(int pos) { if (pos 0 || pos size) { throw std::out_of_range(erase: pos out of range); } ListNodeT* prev head; for (int i 0; i pos; i) { prev prev-next; } ListNodeT* target prev-next; prev-next target-next; delete target; --size; } int find(const T value) const { int index 0; ListNodeT* cur head-next; while (cur ! nullptr) { if (cur-data value) { return index; } cur cur-next; index; } return -1; } int getSize() const { return size; } bool isEmpty() const { return size 0; } void print() const { ListNodeT* cur head-next; while (cur ! nullptr) { std::cout cur-data ; cur cur-next; } std::cout std::endl; } };4.3 链表的快是挑场景的快很多人背结论时容易背成一锅粥链表插入快。但你必须看清前提——在已知前驱节点的情况下插入是O(1)如果只知道要插的位置序号那还得先从头遍历找到前驱遍历本身O(n)整体还是O(n)。删除也是同样的道理erase里真正花时间的不是改指针而是for循环去找前驱节点。所以链表的插入删除优势只在你已经持有一个指向目标位置的指针时才能完全发挥。典型场景就是后面讲LRU缓存淘汰算法时哈希表配合链表哈希表负责O(1)定位节点链表负责O(1)增删。还有一个工程上的坑要单独提醒new操作本身有开销。频繁插入删除时一个节点一次new一个delete内存分配器的调用成本是不可忽略的。顺序表的搬移虽然费时间但内存分配次数少。这个账不能说链表一定快。5. 复杂度之外的工程账缓存、内存碎片和不确定性学校考复杂度两个都算出来就完事真实项目里选型还要看几张隐藏账单。先说说缓存局部性。顺序表的数据在物理内存里是连续排布的遍历时CPU可以预取接下来的数据到高速缓存顺序访问的cache命中率极高。链表每个节点都是单独new出来的碎片状分布在堆上遍历时大概率跳来跳去CPU缓存频频落空。在小规模数据下差距不明显数据量一旦上到百万级顺序表遍历比链表快一个数量级都不稀奇。再聊聊内存碎片。顺序表扩容是整块搬碎片相对可控链表每插入一次就产生一个小块节点越小、插入越频繁碎片越多。堆上零零散散的小内存块会让内存分配器越来越难找到连续大块极端情况下明明还有很多内存却new不出一个大对象。服务端程序长期跑下来这种问题会暴露得很彻底。还有一点常被忽略实时性。顺序表插入的O(n)是均摊后的结果偶尔一次扩容可能很慢造成延迟尖刺。链表每次插入都是稳定的小开销实时性更好。做音视频处理、游戏引擎这些对单帧延迟敏感的场景链表反而更可控。我工作的习惯是能用顺序表就用顺序表除非明确需要频繁在中间插入删除、且数据量很大。很多人开口就是链表其实大部分场景顺序表因为在缓存、内存分配、代码简单性三方面都占优反而更合适。6. 写完两套数组和链表后我必须告诉你的五个坑这节是我最想讲的也是最难在教材里看到的。每一条都是从实际编码和面试复盘里捞出来的。第一个坑erase后指针悬空。链表里删除了target节点如果有其他指针仍指向它后续访问就是use-after-free。工程里常见做法是先断开连接再delete同时保证没有任何局部变量还引用着它。更稳妥的做法是用智能指针比如std::shared_ptr来管理节点让引用计数自动决定何时释放。但这又引入循环引用问题链表天然成环需要weak_ptr打破设计复杂度会上升。第二个坑顺序表的迭代器失效。插入导致扩容时整个数组搬了新家原本保存的指针或迭代器全部失效。C的std::vector在插入后旧的迭代器按标准就是无效的。敢在扩容之后继续用旧迭代器恭喜你你获得了一次随机内存踩踏的体验。第三个坑不要在析构函数里写递归删除链表。我见过有人写~ListNode() { delete next; }节点一多递归深度跟链表长度一样直接爆栈。务必用循环遍历删除。内存碎片堆出来的深链分分钟教你做人。第四个坑模板类的实现不能分离到.cpp文件。如果你把ArrayListT::insert的实现放到.cpp里链接时会报无法解析的外部符号。模板是编译期实例化的编译器必须在每个用到它的翻译单元里看到完整定义。老老实实头文件里写实现或者用.hpp统一维护。第五个坑传引用与const修饰符。写成员函数时能const就const。find和print这类不修改对象的函数如果漏了const就不能在const对象上调用。老练的面试官会专门拿这个考你。7. 一个完整实例用顺序表实现通讯录理论知识再多还不如亲手跑一个实例。我写一个通讯录简化版把今天所有的操作串起来。struct Contact { std::string name; std::string phone; bool operator(const Contact other) const { return name other.name; } friend std::ostream operator(std::ostream os, const Contact c) { os c.name ( c.phone ); return os; } }; int main() { ArrayListContact contacts; contacts.pushBack({张三, 10086}); contacts.pushBack({李四, 10010}); contacts.pushFront({王五, 12345}); std::cout 当前联系人: ; contacts.print(); int pos contacts.find({张三, }); if (pos 0) { std::cout 找到了张三位置: pos std::endl; } contacts.erase(0); std::cout 删掉第一个后: ; contacts.print(); return 0; }这个例子虽然简单但呈现了一个非常重要的点数据结构是通用的数据结构里存的东西才是业务的。ArrayListContact和ArrayListint的代码完全一样只是模板参数不同。所以把线性表学透本质上是掌握了一种容器能力至于里面装什么、怎么组织业务规则那是你领域的事情。实际上通讯录更合理的底层一般是二叉查找树或者跳表但那是后面章节的内容了。这里用它是因为插入、删除、查找三个操作恰好覆盖了线性表的核心接口。8. 写在开篇的最后调试链表的独家心得我知道很多人自己写链表写到一半就卡住。最常见的问题是指针指来指去运行结果跟自己想的不一样。我的经验是三个字画、写、印。先画。纸上画出head、各个节点的方框和箭头模拟每个指针操作的步骤一次只改一个箭头。画明白了再写代码。再印。代码里临时加打印在关键操作前后把当前节点的地址和数据一起打出来std::cout cur地址: cur 值: cur-data 下一个: (cur-next ? cur-next : nullptr) std::endl;一眼就能看出链接关系断没断。能打印出环形链表恭喜你找到了问题。最后用断言和边界用例。空表插入、尾部插入、末尾删除、删除后find每个边界都测一遍这比任何技巧都管用。这一篇把线性表的地基打完了。下一篇我计划把单向链表的变种——循环链表、双向链表和静态链表——一次性讲完然后带着你手写一个LRU缓存。到时候你会发现今天学的单链表操作是后面所有复杂链表操作的基本功。先把这一篇里的代码和例子跑熟再往后走会越走越顺。