前言

上一篇我们学习了 HashMap 的底层原理。

这一篇继续学习 Java 集合中的高频面试题：ArrayList 和 LinkedList 的区别。

这个问题看起来很基础，但面试时经常会继续追问：

• ArrayList 底层是什么？
• LinkedList 底层是什么？
• 为什么 ArrayList 查询快？
• 为什么 LinkedList 插入删除不一定总是快？
• ArrayList 扩容机制是什么？
• 实际开发中更推荐用哪个？

很多人背的是：

ArrayList 查询快，增删慢；LinkedList 查询慢，增删快。

这句话不能说错，但它不够完整。

因为 LinkedList 的增删是否真的快，要看你有没有先找到要操作的位置。如果每次都要从头遍历找位置，那它不一定比 ArrayList 快。

这一篇我们就把 ArrayList 和 LinkedList 从底层结构、查询、插入、删除、扩容和实际使用场景完整梳理一遍。

一、先给结论

可以先记住下面这张表：

对比点	ArrayList	LinkedList
底层结构	动态数组	双向链表
查询效率	高，支持下标随机访问	低，需要从头或尾遍历
尾部添加	较快，容量够时直接添加	较快，直接挂到尾部
中间插入	需要移动元素	找到位置后改指针
中间删除	需要移动元素	找到位置后改指针
内存占用	相对较少	相对较多，因为每个节点要保存前后指针
是否线程安全	不安全	不安全
常见使用	更常用	特定队列、链表场景

简单来说：

ArrayList 底层是数组，适合查询多、遍历多的场景。
LinkedList 底层是双向链表，适合频繁在头尾插入删除的场景。
实际开发中，大多数情况下优先使用 ArrayList。

二、ArrayList 是什么？

ArrayList 是 Java 中最常用的 List 实现类之一。

它的特点是：

1. 有序
2. 可以重复
3. 可以通过下标访问
4. 底层是数组
5. 查询速度快
6. 线程不安全

基本使用：

import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();

        list.add("Java");
        list.add("MySQL");
        list.add("Redis");

        System.out.println(list.get(0));
        System.out.println(list.get(1));
        System.out.println(list.get(2));
    }
}

输出：

Java
MySQL
Redis

这里：

list.get(0)

就是根据下标查询元素。

这也是 ArrayList 的优势。

三、ArrayList 底层结构

ArrayList 底层是数组。

可以简单理解为：

Object[] elementData;

当我们执行：

list.add("Java");
list.add("MySQL");
list.add("Redis");

底层大概是这样：

下标：  0       1        2
元素： Java   MySQL    Redis

数组最大的特点是：

可以通过下标直接定位元素。

比如：

list.get(1);

底层可以直接通过数组下标找到位置，所以查询效率很高。

四、ArrayList 查询为什么快？

因为数组在内存中是一段连续空间。

如果知道数组起始地址和下标，就可以快速计算出元素位置。

比如：

list.get(3);

它不需要从第一个元素开始一个一个找，而是可以直接定位到下标 3 的位置。

所以 ArrayList 按下标查询的时间复杂度是：

O(1)

这就是为什么说 ArrayList 查询快。

五、ArrayList 插入为什么可能慢？

如果是在尾部添加元素，并且数组容量够，ArrayList 很快。

比如：

list.add("Spring");

直接追加到数组末尾即可。

但是如果在中间插入元素，就需要移动后面的元素。

比如原来数组是：

下标： 0      1       2
元素： A      B       C

现在要在下标 1 的位置插入 X：

list.add(1, "X");

插入后应该变成：

下标： 0      1      2      3
元素： A      X      B      C

为了给 X 腾位置，原来的 B 和 C 都要往后移动。

如果列表很大，并且经常在中间插入，移动成本就比较高。

所以 ArrayList 中间插入的时间复杂度大概是：

O(n)

六、ArrayList 删除为什么可能慢？

删除中间元素也类似。

比如原来是：

下标： 0      1      2      3
元素： A      B      C      D

现在删除下标 1 的元素：

list.remove(1);

删除后变成：

下标： 0      1      2
元素： A      C      D

原来后面的 C 和 D 需要往前移动。

所以 ArrayList 删除中间元素也可能比较慢。

不过如果删除的是最后一个元素：

list.remove(list.size() - 1);

就不需要移动大量元素，效率会比较高。

七、ArrayList 扩容机制

ArrayList 底层是数组，而数组长度是固定的。

所以当数组容量不够时，就需要扩容。

比如：

List<String> list = new ArrayList<>();

list.add("A");
list.add("B");
list.add("C");

当元素越来越多，内部数组装不下时，ArrayList 会创建一个更大的新数组，然后把旧数组中的元素复制过去。

扩容过程可以简单理解为：

1. 创建更大的新数组
2. 把旧数组元素复制到新数组
3. 让 ArrayList 使用新数组
4. 继续添加新元素

在 JDK 8 中，ArrayList 扩容通常是原容量的 1.5 倍左右。

比如：

10 -> 15 -> 22 -> 33

这里不用死记具体源码，但要知道：

ArrayList 扩容需要创建新数组并复制旧元素，所以扩容本身有成本。

如果我们一开始就知道大概会存多少数据，可以指定初始容量：

List<String> list = new ArrayList<>(1000);

这样可以减少扩容次数。

八、LinkedList 是什么？

LinkedList 也是 List 接口的实现类。

它的特点是：

1. 有序
2. 可以重复
3. 底层是双向链表
4. 查询需要遍历
5. 头尾插入删除比较方便
6. 线程不安全

基本使用：

import java.util.LinkedList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        List<String> list = new LinkedList<>();

        list.add("Java");
        list.add("MySQL");
        list.add("Redis");

        System.out.println(list.get(0));
        System.out.println(list.get(1));
        System.out.println(list.get(2));
    }
}

从使用方式上看，LinkedList 和 ArrayList 都是 List，都可以使用 add、get、remove 等方法。

但是底层结构完全不同。

九、LinkedList 底层结构

LinkedList 底层是双向链表。

可以简单理解为每个节点保存三部分内容：

class Node {
    Object item;
    Node prev;
    Node next;
}

其中：

字段	含义
item	当前节点保存的数据
prev	指向上一个节点
next	指向下一个节点

结构大概是：

null <- A <-> B <-> C -> null

每个节点都知道自己的前一个节点和后一个节点。

所以它叫双向链表。

十、LinkedList 查询为什么慢？

因为链表不能像数组一样通过下标直接定位。

如果执行：

list.get(2);

LinkedList 需要从头节点或尾节点开始，一个一个往后或往前找。

比如：

A <-> B <-> C <-> D

要找下标 2 的元素，就需要遍历到 C。

所以 LinkedList 根据下标查询的时间复杂度是：

O(n)

这就是为什么说 LinkedList 查询慢。

不过 Java 的 LinkedList 是双向链表，它会根据下标判断从头找还是从尾找更近。

比如列表长度是 100：

• 查询下标 2，可能从头开始找
• 查询下标 98，可能从尾开始找

但无论如何，它还是需要遍历。

十一、LinkedList 插入删除为什么有时快？

链表插入删除的优势在于：

如果已经找到了要操作的节点，插入和删除只需要修改指针。

比如有链表：

A <-> B <-> C

现在要在 B 后面插入 X：

A <-> B <-> X <-> C

只需要调整几个节点的 prev 和 next 指针，不需要像数组那样移动大量元素。

删除也是一样。

比如删除 B：

A <-> B <-> C

删除后：

A <-> C

只需要让 A.next 指向 C，让 C.prev 指向 A。

所以，如果已经定位到节点，链表插入删除效率很高。

十二、为什么不能简单说 LinkedList 增删一定快？

这是面试中很容易踩坑的地方。

很多人会直接说：

LinkedList 增删快，ArrayList 增删慢。

这句话不够严谨。

因为 LinkedList 如果要在中间插入或删除，首先也需要找到那个位置。

比如：

list.add(5000, "Java");

如果链表很长，LinkedList 需要先遍历到下标 5000 的位置。

遍历本身是 O(n)。

找到之后，修改指针才很快。

所以完整说法应该是：

LinkedList 在已知节点位置，或者在头尾插入删除时效率较高。
但如果需要根据下标先查找位置，中间插入删除并不一定比 ArrayList 快。

这句话比简单背“增删快”更准确。

十三、ArrayList 和 LinkedList 遍历区别

对于 ArrayList，使用普通 for 循环按下标遍历通常没问题：

List<String> list = new ArrayList<>();

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

因为 ArrayList.get(i) 是快速下标访问。

但是对于 LinkedList，不建议这样写：

List<String> list = new LinkedList<>();

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

原因是：

list.get(i)

每次都要遍历链表。

如果循环中每次都调用 get(i)，整体效率会比较差。

更推荐使用增强 for 或迭代器：

for (String item : list) {
    System.out.println(item);
}

或者：

Iterator<String> iterator = list.iterator();

while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

十四、LinkedList 还可以当队列使用

LinkedList 不仅实现了 List 接口，也实现了 Deque 接口。

所以它可以作为队列或双端队列使用。

比如：

LinkedList<String> queue = new LinkedList<>();

queue.addLast("A");
queue.addLast("B");
queue.addLast("C");

System.out.println(queue.removeFirst());
System.out.println(queue.removeFirst());

输出：

A
B

这里就是先进先出。

也可以当双端队列：

LinkedList<String> deque = new LinkedList<>();

deque.addFirst("A");
deque.addLast("B");

System.out.println(deque.removeFirst());
System.out.println(deque.removeLast());

不过在现代 Java 开发中，如果是队列场景，也经常会使用更专门的队列实现，比如 ArrayDeque、ConcurrentLinkedQueue 等。

十五、ArrayList 和 LinkedList 内存占用对比

ArrayList 底层是数组，每个位置主要保存元素引用。

LinkedList 底层是节点，每个节点除了保存元素本身，还要保存前后节点引用。

也就是说，LinkedList 每个节点大概需要保存：

item
prev
next

所以相同元素数量下，LinkedList 通常会占用更多内存。

这也是为什么实际开发中，ArrayList 更常用。

十六、线程安全问题

ArrayList 和 LinkedList 都不是线程安全的。

如果多个线程同时修改同一个 List，可能会出现数据不一致。

比如：

List<Integer> list = new ArrayList<>();

Thread t1 = new Thread(() -> {
    for (int i = 0; i < 1000; i++) {
        list.add(i);
    }
});

Thread t2 = new Thread(() -> {
    for (int i = 1000; i < 2000; i++) {
        list.add(i);
    }
});

多个线程同时 add，可能出现问题。

如果需要线程安全的 List，可以考虑：

List<String> list = Collections.synchronizedList(new ArrayList<>());

或者：

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

不过不同线程安全集合适合不同场景，不能乱用。

十七、面试标准回答

如果面试官问：

ArrayList 和 LinkedList 有什么区别？

可以这样回答：

ArrayList 底层是动态数组，支持根据下标随机访问，所以查询效率高，get(index) 时间复杂度是 O(1)。但是如果在中间插入或删除元素，需要移动后面的元素，所以中间增删效率可能比较低。另外，ArrayList 容量不够时会扩容，扩容需要创建新数组并复制旧元素。

LinkedList 底层是双向链表，每个节点保存数据、前驱节点和后继节点。它不能像数组一样通过下标直接定位元素，所以按下标查询需要遍历，时间复杂度是 O(n)。如果已经找到节点，在插入或删除时只需要修改指针，不需要移动大量元素，所以头尾插入删除比较方便。

不过不能简单说 LinkedList 增删一定比 ArrayList 快，因为如果要先根据下标找到中间位置，LinkedList 也需要遍历。实际开发中，如果没有特殊需求，通常优先使用 ArrayList。

十八、常见问题总结

1. ArrayList 底层是什么？

底层是数组，更准确地说是动态数组。

容量不够时会扩容。

2. LinkedList 底层是什么？

底层是双向链表。

每个节点保存当前元素、前一个节点和后一个节点。

3. ArrayList 查询为什么快？

因为数组支持通过下标直接访问，get(index) 时间复杂度是 O(1)。

4. LinkedList 查询为什么慢？

因为链表不能直接通过下标定位，需要从头或尾遍历，时间复杂度是 O(n)。

5. LinkedList 增删一定比 ArrayList 快吗？

不一定。

如果是在头尾操作，或者已经定位到节点，LinkedList 修改指针很快。

但如果要先按下标找位置，遍历成本也很高。

6. 实际开发中更常用哪个？

大多数情况下更常用 ArrayList。

因为实际业务中查询、遍历通常更多，而且 ArrayList 内存占用相对更低。

十九、实际开发建议

实际开发中可以这样选择：

1. 默认优先使用 ArrayList
2. 查询多、遍历多，用 ArrayList
3. 需要频繁头尾插入删除，可以考虑 LinkedList 或其他队列结构
4. 不要在 LinkedList 中频繁使用 get(index) 遍历
5. 如果能预估元素数量，可以给 ArrayList 指定初始容量
6. 多线程修改 List 时，不要直接使用普通 ArrayList
7. 队列场景可以考虑 ArrayDeque 或并发队列
8. 不要死背“ArrayList 查快增删慢，LinkedList 查慢增删快”，要结合位置和场景分析

二十、总结

这一篇主要学习了 ArrayList 和 LinkedList 的区别。

ArrayList 底层是动态数组，查询快，支持下标随机访问，但是中间插入删除可能需要移动元素。容量不够时会扩容，扩容需要复制数组。

LinkedList 底层是双向链表，查询需要遍历。如果已经定位到节点，插入删除只需要修改指针，不需要移动大量元素。但是如果按下标操作中间位置，也需要先遍历，所以不能简单说它增删一定更快。

面试回答时，要从底层结构、查询效率、插入删除、扩容、内存占用、使用场景这几个角度说明。

下一篇我们继续学习面向对象中一个高频问题：接口和抽象类有什么区别。