顺序表这个词很多人在学数据结构第一周就会遇到但真正把它搞明白的人我觉得不多。原因很简单它长得太像数组了大家会下意识觉得“数组我早就会了顺序表有什么好学的”结果一到手写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[] elementDataget时再强转成E。手写时也照做一个是省事一个是和官方实现保持同款。public class MyArrayListE { 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_CAPACITY10一直被沿用后来为了性能还做过懒加载处理也就是你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为00加(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个元素第二次要移动n1个累计是O(n²)的移动量。这个问题在面试里经常以“为什么LinkedList比ArrayList更适合头部插入”出现。但在真实工程里如果要用ArrayList在头部大量插入更靠谱的解法是反过来先用add在尾部收集最后Collections.reverse或者直接用ArrayDeque。3.2 扩容策略的数学推导与实测很多人好奇1.5倍和2倍理论上差距有多大我们算一笔账。假设初始容量为1不断往尾部插入扩容因子为k。每次扩容时需要把旧数组的元素拷贝到新数组。总拷贝次数大概是n × k / (k - 1)当k2时总拷贝约2n当k1.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 遍历时删除元素为什么总出问题有个很经典的问题下面这段代码为什么删不干净ListInteger 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已经指向了原来i1的位置下次循环i后就会跳过一个元素。所以上面代码删完可能还剩一个2。常见绕过方式有三种倒序遍历、迭代器remove、removeIf。// 倒序删 for (int i list.size() - 1; i 0; i--) { if (list.get(i) 2) { list.remove(i); } } // 迭代器删 IteratorInteger 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判断size1大于容量准备扩容线程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怎么选结构对比连续内存随机访问快链表中间插入删除快实际考虑缓存局部性默认ArrayListArrayList扩容机制是什么源码理解1.5倍扩容、Arrays.copyOf、懒加载默认容量10为什么实现了RandomAccess标记接口说明支持快速随机访问fori循环比迭代器快System.arraycopy和Arrays.copyOf区别工具方法arraycopy是native方法copyOf内部调arraycopycopyOf可同时扩容为什么需要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一边观察数组长度和元素位置的变化你会比读十遍源码都更直观地理解“扩容搬移”到底是什么感觉。就用这个习惯把顺序表这个专题彻底吃透。