顺序表这名字听起来像是教材最后才翻的那一页附录但在实际编码里它恰恰是很多人自以为会了、一动手就翻车的地方。数组我们天天在用可真让你用 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翻倍方案最终容量是 10241.5 倍方案一路上涨到 1120 左右虽然最终差距不算离谱但在大数组场景里1.5 倍分配更贴近实际使用量。计算里用了右移一位代替除以 21是纯位运算比浮点乘除快这也是源码级优化的味道。扩容代码里藏着一个容易漏掉的边界万一minCapacity比 1.5 倍算出来的还大怎么办比如单次插入一个超大集合oldCapacity 是 10newCapacity 是 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 是允许的size1 就出界。第二步扩容确保数组塞得下当前元素。第三步后移元素从尾部开始往前搬千万别从头部开始搬否则后面的元素会被覆盖。用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 等于 sizeSystem.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 与非 nullpublic 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) 的底气。累计插入次数需要扩容的次数累计复制元素数10~10~1211423837nlog n不超过 2n这个等比数列求和的结果很直观哪怕连续 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) 之后原来 i1 位置的元素跑到 i 位置但循环里的 i 又把它越过去了。最简单的修正是删除后立刻i--补偿下标偏移for (int i 0; i list.size(); i) { if (条件满足) { list.remove(i); i--; } }更推荐的写法是倒序遍历从尾部往前删。因为删除元素只影响它后面的下标倒着删时前面的元素根本不受影响不需要任何补偿。如果容器实现了迭代器用 Iterator.remove() 最省心。面试时如果被问“为什么倒序删除不会漏元素”你要能说出下标移动的机制删除 i 位置元素后受影响的是 i1 到 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 1remove 里的numMoved迭代器里的快速失败机制每一行都能对上我自己踩过的坑。基本功的价值就在这里——数据结构的实现是有限的知识但理解它们能帮你直接读懂标准库。如果你正在准备面试我强烈建议把顺序表完整手写一遍再去系统过一遍 ArrayList 源码。你不需要背源码但你要能说出为什么 ArrayList 允许 null、为什么扩容用 1.5 倍、为什么迭代中不允许修改结构、为什么 remove 要置 null。这四个问题能答对三个手写代码这关基本就过了。剩下的就是经验问题。6.2 防坑清单送给准备动手的读者最后给你一份我压箱底的检查清单。第一插入和删除前先确认下标范围不要拿 capacity 当边界必须用 size。第二扩容和缩容本质上都是数组替换别想着原地操作。第三System.arraycopy 在处理重叠区域时是安全的可以放心用。第四对象查找用 equals基本类型用 不要一把梭。第五对外暴露任何内部数组之前先问一句“它会不会破坏内部状态”。顺序表不难难的是把“会写”变成“写对”。这份附录讲了很多标准实现背后的取舍也记录了不少实操中的坑。你在自己动手实现时如果遇到什么奇怪 bug欢迎回来对照这篇文章大概率能找到答案。如果哪一天你能熟练地把扩容、缩容、边界检查这些细节一口气写对那你对数据结构这门课的理解就已经超过大多数停留在“背代码”阶段的人了。