数据结构入门：从C语言顺序表到动态数组的底层实现与复杂度分析

1. 内容整体设计与思路拆解1.1 为什么要从线性表开始学数据结构数据结构这门课很多初学者一上来就被树、图、哈希表这些概念砸懵了其实完全没必要。数据结构的核心就一句话怎么把一堆数据组织起来让增删改查变得高效。而线性表是整个学科里最简单、最直观、最贴近人类直觉的一种组织方式——就像排队买奶茶每个人都站在一条线上前面是谁、后面是谁清清楚楚。我第一次看严蔚敏那本紫色封面的《数据结构C语言版》时第一章就被“算法特性”“时间复杂度”这些概念绕得头晕。后来回头才明白真正该先啃下来的是第二章的线性表。因为它包含了你后面学栈、队列、串、数组、广义表、树、图都要用的基本功——顺序存储和链式存储这两种最基本的物理结构就是在线性表里第一次完整介绍的。很多人觉得顺序表太简单考试也不怎么考就草草翻过去了。但实际上顺序表是所有“随机访问”类数据结构的祖师爷你看Java的ArrayList、Python的list底层全是它。面试时问“ArrayList和LinkedList的区别”本质上就是在考你顺序表和链表的区别。把顺序表吃透你后面学栈和队列时就能直接套模板因为栈就是“只能从一头操作的线性表”队列就是“一头进一头出的线性表”它们的代码实现很大程度就是顺序表换了层外衣。这篇博文我会从零开始把顺序表讲透先讲清楚线性表到底是什么、顺序表为什么是“顺序”的再把初始化、插入、删除、查找、扩容这些核心操作逐个拆开给出可直接运行的C语言代码最后把我这些年调试顺序表踩过的一些坑和排错思路分享出来。不管你是期末复习、考研备考还是刚接触数据结构这门课准备第一份实验报告这篇都能帮上忙。1.2 逻辑结构、物理结构与顺序表的定位要搞懂顺序表必须先分清楚两个概念逻辑结构和物理结构。逻辑结构描述的是数据元素之间的抽象关系跟计算机内存没有关系。线性表的逻辑结构就是“一对一”的线性关系——每一个元素除了第一个和最后一个都有且仅有一个直接前驱和一个直接后继。你可以把它想象成一个故事的情节线时间顺序是线性的上一章接下一章逻辑上就是一条线。物理结构则是指这些数据在内存里到底怎么存的。线性表有两种经典的物理实现方式顺序存储和链式存储。顺序存储就是把逻辑上相邻的元素存放在物理地址也相邻的存储单元里也就是说内存里是一块连续的空间。链式存储则允许元素在内存里东一个西一个通过指针把它们串起来。顺序表就是“线性表 顺序存储”的产物。它的核心特征非常明确逻辑相邻物理上也相邻。这带来两个直接后果第一只要知道首元素的地址任何位置的元素都能通过“首地址 下标 × 元素大小”直接算出地址所以随机访问任意元素的时间复杂度是O(1)第二正因为物理上挤在一起插入和删除一个元素时为了保证连续性后面的元素必须整体移动所以平均时间复杂度是O(n)。这个“存取快、插入慢”的底层矛盾就是顺序表所有设计决策的根源。理解了这一点下面讲扩容、讲插入删除的细节你就能自然地接受了而不是靠死记硬背。1.3 动态顺序表和静态顺序表学哪个先顺序表从实现方式上还可以分为静态顺序表和动态顺序表。静态版本用固定长度的数组比如int data[100]一开始就分配好100个int的空间用完了就没了放不下了就报错。动态版本则使用指针加内存分配函数C语言里的malloc/realloc空间不够时就申请一块更大的把旧数据搬过去。初学阶段我建议直接学动态顺序表。原因有三个第一它更接近真实工程。你以后用的ArrayList、vector、Python list全是动态扩容的没有哪个正经库会用固定数组硬扛。第二它能帮你提前熟悉指针和内存管理。C语言数据结构的精髓就在于操作内存动态分配、扩容、释放这些技能学到链表、树的时候全都要用早接触早熟练。第三面试和考试里问得更多的也是动态版本尤其是“扩容策略”这种细节下面我会专门讲。但静态版本也不是完全没用。有些场景下数据规模事先就知道且固定不变比如一个班级的30个学号用静态数组反而更简单、零内存管理负担。顺序表的很多基本操作逻辑比如插入、删除时元素怎么移动其实和静态动态没有关系——你可以先在静态数组上把那套移动逻辑练熟了再迁移到动态版本心理负担会小很多。我的建议是静态的看懂原理就行动手写就写动态的。开头绕过的弯后面全得补回来。2. 核心细节解析与实操要点2.1 存储结构三要素数组、size、capacity一个完整的顺序表结构体在C语言里通常长这样#define INIT_CAPACITY 8 typedef struct { int *data; // 指向动态数组的指针 int size; // 当前元素个数有效长度 int capacity; // 当前数组容量最多能存多少个 } SeqList;这三个成员一个都不能少。data负责指向真正存放数据的内存区域size记录当前实际存了多少个元素它是“逻辑长度”用户访问的下标范围是0到size-1capacity是“物理容量”表示当前这块内存最多能装多少个元素。为什么size和capacity要分开因为数组一旦分配物理容量就固定了但逻辑上你可以只往里面放一部分。比如你分配了能装8个int的空间但只放了3个元素那么size3capacity8。如果只有size没有capacity你永远不知道自己还有多少余量也不知道该什么时候扩容。很多初学者的代码里只定义一个数组长度比如#define MAXSIZE 100然后一个length变量。这样当然也能写但静态味道很重一旦数据超过100就得改代码重新编译。动态版本里capacity是运行时可以变化的这才是“动态”二字的含义。在Java版本中对应的就是ArrayList内部的elementData数组、size字段扩容逻辑在grow()方法里。理解了C语言这个结构体Java的ArrayList源码读起来就是小菜一碟。2.2 初始化与内存分配最容易出错的入口函数初始化是顺序表所有操作的起点也是初学者第一批段错误Segmentation Fault的来源。先看标准写法#include stdio.h #include stdlib.h void initSeqList(SeqList *list) { list-data (int *)malloc(INIT_CAPACITY * sizeof(int)); if (list-data NULL) { printf(内存分配失败\n); exit(1); } list-size 0; list-capacity INIT_CAPACITY; }这里有几个细节必须注意。第一为什么传入的是SeqList *list而不是SeqList list因为C语言函数参数是值传递如果你传结构体本身函数内部对list.size的修改不会反映到外面。必须传指针通过指针修改结构体的成员。这不是顺序表特有的问题但初学者在写init函数时十有八九会载在这里——函数调用完size还是0data还是野指针主函数一访问就崩。第二malloc之后一定要检查返回值。虽然平时写代码的时候内存分配很少失败但一旦失败就是灾难性的空指针解引用。养成检查的习惯后面学链表的时候每一个节点都要malloc不检查的话调试起来极其痛苦。第三sizeof(int)不能省。有人写malloc(INIT_CAPACITY * 4)默认int是4字节这在绝大多数平台上没问题但C标准只规定int至少占2字节。用sizeof(int)不仅保证可移植性还是给别人看的自文档化信息。初始化之后list-data指向一块连续内存size0说明还没有元素capacity8说明现在最多放8个。之后每一次插入操作都会检查size和capacity的关系这就要说到扩容了。2.3 扩容策略为什么不是每次只多分配一个位置当size capacity的时候再插入元素就没地方放了这时候必须扩容。最简单的想法是再申请一块比原来大1的空间把旧数据搬过去。这样做在功能上没有错但性能上是灾难——每插入一个元素就要搬迁一次整个数组插入n个元素的时间复杂度直接变成O(n²)。所以常见的扩容策略是倍增扩容每次扩容成原来的2倍。void ensureCapacity(SeqList *list) { if (list-size list-capacity) { return; } int newCapacity list-capacity * 2; int *newData (int *)malloc(newCapacity * sizeof(int)); if (newData NULL) { printf(扩容失败\n); exit(1); } for (int i 0; i list-size; i) { newData[i] list-data[i]; } free(list-data); list-data newData; list-capacity newCapacity; }为什么乘以2而不是乘以1.5或者加倍再加个常数这里有一个摊还分析的思想假设每次扩容成原来的2倍那么从容量1扩到n的过程中总共搬迁的元素次数约为1 2 4 ... n/2 n 2n - 1均摊到n次插入上每次插入的代价大约是O(1)。如果每次只加1那第k次插入时搬迁k个元素总代价就是12...n n(n1)/2均摊是O(n)。这就是倍增和增量在渐进复杂度上的本质差别。现实中不同语言的实现各有微妙差异。Java的ArrayList默认扩容策略是原容量的1.5倍Java的HashMap扩容是2倍Go语言slice在容量小于1024时翻倍超过1024后增长1.25倍。这些策略都是一个核心权衡翻倍越快搬运次数越少但内存浪费越多倍数越接近1内存越省但搬运越频繁。理解这个权衡面试时就能答出“为什么不是加1”这种问题了。另外有一个细节值得注意我上面用了两次malloc加free而不是C语言里的realloc。用realloc代码更短但它有个坑——如果扩容失败原来那块内存的指针会丢失而且行为在不同环境下有细微差别。对初学者来说先malloc新空间、手动拷贝、再free旧空间流程更透明更不容易写出内存泄漏。性能上虽然多了一次拷贝的余地但现代编译器的优化下这个差别微乎其微。等写熟了再去看realloc的语义也不迟。2.4 复杂度分析为什么“随机访问O(1)”而“插入删除O(n)”顺序表最核心的优势就是O(1)随机访问。假设data数组的首地址是base每个元素占L个字节那么第i个元素的地址就是base i * L。这是一个纯算术计算不需要遍历不管i是0还是999999耗时都一样。这就好比你在一个按门牌号编号的小区里找第58栋楼你不需要从1栋数过去直接按编号找就行。而插入操作就不同了。假设要在第pos个位置插入一个元素为了保证“逻辑相邻物理也相邻”从pos到size-1的所有元素都要往后挪一位。最坏情况是插在表头pos0所有n个元素都得移动最好情况是插在表尾一次都不移动平均情况是插在任意位置的概率相等平均移动n/2个元素所以时间复杂度O(n)。删除操作同理。删掉第pos个位置的元素之后pos后面的元素要往前挪。平均移动(n-1)/2个元素也是O(n)。初学的时候我总是纠结为什么不直接把新元素塞进去就行了后来才想明白顺序表的核心约束是“连续”——物理上不连续了就不能通过base i * L直接算出地址随机访问O(1)的优势也就没了。世间没有完美的数据结构顺序表用“插入删除慢”换来了“访问快”这就叫权衡。这个复杂度是要背下来的但更重要的是能自己推。面试的时候如果面试官问“ArrayList的get(index)为什么是O(1)”你能说出“因为数组是连续内存首地址加下标乘元素大小就能算出地址”这就够了。3. 实操过程与核心操作实现3.1 准备工作环境与代码规范实操之前先交代一下环境。我用的编译器是GCC标准C99以上都行建议开启-Wall -Wextra编译选项看警告。你可以用VS Code加C/C插件或者直接VS、CLion都行。我的建议是刚开始别用太智能的IDE因为它会自动修复很多问题你反而学不到排错的过程用命令行编译看着报错信息自己改印象才深刻。gcc -Wall -Wextra -o seqlist main.c运行测试时我会把顺序表的各种操作串在一个main函数里打印每次改动代码后重新编译运行观察size和capacity的变化确认逻辑正确后再继续下一步。3.2 完整可运行代码顺序表的C语言实现下面这个代码我尽量保持结构清晰每个函数只做一件事。你可以直接复制到一个main.c文件里编译运行对照上面的解释逐步验证。#include stdio.h #include stdlib.h #define INIT_CAPACITY 8 typedef struct { int *data; int size; int capacity; } SeqList; // 初始化 void init(SeqList *list) { list-data (int *)malloc(INIT_CAPACITY * sizeof(int)); if (list-data NULL) { exit(1); } list-size 0; list-capacity INIT_CAPACITY; } // 扩容容量翻倍 void ensureCapacity(SeqList *list) { if (list-size list-capacity) { return; } int newCapacity list-capacity * 2; int *newData (int *)malloc(newCapacity * sizeof(int)); if (newData NULL) { exit(1); } for (int i 0; i list-size; i) { newData[i] list-data[i]; } free(list-data); list-data newData; list-capacity newCapacity; } // 在指定位置 pos 插入元素 valpos 从 0 开始 void insert(SeqList *list, int pos, int val) { if (pos 0 || pos list-size) { printf(插入位置越界: pos%d, size%d\n, pos, list-size); return; } ensureCapacity(list); for (int i list-size; i pos; i--) { list-data[i] list-data[i - 1]; } list-data[pos] val; list-size; } // 尾插法在末尾添加元素 void pushBack(SeqList *list, int val) { insert(list, list-size, val); } // 删除指定位置 pos 的元素 void removeAt(SeqList *list, int pos) { if (pos 0 || pos list-size) { printf(删除位置越界: pos%d, size%d\n, pos, list-size); return; } for (int i pos; i list-size - 1; i) { list-data[i] list-data[i 1]; } list-size--; } // 按值查找返回第一个匹配的下标找不到返回 -1 int find(SeqList *list, int val) { for (int i 0; i list-size; i) { if (list-data[i] val) { return i; } } return -1; } // 按下标访问随机访问 int get(SeqList *list, int pos) { if (pos 0 || pos list-size) { printf(访问越界: pos%d, size%d\n, pos, list-size); exit(1); } return list-data[pos]; } // 打印当前顺序表内容 void printList(SeqList *list) { printf(size%d, capacity%d, data[, list-size, list-capacity); for (int i 0; i list-size; i) { printf(%d, list-data[i]); if (i list-size - 1) { printf(, ); } } printf(]\n); } // 释放内存 void destroy(SeqList *list) { free(list-data); list-data NULL; list-size 0; list-capacity 0; } int main() { SeqList list; init(list); // 尾插 1~10观察扩容 for (int i 1; i 10; i) { pushBack(list, i); } printList(list); // 在位置 2 插入 99 insert(list, 2, 99); printList(list); // 删除位置 0 的元素 removeAt(list, 0); printList(list); // 查找元素 5 int idx find(list, 5); printf(find(5) %d\n, idx); // 随机访问下标 3 printf(get(3) %d\n, get(list, 3)); destroy(list); return 0; }这个代码编译运行后的输出如下size10, capacity16, data[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] size11, capacity16, data[1, 2, 99, 3, 4, 5, 6, 7, 8, 9, 10] size10, capacity16, data[2, 99, 3, 4, 5, 6, 7, 8, 9, 10] find(5) 4 get(3) 4看到没有尾插到第9个元素时因为初始容量是8、不够了自动扩容成了16。这就是动态顺序表的核心价值——你不需要提前预估数据量它自己会长大。3.3 核心操作逐行拆解插入、删除与元素移动先重点看insert函数里的移动循环for (int i list-size; i pos; i--) { list-data[i] list-data[i - 1]; }这个循环是从后往前移动的这一点很关键。如果写成从前往后for (int i pos; i list-size; i) { list-data[i 1] list-data[i]; }就会发生数据覆盖——你先把data[pos]的值赋给了data[pos1]下一次循环又把data[pos1]此时已经是旧值赋给了data[pos2]最终所有元素都会变成原来的data[pos]。所以插入从后往前搬删除从前往后搬这是一个经典的原则一定要刻在脑子里。删除操作里的循环方向正好相反for (int i pos; i list-size - 1; i) { list-data[i] list-data[i 1]; }它是把后面的元素往前覆盖从头开始覆盖不会覆盖掉还没用到的数据所以方向是安全的。再看边界条件。insert允许的pos范围是0到size含size——因为size位置就是末尾相当于尾插。而removeAt允许的范围是0到size-1不含size——因为size下标本来就没有元素。这两个边界条件正好差一个是初学者最容易搞混的地方。我的记忆方法是插入是在某个位置放新元素可以有size个位置够放就是从0到size共size1个删除是去掉一个已有元素只有index 0到size-1这size个元素可以删。3.4 实验报告怎么写把代码变成可展示的成果很多学校要求写数据结构实验报告顺带提一嘴。实验报告的核心不是贴代码而是展示你的思考过程。建议按这个结构写实验目的不要只写“实现顺序表”最好写“掌握顺序表的顺序存储结构及插入、删除等基本操作的实现理解时间复杂度O(1)与O(n)的差异来源”。实验原理描述顺序表的存储结构画出示意图逻辑上连续、物理上也连续写下地址计算公式。实验步骤初始化→尾插n个元素→指定位置插入→删除→查找→销毁每一步给出关键代码和运行截图。实验结果与分析贴输出结果重点分析扩容前后capacity的变化、插入删除时元素移动的次数。总结与心得写你踩的坑比如为什么插入要从后往前移动、为什么漏了检查malloc就会段错误。老师们最反感的就是直接抄代码跑一遍就交。你只要在报告里写出“为什么这样设计”的思考分数都不会差。3.5 Java版本顺带看清楚ArrayList的底细考虑到热词里有人搜“java顺序表代码”这里也给出一个Java版的精简实现。Java不能直接操作内存但逻辑和C语言完全一致import java.util.Arrays; public class MyArrayList { private int[] data; private int size; private static final int DEFAULT_CAPACITY 8; public MyArrayList() { data new int[DEFAULT_CAPACITY]; size 0; } private void ensureCapacity() { if (size data.length) { return; } int newCapacity data.length * 2; data Arrays.copyOf(data, newCapacity); } public void add(int val) { ensureCapacity(); data[size] val; } public void add(int index, int val) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } ensureCapacity(); System.arraycopy(data, index, data, index 1, size - index); data[index] val; size; } public int remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } int oldValue data[index]; System.arraycopy(data, index 1, data, index, size - index - 1); size--; return oldValue; } public int get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } return data[index]; } public int size() { return size; } public void print() { System.out.println(size size , capacity data.length , data Arrays.toString(Arrays.copyOf(data, size))); } public static void main(String[] args) { MyArrayList list new MyArrayList(); for (int i 1; i 10; i) { list.add(i); } list.print(); list.add(2, 99); list.print(); list.remove(0); list.print(); } }Java版的System.arraycopy本质上还是那个移动循环只是底层用native方法帮你搬了。你去看ArrayList源码grow()方法里的扩容倍数、rangeCheck()里的越界检查本质上都和上面这几十行代码一一对应。自己写一遍再去看JDK源码会有豁然开朗的感觉。4. 常见问题与排查技巧实录4.1 段错误十个有八个是指针问题顺序表调试过程中段错误Segmentation Fault是最常见的崩溃方式。它通常不是你的逻辑错了而是访问了不该访问的内存。我总结了几类高频原因原因一忘记调用init函数就使用list.data。我在调试很多同学的代码时都发现他们声明了SeqList list;之后直接调用pushBack(list, 10)此时list.data是未初始化的野指针一访问就崩。解决办法使用顺序表前先想清楚list的生命周期先init再使用。原因二insert时越界写。比如size8、capacity8你没有调用ensureCapacity就直接执行list-data[8] val越界写入了数组边界之外。很多情况下程序不会立刻崩但内存已经被污染了等到某个时刻才以莫名其妙的方式炸出来。这种问题最难调因为崩溃点和错误点往往不在同一个地方。解决办法插入前一定要确保sizecapacity也就是调用ensureCapacity同时insert函数里的越界检查不能省。原因三传参忘记取地址。写了init(list)而忘了写init(list)。C语言里结构体作为参数传递时函数内部是原结构体的副本你初始化了一个副本原来的list还是野的。这个问题可以通过给init函数加一个断言assert(list-data ! NULL)来发现。调试段错误的首选工具是GDB。编译时加-g选项运行gdb ./a.out崩溃后输入btbacktrace就能看到崩溃点所在的函数调用栈。这个方法效果立竿见影。gcc -g -Wall -Wextra -o seqlist main.c gdb ./seqlist (gdb) run (gdb) bt4.2 扩容后指针悬空与内存泄漏扩容代码里有一个非常隐蔽的坑如果你不使用临时变量而是直接写list-data (int *)realloc(list-data, newCapacity * sizeof(int));当realloc失败时它会返回NULL但原来那块内存并没有被释放而你已经把list-data覆盖成NULL了。这就造成了两个问题一是原数据丢失二是原内存泄漏而且你再也找不到它了。我自己的习惯是永远不要直接把realloc的结果赋给原指针而是用一个临时变量接收判断非NULL之后再赋值。另外C语言不像Java有垃圾回收free必须手动配对。很多初学者做完实验后从来没有free过程序跑完就退了短期内看起来没毛病但在长期运行的服务器环境下内存泄漏会导致内存越用越多最后进程被系统杀掉。我的建议是每次写完一个结构体都要写一个destroy函数和init成对出现。init分配了内存destroy负责释放这个习惯带到链表、栈、图的所有实现里去能少掉很多头发。4.3 边界条件测试清单用一个表搞定防翻车很多人的代码在正常用例下跑得好好的一到考试、面试的手写题就翻车问题出在只测了“正常情况”没测“极端情况”。我习惯在写完代码后用下面这个测试清单挨个过一遍测试场景操作期望结果实际风险点空表删除位置0不崩、报越界未检查pos size空表查找任意值返回-1循环体没执行、返回正确空表访问位置0报越界退出未检查pos范围插入pos0头插所有元素后移一位循环方向写反插入possize尾插元素直接追加移动0次循环条件写错删除最后一个元素删除possize-1移动0次size减1删除后size变小容量满时插入连续插入超过capacity个元素自动扩容不丢数据漏调ensureCapacity连续多次扩容插入1000个元素每次扩容翻倍数据完整内存泄漏或指针悬空这个清单看似简单但对刚学的人特别管用。我在自己学习的过程中最常犯的一个错误就是写完代码觉得“逻辑没问题”就交差了结果一测试头插、尾插、空表边界全都有问题。把这些边界条件当成测试用例写下来实际上就是一个最朴素的单元测试思想哪怕没有测试框架也能帮你少走很多弯路。4.4 考研与面试常见追问学完顺手就能答顺序表在很多学校的期末考试、考研初试、面试里都是最基础的热身题。这里把高频追问整理一下你如果都能不看答案说出来说明这块真的掌握了。顺序表和链表的区别是什么核心是三个维度存储空间上顺序表需要连续内存且预先分配动态的也不需要一次性给足但物理上始终连续链表不需要连续时间性能上顺序表访问O(1)、插入删除O(n)主要花在移动元素上链表访问O(n)、插入删除如果是已知位置则是O(1)主要花在查找前驱上空间上顺序表有扩容浪费和空闲浪费链表有指针域开销。顺序表的插入、删除平均时间复杂度为什么是O(n)要能推出平均移动n/2个元素的过程。扩容为什么是倍增而不是加常数从均摊分析的角度说明。顺序表在什么场景下比链表更合适读多写少、需要频繁随机访问、数据规模可控的场景比如存储静态配置、排行榜快照、按索引访问的数据集合。手写一个顺序表插入函数要求自带越界检查和扩容。这要求你上面代码真的自己练过不要只是看过。很多人在面试时栽在“太紧张手抖写不出代码”上。我的建议是顺序表这五个函数init、insert、removeAt、find、destroy真的能手写出来不看任何参考。手写顺序表就相当于武术里的扎马步马步扎不稳后面的东西都是空中楼阁。等你做到这一点再看栈、队列会发现它们的代码你也能顺手写出来因为这个基础已经打牢了。写在最后的几个小建议顺序表这个东西说实话看着真的简单一个数组加几个循环而已。但正是因为它简单很多人轻视它光看代码觉得自己懂了一合上书啥也写不出来。我个人这几年的体会是学数据结构最忌讳的就是“看懂了”一定要“写出来”。你会发现看懂别人写的插入函数只需要三分钟自己关掉参考从零敲出来可能要三十分钟但这三十分钟里想明白的问题——为什么循环从后往前、为什么边界条件是pos size、为什么size和capacity要分开——才是你真正学到的东西。另外一个实用的小技巧是先把图给画出来。插入一个元素之前把数组在纸上画成一个个格子然后用箭头标出每个元素要搬去的地方。凡是图画明白了代码基本就是照着图填循环而已。我教过不少零基础的朋友他们觉得顺序表难难的不是代码是脑子里没有一个具体的画面。一旦有了画面一切都很自然。顺序表撑起了后面一整个知识链条。你去学栈那是“限制了一端操作的线性表”学队列那是“一端进另一端出的线性表”学字符串那是“元素类型为字符的顺序表”学矩阵压缩存储那是“二维数组映射到一维的顺序存储”。把今天这个基础打牢接下来那些看起来很高深的概念你会突然发现原来都是老朋友换了个马甲。这篇就写到这里。如果你照着代码敲了一遍建议你再做一个小实验记录插入10000个元素时扩容发生了多少次、每次容量怎么变化亲眼看一下倍增策略有多省事。这个实验做完你对顺序表的理解会比看十遍博客都深。