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 ≤ capacitysize真实数据量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[i1]; } 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. 按下标访问 getO(1)内存连续直接地址偏移访问随机访问最优。2. 尾插 pushBack均摊 O(1)绝大多数情况直接尾部赋值仅少数情况触发扩容均摊后为常数级。3. 中间/头部插入 insertO(n)需要批量后移元素数据量越大开销越高。4. 中间/头部删除 eraseO(n)需要批量前移元素存在数据移位开销。5. 按值查找 findO(n)无有序保障只能线性遍历匹配。6. 高频边界坑点刷题/工程必避1.下标越界插入、删除、访问必须校验 pos 范围pos 合法区间为 [0, size]2.插入遍历顺序错误元素后移必须从后往前遍历否则数据会被覆盖3.删除遍历顺序错误元素前移必须从前向后遍历移位逻辑不可逆4.扩容不释放旧内存导致严重内存泄漏5.混淆 size 与 capacity有效数据量与内存容量概念错乱导致越界访问6.扩容后不更新指针旧指针悬空引发野指针崩溃。7. 顺序表与 vector 底层映射今天手写的顺序表完全对应 STL vector 核心底层1. 动态扩容机制 vector 自动扩容2. pushBack 尾插 vector::push_back3. insert 任意位置插入 vector::insert4. erase 位置删除 vector::erase5. 迭代器失效根源 扩容内存更换。看懂手写顺序表就彻底看懂了 vector 的底层工作原理。8. 面试满分问答必背Q1顺序表的存储特点是什么内存连续、逻辑与物理顺序一致支持随机访问增删需要移动元素适合查询多、增删少的场景。Q2顺序表为什么随机访问是 O(1)内存连续存储可通过首地址下标偏移量直接计算元素地址无需遍历实现常数级访问。Q3顺序表头部插入为什么效率极低头部插入需要将所有原有元素整体后移一位数据量越大移位开销越高时间复杂度 O(n)。Q4vector 扩容为什么会导致迭代器失效扩容会开辟新内存、释放旧内存原有迭代器指向已销毁的旧内存空间变成野迭代器完全失效。9. 全文总结今天我们完成了线性表第一篇顺序表完整精讲吃透了顺序表定义、存储特性、优缺点、静态与动态数组差异、2倍扩容底层原理、全套增删查改逻辑、边界处理、复杂度分析并且从零手写了可运行的完整顺序表完美对标 STL vector 底层核心机制。顺序表是所有线性结构的基础理解了内存连续、数据移位、动态扩容、迭代器失效就能彻底看懂 vector 的所有特性为后续链表、栈队列、哈希表、算法刷题筑牢最核心的底层认知。
顺序表（动态数组）深度精讲，从零手写实现、扩容机制、边界处理、增删查改全解析与复杂度分析
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 ≤ capacitysize真实数据量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[i1]; } 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. 按下标访问 getO(1)内存连续直接地址偏移访问随机访问最优。2. 尾插 pushBack均摊 O(1)绝大多数情况直接尾部赋值仅少数情况触发扩容均摊后为常数级。3. 中间/头部插入 insertO(n)需要批量后移元素数据量越大开销越高。4. 中间/头部删除 eraseO(n)需要批量前移元素存在数据移位开销。5. 按值查找 findO(n)无有序保障只能线性遍历匹配。6. 高频边界坑点刷题/工程必避1.下标越界插入、删除、访问必须校验 pos 范围pos 合法区间为 [0, size]2.插入遍历顺序错误元素后移必须从后往前遍历否则数据会被覆盖3.删除遍历顺序错误元素前移必须从前向后遍历移位逻辑不可逆4.扩容不释放旧内存导致严重内存泄漏5.混淆 size 与 capacity有效数据量与内存容量概念错乱导致越界访问6.扩容后不更新指针旧指针悬空引发野指针崩溃。7. 顺序表与 vector 底层映射今天手写的顺序表完全对应 STL vector 核心底层1. 动态扩容机制 vector 自动扩容2. pushBack 尾插 vector::push_back3. insert 任意位置插入 vector::insert4. erase 位置删除 vector::erase5. 迭代器失效根源 扩容内存更换。看懂手写顺序表就彻底看懂了 vector 的底层工作原理。8. 面试满分问答必背Q1顺序表的存储特点是什么内存连续、逻辑与物理顺序一致支持随机访问增删需要移动元素适合查询多、增删少的场景。Q2顺序表为什么随机访问是 O(1)内存连续存储可通过首地址下标偏移量直接计算元素地址无需遍历实现常数级访问。Q3顺序表头部插入为什么效率极低头部插入需要将所有原有元素整体后移一位数据量越大移位开销越高时间复杂度 O(n)。Q4vector 扩容为什么会导致迭代器失效扩容会开辟新内存、释放旧内存原有迭代器指向已销毁的旧内存空间变成野迭代器完全失效。9. 全文总结今天我们完成了线性表第一篇顺序表完整精讲吃透了顺序表定义、存储特性、优缺点、静态与动态数组差异、2倍扩容底层原理、全套增删查改逻辑、边界处理、复杂度分析并且从零手写了可运行的完整顺序表完美对标 STL vector 底层核心机制。顺序表是所有线性结构的基础理解了内存连续、数据移位、动态扩容、迭代器失效就能彻底看懂 vector 的所有特性为后续链表、栈队列、哈希表、算法刷题筑牢最核心的底层认知。
