顺序表这玩意儿，说难不难，说简单也真不简单。前阵子带一个新人，说到集合框架，他张口就是ArrayList、LinkedList，但一问到底底层怎么存、扩容怎么扩、删除一个元素背后发生了什么，就答不上来了。后来我让他自己用数组徒手实现一个顺序表，写完那一下午，他自己都说“感觉以前用集合就跟背答案似的，现在才算真懂了”。这篇文章就把当时我们聊的内容整理出来，从为什么值得自己写一遍，到每个方法怎么设计、扩容怎么调参、迭代时为什么容易踩坑，全部分享给正在学数据结构，或者想补基础的同学。
我自己带过好几个项目组，发现一个规律：Java基础再熟，如果顺序表这种最基础的线性结构没亲手写过，后面接触队列、栈、哈希表、树这些，总会有点飘。所以这篇文章适合所有正在啃数据结构的人，也适合工作了一两年但想回头把地基打牢的同学。咱们不聊虚的，直接从一个可运行、可调试的代码出发，把顺序表从头到尾实现一遍。
1. 动手之前，先搞清楚顺序表到底解决了什么问题
1.1 顺序表本质是什么
顺序表（Sequential List）就是线性表的顺序存储结构，底层用一段连续的内存空间依次存放数据元素。说人话就是：用数组来实现一个可以动态增删元素的列表。Java里的ArrayList就是最典型的顺序表实现，但它毕竟封装好了，你平时调add、remove感觉不到里面发生了什么。自己写一遍，才算把这层窗户纸捅破。
为什么管它叫“顺序表”？因为逻辑上相邻的元素，在物理存储空间里也是相邻的。数组在内存里就是一段连续的地址空间，按下标访问任意元素的时间复杂度是O(1)，这是它最大的本钱。但同时，连续存储也带来了原罪：中间插入一个元素，要把后面的元素全部往后挪；删除一个元素，要把后面的元素全部往前挪。挪一次两次没事，频繁在头部插入删除，性能就崩了，这正是顺序表和链表各自适用的分水岭。
1.2 为什么非要自己实现一遍，而不是直接用ArrayList
很多人觉得这个练习多余，生产环境里直接用ArrayList不就行了嘛。但我的看法不一样。第一，面试的时候，ArrayList源码几乎是必考点，你背了扩容因子、背了System.arraycopy，不如自己真写一遍记得牢。第二，理解顺序表的操作代价，你才能在日常开发里做出合理选型。比如明知道某个接口要频繁在列表头部插入数据，你还用ArrayList，那在数据量大的时候就是自己给自己埋雷。第三，自己实现一个最简单的线性结构，是后面理解队列、栈乃至哈希表的基础，那几样东西底层全是数组加指针、数组加链表的组合拳。
我在某公司做技术方案评审的时候，见过不少把ArrayList当万能容器用的场景。数据量大到一定级别，又涉及频繁中间插入，线上就会CPU飙升，其实就是数组搬移在作怪。如果我们一开始就清楚顺序表搬移元素的代价，很多事故是可以提前避免的。
1.3 实现之前先定设计目标
我让新人写之前，先定了几个目标，保证不会写着写着就跑偏：
- 支持泛型，不局限于存int或String一种类型。
- 支持动态扩容和缩容，不能写一个固定容量的数组就完事。
- 实现增、删、改、查、遍历、判空、清空等常用方法，接口风格对齐ArrayList的常用方法。
- 代码要能直接编译运行，通过简单的测试用例验证。
泛型这块要提一下，很多初学者写顺序表喜欢直接用Object数组，然后强转。这样能用，但用起来很难受，取出来的对象都得自己强转，编译期检查也失效了。既然Java有泛型，我们直接用泛型来写，用起来更舒服，也更接近实际开发习惯。
2. 核心设计：成员变量、构造方法、扩容机制
2.1 成员变量怎么定
一个顺序表，核心就三样东西：
private Object[] elementData; private int size; private static final int DEFAULT_CAPACITY = 10;elementData是真正存数据的数组，size记录当前元素个数，DEFAULT_CAPACITY是默认初始容量。这里有个细节，为什么要用Object[]而不是E[]？因为Java泛型擦除机制，直接new E[10]在编译期是过不去的，除非用Array.newInstance反射，但那样反而麻烦。稳妥做法就是底层用Object[]，方法签名和返回值都用E，存取的时候做类型转换。
size变量特别重要，它是逻辑长度和数组长度的分水岭。数组长度是elementData.length，代表当前容量；size是已经存了多少有效元素。effective element只在前size个位置，后面都是预留的空位。我在代码里凡是用到length的地方，都特别留意描述的是容量还是有效个数，写错一个，bug就不远了。
2.2 构造方法怎么设计
至少要有两个构造方法：无参构造，使用默认容量；带初始容量的构造，允许用户指定初始大小。还有一个是用户传入一个集合直接转成顺序表，这个先不做，免得把核心逻辑搞混。
public MyArrayList() { this(DEFAULT_CAPACITY); } public MyArrayList(int initialCapacity) { if (initialCapacity < 0) { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } elementData = new Object[initialCapacity]; size = 0; }注意那个小于0的判断。有些新手会写成if (initialCapacity == 0)，其实容量为0是合法的，比如你一开始就知道存不了几个元素。但小于0就是非法参数了，必须抛异常。这个习惯也体现在其他方法里，凡是不符合预期的参数，尽早抛出异常，比让程序带病运行好得多。
2.3 扩容为什么是1.5倍而不是2倍
Java的ArrayList扩容时是oldCapacity + (oldCapacity >> 1)，也就是1.5倍。有人问为什么不用2倍？用2倍扩容，数组增长速度太快，可能白白浪费内存；用1.5倍，空间和时间上更均衡。如果只增长一个固定值，比如每次加10，那频繁插入时扩容次数太多，每次都涉及整个数组的复制，均摊成本高得吓人。
实现扩容的方法：
private void ensureCapacity(int minCapacity) { if (minCapacity > elementData.length) { int newCapacity = elementData.length + (elementData.length >> 1); if (newCapacity < minCapacity) { newCapacity = minCapacity; } elementData = Arrays.copyOf(elementData, newCapacity); } }这里有个细节容易忽略：如果当前容量是0（比如用户new MyArrayList(0)），那么old + (old >> 1)结果还是0，如果不加判断，扩容就永远扩不上去。所以上面加了if (newCapacity < minCapacity)兜底，确保至少能装下minCapacity个元素。这个兜底逻辑在实际源码里也是存在的，而且是个很经典的防御性写法。
2.4 缩容要不要做
缩容是个有争议的话题。ArrayList默认不缩容，避免频繁扩容缩容导致性能抖动。但作为练习，我们可以实现一个trimToSize方法，把数组容量压缩到刚好等于size，在有大量元素被删除、想释放内存的场景下，这个方法很有用。
public void trimToSize() { if (size < elementData.length) { elementData = Arrays.copyOf(elementData, size); } }注意缩容后数组长度等于size，如果后面又要add，就得扩容，所以缩容不能频繁调用。我一般只提供方法，不在remove里自动缩容。如果你在remove里每次删完都缩容，遇到反复增删的场景，性能会惨不忍睹，这是很多人容易踩的坑。
3. 核心操作的实现：增删改查逐个击破
3.1 添加元素：尾部添加和指定位置插入
先说最简单的尾部add：
public boolean add(E element) { ensureCapacity(size + 1); elementData[size++] = element; return true; }先保证容量，再存元素，然后size加一。三行代码，但顺序不能乱。如果你先size++再存元素，就会把元素存到下标为size的位置，后面读取的时候会读到错位的数据。这是个很低级但新手特别容易犯的错。
指定位置插入稍微复杂一点：
public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacity(size + 1); // 将 index 及之后的元素整体后移一位 System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } private void rangeCheckForAdd(int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } }注意index的范围是0到size，等于size时相当于尾部插入，所以校验条件是index > size，而不是index >= size。这里也是老生常谈的边界问题。System.arraycopy是Java里搬移数组的高效方式，它走的是native方法，比自己写for循环一个个赋值快得多。所以实现顺序表的时候，凡是涉及数组搬移，我都优先用它。
3.2 删除元素：remove方法和内存泄漏隐患
删除有两种：按下标删，按元素内容删。按下标删的核心是把后面的元素往前挪，然后置空最后一个位置，最后size减一：
public E remove(int index) { rangeCheck(index); E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(elementData, index + 1, elementData, index, numMoved); } elementData[--size] = null; return oldValue; }这里最关键的一行就是elementData[--size] = null。为什么要置null？如果不置空，数组最后一个位置仍然持有对象的引用。假设存的是一个很大的对象，你remove之后，这个对象明明已经逻辑上不存在了，但仍然被数组引用着，GC根本回收不掉。这在ArrayList源码里叫“清空引用帮助GC”，面试时经常被问到。作为工程师，我们要养成好习惯，删了就断干净。
按元素内容删除，就遍历一遍找到第一个相等的元素，然后按下标删除。这里需要注意null的处理，如果你remove(null)，逻辑上应该能删掉第一个null，不能让NPE炸掉。代码里用element == null ? o == null : element.equals(o)这样的写法来兼容null。
3.3 查找与修改：get、set、indexOf
get和set非常简单，关键是边界检查：
public E get(int index) { rangeCheck(index); return elementData(index); } public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }set方法返回旧值，这个设计和Map的put返回旧值一样，好处是调用方如果想保留旧状态，不用自己提前存一份。我在代码设计时一直强调：方法返回值不要随便定，对齐主流容器的习惯能让使用者少踩坑。
indexOf和contains是一对，核心是遍历找第一个匹配项：
public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) { if (elementData[i] == null) { return i; } } } else { for (int i = 0; i < size; i++) { if (o.equals(elementData[i])) { return i; } } } return -1; }注意遍历的条件是i < size，不是i < elementData.length。如果把遍历范围扩大到整个容量，你会把那些已经删除但还没被覆盖的脏数据一起遍历出来，结果自然就不对了。这种精细的区别很难靠背代码记住，只有自己写一遍、断点调试一遍，才会有肌肉记忆。
3.4 clear和toString这些容易被忽视的方法
clear不能只是size = 0。想想看，如果只把size置0，但数组里仍然持有所有元素引用，这些对象一样不会被GC回收。所以clear也要遍历置null：
public void clear() { for (int i = 0; i < size; i++) { elementData[i] = null; } size = 0; }toString方法虽然不是核心功能，但对调试特别有帮助。我写顺序表一定会带上toString，否则打印出来就是一串[Ljava.lang.Object;@hashcode，没法看。实现上遍历有效元素，拼成[a, b, c]这样的格式。注意不要用字符串拼接大法，用StringBuilder就好。这个方法实现很简单，但对日常查问题价值极大，算是我个人写数据结构的习惯。
4. 遍历相关的坑：迭代器和结构性修改
4.1 为什么不建议用get(i)遍历
有一种很朴素的遍历方式：for (int i = 0; i < list.size(); i++) { list.get(i); }。小数据量没问题，但get每次都要做边界检查，频繁调用有一定开销。更重要的是，它不符合面向对象的封装思想。ArrayList等容器都提供了Iterator模式，让使用者不关心内部结构也能安全遍历。
4.2 Fail-Fast机制是怎么回事
Java集合里有个大名鼎鼎的fail-fast机制：在迭代过程中，如果容器结构被修改了（比如add或remove），迭代器就会在下一次next的时候抛出ConcurrentModificationException。这个机制靠一个modCount字段实现，每次结构性修改都会modCount++，迭代器初始化时记录expectedModCount = modCount，每次迭代都校验两者是否一致。
我们自己实现顺序表时，也完全可以引入这个机制。在迭代器内部持有expectedModCount，调用next、remove时先检查：
private class Itr implements Iterator<E> { int cursor; int expectedModCount = modCount; public boolean hasNext() { return cursor != size; } public E next() { checkForComodification(); int i = cursor; if (i >= size) { throw new NoSuchElementException(); } cursor = i + 1; return elementData(i); } private void checkForComodification() { if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } }这里有个经验之谈：迭代器里的remove方法，删除元素后要把cursor回退一位，然后把expectedModCount同步成最新modCount，否则删完再next就会误报并发修改。很多人实现remove时会忘记同步expectedModCount，导致明明是自己内部修改，却抛出并发异常。这个问题我在新人的代码里见过不止一次。
4.3 为什么不要在foreach里删除元素
就算你不自己实现迭代器，日常用Java的foreach遍历时删除元素，同样会触发fail-fast。因为foreach本质上就是语法糖，底层用的就是迭代器。很多同学在foreach里调用list.remove(o)，期待删掉目标元素，结果抛了ConcurrentModificationException。
如果你要在遍历时删除元素，正确的做法是使用Iterator的remove方法，或者倒序for循环。倒序for循环的好处是删除元素后，后面的元素往前移，但你已经处理过那些位置了，不会漏掉元素。正序for循环删除时，因为元素搬移，会导致跳过下一个元素，这是个非常隐蔽又常见的bug。
5. 常见问题速查表与调试技巧
5.1 高频问题整理
把实现顺序表过程中最常遇到的几个问题整理成一张速查表，方便大家排查：
| 问题现象 | 根因分析 | 解决方案 |
|---|---|---|
| 存入N个元素后，add第N+1个报数组越界 | 没有扩容或扩容逻辑判断错误 | 插入前调用ensureCapacity(size + 1) |
| 删除元素后，列表末尾还能get到旧值 | 删除时没有置空尾部引用 | remove和clear中设置elementData[--size] = null |
| 指定位置插入后，数据顺序错乱 | arraycopy的源位置和目标位置写反 | 牢记：从index开始，整体后移一位 |
| 用foreach删除元素时抛并发修改异常 | 迭代器检测到modCount变化 | 改用Iterator.remove或倒序遍历 |
| 传入容量为负数时没有报错 | 构造方法缺少参数校验 | 增加IllegalArgumentException抛出逻辑 |
| 扩容后仍不够装 | 新容量计算后小于minCapacity | 用if (newCapacity < minCapacity)兜底 |
5.2 我调试时的几个土办法
第一，打印size和elementData.length两个值。很多问题一看这两个值，立刻就能判断是逻辑长度和物理容量没分清。第二，每个核心方法写完之后，立刻写几行对应的测试代码，不要攒到最后再测。第三，善用IDE的调试器，在System.arraycopy前后各加一个断点，观察数组内容的变化。说实话，数据结构这种东西，光看代码很难形成直觉，必须亲眼看到数据搬移的过程，才会真正记住为什么插入操作是O(n)。
我还习惯在每次插入和删除后，自己跑一遍全遍历，打印出当前所有有效元素。这个操作虽然笨，但能最快暴露下标错位问题。比如在头部插入一个元素，正常打印结果应该比原来的遍历结果多一个且开头多出目标元素，如果打印出来末尾多了一个奇怪的值，多半是size管理出了问题。
5.3 性能对比：顺序表在什么场景下占优
最后说下选型。顺序表在按下标随机访问的场景下完胜链表，因为数组支持O(1)随机访问，链表要O(n)从头遍历。顺序表在尾部添加元素时均摊时间也是O(1)，只有在扩容时才需要复制整个数组，均摊下来依然很划算。但顺序表在头部插入和中间插入上，时间复杂度是O(n)，链表只需O(1)（前提是已经找到插入位置）。
所以日常判断标准很简单：
- 频繁按索引取值、主要从尾部追加数据：用顺序表。
- 频繁在头部或中间插入删除，访问需求低：考虑链表。
- 两者都有：用双端队列或者其他混合结构，别硬选。
我之前在某跨平台系统的消息队列模块里做过一次优化，原先用顺序表存待推送的消息，后来消息量涨上去，头部消费的效率越来越低，换成链表之后，虽然随机访问变差了，但整体吞吐明显提升。这就是对数据结构特性有概念带来的直接收益。
6. 实操心得与后续扩展方向
6.1 写完基础版之后，我建议再加点料
如果你照着上面的思路把基础版顺序表写完并且测试通过，我建议不要停在这里，往下做三个扩展练习。
第一个是增加一个subList方法，返回原列表某个区间的视图。视图的意思是，对subList的修改会直接反映在原列表上，这对理解“视图与快照”的区别很有帮助。
第二个是给列表增加一个reverse方法，实现原地反转。这个练习看起来简单，但对指针、下标的理解非常有用。反转过后的顺序表，你能直观看到数组搬移是怎么发生的，也能顺便想想，如果不用额外空间，只靠交换元素，要怎么实现。
第三个是尝试写一个支持线程安全的版本，也就是把增删改查涉及结构性修改的方法全部加上synchronized，或者使用读写锁。这个练习会让你意识到，并发安全不是简单加个锁就完事，读操作和写操作之间还有很多细节要考虑。
6.2 我个人踩过的几个真坑
有个很典型的错误，我自己刚学的时候也犯过：在扩容的时候直接把原数组长度翻倍，然后忘了处理原来size是0的情况，结果数组永远是空数组，加多少元素都报越界。后来我总结出一个经验：凡是涉及0值运算和负数运算的业务代码，一定要专门想想边界条件，别指望常规逻辑能自动覆盖。
另外一个让我印象很深的坑，是删除元素后没有置null。我在一个模拟项目里，自己实现了一个类似ArrayList的容器，临时代码没有置null，跑了一段时间后，内存占用居高不下，排查了很久才发现是大量删除的对象一直被数组引用着，GC根本没法回收。从那以后，我写任何容器类，凡是删除逻辑，必置null。
6.3 一句话总结这条学习路径
顺序表是整个数据结构学习的起点，但它不只是考试题，它是ArrayList这类每天都要用的工具的内部原理。花一个下午亲手实现一遍，搞懂扩容、搬移、迭代器、modCount这些机制，往后你用任何集合心里都会更有底。毕竟原理这东西，听别人讲十遍，不如自己写一遍来得实在。
我个人现在的习惯是，每接触一种新的数据结构，都会在本地用一个最简单的实现把它还原出来，然后跑一组边界测试，比如空列表、单元素列表、满容量列表、删除到空列表。这套动作做完，我才会放心在项目里使用它。希望这篇文章也能帮你养成这个习惯。
