企业官网建设流程全解析

顺序表这名字听起来像是教材最后才翻的那一页附录，但在实际编码里，它恰恰是很多人自以为会了、一动手就翻车的地方。数组我们天天在用，可真让你用 Java 从零手写一个顺序表，有趣的就来了：扩容因子到底选几倍？size 和 capacity 谁说了算？删除之后要不要缩容？遍历的时候删元素为什么莫名其妙漏了一个？每一个问题都能戳中一批人。这篇“顺序表附录”，就是把我这些年踩过的坑、翻过的源码、总结出的边界细节全部摊开，用 java 顺序表代码把实现拆给大家看，从底层数组一路聊到 ArrayList 的源码逻辑。适合刚学完数据结构想动手写代码的学生，也适合准备面试前快速查漏补缺的开发者。

1. 顺序表附录到底在补什么

1.1 顺序表不是“会写数组”就够的

很多人把顺序表当成数组的同义词，这个印象对也不对。数组只是编程语言提供的基础语法，int[]、Object[]本质上是内存里一段连续的地址描述；而顺序表是构建在数组之上的一层抽象，它额外记录了“当前有多少有效元素”，负责“满了之后自动扩容”，还定义了插入、删除、查找时完整的边界语义。用大白话说，数组是材料，顺序表是把材料加工成能安全使用的成品。

底层依旧是连续内存，逻辑相邻的元素物理地址也相邻，这是顺序表最鲜明的特征，也是它和链表最大的分水岭。我习惯用一个影厅座位的类比：连续内存就像一排连座，座位号就是下标，从 0 号坐到 n-1 号座，你想找第 7 号客人，直接看 7 号座位就行，这就是随机访问 O(1)。链表则像餐厅里的散座，每张桌子只记着下一张桌子的位置，想找第 7 桌，你只能从门口一张一张数过去，访问复杂度自然是 O(n)。这个物理特性决定了顺序表的一生：读快写慢。

但“写慢”要辨证看。中间插入和删除确实要挪动大量元素，因为连续内存不允许中间留一个空位；可尾部追加根本没有挪动成本，均摊下来依然是 O(1)。这也是 ArrayList 作为“动态数组”能横扫日常开发的底气。很多人一听到“数组插入是 O(n)”就把顺序表打入冷宫，其实是没算明白这笔复杂度的账，后面我会单独展开。

1.2 这份附录为什么值得收藏

搜索热词里常年挂着“java顺序表代码”，说明手写顺序表是算法课、面试、工作中的高频刚需。但我翻了翻网上大量示例，大多数只写到“能用”，离“能扛”差得远。比如不少实现根本不做缩容，删除一万条之后数组还占着三万条的内存；再比如直接返回底层数组，外部改一下连内部数据都变了；还有的 indexOf 用==判断对象相等，在字符串场景下坑得人找不着北。

正因为这些细节藏在教程正文之外，我把它们整理成一份附录式的清单：实现顺序表时需要做的设计决策、每个核心操作的边界条件、扩容缩容背后的性能账、以及实战踩坑记录。目标很明确——看完这篇你不仅能手写出一个健壮的 MyArrayList，还能在面试时把“ArrayList 扩容为什么是 1.5 倍”“为什么删除元素最好倒着遍历”这类追问答得明明白白。这份附录不是对教材的重复，而是教材不会写、但实际必踩的那部分。

2. Java顺序表代码：动手之前先定四件事

2.1 初始容量：给 0、给 8 还是给 10

写一个顺序表，第一行就是Object[] data，紧接着要决定初始容量。很多教程直接写new Object[10]，问题不大但不优雅：给 10 意味着哪怕你只存 1 个元素，也白占了 9 个引用位；给 0 又意味着第一次 add 就要扩容，多走一次分配流程。

我个人偏爱懒加载，data = new Object[0]，第一次 add 时统一扩容到默认容量，比如 8。这样零初始化开销最小，真正用到时才分配内存，逻辑上也更清晰。ArrayList 源码选的是默认容量 10，属于历史包袱加综合权衡，你用 8 完全合理，因为 8 是 2 的幂，配合位运算更方便。关键是这个默认值要作为常量隔离出来，别在方法里写魔法数字。实战中如果已知数据规模，比如要存 1000 条日志，构造时直接给容量 1000，能省掉后续多次扩容拷贝，这种“预分配”的小习惯在大数据量下收益很明显。

2.2 扩容因子：1.5 倍背后的算账逻辑

扩容策略是手写顺序表遇到的第一个值得深思的点。固定加 10 个位置？不行，频繁扩容拷贝太贵。每次翻倍？可以，拷贝次数最少，但内存浪费严重：容量 1024 的数组只存 513 个元素，一半空间空置。折中方案就是扩容因子取 1.5，这正好是 Java 标准库的答案：int newCapacity = oldCapacity + (oldCapacity >> 1);。

为什么 1.5 倍比 2 倍更省内存？假设要从容量 1 涨到 1000，翻倍方案最终容量是 1024，1.5 倍方案一路上涨到 1120 左右，虽然最终差距不算离谱，但在大数组场景里，1.5 倍分配更贴近实际使用量。计算里用了右移一位代替除以 2，>>1是纯位运算，比浮点乘除快，这也是源码级优化的味道。

扩容代码里藏着一个容易漏掉的边界：万一minCapacity比 1.5 倍算出来的还大怎么办？比如单次插入一个超大集合，oldCapacity 是 10，newCapacity 是 15，但要塞 20 个元素。标准写法是取两者的较大值，再配合Arrays.copyOf完成数组替换。我给出一段可以直接用的实现：

private static final int DEFAULT_CAPACITY = 8; private void ensureCapacity(int minCapacity) { if (minCapacity <= data.length) { return; } int newCapacity = Math.max(DEFAULT_CAPACITY, data.length + (data.length >> 1)); if (newCapacity < minCapacity) { newCapacity = minCapacity; } data = Arrays.copyOf(data, newCapacity); }

这里的Math.max(DEFAULT_CAPACITY, ...)保证了即使data.length为 0，第一次扩容也能直接到 8，而不是涨到 1 之后又立刻扩容。

2.3 泛型数组的魔法与缺陷

Java 里想写一个泛型的顺序表，第一关就是new T[capacity]编译不过。原因在于类型擦除：JVM 运行时根本不知道 T 是什么，泛型只是编译期概念。所以所有手写实现都会选择Object[]存储，取出来再强转。

@SuppressWarnings("unchecked") private T elementData(int index) { return (T) data[index]; }

强转那一行编译器会提示 unchecked，这很正常，运行时确实无法验证类型。只要保证所有写入都来自外部传入的 T 类型，这个转换就是安全的。理解这点很重要，面试官很喜欢问“为什么不能直接创建泛型数组”，标准答案就是擦除之后 JVM 无法确切知道数组元素类型，直接创建会破坏数组的运行时类型安全检查。这个知识点表面扯的是泛型，内里考的还是对 JVM 运行时的理解，顺序表只是载体。

2.4 缩容策略：删除之后放不放内存

动态扩容大家都会做，缩容却是很多手写实现里缺失的一环。想想这个场景：先 add 一万个元素，再 remove 九千个，数组容量还保持一万，这本身没问题，但如果是长期运行的服务，内存就白白被占着。缩容太激进也不行：删除一个元素就把容量砍一半，下次 add 又要扩容，来回复制，性能雪崩。

业界常用的对策是“滞后缩容”：容量超过默认阈值的前提下，当size < capacity / 4时，才把容量缩为一半。这个 1/4 阈值留出了回旋余地，意味着至少有四分之三的空间被释放了，而下次要触发扩容还得跨过满容量，远不会出现反复横跳。缩容同样要复制数据，所以必须判断size > 0，别把空数组缩没了。

private void shrinkIfNeeded() { int capacity = data.length; if (capacity > DEFAULT_CAPACITY && size < capacity / 4) { data = Arrays.copyOf(data, capacity / 2); } }

你也完全可以选择不缩容，JDK 的 ArrayList 就不缩，设计哲学是“空间换性能”。但如果这是你自己维护的底层容器，尤其要常驻内存的场景，我强烈建议加上缩容。那几行代码换来的内存节省非常可观，尤其在删多增少的业务里。这也是手写容器最有价值的地方——你能根据自己的业务特征定制策略。

3. 增删改查的边界细节：最容易出 bug 的地方

3.1 add：先检查、再扩容、最后移数据

插入是顺序表里逻辑最重的一环，执行顺序不能乱。第一步校验下标：合法范围是 0 到 size 闭区间，也就是说往末尾追加时 index 等于 size 是允许的，size+1 就出界。第二步扩容，确保数组塞得下当前元素。第三步后移元素，从尾部开始往前搬，千万别从头部开始搬，否则后面的元素会被覆盖。用System.arraycopy一步搞定：

public void add(int index, T element) { 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] = element; size++; }

很多初学者担心 System.arraycopy 源和目标重叠会不会出事，这点 Java 官方保证过：这个方法语义上等价于先把源数据复制到临时区域，再写入目标位置，所以重叠是安全的，类似 C 语言的 memmove。这也是 ArrayList 源码里的标准姿势，性能上比手写 for 循环好得多，底层是 native 方法。

这里有一个实操细节：如果 index 是 0，整段数据要搬一位，这是顺序表最慢的场景，O(n)；如果 index 等于 size，System.arraycopy 的长度是 0，什么都不用搬，O(1)。你看，同样叫 add，位置不同性能天差地别。这也是 LinkedList 在特定场景下能赢 ArrayList 的根本原因——只谈复杂度不看位置，都是耍流氓。

3.2 remove：覆盖之后记得置 null

删除和插入正好反过来。第一步校验下标：合法范围是 0 到 size-1。第二步把 index 右侧的元素整体左移一位。第三步非常关键：把末尾位置置为 null，否则数组末尾还会强引用着一个逻辑上已删除的对象，它永远无法被 GC 回收，形成内存泄漏。

public T remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } T old = (T) data[index]; int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(data, index + 1, data, index, numMoved); } data[--size] = null; return old; }

置 null 这条我见过太多人漏掉了。表面上 remove 之后 list.size 变小，外部访问不到那个位置了，可底层数组还引用着对象。如果一个大对象被 remove 后你还希望它尽快被回收，不置 null 它就会一直赖在数组里。ArrayList 源码里同样有data[--size] = null，这不是代码洁癖，是防止内存泄漏的刚需。配合前面的缩容策略，删除时顺手调一下 shrinkIfNeeded 就行。

删除操作还有一个面试常问的点：要不要同步缩容。标准库答案是“不缩”，我们这里是“滞后缩容”，两者的差异恰好能体现你对业务的理解。如果你在做一个消息队列的底层缓冲，峰值过后消息被消费完，不缩容就意味着那些消息占用的对象引用一直留在内存里，长时间运行风险很大。

3.3 get/set/indexOf：访问器里的隐性差别

get 和 set 是顺序表最自豪的操作：按下标直达，O(1)。实现时无非是校验越界后强转返回。可 indexOf 这类查询操作就藏着一个经典陷阱：对象相等比较到底用==还是equals。基本类型和内存地址相同的引用可以用==，但字符串、包装类、自定义对象都应该走 equals。

我之前见过一段代码，直接写if (o == data[i])，在字符串场景里查什么都返回 -1，调了半天才发现是==在作祟。健壮的写法要区分 null 与非 null：

public int indexOf(Object o) { for (int i = 0; i < size; i++) { if (o == null ? data[i] == null : o.equals(data[i])) { return i; } } return -1; }

这样写还有个额外好处：null 也能查。一个列表里可以存几个 null 占位，indexOf(null) 依然能返回正确位置。ArrayList 对 null 元素是开放的，我们也顺着这个设计来。至于 set 方法，注意要先保存旧值、返回给调用者，这是 List 接口的约定。很多手写实现只记得data[index] = value，忘了返回，乍看没问题，一对接接口就漏了。

4. 复杂度与扩容的账：算清楚才敢用

4.1 均摊 O(1) 是怎么算出来的

顺序表尾部添加的复杂度，不能简单看成扩容时 O(n)、平时 O(1)。工程上我们看的是均摊复杂度：把偶尔一次高成本操作的成本，平摊到所有低成本操作头上。假设容量从 1 开始翻倍扩容到 2、4、8……第 k 次扩容需要复制 2^(k-1) 个元素，n 次插入过程中总复制量最多是 2n。所以平均每次 add 分摊下来的成本是常数级，这就是均摊 O(1) 的底气。

这个等比数列求和的结果很直观：哪怕连续 add 一百万次，总复制次数也不会超过两百万次，均摊到每次插入就是常数开销。这也是为什么“数组插入是 O(n)”要辩证看待。尾部插入是均摊 O(1)，这是 ArrayList 日常胜过 LinkedList 的重要原因；头部插入才是真正的 O(n)，因为每次都要挪动全体成员。面试时如果有人说数组插入慢，你要能补充这个区别，这就是认知分水岭。

4.2 顺序表 vs 链表：不是谁替代谁

搞清顺序表的复杂度之后，把它和链表放在一起对比才有意义。按下标随机访问，顺序表 O(1)，链表 O(n)；头部插入，顺序表 O(n)，链表 O(1)；尾部插入，顺序表均摊 O(1)，链表如果是双向且持有尾节点引用也是 O(1)。单看复杂度互有胜负，可现实中 ArrayList 的出场率远超 LinkedList，关键差别在内存布局。

顺序表的连续内存天然具备局部性。CPU 读内存时会整块载入缓存，遍历顺序表相当于顺着缓存一块块命中，速度飞快；链表节点散落在内存各处，每次跳转都可能触发缓存缺失，实际遍历差距能到一个数量级。这些都是大 O 表示法看不出来的现实因素。我的建议很简单：大部分场景无脑选顺序表；只有频繁在头部插入删除、而且节点数量庞大时，才考虑链表。工程选型不能只看复杂度表格，还要看硬件行为，这也是资深开发者和新手拉开差距的地方。

5. 实战踩坑记录：这些 bug 我全踩过

5.1 扩容之后，别人的引用全断了

这是一个非常隐蔽的设计问题。如果我把底层数组通过某个 getData() 方法直接暴露出去，外部代码拿到的是最初的数组引用。等顺序表扩容，内部执行data = Arrays.copyOf(...)，内部变量指向了新数组，可外部还握着旧数组。旧数组里的数据不会坏，但它已经不再是顺序表当前的数据了，更可怕的是旧数据可能已经过时，外部拿过期数据用，谁都不知道。

规避方法很简单：绝不把内部数组直接交给外部。要导出数据，就提供toArray()返回一份拷贝，或者用迭代器。这也是 ArrayList 源码里 toArray 永远返回新数组的原因。如果你发现手写的顺序表在扩容后出现“数据丢失”“修改不生效”这类诡异问题，第一个该查的就是有没有人摸到了内部数组。这类 bug 最容易出现在封装不严的工程代码里，越早意识到越安全。

5.2 边遍历边删除，元素悄悄溜走

这个坑的经典程度不需要多讲。用 for 循环从头到尾删除符合条件的元素，结果删除一个之后，下一个就被跳过了。原因在于 remove(i) 之后，原来 i+1 位置的元素跑到 i 位置，但循环里的 i++ 又把它越过去了。最简单的修正是删除后立刻i--，补偿下标偏移：

for (int i = 0; i < list.size(); i++) { if (条件满足) { list.remove(i); i--; } }

更推荐的写法是倒序遍历，从尾部往前删。因为删除元素只影响它后面的下标，倒着删时前面的元素根本不受影响，不需要任何补偿。如果容器实现了迭代器，用 Iterator.remove() 最省心。面试时如果被问“为什么倒序删除不会漏元素”，你要能说出下标移动的机制：删除 i 位置元素后，受影响的是 i+1 到 size-1，倒序刚好绕开了这片区域。

5.3 浅拷贝和“只读保护”是两码事

手写顺序表时，有人会提供一个 clone 方法。如果直接return new MyArrayList<>(this.data, this.size)，看起来没问题，但这是浅拷贝。data 数组里存的是引用，复制数组只是复制了引用本身，数组里的对象还是同一批。如果外部通过 get 拿到对象后修改了对象字段，原本列表里的对象也变了，因为它们根本就是同一个对象。

要真正做到隔离，得看业务需求。如果只是把顺序表当集合容器，浅拷贝通常是标准行为，Java 集合框架也是浅拷贝，但底层数组必须新开一块，不能让两个实例共享同一个数组。我在实现里特别留意：clone 和 toArray 都返回新数组，内部字段永远指向自己独有的数组。把这条规则写进注释之后，后续维护再也没有踩过相关 bug。所以设计接口时多问一句“这个数组会泄露内部状态吗”，能省掉很多深夜排查。

6. 附录之外：手写一遍胜过看十遍

6.1 亲手实现后，再看 ArrayList 源码像开了天眼

我最初学顺序表也是背代码，真正发生质变是在自己写了三遍之后。第一遍照着抄，第二遍不看参考写，第三遍开始思考那些被隐藏的设计决策。等我再去读 ArrayList 源码，简直像看老朋友：grow 方法里的oldCapacity >> 1，remove 里的numMoved，迭代器里的快速失败机制，每一行都能对上我自己踩过的坑。基本功的价值就在这里——数据结构的实现是有限的知识，但理解它们能帮你直接读懂标准库。

如果你正在准备面试，我强烈建议把顺序表完整手写一遍，再去系统过一遍 ArrayList 源码。你不需要背源码，但你要能说出：为什么 ArrayList 允许 null、为什么扩容用 1.5 倍、为什么迭代中不允许修改结构、为什么 remove 要置 null。这四个问题能答对三个，手写代码这关基本就过了。剩下的，就是经验问题。

6.2 防坑清单，送给准备动手的读者

最后给你一份我压箱底的检查清单。第一，插入和删除前，先确认下标范围，不要拿 capacity 当边界，必须用 size。第二，扩容和缩容本质上都是数组替换，别想着原地操作。第三，System.arraycopy 在处理重叠区域时是安全的，可以放心用。第四，对象查找用 equals，基本类型用 ==，不要一把梭。第五，对外暴露任何内部数组之前，先问一句“它会不会破坏内部状态”。

顺序表不难，难的是把“会写”变成“写对”。这份附录讲了很多标准实现背后的取舍，也记录了不少实操中的坑。你在自己动手实现时如果遇到什么奇怪 bug，欢迎回来对照这篇文章，大概率能找到答案。如果哪一天你能熟练地把扩容、缩容、边界检查这些细节一口气写对，那你对数据结构这门课的理解，就已经超过大多数停留在“背代码”阶段的人了。