当前位置：首页 > news >正文

顺序表（动态数组）深度精讲，从零手写实现、扩容机制、边界处理、增删查改全解析与复杂度分析

news 2026/6/12 23:27:45

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; }