0. 前言
我们学完了 C++ STL 全套排序算法，掌握了 sort、stable_sort、partial_sort 的底层差异与工程选型规范，也通过复杂度理论知道了不同数据结构操作的性能差距。从今天开始，我们正式进入线性表体系的系统学习。
线性表是所有数据结构的基石，而顺序表是线性表最基础、最常用的存储结构。C++ 中的 vector、Java 中的 ArrayList、Python 中的 list，底层全部都是顺序表。可以说，掌握顺序表，就掌握了 80% 容器底层的核心逻辑。
很多初学者只会调用 vector 的 API，完全不懂底层机制：不知道为什么扩容会迭代器失效、不清楚头部插入为什么慢、不理解为什么随机访问是 O(1)、分不清静态数组与动态顺序表的本质区别。刷题时频繁超时、工程中莫名迭代器失效、内存浪费，根源都是顺序表底层认知缺失。
顺序表是后续栈、队列、哈希表、各种高级算法的前置基础，也是面试笔试必考手写数据结构第一题。几乎所有数据结构面试，都会优先考察：手写顺序表、扩容机制、增删复杂度、边界条件处理。
我们从零深度拆解顺序表，从理论定义、存储特性、优缺点、完整手写实现、扩容原理、边界坑点、复杂度分析、STL vector 底层映射全方位吃透，彻底搞定线性表开篇核心。
1. 顺序表核心理论（必背）
1.1 什么是顺序表？
顺序表是用一段连续的内存空间，依次存储线性表数据元素的存储结构。简单来说，就是动态可扩容的数组。
核心两大特征：
1.内存连续：所有元素在内存中紧密排布，无空隙、不分散；
2.顺序存储：逻辑相邻的元素，物理内存也相邻。
1.2 静态数组 vs 动态顺序表
很多新手混淆普通数组与顺序表，二者本质区别极大：
静态数组 int arr[N]：编译期固定大小，内存不可扩容，空间不足直接越界，空间多余造成浪费；
动态顺序表 vector：运行期动态扩容，自动适配数据量，灵活分配内存，是工程通用存储结构。
我们今天手写的顺序表，就是简易版 STL vector。
1.3 顺序表核心优缺点（面试高频）
优点：
1.支持随机访问 O(1)：通过下标可直接定位元素，无需遍历，这是顺序表最大优势；
2. 内存连续、缓存命中率高、访问速度极快；
3. 结构简单、内存紧凑、无额外指针开销。
缺点：
1.插入、删除效率低 O(n)：中间/头部增删需要批量移动元素；
2. 扩容需要开辟新内存、拷贝数据、释放旧内存，存在性能开销；
3. 无法碎片化利用内存，必须申请连续大块空间。
2. 顺序表核心结构设计
手写顺序表需要维护三个核心成员变量，完全对标 STL vector 的底层设计：
1.data：动态数组指针，指向连续内存首地址；
2.size：当前有效元素个数；
3.capacity：当前最大容量（内存总大小）。
核心关系：size ≤ capacity
size：真实数据量；capacity：内存承载上限，size 触达 capacity 触发扩容。
3. 从零手写完整顺序表（C++ 实现）
我们手写一款完整、可运行、包含初始化、尾插、指定位置插入、删除、查找、扩容、打印、析构释放的工业级简易顺序表，完全对标 vector 核心功能。
#include <iostream> using namespace std; // 手写动态顺序表（简易vector） class SeqList { private: int* data; // 动态内存指针 int size; // 当前有效元素个数 int capacity; // 当前容量上限 // 扩容函数 void expand() { // 初始容量为4，后续2倍扩容 int newCap = (capacity == 0) ? 4 : capacity * 2; int* newData = new int[newCap]; // 拷贝旧数据到新内存 for(int i = 0; i < size; i++) { newData[i] = data[i]; } // 释放旧内存，避免内存泄漏 delete[] data; data = newData; capacity = newCap; } public: // 构造函数：初始化空顺序表 SeqList() : data(nullptr), size(0), capacity(0) {} // 尾插数据 void pushBack(int val) { // 容量不足，触发扩容 if(size >= capacity) { expand(); } data[size++] = val; } // 指定位置插入数据（pos从0开始） void insert(int pos, int val) { // 边界合法性校验 if(pos < 0 || pos > size) { cout << "插入位置不合法" << endl; return; } if(size >= capacity) { expand(); } // 元素后移，腾出插入位置（从后往前移） for(int i = size; i > pos; i--) { data[i] = data[i-1]; } data[pos] = val; size++; } // 删除指定位置元素 void erase(int pos) { if(pos < 0 || pos >= size) { cout << "删除位置不合法" << endl; return; } // 元素前移，覆盖被删除元素 for(int i = pos; i < size - 1; i++) { data[i] = data[i+1]; } size--; } // 根据下标获取元素 int get(int pos) { if(pos < 0 || pos >= size) { cout << "下标越界" << endl; return -1; } return data[pos]; } // 根据值查找下标 int find(int val) { for(int i = 0; i < size; i++) { if(data[i] == val) return i; } return -1; // 未找到 } // 打印所有元素 void print() { cout << "顺序表元素："; for(int i = 0; i < size; i++) { cout << data[i] << " "; } cout << endl; cout << "size:" << size << " capacity:" << capacity << endl; } // 析构函数：释放动态内存 ~SeqList() { delete[] data; data = nullptr; } }; // 测试主函数 int main() { SeqList list; // 尾插测试 list.pushBack(10); list.pushBack(20); list.pushBack(30); list.print(); // 中间插入 list.insert(1, 99); list.print(); // 删除元素 list.erase(2); list.print(); // 查找与获取 cout << "下标1元素：" << list.get(1) << endl; cout << "99的下标：" << list.find(99) << endl; return 0; }4. 核心机制深度解析：扩容原理
4.1 扩容完整流程
顺序表所有自动扩容，都遵循固定四步流程，STL vector 底层也是这套逻辑：
1. 判断当前 size 是否等于 capacity，满容量则触发扩容；
2. 开辟一块更大的连续新内存空间（默认2倍扩容）；
3. 将旧内存的所有数据，逐字节拷贝到新内存；
4. 释放旧内存、更新指针、更新容量参数。
4.2 为什么是2倍扩容？（面试必考）
1. 扩容倍数过小（1.5倍以下）：扩容频繁、拷贝次数多，性能损耗大；
2. 扩容倍数过大（3倍及以上）：单次扩容内存冗余过多，造成内存浪费；
3.2倍是时间与空间的最优平衡点，兼顾扩容频次与内存利用率，是工业级标准。
补充：部分 STL 版本采用 1.5 倍扩容，目的是更好的内存复用，减少内存碎片。
4.3 扩容带来的核心问题：迭代器失效
扩容会更换内存地址，旧的迭代器、指针、引用全部指向已释放的旧内存，直接失效，解引用会崩溃。
这也是 vector 插入数据后，需要重新获取迭代器的底层原因，完美衔接我们之前 STL 容器的知识点。
5. 所有操作时间复杂度终极复盘
结合第五十二天复杂度理论，我们精准推导顺序表所有接口复杂度：
1. 按下标访问 get：O(1)
内存连续，直接地址偏移访问，随机访问最优。
2. 尾插 pushBack：均摊 O(1)
绝大多数情况直接尾部赋值，仅少数情况触发扩容，均摊后为常数级。
3. 中间/头部插入 insert：O(n)
需要批量后移元素，数据量越大开销越高。
4. 中间/头部删除 erase：O(n)
需要批量前移元素，存在数据移位开销。
5. 按值查找 find：O(n)
无有序保障，只能线性遍历匹配。
6. 高频边界坑点（刷题/工程必避）
1.下标越界：插入、删除、访问必须校验 pos 范围，pos 合法区间为 [0, size]；
2.插入遍历顺序错误：元素后移必须从后往前遍历，否则数据会被覆盖；
3.删除遍历顺序错误：元素前移必须从前向后遍历，移位逻辑不可逆；
4.扩容不释放旧内存：导致严重内存泄漏；
5.混淆 size 与 capacity：有效数据量与内存容量概念错乱，导致越界访问；
6.扩容后不更新指针：旧指针悬空，引发野指针崩溃。
7. 顺序表与 vector 底层映射
今天手写的顺序表，完全对应 STL vector 核心底层：
1. 动态扩容机制 = vector 自动扩容；
2. pushBack 尾插 = vector::push_back；
3. insert 任意位置插入 = vector::insert；
4. erase 位置删除 = vector::erase；
5. 迭代器失效根源 = 扩容内存更换。
看懂手写顺序表，就彻底看懂了 vector 的底层工作原理。
8. 面试满分问答（必背）
Q1：顺序表的存储特点是什么？
内存连续、逻辑与物理顺序一致，支持随机访问，增删需要移动元素，适合查询多、增删少的场景。
Q2：顺序表为什么随机访问是 O(1)？
内存连续存储，可通过首地址+下标偏移量直接计算元素地址，无需遍历，实现常数级访问。
Q3：顺序表头部插入为什么效率极低？
头部插入需要将所有原有元素整体后移一位，数据量越大移位开销越高，时间复杂度 O(n)。
Q4：vector 扩容为什么会导致迭代器失效？
扩容会开辟新内存、释放旧内存，原有迭代器指向已销毁的旧内存空间，变成野迭代器，完全失效。
9. 全文总结
今天我们完成了线性表第一篇：顺序表完整精讲，吃透了顺序表定义、存储特性、优缺点、静态与动态数组差异、2倍扩容底层原理、全套增删查改逻辑、边界处理、复杂度分析，并且从零手写了可运行的完整顺序表，完美对标 STL vector 底层核心机制。
顺序表是所有线性结构的基础，理解了内存连续、数据移位、动态扩容、迭代器失效，就能彻底看懂 vector 的所有特性，为后续链表、栈队列、哈希表、算法刷题筑牢最核心的底层认知。
