顺序表这个词，很多人在学数据结构第一周就会遇到，但真正把它搞明白的人，我觉得不多。原因很简单：它长得太像数组了，大家会下意识觉得“数组我早就会了，顺序表有什么好学的”，结果一到手写ArrayList、一聊到ArrayList和LinkedList怎么选，马上露馅。我最早带项目时也这样，概念背了一堆，代码却写不出一版像样的，后来啃源码、自己手写、再回到工程里排bug，才算把这块补扎实。这篇就结合Java顺序表代码来聊顺序表，重点不是背定义，而是把它到底怎么实现、为什么这样实现、实际开发里会踩哪些坑，一次性说透。适合正在学数据结构的人、准备Java面试的人，以及想真正吃透ArrayList源码的开发者参考。
1. 顺序表到底是什么：先搞懂底层的“连续内存”
1.1 从数组到顺序表：顺序表不是新东西
计算机内存是一长串连续编址的存储单元，数组就是对这个模型最直接的使用。顺序表本质上就是数组的一种封装：它依然是“逻辑相邻的元素，在物理地址上也相邻”，只是把数组最让人难受的“定长”问题，通过动态扩容解决掉了。所以别把顺序表当成一个全新的概念，它更像“长了腿的数组”。
Java里最典型的就是ArrayList。你执行new ArrayList<>()时，它在内存里做的事就是申请一块连续空间，内部维护一个Object数组，然后记录当前元素个数size。插入、删除时，如果需要移动元素，就是在这块连续空间里做System.arraycopy。理解了这个底层模型，后面所有顺序表的特性都能推导出来：为什么下标访问快？因为数组头地址加上下标乘以类型大小，一步就能算出目标地址；为什么中间插入慢？因为后面的元素都要往后挪；为什么扩容要拷贝？因为连续空间不够用了，只能另找一块更大的连续空间，把旧数据整体复制过去。
这里有个很容易被忽略的点：逻辑相邻和物理相邻同时成立，是顺序表区别于链表最核心的特征。链表只保证逻辑相邻，物理地址可能分散在任意地方；顺序表则是“座位号”和“内存地址”一一对应。这个差异直接决定了两种结构的适用场景，也决定了你在面试里怎么回答“ArrayList和LinkedList选哪个”这种问题。
1.2 顺序表和链表的定位差异：为什么先学顺序表
很多人有个误解：既然链表插入删除快，是不是实际开发里就该优先用链表？说实话，在JVM里跑出来的结果是另一回事。CPU有缓存，顺序表的元素紧密排列，读取时能很好地命中缓存行，一次内存加载能把好几个元素一起拉进来，遍历速度非常可观。链表节点到处散落，每次访问都可能是一次cache miss，再加上每个节点还要存前后指针，内存占用也更大。所以很多场景下，即便你只是频繁遍历而不做中间插入，LinkedList也没比ArrayList快，反而更慢。
那为什么初学数据结构时，老师普遍先讲顺序表？我觉得有两个原因：第一，顺序表最贴近内存的真实模型，学它等于把“内存是连续编址的”这个概念烙进脑子里，后面学链表、树、图都有帮助；第二，顺序表的代码复杂度相对低，适合作为第一个手写的线性结构。你可以用最小成本体会边界检查、扩容、元素搬移这些通用操作，而这些操作在后来的HashMap扩容、ConcurrentHashMap分段锁设计里，都能看到影子。
所以回答“ArrayList和LinkedList怎么选”时，不要只背“查多选ArrayList，增删多选LinkedList”。真实结论是：绝大多数情况下用ArrayList，除非你能明确证明热点操作是在集合中部高频插入删除，且集合规模很大。顺序表连续内存带来的缓存优势，在工程里往往比理论上的O(1)插入更重要。
2. 手写一个Java顺序表：核心结构设计
2.1 类的基本骨架与字段选择：为什么用Object数组
既然顺序表本质是“可变长数组”，第一件事就是把底层存储定义好。我看过不少手写实现，最典型的错误是直接用E[] data。为什么不直接这么干？因为Java泛型是类型擦除，运行时E并不存在，直接new E[10]编译不通过；就算通过强转搞出E[]，类型信息也会丢失，后续赋值容易出现ClassCastException。官方ArrayList内部就是Object[] elementData，get时再强转成E。手写时也照做，一个是省事，一个是和官方实现保持同款。
public class MyArrayList<E> { private static final int DEFAULT_CAPACITY = 10; private Object[] data; private int size; public MyArrayList() { this(DEFAULT_CAPACITY); } public MyArrayList(int initialCapacity) { if (initialCapacity < 0) { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } data = new Object[initialCapacity]; } public int size() { return size; } public boolean isEmpty() { return size == 0; } }这里有个细节：size和data.length含义完全不同。data.length是容量，表示这块连续内存最多还能放多少；size是当前存了多少元素。很多新手写判断时容易把两者混掉，结果容量还剩很多，却报数组越界。我的习惯是：凡是涉及用户传入下标的地方，都用size来校验；凡是涉及扩容判断的地方，才比较size和data.length。
至于默认容量为什么是10，其实没有特别玄学的原因，更多是历史选择。JDK源码里DEFAULT_CAPACITY=10一直被沿用，后来为了性能还做过懒加载处理，也就是你new ArrayList()时，真实数组先不创建，等第一次add，才以默认容量创建。这样能省掉一批“new完不用”的对象内存，也缩短启动时间。手写版可以不做这个优化，但知道这个发展过程，对读源码有帮助。
2.2 扩容机制：为什么是1.5倍而不是两倍
ArrayList扩容的核心逻辑，简单讲就是：
int oldCapacity = data.length; int newCapacity = oldCapacity + (oldCapacity >> 1); data = Arrays.copyOf(data, newCapacity);oldCapacity >> 1就是除以2，所以新容量是原来的1.5倍。为什么不是两倍？两倍扩容意味着每次扩容后，会留下约等于当前容量大小的空闲空间，如果数据量很大，内存浪费相当可观；而且扩容次数虽然更少，但每次申请连续大空间更容易触发GC。1.5倍是时间与空间的折中：既不会频繁扩容，也不至于浪费太多内存。
还要注意一个前提：扩容时旧数组还在内存里，新数组又申请了一块，两个数组的引用同时存在，等拷贝完成、引用替换后，旧数组才能被回收。如果在老年代里做大数组扩容，很可能触发Full GC。这也是为什么能用ensureCapacity提前指定容量就要提前指定，省的不只是几次拷贝，还有GC压力。用过Android开发的人可能更有感触，内存紧张环境下ArrayList疯狂扩容，卡顿肉眼可见。
追加元素的扩容判断代码可以写成这样：
public boolean add(E e) { ensureCapacity(size + 1); data[size++] = e; return true; } 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); } }这个版本比官方源码简单一些，但关键逻辑都在。特别注意：如果原来数组是空数组，data.length为0，0加(0 >> 1)还是0，会死循环。所以官方对空数组做了特判，newCapacity算出来后如果还是0，会跳到默认容量10。手写时可以把初始化改成data = new Object[DEFAULT_CAPACITY]，绕开这个问题，但实现时要知道有这种边界情况。
2.3 增删改查的完整实现：边界条件才是灵魂
add(int index, E e)指定位置插入，核心是右移一位，空出index位置：
public void add(int index, E e) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } ensureCapacity(size + 1); System.arraycopy(data, index, data, index + 1, size - index); data[index] = e; size++; }这里允许index等于size，表示尾部追加，所以判断是index > size，而不是index >= size。System.arraycopy最后一个参数是移动的元素个数，size - index刚好是index及其之后的所有元素，这个数量在删除时也是一样的，注意不要写错成size。
remove(int index)核心是左移一位：
public E remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } E oldVal = (E) data[index]; int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(data, index + 1, data, index, numMoved); } data[--size] = null; return oldVal; }最后这个data[--size] = null是很多初学手写时最容易漏的。如果只做左移而不把最后一个位置置空，size虽然减了，但旧对象还持有引用，GC没办法回收，集合本身也存在潜在内存泄漏。Java官方ArrayList里同样有一句elementData[--size] = null，这不是废话，是给GC“断引用”的关键操作。
get、set、indexOf相对简单，但同样要检查边界：
public E get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } return (E) data[index]; } public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) { if (data[i] == null) { return i; } } } else { for (int i = 0; i < size; i++) { if (o.equals(data[i])) { return i; } } } return -1; }indexOf里对null单独处理，是因为null无法调用equals，直接调用会NPE。这也是ArrayList允许存null的副作用之一，凡是涉及判等的操作都得兼容null。写到这里你应该发现了，顺序表代码的核心不是算法，而是边界条件的处理：容量、size、下标、null，任何一个考虑不周都会在特定时刻给你埋雷。
3. 关键操作的时间复杂度与参数选择
3.1 增删改查复杂度分析：别只背结论
顺序表的时间复杂度表基本是面试必问，整理如下：
| 操作 | 最好情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| get(int index) | O(1) | O(1) | O(1) |
| set(int index, E e) | O(1) | O(1) | O(1) |
| add(E e) 尾部追加 | O(1)（容量够） | O(1)（摊还） | O(n)（触发扩容） |
| add(int index, E e) | O(1)（尾部） | O(n)（中间） | O(n)（头部） |
| remove(int index) | O(1)（尾部） | O(n)（中间） | O(n)（头部） |
| indexOf(Object o) | O(1)（第一个） | O(n) | O(n) |
为什么get和set是O(1)？因为连续内存，通过数组头地址可以直接计算出目标地址，不需要遍历。为什么尾部add平均是O(1)？因为扩容不是每次add都发生，只有在容量不够时才触发，把扩容的拷贝开销摊到所有add操作上，每次约摊O(1)。这就是摊还分析的思想。
真正要小心的不是平均情况，而是最坏情况。如果你在头部反复插入，比如在一个长度为n的列表头部连续插入n次，第一次要移动n个元素，第二次要移动n+1个，累计是O(n²)的移动量。这个问题在面试里经常以“为什么LinkedList比ArrayList更适合头部插入”出现。但在真实工程里，如果要用ArrayList在头部大量插入，更靠谱的解法是反过来，先用add在尾部收集，最后Collections.reverse，或者直接用ArrayDeque。
3.2 扩容策略的数学推导与实测
很多人好奇，1.5倍和2倍，理论上差距有多大？我们算一笔账。假设初始容量为1，不断往尾部插入，扩容因子为k。每次扩容时，需要把旧数组的元素拷贝到新数组。总拷贝次数大概是：
n × k / (k - 1)
当k=2时，总拷贝约2n；当k=1.5时，总拷贝约3n。也就是说，1.5倍扩容比2倍扩容多了约50%的拷贝量，但每次都少申请一些空间，历史高峰期的内存占用更低。这个权衡没有绝对正确答案，取决于场景：内存充足、追求极致吞吐，可以选2倍；内存敏感、GC敏感，1.5倍更温和。
我实际在本地做过一个简单测试：往ArrayList里add 1000万个元素，然后观察内存和GC。默认1.5倍策略下，Full GC次数明显少于我手动改成2倍扩容后的版本，但插入耗时略高。因为2倍策略申请大数组时会频繁进入老年代，而1.5倍策略单次申请更小，更容易在Young区完成。这个测试不一定代表所有JVM配置，但至少说明：扩容因子不只是数学题，还和垃圾收集器的分代回收机制强相关。
补充一个参数选择经验：如果你能提前知道数据量，调用new ArrayList<>(expectedSize)，或者add前ensureCapacity(expectedSize)。不要创建空列表后慢慢add，否则会经历多次扩容。比如已知要放100万条数据，却new ArrayList<>()默认容量10，过程中至少扩容17次，每次都是一次全量拷贝加新建数组。我见过不少线上OOM，根因就是这种“先小后大”的集合初始化方式。
4. 常见问题与性能陷阱：我把这些坑都踩过
4.1 遍历时删除元素为什么总出问题
有个很经典的问题：下面这段代码为什么删不干净？
List<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(2); list.add(3); for (int i = 0; i < list.size(); i++) { if (list.get(i) == 2) { list.remove(i); } }原因很简单：remove(i)之后，被删除元素后面的所有元素左移一位，i已经指向了原来i+1的位置，下次循环i++后，就会跳过一个元素。所以上面代码删完可能还剩一个2。常见绕过方式有三种：倒序遍历、迭代器remove、removeIf。
// 倒序删 for (int i = list.size() - 1; i >= 0; i--) { if (list.get(i) == 2) { list.remove(i); } } // 迭代器删 Iterator<Integer> it = list.iterator(); while (it.hasNext()) { if (it.next() == 2) { it.remove(); } } // Java 8以后最省事 list.removeIf(n -> n == 2);我推荐优先用removeIf，因为它内部已经处理好了迭代和删除逻辑，代码意图也最清楚。但要注意，removeIf会触发fail-fast机制，如果在遍历过程中有其他线程修改了集合，会抛出ConcurrentModificationException。这其实是保护机制，不是Bug。如果你非要在遍历时做复杂删除逻辑，那也请先搞清楚modCount是怎么回事。
4.2 扩容带来的线程安全问题
ArrayList不是线程安全的，多线程并发add时，出现的问题往往不是“数据错乱”这么简单，而是直接抛ArrayIndexOutOfBoundsException。为什么？扩容判断和赋值是两个步骤：线程A判断size+1大于容量，准备扩容；线程B也判断同样条件，也准备扩容；两个线程可能同时执行Arrays.copyOf，最终某个线程拿着旧的失效数组继续写，或者size还没更新，就会越界。
解决办法不是给ArrayList加一个synchronized关键字就完事。Vector就是这么干的，但它的每个方法都加锁，并发度非常差，已经被官方建议少用了。按场景选：
- 读多写少的场景，用CopyOnWriteArrayList，写时复制，读不阻塞。
- 写多读少的场景，可以用Collections.synchronizedList包装。
- 如果只是初始化阶段并发写，之后不改了，可以先把数据收集到并发结构里，再一次性转换成ArrayList。
还有一个工程细节：即使加了锁，也要避免在遍历过程中进行结构性修改，否则fail-fast照样会抛异常。锁只能保证原子性，不能保证你对集合预期的一致性。
4.3 内存连续性的双刃剑：从性能优势到内存问题
连续内存是顺序表的立身之本，但它带来的不只是优势。第一个问题是扩容时需要一整块够大的连续空间。如果列表已经很大，比如几千万个Integer对象，底层Object数组可能要求几十上百MB连续堆空间。这时候即使堆总内存还有，也不一定能找到这么大块的连续区域，就会频繁触发GC，甚至OOM。解决方案就是上面说的：预估大小、避免频繁扩容、必要时换用链表或分段结构。
第二个问题是引用清理。remove时如果不把最后的位置置null，列表虽然size变小，但该位置的对象仍然被底层数组强引用着，GC就没法回收。这在大列表中会导致可用内存逐渐被“幽灵对象”占满。我曾排查过一个服务，频繁往列表里add再remove，内存却只增不减，最后定位到是自定义集合的remove方法没有断引用。修一行代码，内存曲线直接平了。
第三个问题是subList和toArray的使用要格外谨慎。subList返回的是原列表的视图，不是副本；如果你对subList做add/remove，原列表也会变。toArray()如果传入的数组容量不够，内部也会重新扩容并拷贝，并非零成本。这些细节不处理好，顺序表很容易从“高效”变成“隐性性能黑洞”。
5. 面试题和实战经验：顺序表相关考点怎么答
5.1 高频面试题速查
顺序表这个话题在面试里的密度非常高，常见的考点整理成一张表：
| 面试题 | 考察点 | 建议回答要点 |
|---|---|---|
| ArrayList和数组有什么区别 | 底层认知 | 数组定长，ArrayList动态扩容；ArrayList封装了增删改查和边界检查 |
| ArrayList和LinkedList怎么选 | 结构对比 | 连续内存随机访问快；链表中间插入删除快；实际考虑缓存局部性，默认ArrayList |
| ArrayList扩容机制是什么 | 源码理解 | 1.5倍扩容、Arrays.copyOf、懒加载默认容量10 |
| 为什么实现了RandomAccess | 标记接口 | 说明支持快速随机访问，fori循环比迭代器快 |
| System.arraycopy和Arrays.copyOf区别 | 工具方法 | arraycopy是native方法，copyOf内部调arraycopy；copyOf可同时扩容 |
| 为什么需要fail-fast | 并发安全 | 防止迭代过程中被并发修改，避免脏读，用modCount计数器 |
| 线程安全怎么实现 | 并发编程 | 单方法加锁不够，分场景用包装集合或CopyOnWriteArrayList |
面试回答时，不要只背结论，要往“连续内存”“扩容成本”“边界条件”三个方向上靠。比如问你为什么RandomAccess是标记接口，你可以说：LinkedList没实现RandomAccess，那么fori循环每次get(i)都要从头遍历，复杂度O(n²)，而ArrayList用fori则是O(n)，所以代码里判断list instanceof RandomAccess再决定用fori还是迭代器，是常见优化。这样说，就能把知识点串起来。
5.2 顺序表后续可以怎么扩展：从会用到会用明白
手写顺序表的最大价值，不是让你在生产环境替换ArrayList，而是让你知道官方源码里每一行到底在干什么。基于这个基础，你可以继续做几个小练习：
- 实现Iterator和Iterable，加入modCount，复现fail-fast机制。
- 实现ensureCapacity和trimToSize，体会容量收缩和扩容的对称操作。
- 实现binarySearch，前提是有序，熟悉连续内存上的二分查找终止条件。
- 用顺序表作为底层结构实现栈和队列，理解线性结构如何被上层复用。
- 把顺序表泛型化后接入Comparator，实现sort排序，观察排序稳定性对元素顺序的影响。
我自己在带人时还会加一个需求：给手写顺序表加一个批量插入方法addAll(int index, Collection<? extends E> c)，要求在不频繁扩容的前提下，一次搬移完成插入。这个练习能把ensureCapacity、System.arraycopy、size更新这三件事一次性串起来。做过一遍，再看ArrayList源码的addAll实现，基本就是“原来如此”的感觉。
顺序表这块内容，说简单真简单，说深也能挖很深。我在实际开发中最大的体会是：很多线上性能问题，最终都能追溯到“集合底层结构选错”或“扩容策略不当”。所以碰到ArrayList，别只当它会用就行，抽空把它拆开看看，长远来看绝对划算。
最后一个实用技巧：调试的时候，在IDEA里把ArrayList的elementData和size两个字段加到Watch里，一边add一边观察数组长度和元素位置的变化，你会比读十遍源码都更直观地理解“扩容搬移”到底是什么感觉。就用这个习惯，把顺序表这个专题彻底吃透。
