← 课程目录 🚀 从零到一
📐 学习维度 阶段1 · 第4章 常用 API 与集合入门 🚀 从零到一 📚 课程目录 🏠 首页 🛤️ 学习路径

4.3 手写 ArrayList 与 LinkedList:拆开看看内部

审校 2026-09-26 · 素材来源:老wiki「手写ArrayList/手写LinkedList」(底稿改写)
📑 本篇章节导航 (共12节,点击直达)
ArrayList 的真身:会搬家的数组LinkedList 的真身:手拉手的节点链表随机访问:从第一条数起对比与选型被问选型怎么答才像懂了先补课:O 记号到底是什么均摊:尾部 add 为什么敢标 O(1)ArrayDeque:一个类顶两个用为什么不干脆全用链表手写完的检验清单踩坑清单一句话总结

用了两年 ArrayList,被问「它为什么能自动变长」却答不上来。最好的回答方式:自己写一个。两个迷你实现加起来不到百行,写完集合的选型直觉直接换代。

ArrayList 的真身:会搬家的数组

ArrayList 内部就是一个 Object 数组加一个 size 计数器。装满了怎么办?换个大数组,把旧家当全体搬过去:


class MyArrayList {
    private Object[] data = new Object[10];
    private int size = 0;              // 已装个数,不是数组长度

    public void add(Object e) {
        if (size == data.length) grow();   // 满了先搬家
        data[size++] = e;                  // 放进去,size 后移
    }

    private void grow() {
        data = Arrays.copyOf(data, data.length + (data.length >> 1));
    }
}

grow 那行右移一位就是除以二,新容量即 1.5 倍。查询和删除是另外两员主力:


public Object get(int index) {
    if (index >= size) throw new IndexOutOfBoundsException();
    return data[index];               // 下标直取:O(1)
}

public void remove(int index) {
    System.arraycopy(data, index + 1, data, index, size - index - 1);
    data[--size] = null;              // 尾巴置 null,帮 GC
}

三个设计点值得咂摸:

JDK 真货多了优化(懒初始化、指定容量构造),骨架与此无异。

LinkedList 的真身:手拉手的节点


class MyLinkedList {
    private static class Node {              // 静态内部类(3.4 节刚学的用法)
        Object item; Node prev; Node next;   // 双向手拉手
        Node(Node prev, Object item, Node next) {
            this.prev = prev; this.item = item; this.next = next;
        }
    }

    private Node first, last;
    private int size = 0;
}

节点是个三格包裹:一格装货,两格攥着前后邻居的手;整条链表只记着头尾两个门牌。addLast 把新节点接到尾巴:


public void addLast(Object e) {
    Node l = last;
    Node n = new Node(l, e, null);   // 新节点接在尾巴后面
    last = n;
    if (l == null) first = n;        // 空表:它既是头也是尾
    else l.next = n;
    size++;
}

头插和头删是对称动作,指针照着镜像接一遍:


public void addFirst(Object e) {         // 头插
    Node f = first;
    Node n = new Node(null, e, f);
    first = n;
    if (f == null) last = n; else f.prev = n;
    size++;
}

public Object removeFirst() {
    Object v = first.item;
    first = first.next;                  // 头节点直接断开
    if (first == null) last = null; else first.prev = null;
    return v;
}

头尾增删只是改两个指针,O(1)——这是它唯一的看家本领。

链表随机访问:从第一条数起


public Object get(int index) {
    check(index);
    Node x = first;
    for (int i = 0; i < index; i++) x = x.next;   // 一节节数过去
    return x.item;                                 // O(n)!
}

真实 LinkedList 做了个小优化(index 在前半就从 first 数,后半从 last 倒着数),但本质还是数。list.get(i) 在链表上是隐藏的循环——外面再套个 for 就是循环套循环,数据一大数据结构课白学。

对比与选型

操作ArrayListLinkedList
get(i) 随机访问O(1) 直取O(n) 逐节数
尾部 add均摊 O(1)O(1)
头部插入O(n) 全体搬家O(1) 改指针
中间插入搬家 O(n)数过去 O(n) + 改指针
每个元素内存紧凑连续每个多 prev/next 两指针

注意中间插入那行:链表也快不过数组——「找到那个位置」本身就是 O(n)。所以结论干脆:默认 ArrayList;只有「当队列用、只在头尾进出」(如任务队列)才考虑 LinkedList 或 ArrayDeque。

表格不用背,记两个画面就够:ArrayList 是电影院连排座位,坐满了服务员开一排更大的厅把人整体请过去;LinkedList 是排队的人互相牵手——中途插队容易,但找第 100 个人得从队头一个个问过去。

被问选型怎么答才像懂了

「ArrayList 还是 LinkedList」,满分答法分三层:先给结论——绝大多数场景 ArrayList;再给理由——随机访问 O(1)、内存连续缓存友好,链表找位置 O(n) 拖后腿;最后补边界——头尾频繁进出的队列场景才考虑链表或 ArrayDeque。结论、理由、边界——这个三层骨架是答一切选型题的模板,往后数据库选型、缓存选型,全是同一副腔调。

先补课:O 记号到底是什么

表格里的 O(1)、O(n) 是时间复杂度——数据量上涨时耗时的涨法。O(1) 恒定:数组按下标取值,一万个元素也是一步到位。O(n) 线性:链表找第 i 个,有多少节数多少节。O(n²) 平方:循环套循环,数据翻十倍、耗时翻一百倍。

它不问「具体几毫秒」,只问「涨得有多凶」。这正是选容器的依据:业务怎么访问数据,决定哪种涨法能接受。排序记一档:常数最好,对数(红黑树的 O(log n))次之,线性要警惕,平方基本是事故。

均摊:尾部 add 为什么敢标 O(1)

搬家明明是 O(n),凭什么说尾部添加是 O(1)?答案是均摊:搬一次家的成本,被之前十几次免搬的添加分摊了。像手机套餐:每天月租很便宜,偶尔一天国际漫游贵一次,拉平到每天看依然便宜。准确说法叫「均摊 O(1)」——偶尔贵一次,长期常数级。这个思路在动态数组、StringBuilder 扩容、HashMap 搬格子(rehash)里全是一个模子,第 6 章讲 HashMap 时它还会出场。

ArrayDeque:一个类顶两个用

4.2 说 ArrayDeque 既当栈又当队列,看完实现就明白凭什么:内部是循环数组,两头各留指针。当栈用,push 和 pop 操作同一头;当队列用,offer 一头进、poll 另一头出。两头操作全是挪指针,都是 O(1)。再加上它没有链表的节点开销、内存连续对 CPU 缓存友好——单线程要栈或队列,闭眼选它。

为什么不干脆全用链表

新手容易觉得链表「插入快」就该全用它。但数据结构是组合拳:找位置 O(n) 拖后腿,每个节点多付两个指针的内存,散落的地址还让 CPU 缓存频繁失效。连续内存对现代 CPU 极度友好——顺序扫一遍数组比顺链数一遍快好几倍,不是玄学,是缓存局部性。所以工程默认连续存储,链表只在「频繁头尾进出」这道窄门里赢。

手写完的检验清单

合上代码问自己五个问题:size 和数组长度为什么分开记?grow 为什么 1.5 倍?get 为什么用 size 判界?remove 为什么要置 null?链表 get 为什么慢?全能秒答,这两个容器就算拆明白了。以后再被问「ArrayList 默认容量、扩容几倍」,你答的是理解,不是背书。

踩坑清单

一句话总结

ArrayList 是会按 1.5 倍搬家的数组,随机访问 O(1);LinkedList 是双向手拉手的节点链,头尾 O(1) 但找位置要数——默认 ArrayList,纯头尾操作才轮到链表。