1. 顺序表到底是什么先摘掉“数据结构”这顶帽子很多初学者看到“顺序表SeqList”这个名字第一反应是又要背一个抽象概念了。但实际上你早就见过它了——数组中里日常写的 int[]、String[]底层就是顺序表Java 里天天用的 ArrayList本质就是装进类壳子里的顺序表。顺序表不是某种高深魔法它就是“用一段连续的内存空间按顺序存储一列相同类型数据”的容器。1.1 数组和顺序表同一件事的两种说法数组是语言层面的东西你写int[] arr new int[10]编译器就给你划一块连续内存。顺序表是数据结构层面的概念它描述的是“逻辑上相邻的元素在物理存储上也相邻”的线性结构。区别在哪里数组的长度在创建时就固定了装满了想再装就得自己找新数组、自己拷数据顺序表却把这一套“扩容、移动、管理”的逻辑封装成了操作使用者只需要 add、get、remove不用关心底层数组满了怎么办。所以顺序表 数组 一套自动管理的操作方法。这也是为什么 Java 里ArrayList的实现核心就是一个Object[] elementData——它就是一个会自己长大的数组。1.2 顺序表的三个底层特征要真正理解顺序表抓住三个特征就够了逻辑连续元素之间的先后关系是线性排列的第 i 个元素有且只有一个前驱除第一个和一个后继除最后一个。物理连续所有元素存放在一块地址连续的内存中第 i 个元素的地址可以通过基地址 i × 元素大小直接算出来。随机访问因为物理连续访问任意下标的时间都是 O(1)这是顺序表最大的底牌。这三个特征决定了顺序表的性格查找特别快但插入删除要搬家。1.3 为什么顺序表是“入门第一课”数据结构这门课几乎所有教材都从顺序表讲起。不是因为简单是因为它是后面所有结构的基石栈、队列的底层实现哈希表的 open addressing 方案堆排序里的数组建堆……到处都依赖“物理连续 随机访问”这个底层能力。我见过太多人跳着学上来就看 HashMap 源码、二叉树平衡旋转结果遇到“为什么 ArrayList 扩容用位运算”、“为什么 remove 后要置空引用”这类基础问题就卡壳。顺序表这一章学透了后面的源码阅读和算法设计会顺畅得多。2. 自己动手实现一个 SeqList不依赖 ArrayList 的顺序表想真正搞懂 ArrayList最好的方式是自己写一个。不要用 IDE 的自动补全打开一个空白文件从类名开始敲。写完之后你会发现再看 Java 源码简直是“拿着参考答案做题”。2.1 怎么选底层存储固定数组版和可变容量版最朴素的实现方式有两种。方案一构造时指定容量满了就抛异常。这种写法简单但是实用性很差因为实际业务里几乎无法预测数据量的上限。很多数据结构的教材题里会这么写因为教学场景要回避扩容逻辑。如果你只是做课设可以这样写public class SeqList { private int[] data; private int size; public SeqList(int capacity) { data new int[capacity]; size 0; } public void add(int element) { if (size data.length) { throw new IllegalStateException(顺序表已满); } data[size] element; } public int get(int index) { rangeCheck(index); return data[index]; } }注意这里我用的是int[]而不是Object[]因为不涉及泛型写起来最清爽做实验最合适。方案二自动扩容版容量不够就“搬家”。这才是 ArrayList 的真实形态。扩容时的关键是先判断元素个数是否已经等于数组长度如果等于就申请一个新数组长度通常是旧数组的 1.5 倍用System.arraycopy把旧数据整体搬过去再把新元素放到 size 的位置上。搬迁成本均摊下来每次 add 的时间复杂度仍然是 O(1)。有个细节值得注意很多教材里的扩容是“满了才扩”但生产级实现会在“size 1 超出容量”时触发 grow。两者的差别在于前者创建空表时就要指定容量后者可以选择懒加载先不申请底层数组第一次 add 再分配。ArrayList 就采用了后者这也是它构造开销极小的原因。2.2 扩容为什么要用 1.5 倍而不是 2 倍这是我在讲 ArrayList 源码时一定会展开的问题。先看 JDK 里实际怎么写private Object[] grow(int minCapacity) { int oldCapacity elementData.length; if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity oldCapacity (oldCapacity 1); ... } ... }oldCapacity 1就是除以 2所以新容量是旧容量的 1.5 倍。为什么不直接翻倍一方面1.5 倍能显著减少内存浪费。如果一直翻倍一个初始容量 10 的列表扩容到第 10 次时容量会到 10240但实际可能只用了 1000 个浪费了九成。1.5 倍的增长曲线更平缓内存占用更收敛。另一方面1.5 倍依然保证了“均摊 O(1) 插入”的数学性质因为每次扩容增加的容量和已用容量是同阶的搬运 n 个元素的累计成本仍然是 O(n)。翻倍不是不行Redis 的 list 就常用翻倍策略但 Java 选择了更省内存的方案。这个细节面试中考“为什么”的人是真多但真正能说透的少。你如果能从“均摊复杂度”和“内存浪费”两个角度解释基本就是满分回答。2.3 元素移动的微优化System.arraycopy 为什么比 for 循环快中间插入或删除时需要把后面的元素整体前移或后移。新手最容易写成for (int i size; i index; i--) { data[i] data[i - 1]; }这写法没错但性能差点意思。更好的方式是调用System.arraycopySystem.arraycopy(data, index, data, index 1, size - index);System.arraycopy是 JVM 层面的 native 方法它不仅仅是一个“循环搬数据”的语法糖。JVM 在实现它时会尝试使用 SIMD 指令做向量化拷贝一次搬运 8 字节甚至更多数据同时还能配合内存屏障做一些特殊优化。相比之下普通 for 循环每次只搬一个元素还要受 JIT 启发式优化的不确定性影响。所以在顺序表核心操作里凡是涉及批量移动元素的地方都应该用System.arraycopy。另一个细节是删除元素后如果不把data[size]置为 null对象引用会一直留在数组里导致 GC 无法回收这段内存这在长时间运行的 Java 服务里会变成隐性内存泄漏。JDK 源码里 remove 操作的最后一步就是elementData[--size] null这个细节我 3.3 节还会再展开。3. 手写 SeqList 的完整 Java 代码与踩坑记录下面我给你一份可以拿去直接用、也可以对照着学原理的泛型版本。它实现了顺序表最核心的增删改查并包含扩容、缩容、越界检查等逻辑。import java.util.Arrays; import java.util.Objects; public class SeqListT { private static final int DEFAULT_CAPACITY 10; private Object[] data; private int size; public SeqList() { data new Object[DEFAULT_CAPACITY]; size 0; } public SeqList(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(容量不能为负数: initialCapacity); } data new Object[initialCapacity]; size 0; } public boolean add(T element) { ensureCapacity(size 1); data[size] element; return true; } public void add(int index, T element) { rangeCheckForAdd(index); ensureCapacity(size 1); System.arraycopy(data, index, data, index 1, size - index); data[index] element; size; } SuppressWarnings(unchecked) public T get(int index) { rangeCheck(index); return (T) data[index]; } public T set(int index, T element) { rangeCheck(index); T oldValue (T) data[index]; data[index] element; return oldValue; } SuppressWarnings(unchecked) public T remove(int index) { rangeCheck(index); T removed (T) data[index]; int numMoved size - index - 1; if (numMoved 0) { System.arraycopy(data, index 1, data, index, numMoved); } data[--size] null; return removed; } public int size() { return size; } public boolean isEmpty() { return size 0; } public void clear() { Arrays.fill(data, 0, size, null); size 0; } private void ensureCapacity(int minCapacity) { if (minCapacity data.length) { int newCapacity data.length (data.length 1); if (newCapacity minCapacity) { newCapacity minCapacity; } data Arrays.copyOf(data, newCapacity); } } private void rangeCheck(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(索引越界: index , 当前大小: size); } } private void rangeCheckForAdd(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(索引越界: index , 当前大小: size); } } Override public String toString() { StringBuilder sb new StringBuilder([); for (int i 0; i size; i) { sb.append(data[i]); if (i ! size - 1) { sb.append(, ); } } return sb.append(]).toString(); } }3.1 这段代码里最值得琢磨的三个 API 设计等你写完上面这份代码再看ArrayList的 API会发现几个有意思的对应关系第一ensureCapacity。这个私有方法负责扩容判断它的核心参数是minCapacity也就是“这次至少需要多少容量”。如果新容量算出来还不够就得直接用minCapacity。JDK 源码里也有同样的处理流程就是为了防止极端情况下 1.5 倍不够用。你可能会说“这怎么可能”但如果初始容量是 0再加 5 个元素1.5 倍永远是 0就必须靠 minCapacity 兜底。第二remove的置空操作。方法最后一行data[--size] null是 JDK 源码的忠实还原。这一步处理的是“游离引用”问题——数组里已经没有逻辑上的元素了但物理引用还在如果不清掉size缩减后这个对象就不会被当作业务数据访问但依然被数组引用着垃圾回收器不会回收它。在写长连接服务、消息队列消费者这类需要长时间运行的场景里这个小细节能避免大量无用的“老年代存货”。第三rangeCheckForAdd和rangeCheck是两套越界检查。add 的 index 允许等于 size追加到末尾而 get/remove 的 index 不允许等于 size。你如果只写一个 check加元素时就会漏掉“末尾追加”这个合法操作。这个细节我自己第一次写的时候就没注意到导致add(list.size(), x)直接被误判越界。3.2 泛型擦除留下的坑为什么强制类型转换到处都是上面代码里有很多(T) data[index]这种强制类型转换因为 Java 的泛型是“伪泛型”——在编译阶段全部擦除为 Object。运行时数组里存的就是 Object 引用取出来时只能靠你手动强转。这就是为什么 JDK 的ArrayList里elementData声明成了Object[]而不是T[]。有的教材会写成这样T[] elements (T[]) new Object[capacity];这种写法本质上是一次性的假强转赋值时整段数组就被标记为 T[] 了后续 get 就不用每个元素都转。但问题在于编译器会警告“unchecked cast”而且如果某个调用方用反射拿这个数组当 String[] 用运行期依然会报ClassCastException。所以不要迷信这种写法老老实实每个元素强转反而更安全。3.3 我在手写过程中踩过的三个坑第一次写属于自己的 SeqList 时我踩过几个印象深刻的坑值得拿出来分享。坑一扩缩容不对称。我最初只写了扩容没写缩容结果从一个包含 100 万元素的列表里 remove 到只剩 100 个时底层数组还占着 100 万的空间。这是典型的“内存只借不还”。不过这事不能走极端——频繁的缩容会引发频繁的数组复制反而更伤性能。Java 的ArrayList干脆默认不缩容除非你手动调用trimToSize()。我的建议是业务中有批量删除后列表长期保持小规模的场景才需要考虑缩容否则保持原样即可。坑二加元素的时候先判断再扩容。我最初把ensureCapacity(size 1)写成了先扩容再加入结果每次 add 都触发一次Arrays.copyOf性能惨不忍睹。正确顺序是先判断是否需要扩容需要才扩不需要直接写入。这个“判断先行”的习惯对后面看HashMap的 resize 逻辑也很有帮助。坑三insert 中间位置时忘了从后往前搬。在add(int index, T element)里如果写 for 循环从 index 开始往后搬会出现“后面的旧值覆盖掉前面的新位置”的错乱结果。正确方式是先从后往前搬System.arraycopy(data, index, data, index 1, size - index)内部就是从源区间的头部往尾部拷贝天然规避了这个问题。这也是直接调用arraycopy的好处之一。4. ArrayList 源码级拆解JDK 对顺序表的官方实现看完自己写的版本再看 JDK 的ArrayList会感觉一切都很亲切。但源码里还有一些“教科书不写”的细节。4.1 构造函数你都以为 new ArrayList() 创建了一个空数组其实不是new ArrayList()真的会分配Object[0]吗不是。JDK 8 的源码里无参构造会给你一个共享的空数组常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个数组长度为 0但在第一次 add 时会扩容到默认容量 10。这个“懒加载”设计是故意的它在大多数场景下避免了无谓的数组分配。看一下无参构造的关键源码private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }这样设计的好处是你 new 一个 ArrayList 但始终没有添加元素或者只添加几个元素就结束了它就不会为“可能需要的容量”提前掏内存。而如果你构造时明确给了初始容量比如new ArrayList(1000)它才会立刻分配一个长度为 1000 的 Object 数组。4.2 grow() 方法位运算扩容和 modCount 的用途JDK 里扩容的入口是grow(int minCapacity)前面提过它的核心逻辑是oldCapacity (oldCapacity 1)。我补充一个细节为什么 JDK 偏爱位运算因为移位比/除法更快。虽然现代 JIT 会在热点代码里自动把除以 2 优化成右移但在源码层面写 1可以让意图更明确也避免一些旧 JVM 上的性能差异。你不需要在业务代码里到处用位运算但读源码时要知道这些写法背后的原因。另外所有结构性修改方法add、remove、clear都会modCount这个字段用于快速失败fail-fast机制当某个迭代器正在遍历时如果集合结构被意外修改modCount变了下次next()调用就会直接抛ConcurrentModificationException。这个设计不是防止并发写而是提醒你“别再用了数据已经和你预期的不一致了”。这也是foreach循环里调用list.remove()会炸的原因。4.3 get/add/remove 的时间复杂度为什么和教科书一致但实际体验不同教科书写着随机访问 O(1)尾部插入均摊 O(1)中间插入 O(n)。这个严谨但有个前提——你操作的是 ArrayList。真实应用里的“原因差异”主要体现在几个方面随机访问确实是 O(1)但它还涉及一次数组边界检查和一次引用读取现代 CPU 上这个操作会有缓存命中加持所以 get 极快。尾部 add是均摊 O(1)但每次扩容都伴随着一次 O(n) 的数组复制所以在批量写入大数据时你能感受到突发的卡顿。想平滑这种卡顿预分配容量是关键ArrayListInteger list new ArrayList(预估大小)。remove(0)是 O(n)因为它要把后面所有元素前移。如果你经常要删第一个元素ArrayList 不合适LinkedList或者ArrayDeque才是好选择。很多网帖喜欢说“LinkedList 插入删除比 ArrayList 快”这是典型的以偏概全。实际做基准测试你会发现在随机位置插入时ArrayList 的System.arraycopy是一个非常快的内存拷贝而 LinkedList 需要逐个节点遍历找到插入位置这部分 O(n) 的开销并不比 ArrayList 的“搬家”小多少。数据量大、插入点靠前时LinkedList 未必赢甚至更慢。真正的银弹是频繁随机插入请用CopyOnWriteArrayList适合读多写少并发或跳到ArrayList以外去找新结构而不是在两者之间硬选。5. 顺序表的性能边界能打的地方在哪别硬刚的地方有哪些给顺序表做性能画像比背“O(1)/O(n)”这种结论更有用。你要搞清楚它适合什么场景、不适合什么场景才能在项目里做正确的结构选型。5.1 随机访问和缓存命中为什么顺序表遍历比链表快顺序表遍历比链表快不是玄学是 CPU 缓存带来的硬件红利。CPU 读取内存时不是一次只取一个元素而是按“缓存行”一次性取 64 字节左右。数组里相邻元素在物理地址上连续所以你遍历数组时第一次读arr[0]时其实已经把arr[0]..arr[15]假设每个元素 4 字节都装入缓存了后面连续读取几乎不触碰内存。链表的节点分散在堆的不同地址上每次读下一个节点都可能缓存未命中触发一次内存访问。这个区别在数据量小的时候不明显数据量达到百万级、千万级后遍历顺序表的速度通常是链表的 3 到 5 倍。这也是为什么 Java 里很多“内存数据库”和搜索引擎的倒排索引底层用数组实现——不是图省事是图缓存命中。5.2 插入删除的“搬家成本”到底有多高顺序表的中间插入删除成本是 O(n)但 n 的具体含义是“要搬动的元素个数”不是整个列表长度。你在末尾插入n0成本是 O(1)你在头部插入nsize成本是 O(size)。所以业务上有个很实用的建议如果你经常需要在列表头部操作把 ArrayList 倒过来用——用add(0, e)不如反过来存或者直接用ArrayDeque。还有一个工程小技巧大批量插入时与其用循环list.add(i, element)不如一次性构建好一个临时数组再用System.arraycopy批量搬移。比如要把一个子列表插到主列表中间先算好目标下标一次性arraycopy比逐次调用 add 减少好多次整段搬移。5.3 和 LinkedList 对比的实测倾向网上随手能搜到很多 LinkedList vs ArrayList 的测试报告但很多测试设计有漏洞没有预热、没有控制 GC、没区分操作类型。根据我的实测经验简单概括一下不同操作的倾向操作ArrayListLinkedList结论末尾追加快快差不多ArrayList 略优按下标随机访问O(1)O(n)ArrayList 完胜按对象查找O(n)O(n)差不多ArrayList 因缓存更优头部插入O(n)整段搬家O(1)改指针LinkedList 胜中间插入O(n)连续内存拷贝O(n)指针定位实际接近ArrayList 往往更快内存占用有预留容量浪费每个节点多 16~24 字节指针数据量小时都还好量大时 LinkedList 明显更费所以不要被“链表插入快”这个结论洗脑。真正让 LinkedList 受益的场景非常窄要么头部高频插入删除要么你手里已经有 Node 引用可以直接做节点级操作但 Java 官方 LinkedList 压根没暴露这种能力。大多数 CRUD 业务里ArrayList 就是综合最优解。6. 面试、复习和考试里的高频考点这些坑别等踩了再学顺序表是面试和笔试的“老熟人”很多题目看起来简单但答好的人不多。这一节我把高频考点整理一下顺带给出答题思路。6.1 顺序表和链表的对比背下来不如理解这是数据结构课和校招面试都必考的对比题。我建议你不仅仅背表格还要能说出“为什么”存储密度顺序表每个元素只存数据本身链表每个节点还要存指针紧凑度更高。空间利用率顺序表有预分配机制可能浪费一部分容量链表按需分配但每个节点有指针开销。访问效率顺序表随机访问 O(1)链表只能顺序访问 O(n)。插入删除顺序表要搬移大量元素链表只需要改指针。但落实到工程实现里顺序表的搬移是内存拷贝链表的“改指针”要先遍历定位前者未必慢。CPU 缓存顺序表连续存储缓存友好链表随机散落缓存不友好。扩容顺序表需要扩容搬移链表天生支持动态增长但这会带来频繁的内存分配。面试官如果追问“什么时候用哪个”你可以给出有层次的回答读多写少、需要随机访问、追求缓存性能用顺序表频繁在头部插入删除、不在乎内存碎片、数据总量不可预知且节点结构复杂可以考虑链表。如果还在用 Java 开发除非你明确需要按节点增删否则优先想到 ArrayList 都不会太离谱。6.2 ArrayList 相关的高频判断题我不给你一长串选择题只说几个最容易让人翻车的点第一个坑Arrays.asList()返回的是不可变长度列表吗它返回的是固定大小的Arrays$ArrayList不能 add 也不能 remove但可以 set。很多人以为它和普通 ArrayList 一样结果 add 的时候直接抛 UnsupportedOperationException然后一脸懵。你要是想得到一个真正的 ArrayList得new ArrayList(Arrays.asList(...))包一层。第二个坑ArrayList.subList()返回的是视图不是副本。你对 subList 做结构性修改比如 add会直接改到原列表并且原列表的 modCount 会变。如果你后续又去操作原列表可能触发 ConcurrentModificationException。这是典型的“视图 vs 副本”混淆很多工作两三年的开发也踩过。第三个坑用 foreach 循环删除元素。for (Integer x : list) { if (x 3) list.remove(x); }这段代码会抛 ConcurrentModificationException因为迭代器检测到 modCount 变化。正确的删除方式是用Iterator.remove()或者从后往前用下标删。第四个坑new ArrayList(100)并不是直接分配 100 个元素的数组。它只是把初始容量设置为 100size 仍然是 0。所以list.size()还是 0list.isEmpty()是 true。初学者经常把这个和“创建包含 100 个默认值的列表”搞混。想创建包含 null 的列表得用循环 add。6.3 一点学习建议和一个扩展话题如果只是为了应付考试顺序表这一章做题就够了。但如果你想把顺序表的价值发挥到最大我建议你做两件事第一对着 JDK 源码自己把ArrayList的核心方法用自己的话讲一遍讲不出来就回去看第二把顺序表作为“垫脚石”去理解更复杂的数据结构——比如ArrayDeque怎么用循环数组实现双端队列HashMap为什么在冲突少的时候用链表转红黑树TREEIFY_THRESHOLD 8以及ArrayList的“连续内存 随机访问”在 JVM 内的对象布局里是怎么体现的。扩展阅读的方向还可以是C 语言里顺序表的实现用结构体 realloc、C 里std::vector的扩容策略、Python 里 list 的“预分配 4 元素起步”策略。你会发现各个语言底层的顺序表实现大同小异核心都是“连续内存 动态扩容 随机访问”。这种跨语言对比会帮助你建立真正的数据结构直觉。最后说一点个人体会。我见过太多人用 ArrayList 用得熟却写不出一个手写顺序表。原因很简单用别人的封装太顺手自己没拆过轮子。但真正到了性能排查、内存调优、设计中间件 API 的时候你对底层数据结构理解有多深决定了你能走多远。顺序表这一课值得从头到尾亲手重写一遍而且别用 IDE 的自动补全。