顺序表这个名字听起来确实不玄乎但真到面试手撕、期末上机或者备战考研时很多人反而就是在这种最基础的东西上翻车。数据结构这门课里线性结构开篇要解决的就是顺序表你天天用的Java ArrayList、C语言里自己malloc出来的连续内存块本质都是它的变体。这篇文章不想按教材的口吻从头念一遍我想用实际操作时候的思路来讲它到底解决什么问题、核心操作是怎么设计出来的、手写代码时哪里容易踩坑以及考试和面试里最常见的考法在哪。无论你是刚开始学数据结构的新手还是正在绞尽脑汁记复杂度公式的考生这篇文章应该都能给你一些直接能拿去用的东西。1. 先搞清楚顺序表在数据结构里站在什么位置先把结论拍在桌面上顺序表是一种“逻辑上线性、物理上也线性连续”的存储结构。逻辑线性很好理解就是数据一个挨一个像排队买奶茶物理连续就重要了意思是这些元素在内存里真的是放在一整块连续的空间里而不是像链表那样东一个西一个散落着。这个“连续”两个字既是顺序表最大的优势也是它所有设计矛盾和性能瓶颈的来源。我见过不少初学者学完数组就直接跳过顺序表觉得这有什么好学的不就是数组套一个壳吗话不能这么说。数组是最基础的内存抽象而顺序表是在数组之上封装了动态扩容、按位置插入、按值查找、删除后保持紧凑等一套完整逻辑的容器。你去看Java里ArrayList的源码去看C里vector的实现看底层就是顺序表这套玩法。搞清楚顺序表其实是在帮你理解所有现代动态数组类容器共同的底层设计逻辑这个价值远不是“会写个增删改查”这么简单。1.1 顺序表的存储模型和一个生活化类比在真实内存里顺序表对应的就是一块连续地址空间。假设每个元素占4个字节第一个元素地址是1000第二个就是1004第三个是1008。所以按下标访问时地址计算公式基本就是base index * elementSize一步乘法加法直接定位不需要遍历。这就是为什么说顺序表随机访问的时间复杂度是O(1)。用一个更贴近日常的类比顺序表像电影院里固定连排的座位每个人在进场前就分配好了座位号你想找第13排第5座的人跟着号码走过去就行不需要从第一排挨个问。而链表更像我手里拿了一叠线索卡片每张卡片上写着“下一个人的位置在哪儿”想要找到某个人就得一张一张翻。这个差异就是顺序表与链表最核心的分水岭读得快但插入和删除时需要给后面所有的人腾位置或补空缺。正因如此设计一个顺序表时你始终在做两个互相拉扯的取舍。如果预留大量空闲空间插入时移动元素的压力小了但内存浪费严重如果每个位置都精打细算内存是省了可每次插入都要搬动一堆数据。所有的扩容策略、缩容阈值、插入位置选择本质上都是在这个矛盾里找平衡点。1.2 顺序表和其他存储结构的横向对比学习数据结构时最忌讳“就事论事”学顺序表就把顺序表背下来学链表又把链表单独背一遍两套知识在脑子里完全割裂。所以我建议一开始就做一个横向表把顺序表和同一家族里的其他线性存储结构放在一块看对比维度顺序表单链表双向链表存储方式一块连续内存每个节点分散存储每个节点两个指针结构更重按下标访问O(1)直接算地址O(n)必须从头走O(n)但可双向走插入/删除头部O(n)所有元素后移O(1)改指针即可O(1)改两个方向指针插入/删除尾部位置已知O(1)尾部直接添O(n)必须先找到尾节点O(1)有尾指针时额外内存开销极小只有数组空间每个节点多一个指针每个节点多两个指针缓存友好性高连续内存读完一片低可能频繁跳到随机地址更低指针跳跃更多这张表不是让你背的是让你在真正做设计时快速权衡一个场景如果以“按下标取值”为主比如排行榜、缓存队列的快照那顺序表就是最合适的选择如果业务里大量操作是“在中间频繁插入”比如编辑器的撤销历史那链表反而更有优势。顺序表真正强大和真正薄弱的点都在表里一目了然。2. 顺序表的核心操作是怎么设计出来的顺序表的核心操作翻来覆去就是五个初始化、插入、删除、按位查找、按值查找。单拿出来看都很简单但设计这些操作时每一个细节都在处理同一个问题如何维护“元素搬迁”的正确性。很多教材都会直接给出伪代码看起来很短但伪代码跳过了大量边界条件。真正动手实现时你要回答的问题远不止“写个for循环”那么简单插入时循环到底从哪边开始删除后数组末尾要做什么扩容容量怎么算越界条件怎么判断这一节我把每个核心操作背后的设计意图拆开讲顺带把容易翻车的细节点明。2.1 插入操作位置合法性和移位方向是两座大山插入操作有个关键前置逻辑插入位置合法范围是0到当前长度也就是说可以在末尾追加也可以在头部塞入。如果位置是负数或者比长度还大就必须抛越界异常。这个判断看起来多余但真到写代码时最容易漏尤其是在Java这种有异常机制的代码里漏掉越界检查后续会打出很难查的ArrayIndexOutOfBoundsException。确定位置合法之后核心就是移位的“方向”。在顺序表里插入一个元素到下标index时下标index以及它之后的所有元素都要往右挪一格而且这个挪动必须从最后一个元素先开始倒着往前挪。举个例子当前数组是[1,5,6,9]要在下标1的位置插入99。正确做法是先把下标3的9挪到下标4再把下标2的6挪到下标3再把下标1的5挪到下标2最后把99放到下标1。为什么必须倒着来因为如果你先把下标1的5挪到下标2那下标2原来的6就被覆盖了后面的数据直接烂掉。这个方向搞反了甚至不需要等程序跑完人就已经能看出结果不对。正因为要搬动“后面所有元素”插入的平均时间复杂度是O(n)。注意我说的是平均因为如果每次都插在末尾那只需要一步操作只有插在中间和头部时才需要大面积搬运。所以很多人在数据结构课程里纠结“插入到底是O(1)还是O(n)”真相是插入本身定位是O(1)但腾位置这个动作是O(n)整体取最坏情形就是O(n)。还有一个经常被忽略的点是内存空间不足时插入前必须扩容。这里就引出了一个设计选择——每次插入前都检查“有没有空位”只是最基础的更好的做法是预判增长策略把扩容的代价均摊到多次插入里。这也是为什么动态数组类容器扩容时不只扩一个位置而是整体翻倍或1.5倍扩我后面会专门讲。2.2 删除操作和查找操作复杂度背后的真实代价删除逻辑和插入是对称的但有一个容易踩的坑。删除下标index的元素时需要把index后面的所有元素整体往左挪一位这次必须正着来从index1开始把每个元素复制到它前一个位置。方向反了也不行因为你把index2复制到index1后再想复制index1的原始值到index时那个值早就被覆盖了。删除操作的时间复杂度同样是O(n)。这一点很多教材讲得太含糊导致期末考试或者面试问“顺序表删除中间元素的复杂度”时有人答O(1)、有人答O(n)其实都不算完全错但你必须能说清楚如果只讨论“把某个位置标记为无效”那确实是O(1)但顺序表的定义要求“删除后仍然保持紧密排列、不能留空洞”所以必须把后续元素整体搬过来这个搬运动作就是O(n)。按位查找就简单得多知道下标直接算地址拿值O(1)这跟随机访问一个道理。按值查找则要遍历整个数组平均比较n/2次所以是O(n)。这个对比非常有意思顺序表牺牲了插入删除的灵活性换来了“按位直达”的高效。如果业务场景是“知道位置就取值”顺序表收益很大如果是“知道值但不知道位置”那它和链表一样要遍历优势不明显。值得多说一句的是按值查找在Java里默认用equals比较不能用去比较引用类型。这个细节在源码里体现得很清楚如果查null就走了独立的null处理分支查非null用equals逐项比。很多自己手写顺序表的同学在比较整数或者字符串时用了局部测起来好像没问题一旦存的是自定义对象立刻全军覆没。遇到这种问题先别怀疑算法先检查你用的是equals还是。3. 手撕一个动态顺序表Java实现细节数据结构考试里顺序表手写实现几乎是必考题但真正有价值的并不只是“把功能跑通”而是代码结构合理、边界清晰、扩展性够用。我自己比较推荐用Java语言来练习实现顺序表原因是Java有成熟的泛型机制、数组拷贝工具和异常体系代码写出来更贴近真实开发里的容器实现。下面这套实现我按“基础功能完整 扩展机制简洁 边界处理严格”这三个原则来写。它不是那种为了应付上机课拼命精简的玩具代码而是你做完之后可以对照源码看懂ArrayList底层逻辑的版本。3.1 类骨架泛型数组、容量初始化和size变量先看核心骨架public class SeqListT { // 真正的数据存储在Object数组里 private Object[] data; // 当前实际存了多少个元素不是数组的长度 private int size; public SeqList() { this(10); } public SeqList(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(容量不能为负数: initialCapacity); } data new Object[initialCapacity]; size 0; } }这里有个很重要的设计原则size和数组长度是两个完全不同的概念。数组长度是容量capacity表示当前最多能放多少元素size是真实元素个数表示现在存了多少。很多新手写顺序表把这两个混淆扩容判断和返回值都会出bug。泛型方面Java的泛型在运行时会被擦除所以不能直接new T[10]只能先创建Object数组再强制转型。这也是为什么源码里到处能看到(T) data[i]这样的强转。你不需要在这点上纠结知道这是Java泛型擦除的代价就行。如果你用C语言练习思路完全一致只是把Object换成了结构体的指针或者直接用void*数组逻辑相通。还有一个小点构造函数里负数容量要主动抛异常。这个判断看起来是小题大做却能逼着使用方在逻辑层面提前暴露错误而不是等到数组创建的时候报个奇怪的负数异常。真实开发里这种早期失败比后期兜底有价值得多。3.2 增删改查完整实现与关键细节接着看核心操作实现。我特意把System.arraycopy和手动循环两种方式都讲一下。System.arraycopy是JVM提供的高效数组复制方法但在数据结构练习里不少人看不懂它的参数容易用错。public void add(T value) { ensureCapacity(); data[size] value; size; } public void insert(int index, T value) { if (index 0 || index size) { throw new IndexOutOfBoundsException(插入位置越界: index); } ensureCapacity(); // 将 index 及其之后的所有元素整体右移一格 System.arraycopy(data, index, data, index 1, size - index); data[index] value; size; } public T remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(删除位置越界: index); } T oldValue (T) data[index]; int numMoved size - index - 1; if (numMoved 0) { System.arraycopy(data, index 1, data, index, numMoved); } data[size - 1] null; size--; return oldValue; } public T get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(下标越界: index); } return (T) data[index]; } public int indexOf(T target) { if (target null) { for (int i 0; i size; i) { if (data[i] null) { return i; } } } else { for (int i 0; i size; i) { if (target.equals(data[i])) { return i; } } } return -1; }有几个细节值得多说两句。第一插入时System.arraycopy(data, index, data, index 1, size - index)这个写法意思是“把从index开始、长度为size-index的元素整体挪到index1开始的地方”。因为源数组和目标数组是同一个Java底层会用临时变量处理重叠复制所以你不用担心覆盖问题。第二删除后我把最后一个位置data[size-1]置为null。这一步在泛型代码里很重要因为数组中还留着一个指向原对象的引用如果不清空这个对象就永远不会被垃圾回收这就是所谓“内存泄漏”。很多手写版本不做这一步能跑但不好我在实际开发里养成习惯用不上的引用尽量及时切断。第三indexOf里为什么单独处理null因为调用target.equals(data[i])时如果target是null直接空指针异常。要么反过来写data[i] ! null data[i].equals(target)要么像上面一样给null单独开一条循环。在ArrayList源码里也是类似做法这不是炫技是必须处理的边界。3.3 扩容机制什么时候扩容为什么不是固定加1上面的ensureCapacity()还需要单独实现这正是顺序表从“静态数组”进化成“动态容器”的关键一步private void ensureCapacity() { if (size data.length) { int oldCapacity data.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity - oldCapacity 0) { newCapacity 10; } data Arrays.copyOf(data, newCapacity); } }这段代码的意思是当当前元素个数已经达到数组容量时新容量按1.5倍扩张然后调用Arrays.copyOf把旧数组内容复制进新数组。为什么不是每次只加一个位置因为如果每次只加1个连续插入n个元素就会触发n次扩容每次扩容都要复制已有全部元素总代价是123...n也就是O(n²)这会直接把性能拖垮。采用倍数扩容后虽然单次扩容的成本仍然是O(n)但“均摊”到多次插入上每次插入的平均复杂度可以近似认为是O(1)。这个均摊分析在面试里经常被追问核心论点就是扩容次数只有O(logn)复制操作的总量是O(n)均摊到n次插入就是O(1)。这个思想不只顺序表用很多动态数据结构都遵循同样的逻辑。4. 扩容机制与缩容边界容量变化是顺序表最容易翻车的点说扩容是顺序表最容易翻车的地方毫不夸张。因为顺序表的基础操作无非就是数组移动只要逻辑清晰就很好写但容量怎么涨、什么时候缩、缩多少这里面藏着大量性能陷阱和工程取舍。很多教材为了省事把顺序表设计成“一次性申请一个最大容量”比如数组大小固定为100满了就报错。这样写确实简单但它没有实现真正意义上的动态管理学完之后你对ArrayList的理解依然是空的。所以我更推荐把动态扩容做进去哪怕只加一个ensureCapacity方法整个实现就从“练习”跳到了“容器”。4.1 扩容因子为什么推荐1.5倍而不是2倍可能有人会问Java的ArrayList源码里扩容是1.5倍C的vector不同版本有2倍也有1.5倍到底选哪个这不是玄学背后有内存分配和空间利用率的考量。我举个直观的例子。假设当前容量是10如果按2倍扩到20再扩到4080。这个增长速度很快扩容次数少但空间浪费明显因为旧数组腾出来之后新数组很可能没有立刻把旧空间全部消化。而1.5倍的增长率更温和在操作系统层面更容易复用刚释放的内存块同时长时间运行后容量增长不会像指数爆炸一样剧烈。还有一个更实际的原因开发者经验里连续多次扩容之后2倍策略产生的空余容量往往超过实际需求的50%以上。而1.5倍策略在均摊复杂度和空间利用率之间取得了一个更好平衡。我这里说的“更好”不是绝对意义上的最优而是工程实践中一套经过验证的默认值。你自己实现时完全可以根据业务场景改成2倍但一定要知道为什么改成2倍以及会多付出多少空间代价。**扩容的关键经验是扩容操作本身是高位成本尽量通过预留容量来减少触发次数。**如果预估要插入100条数据就不要在99个元素时才扩容到100直接在初始化时给够容量。ArrayList就有这个构造重载传入初始容量。很多人不知道这一点导致插入大量数据时频繁触发Arrays.copyOf大白话讲就是“反复搬家”性能自然上不去。4.2 缩容机制和抖动问题的两个思路扩容聊得多缩容却很少有人认真讨论。道理也很简单考试不考面试也不常问但真实开发里一定会遇到。先想想为什么需要缩容因为顺序表删掉大量元素后数组还是原来那么大比如容量10000删到只剩10个元素却被占用着1万块内存空间。在移动端或嵌入式环境里这可能是不可接受的内存浪费。所以缩容策略常见的有两种半满才缩当size小于capacity / 2时把容量减半。四分之一阈值当size小于capacity / 4时缩到capacity / 2留出一半缓冲。第二种策略更稳健因为它避免了“反复横跳”的抖动问题。设想一个场景容量16删到7个元素此时7 16/28触发缩容容量变成8。但紧接着再插入一个元素大小变成88 8又不缩了。看起来还行但如果阈值是7 8缩容后容量4下一轮插入一个元素又触发了扩容到8。这种频繁扩容-缩容交替的现象叫作抖动轻则浪费CPU重则导致内存碎片化。**实际操作中我很少在本地维护一个带自动缩容的顺序表。**除非明确知道用户会删除大量数据后长期不插入否则宁可不缩容保持容量复用。做系统设计时基本上要让容量只增不减配合业务峰值预估来控制内存上限。这一点跟JVM堆内存的设定很像宁可多留不要频繁调整。5. 顺序表实操中我踩过的坑和排查方法我前面讲了那么多理论但代码一旦跑起来最折磨人的永远是具体的bug。这一节我想把自己在写各种顺序表版本时踩过的坑、排查过的现象原原本本整理出来。你如果正在实验台上调代码大概率能直接命中一二。5.1 越界和空表一类高频但容易被忽略的错误越界这个坑最迷惑人的地方在于它不一定立刻报错。Java里数组访问越界会直接抛ArrayIndexOutOfBoundsException这算好的但在C语言里越界访问是未定义行为可能表现为“数组写穿了修改了相邻变量的值”这种bug非常难查。我自己见过最多的场景是写一个删除操作循环里从index开始往后移动结果没有检查index是否合法在某些极端调用下index被传成了size于是删除时访问data[size]越界。还有一种空表问题对一个没有任何元素的顺序表执行删除或取值很多人只在插入时检查长度删除时忘了检查非空。这导致每次跑出来的错误都很随机一会儿数组越界一会儿返回垃圾值。排查这类问题我有一个很土但很有效的办法在所有公共操作入口统一加边界断言。不管调用方是不是已经检查过你都在方法内部再堵一次。宁可多写一行if也不要让异常从深处冒出来。代码里这种“防御式编程”思路在数据结构练习阶段就有必要养成。5.2 移植到C语言时的指针陷阱C语言版本是很多学校实验课的标准配置但写起来比Java要小心得多。因为你需要手动管理内存数组本身就是一块堆内存指针扩容时还要用realloc。这个过程中最经典的问题就是传参时把结构体按值传了函数内部扩容修改了指针指向但外面还在用旧的指针导致后续访问直接读出乱码。我踩过的那个版本大概是这样的初始化函数里给结构体里的指针分配了空间插入满了以后realloc地址变了但没把新地址回传给调用者。结果插入成功后外层拿到的还是旧地址一访问就“炸”。后面我发现要么用二级指针传入要么让插入函数返回新地址两者选一。这个坑在Java里不存在因为引用传递自动帮你解决了但如果你用C写必须时刻想着“谁持有这块内存”。如果说要给个通用总结的话我建议写顺序表排查bug时永远先从“容量和size是否匹配”查起。**大多数让人看不懂的诡异数据都是size和真实容量不一致导致的。**把你看到的数组内容手动写一遍对照size去数往往立刻能发现到底是有空洞还是有越界写入了。6. 考试、面试和实际开发中怎么用顺序表才不吃亏把上面这些实现和原理吃透之后真正关键的问题来了这些知识在考研、期末、面试、实际开发里分别是怎么被考、怎么被用的很多人学完数据结构觉得整个课都是为了考试但其实顺序表的思想贯穿了算法和工程的方方面面只是你需要会“翻译”。6.1 考研和期末复习里的重点考法结合我在考研阶段和新手复习时总结的经验顺序表的考法大致可以分成三类。第一类是概念题问你顺序表的存储特点、随机访问O(1)和插入删除O(n)背后的原因。这种题千万别只背结论因为阅卷老师特别爱挖“为什么”。你要把“地址连续按下标直接计算地址”这句话写出来再补一句“插入删除需要移动元素移动次数和线性表长度相关”分数就稳了。第二类是应用题比如给定一个线性表要求用最少时间删除所有值为x的元素或者删除重复元素。这类题非常考验你对顺序表特性的理解代表性的刷题思路有“双指针原地覆盖”用慢指针指向保留区末尾位置用快指针往后扫遇到满足条件的就把它搬到慢指针位置。这样一次遍历就能原地完成过滤不需要反复删除和移动时间复杂度是O(n)空间复杂度做到O(1)。这种思路在数据结构实验报告里经常出现面试里同样高频。第三类是手写代码题最常见的就是实现顺序表的插入和删除。按我经验写这类题时务必注意三件事首先要检查传入下标是否合法其次插入要从后往前移动删除要从前往后移动最后要根据表长和数组容量区分“满”和“空”两种情况。这三点能全对代码题基本就能通过。面试官往往不那么在乎你把代码写得多么精简更在乎边界判断和复杂度分析能不能说清楚。408统考里有一类常考的题是给出一组数据规模让你判断应该用顺序表还是链表存储。通常这种题会强调“经常按下标访问”或“数据元素个数基本固定”那选顺序表如果强调“频繁在头部插入删除”且不知道元素总数量级链表会更合适。把存储结构适配到场景之间做转化这个概念学到后面其实会映射到Redis、数据库索引等更复杂的存储选择思路上。6.2 实际开发里我怎么判断该不该用顺序表平时写业务代码大家很少直接说“我要建一个顺序表”但Java里随手就是ArrayList、C里vector本质上都是它。我自己的判断经验有三条铁律第一如果数据量大且主要操作是“追加按下标读取”顺序表几乎是唯一选择。典型场景是日志缓冲区、游戏排行榜、事务快照这些地方用链表反而因为缓存命中率低而变慢。第二如果业务出现大量“头插头删”或“中间频繁改插”的需求优先想一想是不是可以用队列、栈或者换成链表设计。比如一个聊天软件最近会话列表你要把最新一条消息顶到最前面还要淘汰旧消息这种场景用ArrayList头部插入就是噩梦每次都要整体搬移数据量一大必然卡。第三容量要预留。真实开发中和做题不一样你很少能准确预测数据规模。我的习惯是能预判就预判预判不了就设一个相对合理的初始容量比如100或1000然后用1.5倍扩容。不要在构造函数里不传初始容量除非你知道数据本来就很少。这一条在批处理、导入导出业务里特别有效能把大批量写入的耗时直线降下来。6.3 最后再分享一个我在实际工作中养成的习惯如果你已经把顺序表理解清楚建议顺手就把Java的ArrayList源码看一遍不用从头到尾逐行读重点看它的add、remove、ensureCapacity和迭代器的实现。看完你会有种“原来如此”的感觉因为我们自己手写的顺序表和它差的最多的不是算法而是各种边界处理、快速失败机制、判空策略。比如ArrayList里的remove会把最后一个位置置null每次modCount变化都会影响迭代器是否抛ConcurrentModificationException。这些都是在实战里逼出来的细节比教科书上那几行伪代码有营养得多。我自己的体会是顺序表就像编程世界里的“煎鸡蛋”一样看起来人人会做但做得好不好差的全是细节功夫。面试官问顺序表往往不是想考验你能不能默写一个插入方法而是想知道你有没有理解它“连续存储、移动元素、动态扩容”这三个核心的代价。你把这些讲明白无论是一道算法题还是一个现实的技术选型都能比只会背书的人多一层底气。 
长河君 · 2026/10/8 15:07:12 · 阅读 1.2k 顺序表核心原理与手写实现：从动态扩容到复杂度分析
顺序表这个名字听起来确实不玄乎但真到面试手撕、期末上机或者备战考研时很多人反而就是在这种最基础的东西上翻车。数据结构这门课里线性结构开篇要解决的就是顺序表你天天用的Java ArrayList、C语言里自己malloc出来的连续内存块本质都是它的变体。这篇文章不想按教材的口吻从头念一遍我想用实际操作时候的思路来讲它到底解决什么问题、核心操作是怎么设计出来的、手写代码时哪里容易踩坑以及考试和面试里最常见的考法在哪。无论你是刚开始学数据结构的新手还是正在绞尽脑汁记复杂度公式的考生这篇文章应该都能给你一些直接能拿去用的东西。1. 先搞清楚顺序表在数据结构里站在什么位置先把结论拍在桌面上顺序表是一种“逻辑上线性、物理上也线性连续”的存储结构。逻辑线性很好理解就是数据一个挨一个像排队买奶茶物理连续就重要了意思是这些元素在内存里真的是放在一整块连续的空间里而不是像链表那样东一个西一个散落着。这个“连续”两个字既是顺序表最大的优势也是它所有设计矛盾和性能瓶颈的来源。我见过不少初学者学完数组就直接跳过顺序表觉得这有什么好学的不就是数组套一个壳吗话不能这么说。数组是最基础的内存抽象而顺序表是在数组之上封装了动态扩容、按位置插入、按值查找、删除后保持紧凑等一套完整逻辑的容器。你去看Java里ArrayList的源码去看C里vector的实现看底层就是顺序表这套玩法。搞清楚顺序表其实是在帮你理解所有现代动态数组类容器共同的底层设计逻辑这个价值远不是“会写个增删改查”这么简单。1.1 顺序表的存储模型和一个生活化类比在真实内存里顺序表对应的就是一块连续地址空间。假设每个元素占4个字节第一个元素地址是1000第二个就是1004第三个是1008。所以按下标访问时地址计算公式基本就是base index * elementSize一步乘法加法直接定位不需要遍历。这就是为什么说顺序表随机访问的时间复杂度是O(1)。用一个更贴近日常的类比顺序表像电影院里固定连排的座位每个人在进场前就分配好了座位号你想找第13排第5座的人跟着号码走过去就行不需要从第一排挨个问。而链表更像我手里拿了一叠线索卡片每张卡片上写着“下一个人的位置在哪儿”想要找到某个人就得一张一张翻。这个差异就是顺序表与链表最核心的分水岭读得快但插入和删除时需要给后面所有的人腾位置或补空缺。正因如此设计一个顺序表时你始终在做两个互相拉扯的取舍。如果预留大量空闲空间插入时移动元素的压力小了但内存浪费严重如果每个位置都精打细算内存是省了可每次插入都要搬动一堆数据。所有的扩容策略、缩容阈值、插入位置选择本质上都是在这个矛盾里找平衡点。1.2 顺序表和其他存储结构的横向对比学习数据结构时最忌讳“就事论事”学顺序表就把顺序表背下来学链表又把链表单独背一遍两套知识在脑子里完全割裂。所以我建议一开始就做一个横向表把顺序表和同一家族里的其他线性存储结构放在一块看对比维度顺序表单链表双向链表存储方式一块连续内存每个节点分散存储每个节点两个指针结构更重按下标访问O(1)直接算地址O(n)必须从头走O(n)但可双向走插入/删除头部O(n)所有元素后移O(1)改指针即可O(1)改两个方向指针插入/删除尾部位置已知O(1)尾部直接添O(n)必须先找到尾节点O(1)有尾指针时额外内存开销极小只有数组空间每个节点多一个指针每个节点多两个指针缓存友好性高连续内存读完一片低可能频繁跳到随机地址更低指针跳跃更多这张表不是让你背的是让你在真正做设计时快速权衡一个场景如果以“按下标取值”为主比如排行榜、缓存队列的快照那顺序表就是最合适的选择如果业务里大量操作是“在中间频繁插入”比如编辑器的撤销历史那链表反而更有优势。顺序表真正强大和真正薄弱的点都在表里一目了然。2. 顺序表的核心操作是怎么设计出来的顺序表的核心操作翻来覆去就是五个初始化、插入、删除、按位查找、按值查找。单拿出来看都很简单但设计这些操作时每一个细节都在处理同一个问题如何维护“元素搬迁”的正确性。很多教材都会直接给出伪代码看起来很短但伪代码跳过了大量边界条件。真正动手实现时你要回答的问题远不止“写个for循环”那么简单插入时循环到底从哪边开始删除后数组末尾要做什么扩容容量怎么算越界条件怎么判断这一节我把每个核心操作背后的设计意图拆开讲顺带把容易翻车的细节点明。2.1 插入操作位置合法性和移位方向是两座大山插入操作有个关键前置逻辑插入位置合法范围是0到当前长度也就是说可以在末尾追加也可以在头部塞入。如果位置是负数或者比长度还大就必须抛越界异常。这个判断看起来多余但真到写代码时最容易漏尤其是在Java这种有异常机制的代码里漏掉越界检查后续会打出很难查的ArrayIndexOutOfBoundsException。确定位置合法之后核心就是移位的“方向”。在顺序表里插入一个元素到下标index时下标index以及它之后的所有元素都要往右挪一格而且这个挪动必须从最后一个元素先开始倒着往前挪。举个例子当前数组是[1,5,6,9]要在下标1的位置插入99。正确做法是先把下标3的9挪到下标4再把下标2的6挪到下标3再把下标1的5挪到下标2最后把99放到下标1。为什么必须倒着来因为如果你先把下标1的5挪到下标2那下标2原来的6就被覆盖了后面的数据直接烂掉。这个方向搞反了甚至不需要等程序跑完人就已经能看出结果不对。正因为要搬动“后面所有元素”插入的平均时间复杂度是O(n)。注意我说的是平均因为如果每次都插在末尾那只需要一步操作只有插在中间和头部时才需要大面积搬运。所以很多人在数据结构课程里纠结“插入到底是O(1)还是O(n)”真相是插入本身定位是O(1)但腾位置这个动作是O(n)整体取最坏情形就是O(n)。还有一个经常被忽略的点是内存空间不足时插入前必须扩容。这里就引出了一个设计选择——每次插入前都检查“有没有空位”只是最基础的更好的做法是预判增长策略把扩容的代价均摊到多次插入里。这也是为什么动态数组类容器扩容时不只扩一个位置而是整体翻倍或1.5倍扩我后面会专门讲。2.2 删除操作和查找操作复杂度背后的真实代价删除逻辑和插入是对称的但有一个容易踩的坑。删除下标index的元素时需要把index后面的所有元素整体往左挪一位这次必须正着来从index1开始把每个元素复制到它前一个位置。方向反了也不行因为你把index2复制到index1后再想复制index1的原始值到index时那个值早就被覆盖了。删除操作的时间复杂度同样是O(n)。这一点很多教材讲得太含糊导致期末考试或者面试问“顺序表删除中间元素的复杂度”时有人答O(1)、有人答O(n)其实都不算完全错但你必须能说清楚如果只讨论“把某个位置标记为无效”那确实是O(1)但顺序表的定义要求“删除后仍然保持紧密排列、不能留空洞”所以必须把后续元素整体搬过来这个搬运动作就是O(n)。按位查找就简单得多知道下标直接算地址拿值O(1)这跟随机访问一个道理。按值查找则要遍历整个数组平均比较n/2次所以是O(n)。这个对比非常有意思顺序表牺牲了插入删除的灵活性换来了“按位直达”的高效。如果业务场景是“知道位置就取值”顺序表收益很大如果是“知道值但不知道位置”那它和链表一样要遍历优势不明显。值得多说一句的是按值查找在Java里默认用equals比较不能用去比较引用类型。这个细节在源码里体现得很清楚如果查null就走了独立的null处理分支查非null用equals逐项比。很多自己手写顺序表的同学在比较整数或者字符串时用了局部测起来好像没问题一旦存的是自定义对象立刻全军覆没。遇到这种问题先别怀疑算法先检查你用的是equals还是。3. 手撕一个动态顺序表Java实现细节数据结构考试里顺序表手写实现几乎是必考题但真正有价值的并不只是“把功能跑通”而是代码结构合理、边界清晰、扩展性够用。我自己比较推荐用Java语言来练习实现顺序表原因是Java有成熟的泛型机制、数组拷贝工具和异常体系代码写出来更贴近真实开发里的容器实现。下面这套实现我按“基础功能完整 扩展机制简洁 边界处理严格”这三个原则来写。它不是那种为了应付上机课拼命精简的玩具代码而是你做完之后可以对照源码看懂ArrayList底层逻辑的版本。3.1 类骨架泛型数组、容量初始化和size变量先看核心骨架public class SeqListT { // 真正的数据存储在Object数组里 private Object[] data; // 当前实际存了多少个元素不是数组的长度 private int size; public SeqList() { this(10); } public SeqList(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(容量不能为负数: initialCapacity); } data new Object[initialCapacity]; size 0; } }这里有个很重要的设计原则size和数组长度是两个完全不同的概念。数组长度是容量capacity表示当前最多能放多少元素size是真实元素个数表示现在存了多少。很多新手写顺序表把这两个混淆扩容判断和返回值都会出bug。泛型方面Java的泛型在运行时会被擦除所以不能直接new T[10]只能先创建Object数组再强制转型。这也是为什么源码里到处能看到(T) data[i]这样的强转。你不需要在这点上纠结知道这是Java泛型擦除的代价就行。如果你用C语言练习思路完全一致只是把Object换成了结构体的指针或者直接用void*数组逻辑相通。还有一个小点构造函数里负数容量要主动抛异常。这个判断看起来是小题大做却能逼着使用方在逻辑层面提前暴露错误而不是等到数组创建的时候报个奇怪的负数异常。真实开发里这种早期失败比后期兜底有价值得多。3.2 增删改查完整实现与关键细节接着看核心操作实现。我特意把System.arraycopy和手动循环两种方式都讲一下。System.arraycopy是JVM提供的高效数组复制方法但在数据结构练习里不少人看不懂它的参数容易用错。public void add(T value) { ensureCapacity(); data[size] value; size; } public void insert(int index, T value) { if (index 0 || index size) { throw new IndexOutOfBoundsException(插入位置越界: index); } ensureCapacity(); // 将 index 及其之后的所有元素整体右移一格 System.arraycopy(data, index, data, index 1, size - index); data[index] value; size; } public T remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(删除位置越界: index); } T oldValue (T) data[index]; int numMoved size - index - 1; if (numMoved 0) { System.arraycopy(data, index 1, data, index, numMoved); } data[size - 1] null; size--; return oldValue; } public T get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(下标越界: index); } return (T) data[index]; } public int indexOf(T target) { if (target null) { for (int i 0; i size; i) { if (data[i] null) { return i; } } } else { for (int i 0; i size; i) { if (target.equals(data[i])) { return i; } } } return -1; }有几个细节值得多说两句。第一插入时System.arraycopy(data, index, data, index 1, size - index)这个写法意思是“把从index开始、长度为size-index的元素整体挪到index1开始的地方”。因为源数组和目标数组是同一个Java底层会用临时变量处理重叠复制所以你不用担心覆盖问题。第二删除后我把最后一个位置data[size-1]置为null。这一步在泛型代码里很重要因为数组中还留着一个指向原对象的引用如果不清空这个对象就永远不会被垃圾回收这就是所谓“内存泄漏”。很多手写版本不做这一步能跑但不好我在实际开发里养成习惯用不上的引用尽量及时切断。第三indexOf里为什么单独处理null因为调用target.equals(data[i])时如果target是null直接空指针异常。要么反过来写data[i] ! null data[i].equals(target)要么像上面一样给null单独开一条循环。在ArrayList源码里也是类似做法这不是炫技是必须处理的边界。3.3 扩容机制什么时候扩容为什么不是固定加1上面的ensureCapacity()还需要单独实现这正是顺序表从“静态数组”进化成“动态容器”的关键一步private void ensureCapacity() { if (size data.length) { int oldCapacity data.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity - oldCapacity 0) { newCapacity 10; } data Arrays.copyOf(data, newCapacity); } }这段代码的意思是当当前元素个数已经达到数组容量时新容量按1.5倍扩张然后调用Arrays.copyOf把旧数组内容复制进新数组。为什么不是每次只加一个位置因为如果每次只加1个连续插入n个元素就会触发n次扩容每次扩容都要复制已有全部元素总代价是123...n也就是O(n²)这会直接把性能拖垮。采用倍数扩容后虽然单次扩容的成本仍然是O(n)但“均摊”到多次插入上每次插入的平均复杂度可以近似认为是O(1)。这个均摊分析在面试里经常被追问核心论点就是扩容次数只有O(logn)复制操作的总量是O(n)均摊到n次插入就是O(1)。这个思想不只顺序表用很多动态数据结构都遵循同样的逻辑。4. 扩容机制与缩容边界容量变化是顺序表最容易翻车的点说扩容是顺序表最容易翻车的地方毫不夸张。因为顺序表的基础操作无非就是数组移动只要逻辑清晰就很好写但容量怎么涨、什么时候缩、缩多少这里面藏着大量性能陷阱和工程取舍。很多教材为了省事把顺序表设计成“一次性申请一个最大容量”比如数组大小固定为100满了就报错。这样写确实简单但它没有实现真正意义上的动态管理学完之后你对ArrayList的理解依然是空的。所以我更推荐把动态扩容做进去哪怕只加一个ensureCapacity方法整个实现就从“练习”跳到了“容器”。4.1 扩容因子为什么推荐1.5倍而不是2倍可能有人会问Java的ArrayList源码里扩容是1.5倍C的vector不同版本有2倍也有1.5倍到底选哪个这不是玄学背后有内存分配和空间利用率的考量。我举个直观的例子。假设当前容量是10如果按2倍扩到20再扩到4080。这个增长速度很快扩容次数少但空间浪费明显因为旧数组腾出来之后新数组很可能没有立刻把旧空间全部消化。而1.5倍的增长率更温和在操作系统层面更容易复用刚释放的内存块同时长时间运行后容量增长不会像指数爆炸一样剧烈。还有一个更实际的原因开发者经验里连续多次扩容之后2倍策略产生的空余容量往往超过实际需求的50%以上。而1.5倍策略在均摊复杂度和空间利用率之间取得了一个更好平衡。我这里说的“更好”不是绝对意义上的最优而是工程实践中一套经过验证的默认值。你自己实现时完全可以根据业务场景改成2倍但一定要知道为什么改成2倍以及会多付出多少空间代价。**扩容的关键经验是扩容操作本身是高位成本尽量通过预留容量来减少触发次数。**如果预估要插入100条数据就不要在99个元素时才扩容到100直接在初始化时给够容量。ArrayList就有这个构造重载传入初始容量。很多人不知道这一点导致插入大量数据时频繁触发Arrays.copyOf大白话讲就是“反复搬家”性能自然上不去。4.2 缩容机制和抖动问题的两个思路扩容聊得多缩容却很少有人认真讨论。道理也很简单考试不考面试也不常问但真实开发里一定会遇到。先想想为什么需要缩容因为顺序表删掉大量元素后数组还是原来那么大比如容量10000删到只剩10个元素却被占用着1万块内存空间。在移动端或嵌入式环境里这可能是不可接受的内存浪费。所以缩容策略常见的有两种半满才缩当size小于capacity / 2时把容量减半。四分之一阈值当size小于capacity / 4时缩到capacity / 2留出一半缓冲。第二种策略更稳健因为它避免了“反复横跳”的抖动问题。设想一个场景容量16删到7个元素此时7 16/28触发缩容容量变成8。但紧接着再插入一个元素大小变成88 8又不缩了。看起来还行但如果阈值是7 8缩容后容量4下一轮插入一个元素又触发了扩容到8。这种频繁扩容-缩容交替的现象叫作抖动轻则浪费CPU重则导致内存碎片化。**实际操作中我很少在本地维护一个带自动缩容的顺序表。**除非明确知道用户会删除大量数据后长期不插入否则宁可不缩容保持容量复用。做系统设计时基本上要让容量只增不减配合业务峰值预估来控制内存上限。这一点跟JVM堆内存的设定很像宁可多留不要频繁调整。5. 顺序表实操中我踩过的坑和排查方法我前面讲了那么多理论但代码一旦跑起来最折磨人的永远是具体的bug。这一节我想把自己在写各种顺序表版本时踩过的坑、排查过的现象原原本本整理出来。你如果正在实验台上调代码大概率能直接命中一二。5.1 越界和空表一类高频但容易被忽略的错误越界这个坑最迷惑人的地方在于它不一定立刻报错。Java里数组访问越界会直接抛ArrayIndexOutOfBoundsException这算好的但在C语言里越界访问是未定义行为可能表现为“数组写穿了修改了相邻变量的值”这种bug非常难查。我自己见过最多的场景是写一个删除操作循环里从index开始往后移动结果没有检查index是否合法在某些极端调用下index被传成了size于是删除时访问data[size]越界。还有一种空表问题对一个没有任何元素的顺序表执行删除或取值很多人只在插入时检查长度删除时忘了检查非空。这导致每次跑出来的错误都很随机一会儿数组越界一会儿返回垃圾值。排查这类问题我有一个很土但很有效的办法在所有公共操作入口统一加边界断言。不管调用方是不是已经检查过你都在方法内部再堵一次。宁可多写一行if也不要让异常从深处冒出来。代码里这种“防御式编程”思路在数据结构练习阶段就有必要养成。5.2 移植到C语言时的指针陷阱C语言版本是很多学校实验课的标准配置但写起来比Java要小心得多。因为你需要手动管理内存数组本身就是一块堆内存指针扩容时还要用realloc。这个过程中最经典的问题就是传参时把结构体按值传了函数内部扩容修改了指针指向但外面还在用旧的指针导致后续访问直接读出乱码。我踩过的那个版本大概是这样的初始化函数里给结构体里的指针分配了空间插入满了以后realloc地址变了但没把新地址回传给调用者。结果插入成功后外层拿到的还是旧地址一访问就“炸”。后面我发现要么用二级指针传入要么让插入函数返回新地址两者选一。这个坑在Java里不存在因为引用传递自动帮你解决了但如果你用C写必须时刻想着“谁持有这块内存”。如果说要给个通用总结的话我建议写顺序表排查bug时永远先从“容量和size是否匹配”查起。**大多数让人看不懂的诡异数据都是size和真实容量不一致导致的。**把你看到的数组内容手动写一遍对照size去数往往立刻能发现到底是有空洞还是有越界写入了。6. 考试、面试和实际开发中怎么用顺序表才不吃亏把上面这些实现和原理吃透之后真正关键的问题来了这些知识在考研、期末、面试、实际开发里分别是怎么被考、怎么被用的很多人学完数据结构觉得整个课都是为了考试但其实顺序表的思想贯穿了算法和工程的方方面面只是你需要会“翻译”。6.1 考研和期末复习里的重点考法结合我在考研阶段和新手复习时总结的经验顺序表的考法大致可以分成三类。第一类是概念题问你顺序表的存储特点、随机访问O(1)和插入删除O(n)背后的原因。这种题千万别只背结论因为阅卷老师特别爱挖“为什么”。你要把“地址连续按下标直接计算地址”这句话写出来再补一句“插入删除需要移动元素移动次数和线性表长度相关”分数就稳了。第二类是应用题比如给定一个线性表要求用最少时间删除所有值为x的元素或者删除重复元素。这类题非常考验你对顺序表特性的理解代表性的刷题思路有“双指针原地覆盖”用慢指针指向保留区末尾位置用快指针往后扫遇到满足条件的就把它搬到慢指针位置。这样一次遍历就能原地完成过滤不需要反复删除和移动时间复杂度是O(n)空间复杂度做到O(1)。这种思路在数据结构实验报告里经常出现面试里同样高频。第三类是手写代码题最常见的就是实现顺序表的插入和删除。按我经验写这类题时务必注意三件事首先要检查传入下标是否合法其次插入要从后往前移动删除要从前往后移动最后要根据表长和数组容量区分“满”和“空”两种情况。这三点能全对代码题基本就能通过。面试官往往不那么在乎你把代码写得多么精简更在乎边界判断和复杂度分析能不能说清楚。408统考里有一类常考的题是给出一组数据规模让你判断应该用顺序表还是链表存储。通常这种题会强调“经常按下标访问”或“数据元素个数基本固定”那选顺序表如果强调“频繁在头部插入删除”且不知道元素总数量级链表会更合适。把存储结构适配到场景之间做转化这个概念学到后面其实会映射到Redis、数据库索引等更复杂的存储选择思路上。6.2 实际开发里我怎么判断该不该用顺序表平时写业务代码大家很少直接说“我要建一个顺序表”但Java里随手就是ArrayList、C里vector本质上都是它。我自己的判断经验有三条铁律第一如果数据量大且主要操作是“追加按下标读取”顺序表几乎是唯一选择。典型场景是日志缓冲区、游戏排行榜、事务快照这些地方用链表反而因为缓存命中率低而变慢。第二如果业务出现大量“头插头删”或“中间频繁改插”的需求优先想一想是不是可以用队列、栈或者换成链表设计。比如一个聊天软件最近会话列表你要把最新一条消息顶到最前面还要淘汰旧消息这种场景用ArrayList头部插入就是噩梦每次都要整体搬移数据量一大必然卡。第三容量要预留。真实开发中和做题不一样你很少能准确预测数据规模。我的习惯是能预判就预判预判不了就设一个相对合理的初始容量比如100或1000然后用1.5倍扩容。不要在构造函数里不传初始容量除非你知道数据本来就很少。这一条在批处理、导入导出业务里特别有效能把大批量写入的耗时直线降下来。6.3 最后再分享一个我在实际工作中养成的习惯如果你已经把顺序表理解清楚建议顺手就把Java的ArrayList源码看一遍不用从头到尾逐行读重点看它的add、remove、ensureCapacity和迭代器的实现。看完你会有种“原来如此”的感觉因为我们自己手写的顺序表和它差的最多的不是算法而是各种边界处理、快速失败机制、判空策略。比如ArrayList里的remove会把最后一个位置置null每次modCount变化都会影响迭代器是否抛ConcurrentModificationException。这些都是在实战里逼出来的细节比教科书上那几行伪代码有营养得多。我自己的体会是顺序表就像编程世界里的“煎鸡蛋”一样看起来人人会做但做得好不好差的全是细节功夫。面试官问顺序表往往不是想考验你能不能默写一个插入方法而是想知道你有没有理解它“连续存储、移动元素、动态扩容”这三个核心的代价。你把这些讲明白无论是一道算法题还是一个现实的技术选型都能比只会背书的人多一层底气。