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; // 数据域 ListNode<T>* 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: ListNode<T>* head; // 头节点，不存数据 int size; public: SingleLinkedList() : head(new ListNode<T>(T())), size(0) {}注意一个细节：head初始化时，哨兵节点也得有个data，尽管它永远不会被访问。这里用T()构造了一个临时值占位。如果T没有默认构造函数，这里会编译失败，解决办法是给哨兵节点单独设计一个不用初始化data的构造版本，或者用malloc配合placement new，这些属于进阶话题，先不展开。
~SingleLinkedList() { ListNode<T>* cur = head; while (cur != nullptr) { ListNode<T>* next = cur->next; delete cur; cur = next; } } // 头部插入 void pushFront(const T& value) { ListNode<T>* newNode = new ListNode<T>(value); newNode->next = head->next; head->next = newNode; ++size; } // 尾部插入 void pushBack(const T& value) { ListNode<T>* newNode = new ListNode<T>(value); ListNode<T>* 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"); } ListNode<T>* prev = head; for (int i = 0; i < pos; ++i) { prev = prev->next; } ListNode<T>* newNode = new ListNode<T>(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"); } ListNode<T>* prev = head; for (int i = 0; i < pos; ++i) { prev = prev->next; } ListNode<T>* target = prev->next; prev->next = target->next; delete target; --size; } int find(const T& value) const { int index = 0; ListNode<T>* 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 { ListNode<T>* 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文件。如果你把ArrayList<T>::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() { ArrayList<Contact> 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; }这个例子虽然简单，但呈现了一个非常重要的点：数据结构是通用的，数据结构里存的东西才是业务的。ArrayList<Contact>和ArrayList<int>的代码完全一样，只是模板参数不同。所以把线性表学透，本质上是掌握了一种容器能力，至于里面装什么、怎么组织业务规则，那是你领域的事情。
实际上，通讯录更合理的底层一般是二叉查找树或者跳表，但那是后面章节的内容了。这里用它，是因为插入、删除、查找三个操作恰好覆盖了线性表的核心接口。
8. 写在开篇的最后：调试链表的独家心得
我知道很多人自己写链表，写到一半就卡住。最常见的问题是：指针指来指去，运行结果跟自己想的不一样。
我的经验是三个字：画、写、印。
先画。纸上画出head、各个节点的方框和箭头，模拟每个指针操作的步骤，一次只改一个箭头。画明白了再写代码。
再印。代码里临时加打印，在关键操作前后把当前节点的地址和数据一起打出来：
std::cout << "cur地址: " << cur << " 值: " << cur->data << " 下一个: " << (cur->next ? cur->next : nullptr) << std::endl;一眼就能看出链接关系断没断。能打印出环形链表，恭喜你找到了问题。
最后，用断言和边界用例。空表插入、尾部插入、末尾删除、删除后find，每个边界都测一遍，这比任何技巧都管用。
这一篇把线性表的地基打完了。下一篇我计划把单向链表的变种——循环链表、双向链表和静态链表——一次性讲完，然后带着你手写一个LRU缓存。到时候你会发现，今天学的单链表操作，是后面所有复杂链表操作的基本功。先把这一篇里的代码和例子跑熟，再往后走，会越走越顺。
