很多人学顺序表第一天对着结构定义、初始化、插入、删除一顿操作跑通了输出就觉得自己已经拿下了。但真正到了第二天开始做动态扩容、碰边界条件的时候才发现代码怎么改怎么崩。我自己当年顺序表学习计划做到day2也是被一个扩容后的指针失效问题按在地上摩擦了整整一个晚上。今天这篇就把第二天的学习路径掰开揉碎围绕“动态”和“边界”这两个词展开什么时候扩容、扩多少、插入删除的合法区间怎么判断、查找排序怎么把顺序表的优势用到位以及最后一个能检验学习成果的自查清单。适合正在跟着学习计划走的人也适合那些第一天过了、第二天卡住想回头补基础的人。1. 为什么第二天的主题是“动态”和“边界”1.1 day1结束时的状态以及day2接力的地方第一天通常做的是静态版本的顺序表预先开一个足够大的数组比如int data[100]然后写结构体、初始化、插入、删除、遍历打印。只要不超出100个元素代码基本是稳的。很多人到这里会误以为“顺序表不过如此”于是第二天直接跳到链表、栈、队列结果回头刷题或者做项目的时候遇到需要动态增长的数据集合又开始抓瞎。Day2要解决的核心问题就是让顺序表真正具备“动态”能力当元素个数超出当前容量时自动申请更大的内存把老数据搬过去然后继续工作。另一个隐藏主题是“边界”问题插入位置能不能等于size、删除为空表时怎么办、满表插入时先扩容还是先判断、扩容失败怎么处理。这些在静态数组版本里完全不会暴露但一上动态版本全部变成最容易踩的坑。1.2 从“固定数组”到“动态数组”的思维切换我觉得day2最需要切换的思维是从“用数组实现功能”变成“管理一块内存”。固定数组的写法里你只需要关心业务逻辑动态顺序表里你还得关心三件事当前有多少元素size、当前最多能放多少元素capacity、底层那块内存的地址什么时候会变。这三者的关系可以用一个生活化的类比来理解容量是你的行李箱大小size是箱子里已经装的衣服数量。衣服超过箱子容量时你不能硬塞得换一个大箱子然后把原来的衣服一件不落搬进去。换箱子这件事在代码里就是一次内存重新分配。很多bug就出在“旧地址已经失效了但代码还在用旧地址访问数据”这一步。2. 动态扩容的完整实现策略、参数与指针陷阱2.1 扩容的触发条件为什么不能等越界才处理顺序表插入元素的常规步骤是先判断下标合法性再判断容量是否足够最后移动元素并放入新值。扩容触发点应该放在“插入前检查capacity”这一步而不是等数组越界崩了再去补救。判断条件通常是if (list-size list-capacity)。很多人会问为什么用size capacity而不是size capacity从逻辑上说只要size达到capacity说明下一个元素放不进去了已经等价于“满了”。但日常写代码习惯用更保险因为在某些异常逻辑下size理论上是不会超过capacity的一旦出现就说明程序已经有问题你还让它继续跑风险更大。我个人建议正常逻辑用但加一个断言或者错误提示防止size异常大于capacity。扩容触发之后核心是调用一个专门函数比如expandCapacity它负责申请新内存、拷贝老数据、释放旧内存、更新capacity和data指针。2.2 扩多少合适从摊还分析看2倍扩容为什么主流这是day2里最值得停下来想5分钟的问题。扩多少直接决定程序的时间性能和空间浪费。假设每次扩容只多申请1个元素的位置那么插入第n个元素时需要搬移的次数是123...整体复杂度变成O(n^2)完全不可接受。如果每次固定增加100个位置那么扩容次数大约n/100每次搬移平均100个元素复杂度O(n)看起来不错但问题是你永远不知道自己未来会增长到多少固定增量选大了浪费内存选小了扩容次数还是偏多。比较经典的做法是每次扩容到原来的2倍也就是newCapacity oldCapacity * 2。为什么2倍最优可以从摊还分析的角度粗略理解假设初始容量是1每次翻倍那么插入n个元素的过程中各次扩容产生的搬移总次数大约为 1248...n ≈ 2n分摊到n次插入里每次插入的平均额外代价是常数。这意味着虽然单次扩容可能很慢搬运全部老数据但整体均摊下来插入操作依然是O(1)级别的代价和静态数组的插入体验非常接近。实际工程里有些库会选1.5倍而不是2倍。原因在于2倍扩容导致的内存峰值更糟糕扩容瞬间旧内存和新内存同时存在相当于瞬间需要3倍于旧容量的内存。1.5倍虽然扩容次数多一些但内存峰值相对平缓。对初学者来说先理解2倍的摊还逻辑再了解1.5倍的工程取舍就足够了。这里给一个顺序表结构定义和扩容函数示例采用最通用的C语言写法typedef struct { int *data; // 指向底层数组 int size; // 当前元素个数 int capacity; // 当前容量 } SeqList; int expandCapacity(SeqList *list) { int newCapacity list-capacity * 2; int *newData (int *)malloc(sizeof(int) * newCapacity); if (newData NULL) { return 0; // 扩容失败返回错误标识 } for (int i 0; i list-size; i) { newData[i] list-data[i]; } free(list-data); list-data newData; list-capacity newCapacity; return 1; }注意这里的malloc 循环拷贝 free是最直白的实现新手强烈建议先按这个思路写不要一上来就碰realloc。用realloc可以少写两行代码但它引入了一个非常隐蔽的行为如果扩容时内存原地扩展成功返回的指针和原来一样如果原地没有足够空间它会另找一块地方并自动拷贝然后释放旧内存。这两种情况对调用者来说结果都是一样的但会让“原指针是否有效”这个问题更难感知。等你把malloc版本写熟了再去换realloc心里才踏实。2.3 扩容失败与指针失效最隐蔽的两个坑扩容完成后第一件事是free旧内存但必须确保你已经把所有需要的数据都搬走了而且没有其他地方残留指向旧内存的指针。比如你在别的函数里保存了int *p list-data扩容之后p指向的旧内存已经被释放你再通过p读数据就是典型的悬垂指针轻则读到垃圾数据重则程序直接崩。另一个坑是扩容失败。实际项目中内存申请不一定成功尤其是大容量扩容时。malloc返回NULL如果你没有判断就直接往下执行写入操作等于往空地址写数据段错误跑不掉。我见过不少人刚开始写动态顺序表根本不检查malloc返回值在刷题平台上一直“运行时错误”查了半天才发现是扩容过程没做失败处理。正确的写法是扩容函数返回错误标识插入函数收到失败标识后直接返回失败不再继续执行。3. 插入与删除的边界场景真正容易写错的地方3.1 插入位置的合法区间0到size而不是0到size-1顺序表插入操作的合法下标区间是[0, size]很多人会用pos 0 || pos size来校验这就漏掉了“尾插”这个最常用的场景。所谓尾插就是新元素放到表的最后面下标等于size这时不需要移动任何已有元素只要把新值写到data[size]然后size自增。完整判断应该是pos 0 || pos size视为非法。这里有个小细节size是底层数组的已用长度但底层数组容量可能远大于size所以判断合法的pos范围用的是size不是capacity。插入的核心动作是从最后一个元素开始逐个往后移动一位直到下标pos的位置空出来。方向必须是从后往前移动因为如果你从前往后移第一个元素就会覆盖第二个整段数据就串了。给个直观例子表里有[1,2,3]要在下标1插入9正确做法是把data[2]移到data[3]再把data[1]移到data[2]最后data[1]9。如果反过来先把data[1]移到data[2]data[2]原来的值3就被覆盖了后续再移就全错。3.2 删除时的元素移动从前往后覆盖删除操作和插入正好相反是从pos位置的下一个元素开始从前往后逐个覆盖前一个位置。也就是data[i] data[i1]一直覆盖到size-2的位置最后size减1。为什么不能从后往前因为删除是覆盖语义。比如表里有[1,9,3]要删除下标1的9只需要把data[2]3覆盖到data[1]得到[1,3]如果从后往前移动你会先把data[2]存到某个临时变量然后data[1]data[2]其实也是可行的。但常规写法里大家约定从前往后覆盖复杂度O(n)不会出错就够了。删除前一定要判断表是否为空。空表删除pos范围本身就已经非法了但很多初学代码在list-size 0的时候还继续走data[pos]操作直接访问不存在的元素结果未知。稳妥写法是先判空再判pos是否在[0, size-1]。3.3 典型边界场景速查表下面这个表格是我带过的人里最容易出错的边界场景建议直接保存对照场景正确的预期行为新手常见错误空表插入pos0成功size变为1忘记检查capacity直接写入满表插入先扩容再插入不知道扩容数组越界尾插possize直接写入data[size]size自增误判为非法下标头插pos0全部元素后移一位O(n)从前往后移数据被覆盖空表删除返回失败/错误继续访问data[0]删除最后一个元素possize-1直接size减1不需要移动多执行一次循环赋值3.4 一个隐藏边界删除全部元素后再次插入删除到size0之后顺序表不能继续访问data[0]但底层的capacity并没有变也就是说内存空间还在只是逻辑上为空。这时候如果再插入不需要扩容直接用原来的data指针和capacity即可。这个边界很值得自己动手测一次因为它能帮你理解size和capacity的独立性。容量是“物理内存”概念size是“逻辑元素”概念两者可以相差很大。一个空表capacity可能是64size是0这完全正常。理解了这一点后面学动态字符串、动态数组、各类容器才不会晕。4. 查找与排序把随机访问的优势用透4.1 按值查找顺序扫描的复杂度为什么是O(n)顺序表的按值查找就是从头到尾遍历一遍比较每个元素是否等于目标值找到返回下标找不到返回-1。它的时间复杂度是O(n)这个没有悬念。但很多人忽略了另一个问题如果表中存在多个相同值你返回哪个下标这取决于需求。如果返回第一个匹配项遍历到就return如果返回最后一个匹配项需要遍历完整张表如果需要返回所有匹配项的下标集合就得用一个额外的数组收集。学习计划day2里我建议至少把“返回第一个匹配项”和“统计匹配项个数”都写一遍后者能顺便复习一下遍历逻辑。顺序查找有一个算不上优化的点但对初学者的代码质量影响很大提前计算出边界条件避免条件表达式里每次取size。比如常规写法for (int i 0; i list-size; i) { if (list-data[i] target) { return i; } } return -1;这个写法足够清晰不推荐为了省一次比较而引入哨兵位方案。顺序表上做哨兵优化只有在极端追求性能的库代码里才有意义学习阶段把逻辑写对最重要。4.2 排序之后查找效率为什么质变顺序表支持随机访问这是什么概念你可以在O(1)时间内直接定位到任意下标。这个特性一旦配合“有序”前提查找效率就直接从O(n)降到O(logn)。最常见的就是二分查找每次取中间下标比较中间值和目标把搜索区间砍半。二分查找的前提是表已经有序而且能随机访问。顺序表天然支持随机访问所以它是实现二分的绝佳载体。很多人在day2阶段会尝试写一个二分查找但写出来总是死循环或者漏边界。这里有两个必须注意的细节一是区间定义闭区间[left, right]的写法是while (left right)左闭右开[left, right)的写法是while (left right)二是中间下标计算推荐写mid left (right - left) / 2避免(left right) / 2在极端大数下溢出。我建议day2先别贪多把非递归的闭区间二分写通就行。递归版本、左闭右开版本可以放到后面复习时再换着写免得第一天半天全耗在一个小函数上。4.3 强化排序为什么说插入排序是顺序表的“老朋友”排序算法在day2的学习计划里不必全面铺开但有一个算法强烈建议亲手写一遍直接插入排序。原因有二。第一顺序表插入元素的底层逻辑你已经掌握了插入排序正是反复利用“把一个元素插入有序区间”这个操作两者能形成知识闭环。第二插入排序在基本有序的数据上表现极好后续学更高级的排序时很多东西都能从它的思路里长出来。直接插入排序的核心从下标1开始把当前元素从后往前扫描如果前一个元素比它大就把前一个元素往后挪一位直到找到合适位置插入当前元素。注意看这个“后挪一位”的动作和你第三节学的插入操作完全一致。这就是day2的设计巧妙之处每一块内容都不是孤立的。如果顺序表已经有序而你需要保持它有序插入新元素时就不必先push再排序可以直接用上一节学的插入逻辑找到第一个大于新值的位置然后插入。这是顺序表非常典型的应用场景值得单独练5分钟。5. 内存布局与性能顺序表快在哪以及它埋的坑5.1 连续内存与CPU缓存命中为什么顺序遍历那么快顺序表底层是一块连续的内存这意味着遍历时CPU按顺序读取内存地址能最大化利用缓存。现代CPU读取内存不是逐个字节读的而是按“缓存行”一次性加载一小块连续数据。顺序表遍历时下一个元素大概率就在当前缓存行里不用重新访问内存。这也是为什么同样的遍历操作顺序表通常比链表快很多的原因之一链表节点分散在不同内存地址每访问一个节点都可能发生缓存未命中。实际感受一下一个存了100万个int的顺序表顺序遍历所有元素耗时通常远低于遍历同样逻辑的链表。这个差距在很多刷题平台上不明显因为数据量太小但到了大数据处理、实时系统里缓存命中率直接决定性能上限。5.2 扩容峰值问题为什么1.5倍扩容也有存在价值前面提过2倍扩容的均摊代价是O(1)但它有个隐性代价扩容瞬间需要同时持有旧内存和新内存。假设容量从64扩到128旧内存64个int大约是256字节新内存512字节瞬间占用768字节看起来不多。但如果你有一个容量1000万的顺序表扩容到2倍时瞬间需要旧内存40MB加新内存80MB一共120MB。如果系统内存刚好紧张扩容就会失败。这也是为什么一些注重内存的系统倾向采用1.5倍扩容甚至缩容策略当size远小于capacity时比如只有容量的四分之一可以考虑把容量缩小一半释放多余内存。缩容逻辑和扩容对称但需要注意缩容同样有“旧数据搬移”的成本不能频繁触发。对day2的学习来说理解内存峰值问题就够了。以后你看一些容器的源码会发现扩容因子未必是整数那些设计背后都是在平衡“扩容次数”和“内存浪费”两个指标。5.3 和链表对比时别只盯着时间复杂度表很多资料喜欢给一张顺序表和链表的复杂度对比表插入删除链表O(1)顺序表O(n)随机访问顺序表O(1)链表O(n)。但实际工程里结论没这么简单。链表那个O(1)插入前提是你已经持有目标位置的节点指针如果要从头找位置依然是O(n)。顺序表插入虽然是O(n)但它移动的只是一段连续内存里的元素在现代CPU上这种移动成本往往很低尤其是元素类型简单、数据量不大时。所以day2阶段不必急着给“哪个更好”下结论。你需要建立的认识是顺序表的优势在随机访问、缓存友好、内存密度高劣势在中间插入删除需要搬元素、扩容有内存峰值链表的优势在中间插入删除不需要搬元素劣势在缓存不友好、每个节点有额外指针开销。选择哪种结构永远取决于具体场景。6. 第二天验收三道综合题和一个自查清单6.1 综合练习一合并两个有序顺序表写一个函数输入两个已经升序排列的顺序表返回一个新的顺序表合并后仍然升序。这个练习考察的是顺序表遍历、尾部插入、容量判断、动态扩容以及双指针归并的思想。实现时两个表各用一个下标从0开始比较当前元素谁小先放进新表然后移动对应的下标。一旦其中一个表遍历完把另一个表的剩余元素全部追加到新表尾部。这个过程中很容易出现“新表容量不够”的情况这时候就用到你第二节学的扩容函数了。一个隐藏的考察点如果两个表原本是直接拼接合并不要求有序那么直接先拷贝第一个表再拷贝第二个表复杂度O(nm)且不需要额外判断但有序合并就需要归并复杂度同样是O(nm)但逻辑复杂一些。两种写法的差异恰好反映“相同复杂度下常数因子和代码思维的不同”。6.2 综合练习二一趟删除所有值为x的元素给定一个顺序表和值x删除表中所有等于x的元素要求一趟遍历完成且不能每次删除都整体搬移。这个题是经典的“双指针”应用用两个下标一个负责扫描read一个负责写入位置write。当read遇到不等于x的元素时把它写到write位置然后write自增read无论如何都自增。扫描结束后size更新为write的值即可。这个练习的价值在于让你突破“删除必须移除元素”的思维定式体会到顺序表删除的本质其实是“覆盖无效元素”未必需要逐次搬移。很多人用常规的for循环删除删除一次后面的元素前移一次时间复杂度O(n^2)数据量一大就超时。如果你在day2就掌握了双指针覆盖技巧后面刷数组去重、移除元素这类算法题会非常顺畅。6.3 自查清单学完day2应该能秒答的问题学习计划不能只靠“写完代码就完事”建议最后对照下面这份清单检查一遍能不看资料答出来才说明真的过关了顺序表中size和capacity的区别是什么容量满了之后插入会发生什么扩容为什么大多选择2倍均摊时间复杂度为什么是O(1)插入元素的合法下标范围是多少为什么能把元素插到size位置删除最后一个元素时需要移动其他元素吗为什么尾部插入很快头部插入和中间插入很慢顺序表查找某个值的复杂度是多少有序之后用二分查找复杂度是多少扩容之后原来保存的data指针还能继续使用吗为什么连续内存对顺序表遍历性能有什么影响合并两个有序顺序表的核心思想是什么如果这些问题里有一半需要想很久建议带着疑问把对应的章节再过一遍而不是急着往前赶。顺序表本身就是后续很多数据结构的地基day2把动态和边界吃透后面无论是学链表、栈、队列还是跳表都会顺畅很多。我在实际带学习计划的过程里发现顺序表day2这一天的真正收获不在于你把扩容代码背下来了而在于你心里建立起了一张“内存布局图”清楚底层的数组在哪里、size和capacity各自管什么、什么时候数据要搬移、什么时候指针会失效。这张图一旦建立起来后面遇到任何基于数组的容器你都能用同一套思维去拆解。最后再分享一个小技巧写动态顺序表的时候可以在关键操作里临时打印size、capacity和data的地址亲眼看着它们在扩容前后的变化比看十遍理论都管用。