Java 集合#

1. 什么是 Java 集合#

Java 集合是 Java 提供的一套用于存储和管理对象的容器体系，位于 java.util 包下。
它和数组类似，都是用来存数据的，但集合相比数组更灵活：

集合长度可动态扩展
集合提供了丰富的操作方法，如增删改查、遍历、排序、去重等

所以可以把集合理解为：

Java 为了更方便地管理一组对象而提供的数据结构工具箱。

2. Java 集合的整体体系#

Java 集合主要分为两大类：

Collection：单列集合，一个元素一个元素地存
Map：双列集合，以 key-value 形式存

整体结构大致可以这样理解：

Collection 体系#

List：有序、可重复
Set：无序或有序、不可重复
Queue：队列，通常用于先进先出或特殊调度场景

Map 体系#

Map：键值对存储，key 不可重复，value 可重复

3. Collection 体系详解#

3.1 List#

List 的特点是：

元素有序
元素可重复
可以通过下标访问元素

常见实现类有：

（1）ArrayList#

底层是动态数组。

特点：

查询快
随机访问快
尾部插入效率较高
中间插入、删除较慢
线程不安全

适用场景：

读多写少
频繁根据下标访问元素

（2）LinkedList#

底层是双向链表。

特点：

插入、删除效率高（尤其是中间位置）
查询慢
不适合频繁随机访问
线程不安全

适用场景：

增删操作较多
不太依赖随机访问

（3）Vector#

底层也是动态数组，但它的方法大多带 synchronized。

特点：

线程安全
性能较低
现在基本很少使用

3.2 Set#

Set 的特点是：

元素不可重复
一般没有索引
更关注去重

常见实现类有：

（1）HashSet#

底层基于 HashMap 实现。

特点：

无序
去重
查询、插入效率高
允许一个 null

适用场景：

只关心去重，不关心顺序

（2）LinkedHashSet#

底层基于 LinkedHashMap。

特点：

元素不可重复
可以保持插入顺序
性能略低于 HashSet

适用场景：

既要去重，又希望保留插入顺序

（3）TreeSet#

底层基于红黑树。

特点：

元素不可重复
自动排序
默认自然排序，也可以自定义比较器

适用场景：

需要去重并排序

3.3 Queue#

Queue 表示队列，一般用于：

先进先出
任务调度
消息处理
缓冲区

常见实现类有：

（1）LinkedList#

除了实现 List，也实现了 Queue

（2）PriorityQueue#

优先队列，底层是堆

特点：

不是严格按插入顺序出队
会按优先级出队

适用场景：

定时任务
TopK
优先级调度

（3）Deque#

双端队列，可以两端进出元素
常见实现类：ArrayDeque

4. Map 体系详解#

Map 用于存储键值对，即：

1
key -> value

特点：

key 不可重复
value 可以重复
通过 key 快速查找 value

常见实现类有：

（1）HashMap#

最常用的 Map 实现。

特点：

底层是 数组 + 链表 + 红黑树
key 无序
允许一个 null key
线程不安全
查询效率高

适用场景：

大多数普通键值对存储场景

（2）LinkedHashMap#

在 HashMap 基础上维护插入顺序或访问顺序。

特点：

有序
适合实现 LRU

（3）TreeMap#

底层是红黑树。

特点：

key 自动排序
查询复杂度是 O(logn)

适用场景：

需要按 key 排序存储

（4）Hashtable#

老的线程安全 Map。

特点：

方法基本都加锁
不允许 null key 和 null value
性能一般
现在通常不推荐使用

（5）ConcurrentHashMap#

并发场景下常用的线程安全 Map。

特点：

线程安全
性能比 Hashtable 好
JDK 1.8 之后采用更高效的并发控制机制

适用场景：

高并发环境下的共享 Map

5. 面试一句话回答#

Java 集合是 Java 提供的一套用于存储和管理对象的数据结构体系，主要分为 Collection 和 Map 两大类。其中 Collection 包括 List、Set、Queue 等单列集合，Map 用于存储键值对。不同集合实现类在有序性、可重复性、查询效率、插入删除效率和线程安全性上各不相同，适用于不同业务场景。

ArrayList 和 Array（数组）的区别？#

1. 本质区别#

Array 是 Java 语言内置的数据结构，属于基础容器；
ArrayList 是 Java 集合框架中的一个类，底层基于动态数组实现，位于 java.util 包下。

可以简单理解为：

Array：长度固定的原生数组
ArrayList：可自动扩容的动态数组集合

2. 长度是否可变#

Array#

数组长度一旦创建就不能修改。

例如：

1
int[] arr = new int[3];

这里长度就是 3，后续不能变成 5 或 10。

ArrayList#

ArrayList 的长度是可动态扩容的。
添加元素超过当前容量时，会自动扩容。

例如：

1
List<Integer> list = new ArrayList<>();
2
list.add(1);
3
list.add(2);

不需要手动指定固定长度。

3. 存储的数据类型#

Array#

数组既可以存基本数据类型，也可以存引用类型。

例如：

1
int[] nums = {1, 2, 3};
2
String[] arr = {"a", "b", "c"};

ArrayList#

ArrayList 只能存引用类型，不能直接存基本类型。
如果要存基本类型，需要使用对应的包装类。

例如：

1
ArrayList<Integer> list = new ArrayList<>();
2
list.add(1);

这里放的其实是 Integer，而不是 int。
不过因为有自动装箱机制，所以写起来看起来像能直接放基本类型。

4. 功能丰富程度#

Array#

数组功能比较基础，只能通过下标访问元素：

1
arr[0] = 10;
2
System.out.println(arr[0]);

如果要做插入、删除、扩容等操作，需要自己手动处理。

ArrayList#

ArrayList 提供了很多现成方法，例如：

add()
remove()
get()
set()
size()
contains()

使用起来更方便，适合日常业务开发。

5. 类型安全和泛型支持#

Array#

数组本身不支持泛型，但它在运行时知道自己的元素类型。

例如：

1
String[] arr = new String[3];

ArrayList#

ArrayList 支持泛型，可以在编译期约束元素类型。

例如：

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

这样只能放 String 类型的数据，类型安全更好。

6. 性能方面#

Array#

数组是最基础的数据结构，开销更小，性能通常略高。
因为它是固定长度，内存连续，访问非常快。

ArrayList#

ArrayList 底层虽然也是数组，但由于封装了很多方法，还涉及自动扩容、泛型、装箱拆箱等，性能上通常会比原生数组略差一点。

所以：

对性能要求极高、长度固定时，可以优先考虑数组
对开发效率和灵活性要求更高时，通常用 ArrayList

7. 适用场景区别#

Array 适用场景#

长度固定
数据类型明确
对性能要求较高
底层算法实现

ArrayList 适用场景#

长度不确定
需要频繁添加元素
更关注开发便利性
日常业务开发

8. 底层关系#

ArrayList 底层其实就是用数组实现的。
它内部维护了一个 Object[] 数组，当容量不够时会进行扩容。

所以可以说：

ArrayList 是对数组的一层封装。

9. 面试一句话回答#

数组是 Java 内置的固定长度容器，既可以存基本类型也可以存引用类型；而 ArrayList 是集合框架中的动态数组实现，长度可自动扩容，只能存引用类型，并提供了丰富的增删改查方法。数组更偏底层和高性能，ArrayList 更偏灵活和易用。

ArrayList 插入和删除元素的时间复杂度#

1. 结论先说#

ArrayList 底层是动态数组，因此它的插入和删除时间复杂度要看具体操作位置。

插入#

尾部插入（不考虑扩容）：O(1)
尾部插入（发生扩容）：O(n)
中间或头部插入：O(n)

删除#

删除尾部元素：O(1)
删除中间或头部元素：O(n)
按值删除：最坏 O(n)

2. 为什么尾插通常是 O(1)#

ArrayList 底层是数组，如果当前数组还有空位，尾部添加元素时，直接把元素放到末尾即可，不需要移动其他元素，所以时间复杂度是：

1
O(1)

例如：

1
list.add(10);

这类操作通常就是直接追加。

3. 为什么扩容后尾插会变成 O(n)#

如果底层数组容量满了，再插入元素时就要进行扩容。
扩容时一般会：

创建一个更大的新数组
把旧数组元素拷贝过去
再插入新元素

数组拷贝需要遍历原有元素，所以复杂度是：

1
O(n)

不过从整体上看，ArrayList 的尾插平均下来仍然可以认为是均摊 O(1)。

4. 为什么中间或头部插入是 O(n)#

如果在中间或头部插入元素，为了给新元素腾位置，插入点之后的所有元素都要整体向后移动一位。

例如：

1
list.add(0, 100);

如果数组里原本有 n 个元素，最坏情况下需要移动接近 n 个元素，所以复杂度是：

1
O(n)

5. 删除为什么也可能是 O(n)#

（1）删除尾部元素#

如果删除最后一个元素，只需要把最后位置置空、长度减一即可，复杂度是：

1
O(1)

（2）删除中间或头部元素#

如果删除的是中间或头部元素，那么删除位置之后的元素都要向前移动一位来补空位，所以复杂度是：

1
O(n)

例如：

1
list.remove(0);

最坏情况下，后面所有元素都要移动。

6. 按值删除为什么最坏也是 O(n)#

如果执行：

1
list.remove(Integer.valueOf(10));

需要先遍历查找这个元素的位置，找到后再删除。
查找最坏要遍历整个数组，删除后还可能移动元素，所以整体最坏复杂度仍然是：

1
O(n)

7. 总结表#

操作	时间复杂度
尾部插入（不扩容）	`O(1)`
尾部插入（扩容）	`O(n)`
尾部插入（均摊）	`O(1)`
头部 / 中间插入	`O(n)`
删除尾部元素	`O(1)`
删除头部 / 中间元素	`O(n)`
按值删除	最坏 `O(n)`

8. 面试一句话回答#

ArrayList 底层是动态数组，所以尾部插入在不扩容时是 O(1)，扩容时是 O(n)，均摊下来是 O(1)；而在头部或中间插入、删除元素时，由于需要移动后续元素，时间复杂度通常是 O(n)。

LinkedList 插入和删除元素的时间复杂度？#

1. 结论先说#

LinkedList 底层是双向链表，所以它的插入和删除效率主要取决于：是否已经拿到了目标节点的位置。

插入#

头部插入：O(1)
尾部插入：O(1)
已知节点后插入：O(1)
按索引插入：O(n)

删除#

删除头节点：O(1)
删除尾节点：O(1)
已知节点删除：O(1)
按索引删除 / 按值删除：O(n)

2. 为什么头部和尾部插入是 O(1)#

因为 LinkedList 是双向链表，每个节点都保存：

当前元素
前驱节点引用
后继节点引用

并且链表本身维护了 first 和 last 指针，所以：

头插#

只需要：

创建新节点
修改新节点和原头节点的指针关系
更新 first

尾插#

只需要：

创建新节点
修改新节点和原尾节点的指针关系
更新 last

都不需要遍历，所以时间复杂度是：

1
O(1)

3. 为什么“已知节点位置”时插入和删除也是 O(1)#

链表的优势在于：一旦找到了目标节点，修改指针就可以完成插入或删除，不需要像数组那样整体移动元素。

例如删除某个节点，本质上就是：

让前驱节点指向后继节点
让后继节点指向前驱节点

所以复杂度是：

1
O(1)

但这里有个前提：你已经拿到了这个节点。

4. 为什么按索引插入和删除是 O(n)#

虽然链表修改指针很快，但问题在于：

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

例如：

1
list.add(100, "A");
2
list.remove(100);

在执行这些操作前，必须先从头或尾开始遍历，找到第 100 个位置对应的节点。
查找过程最坏要遍历接近 n 个元素，所以复杂度是：

1
O(n)

找到节点之后，真正插入或删除的动作虽然是 O(1)，但整体操作仍然是：

1
O(n)

5. 为什么按值删除也是 O(n)#

例如：

1
list.remove("abc");

它需要先遍历链表，找到值等于 "abc" 的节点。
查找本身最坏就是：

1
O(n)

找到后删除是 O(1)，但总复杂度仍然是：

1
O(n)

6. 总结表#

操作	时间复杂度
头部插入	`O(1)`
尾部插入	`O(1)`
已知节点插入	`O(1)`
按索引插入	`O(n)`
删除头节点	`O(1)`
删除尾节点	`O(1)`
已知节点删除	`O(1)`
按索引删除	`O(n)`
按值删除	`O(n)`

7. 面试一句话回答#

LinkedList 底层是双向链表，因此在头尾位置插入和删除元素的时间复杂度是 O(1)，在已知节点的情况下插入删除也是 O(1)；但如果是按索引或按值操作，通常要先遍历查找目标节点，所以整体时间复杂度是 O(n)。

ArrayList 与 LinkedList 区别？#

1. 底层数据结构不同#

ArrayList#

ArrayList 底层是动态数组实现的。

特点：

内存连续
支持随机访问
需要扩容

LinkedList#

LinkedList 底层是双向链表实现的。

特点：

节点在内存中不一定连续
每个节点保存前驱和后继引用
不支持高效随机访问

2. 查询性能不同#

ArrayList#

由于底层是数组，可以通过下标直接定位元素，所以：

按索引查询速度快
时间复杂度是 O(1)

LinkedList#

链表不能直接通过下标定位元素，需要从头或尾遍历，所以：

按索引查询速度慢
时间复杂度是 O(n)

所以在查询场景下，ArrayList 明显优于 LinkedList。

3. 插入和删除性能不同#

ArrayList#

如果在尾部添加元素，且不发生扩容，复杂度通常是：

尾插：O(1)

但如果在中间或头部插入、删除元素，需要移动后续元素：

中间插入 / 删除：O(n)

LinkedList#

如果已经找到目标位置，插入和删除只需要修改节点指针：

头尾插入 / 删除：O(1)
已知节点插入 / 删除：O(1)

但如果是按索引插入或删除，先要遍历找到节点，所以整体仍然可能是：

按索引插入 / 删除：O(n)

所以不能简单说 LinkedList 插入删除一定快，只有在已知节点位置时它才更有优势。

4. 内存占用不同#

ArrayList#

ArrayList 主要存储元素本身，空间利用率相对更高。
但因为底层会预留容量，所以可能存在一定空间浪费。

LinkedList#

LinkedList 每个节点除了存数据，还要存：

前驱指针
后继指针

所以单个元素的内存开销更大。

因此在内存占用上，LinkedList 一般比 ArrayList 更高。

5. 扩容机制不同#

ArrayList#

ArrayList 容量不足时会进行扩容，底层会创建更大的数组并拷贝原数据。
扩容会带来一定性能开销。

LinkedList#

LinkedList 不存在数组扩容问题，因为它是链表结构，每次新增节点即可。

6. 遍历性能不同#

虽然很多人觉得 LinkedList 插入删除快，但在实际遍历时：

ArrayList#

由于数组内存连续，CPU 缓存命中率高，遍历效率通常更好。

LinkedList#

链表节点离散，遍历时需要频繁通过指针跳转，缓存命中率较低，所以实际遍历性能通常不如 ArrayList。

7. 使用场景不同#

ArrayList 适合#

查询多，增删少
需要频繁按索引访问元素
大多数普通业务场景

LinkedList 适合#

头尾插入、删除较多
更像队列、双端队列的使用方式
不太依赖随机访问

不过在实际开发中，ArrayList 使用频率通常远高于 LinkedList。

8. 线程安全性#

两者都不是线程安全的。

ArrayList：线程不安全
LinkedList：线程不安全

如果在并发场景下使用，需要额外加锁或使用并发集合。

9. 总结对比表#

对比项	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	快，`O(1)`	慢，`O(n)`
头部插入删除	慢，`O(n)`	快，`O(1)`
中间插入删除	需要移动元素，`O(n)`	找到节点后 `O(1)`，但查找通常 `O(n)`
尾部插入	均摊 `O(1)`	`O(1)`
内存占用	较低	较高
遍历性能	通常更好	通常较差

10. 面试一句话回答#

ArrayList 底层是动态数组，查询快、随机访问性能好，适合读多写少的场景；LinkedList 底层是双向链表，头尾插入删除更高效，但查询较慢、内存开销更大。实际开发中，大多数场景更常用 ArrayList。

说一说 ArrayList 的扩容机制#

1. 先说结论#

ArrayList 底层是动态数组。
当添加元素时，如果底层数组容量不够，就会触发扩容：创建一个更大的新数组，把旧数组中的元素拷贝过去，再把新元素放进去。

所以 ArrayList 所谓的“动态”，本质上并不是原数组自己变长，而是：

旧数组装不下了，就换一个更大的数组。

2. ArrayList 底层是什么#

ArrayList 内部维护了一个数组：

1
transient Object[] elementData;

这个数组就是实际存放元素的地方。

同时，ArrayList 还有一个 size 表示当前已经存了多少个元素：

size：当前元素个数
elementData.length：当前数组容量

要注意：

容量（capacity）不等于元素个数（size）

3. 什么时候会触发扩容#

当执行 add() 添加元素时，如果发现：

1
size + 1 > elementData.length

也就是当前数组放不下新元素了，就会触发扩容。

4. 扩容后的新容量是多少#

在 JDK 1.8 中，ArrayList 每次扩容通常是原容量的 1.5 倍。

核心逻辑大致是：

1
newCapacity = oldCapacity + (oldCapacity >> 1)

也就是：

1
newCapacity = oldCapacity * 1.5

这样设计的目的，是在减少扩容次数和避免浪费太多内存之间做平衡。

5. 空 ArrayList 第一次添加元素会怎样#

这是面试里很爱问的点。

在 JDK 1.8 中：

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

刚创建时，底层并不会立刻分配一个长度为 10 的数组，而是先使用一个空数组。

也就是说，刚 new 出来的时候：

size = 0
elementData.length = 0

当第一次执行 add() 时，才会真正初始化容量，默认扩成 10。

所以可以说：

无参构造创建的 ArrayList，第一次添加元素时才会初始化默认容量 10。

6. 指定初始容量时会怎样#

如果这样写：

1
new ArrayList<>(20);

那底层一开始就会创建一个容量为 20 的数组。
这样可以减少后续扩容次数。

适合场景：

已经大致知道要放多少元素
想减少扩容和数组拷贝带来的性能损耗

7. 扩容时做了什么#

扩容大致分为三步：

（1）计算新容量#

通常扩为原来的 1.5 倍

（2）创建新数组#

创建一个更大的新数组

（3）拷贝旧数据#

把旧数组中的元素复制到新数组中

底层一般会调用：

1
Arrays.copyOf()

本质上还是数组复制。

8. 扩容的代价是什么#

扩容虽然能保证 ArrayList 动态增长，但它是有成本的：

（1）时间开销#

因为要把旧数组元素全部拷贝到新数组，所以扩容时间复杂度是：

1
O(n)

（2）空间开销#

扩容时会临时创建新数组，占用额外内存空间。

所以如果能提前预估数据量，最好指定初始容量。

9. 为什么说尾插是均摊 O(1)#

虽然某一次 add() 可能触发扩容，时间复杂度变成 O(n)，但不是每次都会扩容。
大多数情况下，尾部添加只是直接把元素放到数组末尾即可。

所以从整体平均来看，ArrayList 的尾插时间复杂度可以认为是：

1
均摊 O(1)

10. 面试中容易追问的点#

（1）ArrayList 默认容量是多少？#

无参构造创建时，初始其实是空数组
第一次添加元素后，默认扩成 10

（2）扩容倍数是多少？#

JDK 1.8 中一般是原容量的 1.5 倍

（3）为什么要扩容？#

因为底层数组长度固定，而 ArrayList 要实现动态增长

（4）扩容有什么代价？#

需要新建数组并复制旧数据，时间复杂度 O(n)

（5）如何减少扩容开销？#

初始化时指定合适的容量

11. 面试一句话回答#

ArrayList 底层是动态数组，当添加元素时如果容量不足，就会触发扩容。扩容时会创建一个更大的新数组，并把旧数组元素拷贝过去。JDK 1.8 中通常按原容量的 1.5 倍扩容，无参构造创建的 ArrayList 在第一次添加元素时才会初始化默认容量 10。由于扩容需要数组复制，单次扩容开销是 O(n)，所以在已知数据量较大时建议指定初始容量。

集合中的 fail-fast 和 fail-safe 是什么？#

1. 什么是 fail-fast#

fail-fast 中文通常叫快速失败机制。
它指的是：在遍历集合的过程中，如果集合结构被并发修改，就会立刻抛出异常，防止继续在错误状态下运行。

Java 中最常见的异常是：

1
ConcurrentModificationException

也就是说，集合一边遍历，一边又被直接修改，程序会尽快报错，而不是继续“带病运行”。

2. fail-fast 的原理#

fail-fast 的核心原理是：迭代器内部会检查集合是否被非法修改。

以 ArrayList 为例，底层有一个字段：

1
modCount

它用来记录集合被结构性修改的次数，比如：

添加元素
删除元素
扩容
清空集合

当创建迭代器时，迭代器会保存一个当前的 modCount 值，通常叫：

1
expectedModCount

之后在迭代过程中，每次调用 next()、remove() 等方法，都会检查：

modCount
expectedModCount

如果发现这两个值不一致，就说明集合在迭代期间被别的方式修改过，于是马上抛出异常。

所以可以理解为：

fail-fast 本质上是一种并发修改检测机制。

3. 什么是 fail-safe#

fail-safe 中文通常叫安全失败机制。
它指的是：在遍历集合时，不直接操作原集合，而是基于原集合的副本或快照进行遍历，因此即使原集合被修改，也不会抛出 ConcurrentModificationException。

也就是说：

fail-fast：发现问题，立即报错
fail-safe：不直接用原数据，避免报错

4. fail-safe 的典型场景#

最典型的就是 CopyOnWriteArrayList。

例如：

1
CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
2
list.add(1);
3
list.add(2);
4
list.add(3);
5

6
for (Integer num : list) {
7
    if (num == 2) {
8
        list.remove(num);
9
    }
10
}

这段代码一般不会抛出 ConcurrentModificationException。

原因是： CopyOnWriteArrayList 在遍历时读的是一个快照副本，而修改时会复制出一个新的数组再操作，所以读写分离了。

5. fail-safe 的原理#

fail-safe 并不是说“真的完全安全”，而是说它不会因为遍历时修改集合而快速失败。
它通常采用这些思路：

（1）基于副本遍历#

遍历时用的是集合的一个快照，而不是原集合本身。

（2）读写分离#

读操作读旧数据，写操作修改新副本。

因此遍历过程中即使原集合变化了，当前迭代器看到的仍然是创建迭代器时那份数据。

6. fail-fast 和 fail-safe 的区别#

对比项	fail-fast	fail-safe
中文含义	快速失败	安全失败
遍历时修改集合	通常抛异常	通常不会抛异常
是否直接遍历原集合	是	否，通常遍历副本/快照
典型异常	`ConcurrentModificationException`	一般不会抛这个异常
典型集合	`ArrayList`、`HashMap`	`CopyOnWriteArrayList`、`ConcurrentHashMap`（弱一致性）
代价	检测快，机制简单	可能有额外内存或数据一致性成本

7. 常见集合分别属于哪种#

fail-fast 集合#

大多数普通集合都是 fail-fast，例如：

ArrayList
LinkedList
HashSet
HashMap

这些集合的迭代器通常都会检查 modCount。

fail-safe / 弱一致性集合#

常见有：

CopyOnWriteArrayList
ConcurrentHashMap

不过要注意，ConcurrentHashMap 更准确地说是弱一致性（weakly consistent），它不一定完全基于快照，但遍历时不会像普通集合那样直接抛 ConcurrentModificationException。

7. fail-fast 一定安全吗？#

不一定。
fail-fast 只是尽最大努力发现并发修改问题，它本身不是线程安全机制，也不是绝对可靠的并发控制手段。

官方也强调过，这种异常检测是best-effort，不能依赖它来做程序正确性的保证。

所以：

fail-fast 不是用来解决并发安全的
它只是帮助尽快发现错误

9. 遍历时如果想删除元素怎么办#

如果是普通集合，在遍历过程中想安全删除元素，通常要使用迭代器自己的 remove() 方法，而不是直接调用集合的 remove()。

例如：

1
Iterator<Integer> it = list.iterator();
2
while (it.hasNext()) {
3
    Integer num = it.next();
4
    if (num == 2) {
5
        it.remove();
6
    }
7
}

这样不会触发 fail-fast 异常，因为迭代器会同步更新自己的状态。

10. 面试一句话回答#

fail-fast 是集合在遍历过程中发现结构被并发修改时，立即抛出 ConcurrentModificationException 的快速失败机制，典型实现依赖 modCount；fail-safe 则是在遍历时基于副本或快照访问数据，即使原集合被修改也通常不会抛异常，典型如 CopyOnWriteArrayList。

Comparable 和 Comparator 的区别#

1. 先说结论#

Comparable 和 Comparator 都是 Java 中用来实现对象比较和排序的接口，区别在于：

Comparable：内部比较器，由类自己定义比较规则
Comparator：外部比较器，由类外部单独定义比较规则

也可以简单理解为：

Comparable 是“这个类自己会比”，Comparator 是“找一个裁判来比”。

2. Comparable 是什么#

Comparable 位于：

1
java.lang.Comparable

它只有一个方法：

1
int compareTo(T o);

如果一个类实现了 Comparable 接口，就表示这个类本身具备“可比较性”，也就是说对象之间默认知道怎么比大小。

例如：

1
public class Student implements Comparable<Student> {
2
    private String name;
3
    private int age;
4

5
    @Override
6
    public int compareTo(Student o) {
7
        return this.age - o.age;
8
    }
9
}

这里表示：

当前 Student 对象和另一个 Student 对象比较时
默认按 age 排序

这样之后就可以直接排序：

1
Collections.sort(studentList);

3. Comparator 是什么#

Comparator 位于：

1
java.util.Comparator

它也用于比较两个对象，但比较规则是写在类外部的。
核心方法是：

1
int compare(T o1, T o2);

例如：

1
Comparator<Student> cmp = new Comparator<Student>() {
2
    @Override
3
    public int compare(Student o1, Student o2) {
4
        return o1.getAge() - o2.getAge();
5
    }
6
};

然后排序时显式传入比较器：

1
Collections.sort(studentList, cmp);

也就是说，Comparator 不要求 Student 类本身实现可比较接口，而是由外部指定“这次怎么排”。

4. 两者核心区别#

对比项	Comparable	Comparator
所在包	`java.lang`	`java.util`
比较方法	`compareTo(T o)`	`compare(T o1, T o2)`
比较规则定义位置	类内部	类外部
排序规则数量	一般一个默认规则	可以定义多个不同规则
是否修改类本身	需要实现接口，修改类	不需要修改类
使用场景	类天然有默认排序规则	需要临时、自定义、多种排序规则

5. Comparable 的特点#

优点#

适合定义对象的默认排序规则
使用方便，调用排序时不需要每次传比较器
很多类天然就适合用它，比如：
- Integer
- String
- Date

缺点#

只能在类内部定义一种主要排序规则
如果有多种排序需求，不够灵活
需要修改类源码

6. Comparator 的特点#

优点#

灵活，可以定义多种排序规则
不需要改动原类
适合临时排序、复杂排序、多字段排序

缺点#

使用时通常要额外传入比较器
写法相对稍微麻烦一点

7. 如何选择#

用 Comparable 的场景#

类本身就有明确、天然、唯一的默认排序规则
比如字符串按字典序、整数按数值大小

用 Comparator 的场景#

不想修改原类
一个类有多种排序需求
需要临时指定排序规则
第三方类源码不能改

8. 面试中的经典一句话#

Comparable 是让类本身实现比较规则，属于内部比较器；Comparator 是在类外部定义比较规则，属于外部比较器。Comparable 适合定义默认排序规则，Comparator 更灵活，适合多种自定义排序场景。

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同#

1. 共同点#

HashSet、LinkedHashSet 和 TreeSet 都属于 Set 接口的实现类，所以它们有这些共同特征：

都是单列集合
都具有 Set 的基本特性：元素不可重复
一般都不支持通过索引访问元素
都常用于去重

也就是说，它们的共同核心就是：

都用于存储不重复的元素。

2. 底层实现不同#

HashSet#

HashSet 底层基于 HashMap 实现。

本质上可以理解为：

把元素当作 HashMap 的 key 来存
value 统一是一个固定的占位对象

底层结构在 JDK 1.8 中是：

数组
链表
红黑树

LinkedHashSet#

LinkedHashSet 底层基于 LinkedHashMap 实现。

它在 HashSet 的基础上，多维护了一条双向链表来记录元素顺序，所以它既具备哈希表查找快的特点，又能保留插入顺序。

TreeSet#

TreeSet 底层基于 TreeMap 实现，本质上是红黑树。

它不是按哈希存储，而是按排序规则存储，所以元素会自动有序。

3. 元素顺序不同#

HashSet#

无序。
这里的无序不是“随机”，而是指：

不保证插入顺序
遍历顺序可能和插入顺序不同

LinkedHashSet#

有序，它能保持插入顺序。

TreeSet#

有序，但它保持的不是插入顺序，而是排序顺序。

排序方式可以是：

元素的自然排序
自定义比较器排序

4. 去重方式不同#

HashSet / LinkedHashSet#

这两者底层都依赖哈希结构，所以判断元素是否重复，主要依赖：

hashCode()
equals()

流程大致是：

先比较 hashCode
如果哈希值相同，再用 equals() 比较

所以如果往 HashSet 或 LinkedHashSet 中放自定义对象，通常要正确重写：

hashCode()
equals()

TreeSet#

TreeSet 判断重复主要依赖比较规则，而不是 equals()。

也就是说，如果两个元素比较结果为：

1
compareTo() == 0

或 comparator.compare() == 0

那么 TreeSet 就认为这两个元素重复，后一个不会加入。

所以 TreeSet 的“去重”和“排序”本质上都依赖比较器。

5. 性能不同#

HashSet#

基于哈希表，增删查平均时间复杂度通常是：

1
O(1)

性能通常是三者里最好的。

LinkedHashSet#

因为底层也是哈希表，所以增删查平均复杂度也通常是：

1
O(1)

但由于额外维护链表，性能会略低于 HashSet。

TreeSet#

底层是红黑树，增删查时间复杂度通常是：

1
O(log n)

所以在纯查找性能上，一般不如 HashSet 和 LinkedHashSet。

6. null 值支持情况#

HashSet#

允许存储一个 null

LinkedHashSet#

也允许存储一个 null

TreeSet#

一般不建议存 null，通常会抛出 NullPointerException。
因为 TreeSet 需要比较元素大小，而 null 没法正常比较。

7. 使用场景不同#

HashSet#

适合：

只关心去重
不关心元素顺序
更关注性能

LinkedHashSet#

适合：

需要去重
同时希望保留插入顺序

TreeSet#

适合：

需要去重
还需要自动排序

8. 总结对比表#

对比项	HashSet	LinkedHashSet	TreeSet
底层实现	`HashMap`	`LinkedHashMap`	`TreeMap`（红黑树）
元素是否重复	不可重复	不可重复	不可重复
顺序	无序	按插入顺序	按排序顺序
去重依据	`hashCode + equals`	`hashCode + equals`	`compareTo / Comparator`
查询性能	高，平均 `O(1)`	高，平均 `O(1)`	`O(log n)`
是否支持 null	支持一个	支持一个	一般不支持
适用场景	只去重	去重 + 保留顺序	去重 + 排序

9. 面试一句话回答#

HashSet、LinkedHashSet 和 TreeSet 都是 Set 的实现类，共同点是元素不可重复。不同点在于：HashSet 底层基于 HashMap，无序，性能最好；LinkedHashSet 基于 LinkedHashMap，在去重的同时保留插入顺序；TreeSet 基于红黑树实现，元素会按照自然顺序或自定义比较器自动排序。

Queue 与 Deque 的区别#

1. 先说结论#

Queue 和 Deque 都是 Java 集合中的队列接口，但区别在于：

Queue：单端队列
Deque：双端队列

也就是说：

Queue 主要是在一端入队、另一端出队
Deque 可以在两端都进行插入和删除

所以可以简单理解为：

Deque 是比 Queue 更灵活的队列。

2. Queue 是什么#

Queue 表示普通队列，通常遵循 FIFO（先进先出） 规则。

常见操作是：

在队尾插入元素
在队头删除元素

Queue 常见方法#

offer(e)：入队
poll()：出队并返回队头元素
peek()：查看队头元素但不删除

3. Deque 是什么#

Deque 全称是 Double Ended Queue，即双端队列。

它允许：

在队头插入
在队头删除
在队尾插入
在队尾删除

也就是说，Deque 两端都能操作。

Deque 常见方法#

队头操作#

offerFirst(e)
pollFirst()
peekFirst()

队尾操作#

offerLast(e)
pollLast()
peekLast()

同时，Deque 也兼容普通 Queue 的方法，比如：

offer()
poll()
peek()

4. 两者核心区别#

对比项	Queue	Deque
含义	单端队列	双端队列
插入位置	通常尾部插入	头尾都可插入
删除位置	通常头部删除	头尾都可删除
灵活性	较低	更高
是否可实现栈	不适合	可以
典型场景	普通排队、任务调度	队列 + 栈 + 双端操作场景

5. Deque 为什么更强大#

因为 Deque 不仅能当普通队列用，还能模拟：

（1）普通队列#

尾部入队
头部出队

（2）栈#

头部压栈
头部弹栈

所以：

Deque 既能实现 FIFO，也能实现 LIFO。

这就是为什么在 Java 中，很多时候推荐用 Deque 代替老的 Stack 类。

6. 常见实现类#

Queue 常见实现类#

LinkedList
PriorityQueue

Deque 常见实现类#

ArrayDeque
LinkedList

注意： LinkedList 同时实现了 List、Queue、Deque 接口，所以它既可以当链表用，也可以当队列和双端队列用。

7. 典型使用场景区别#

Queue 适合#

任务排队
消息消费
生产者消费者模型
广度优先搜索（BFS）

Deque 适合#

既要队列又要栈的场景
滑动窗口
单调队列
回文判断
双端调度

8. 一个常见面试点#

很多人会说：

Deque 是 Queue 的子接口。

这句话是对的。
也就是说：

Queue 提供普通队列能力
Deque 在 Queue 基础上扩展成双端队列能力

所以 Deque 功能更多，也更灵活。

9. 面试一句话回答#

Queue 是普通单端队列，通常在队尾插入、队头删除，满足先进先出；Deque 是双端队列，支持在队头和队尾两端进行插入和删除，既可以当队列用，也可以当栈用，因此比 Queue 更灵活。

ArrayDeque 与 LinkedList 的区别#

1. 先说结论#

ArrayDeque 和 LinkedList 都可以实现 Deque 接口，都能当作双端队列使用，但它们的底层实现和适用场景不同：

ArrayDeque：底层是循环数组
LinkedList：底层是双向链表

一般来说：

如果只是把它们当队列、栈、双端队列来用，通常更推荐 ArrayDeque；如果还需要链表特性或频繁在中间位置操作，才考虑 LinkedList。

2. 底层数据结构不同#

ArrayDeque#

ArrayDeque 底层是可扩容的循环数组。

特点：

底层元素存储在连续内存中
通过头尾指针在数组两端操作
容量不够时会扩容

LinkedList#

LinkedList 底层是双向链表。

特点：

每个节点保存数据、前驱指针、后继指针
节点在内存中不连续
不需要数组扩容

3. 性能区别#

（1）头尾插入删除#

两者在头尾插入删除时都很高效。

ArrayDeque#

头尾插入删除通常是 O(1)
扩容时会退化到 O(n)

LinkedList#

头尾插入删除是 O(1)

所以在双端操作这件事上，两者理论上都很快。

（2）实际运行性能#

虽然两者头尾操作复杂度都不错，但实际开发里 ArrayDeque 通常更快。

原因是：

ArrayDeque 底层是数组，内存连续
CPU 缓存命中率更高
没有链表节点对象的额外创建和指针跳转开销

而 LinkedList：

节点分散在内存中
遍历和访问时缓存命中率差
每个节点都有额外对象和指针开销

所以在栈、队列、双端队列场景下，ArrayDeque 一般性能优于 LinkedList。

4. 内存占用区别#

ArrayDeque#

ArrayDeque 底层是数组，只存元素本身，内存利用率相对更高。
不过数组会预留容量，可能有少量空间浪费。

LinkedList#

LinkedList 每个节点除了存元素，还要存：

前驱引用
后继引用

所以单个元素的额外内存开销更大。

因此：

LinkedList 的内存占用通常高于 ArrayDeque。

5. null 元素支持区别#

ArrayDeque#

不允许存 null

因为 ArrayDeque 内部会用 null 表示某个位置没有元素，所以禁止插入 null。

LinkedList#

允许存 null

这也是两者一个很明显的区别。

6. 随机访问能力区别#

ArrayDeque#

虽然底层是数组，但它并没有像 ArrayList 那样对外提供按索引随机访问接口。
它更偏向双端队列，不强调中间位置访问。

LinkedList#

LinkedList 也不适合随机访问，因为底层是链表，按索引查找要遍历，时间复杂度通常是 O(n)。

所以：

两者都不是专门为随机访问设计的
如果需要频繁按下标访问，通常都不合适

7. 作为栈使用时的区别#

虽然 Java 早期有 Stack 类，但现在更推荐使用 Deque 来模拟栈。

例如：

1
Deque<Integer> stack = new ArrayDeque<>();

相比 LinkedList，ArrayDeque 通常更适合作栈，因为：

性能更好
内存更省
没有链表节点额外开销

所以面试里常说：

实现栈和队列时，优先考虑 ArrayDeque，而不是 LinkedList。

8. 适用场景区别#

ArrayDeque 适合#

栈
普通队列
双端队列
频繁头尾操作
更关注性能

LinkedList 适合#

既想当 List 用，又想当 Deque 用
更偏链表语义的场景
允许存 null
需要中间位置插入删除（但前提是已经拿到节点位置）

不过在大多数实际业务开发中，仅从队列角度看，ArrayDeque 更常被推荐。

9. 总结对比表#

对比项	ArrayDeque	LinkedList
底层结构	循环数组	双向链表
头尾插入删除	通常 `O(1)`，扩容时 `O(n)`	`O(1)`
实际性能	通常更好	通常较差
内存占用	较低	较高
是否允许 `null`	不允许	允许
CPU 缓存友好性	更好	较差
适合作栈/队列	很适合	可以，但一般不如 `ArrayDeque`

10. 面试一句话回答#

ArrayDeque 和 LinkedList 都可以实现双端队列，但 ArrayDeque 底层是循环数组，LinkedList 底层是双向链表。两者头尾插入删除都比较高效，但 ArrayDeque 通常性能更好、内存占用更低，不过不允许存 null；LinkedList 允许 null，但节点开销更大、实际效率通常不如 ArrayDeque。

什么是 BlockingQueue？#

1. 什么是 BlockingQueue#

BlockingQueue 是 Java 并发包 java.util.concurrent 中提供的一个阻塞队列接口。
它在线程安全的普通队列基础上，增加了“阻塞”特性。

所谓阻塞，指的是：

队列满了，生产者线程再往里放数据时，会被阻塞，直到队列有空位
队列空了，消费者线程再从里取数据时，会被阻塞，直到队列中有元素

所以可以简单理解为：

BlockingQueue = 线程安全的队列 + 等待机制

2. 为什么需要 BlockingQueue#

在多线程场景下，经常会有：

一个线程负责生产数据
一个线程负责消费数据

这就是典型的生产者-消费者模型。

如果没有 BlockingQueue，就需要自己处理很多问题，比如：

加锁
线程通信
条件等待
唤醒机制

而 BlockingQueue 已经帮我们把这些并发控制逻辑封装好了，使用起来更简单、更安全。

3. BlockingQueue 的核心特点#

（1）线程安全#

BlockingQueue 天生适合多线程环境，多个线程可以安全地同时操作队列。

（2）支持阻塞等待#

这是它和普通 Queue 最大的区别。

队列为空时，获取元素的线程可以等待
队列满时，插入元素的线程可以等待

（3）常用于生产者-消费者模型#

它是实现生产消费解耦的经典工具。

4. 常用方法#

BlockingQueue 提供了四类风格的方法：

（1）抛异常#

add(e)：插入元素，满了抛异常
remove()：删除元素，空了抛异常
element()：查看队头元素，空了抛异常

（2）返回特殊值#

offer(e)：插入成功返回 true，失败返回 false
poll()：取出元素，空了返回 null
peek()：查看队头元素，空了返回 null

（3）一直阻塞#

put(e)：如果队列满了，就一直等
take()：如果队列空了，就一直等

（4）超时阻塞#

offer(e, time, unit)：在指定时间内尝试插入
poll(time, unit)：在指定时间内尝试获取

5. 和普通 Queue 的区别#

对比项	Queue	BlockingQueue
是否线程安全	一般不保证	通常线程安全
队列满时	直接失败或抛异常	可以阻塞等待
队列空时	返回空或抛异常	可以阻塞等待
是否适合生产者消费者模型	一般需要手动控制	非常适合

所以：

普通 Queue 更偏数据结构，BlockingQueue 更偏并发工具。

6. 常见实现类#

（1）ArrayBlockingQueue#

底层是数组
有界队列
必须指定容量
适合固定容量场景

（2）LinkedBlockingQueue#

底层是链表
可以有界，也可以近似无界
吞吐量通常不错
很常用

（3）PriorityBlockingQueue#

支持优先级排序
无界阻塞队列
元素按优先级出队，不一定 FIFO

（4）DelayQueue#

延迟队列
只有到期元素才能取出
常用于定时任务、缓存过期等场景

（5）SynchronousQueue#

不存储元素
每个插入操作必须等待一个取出操作
常用于线程池中任务直接移交

7. 典型使用场景#

（1）生产者-消费者模型#

生产者线程往队列放数据，消费者线程从队列取数据。

（2）线程池#

线程池内部就大量使用阻塞队列保存待执行任务。

（3）消息缓冲#

多个线程之间传递任务、消息、事件时，可以用阻塞队列做缓冲区。

（4）限流与削峰#

高并发请求可以先进入阻塞队列，后端线程慢慢消费，避免系统瞬时被打爆。

8. 使用 BlockingQueue 的好处#

简化线程间通信
避免自己写复杂的 wait/notify
线程安全
非常适合解耦生产和消费速度不一致的问题

9. 面试一句话回答#

BlockingQueue 是 Java 并发包中提供的阻塞队列接口，本质上是一个线程安全的队列，支持当队列为空时消费者阻塞等待、当队列满时生产者阻塞等待。它非常适合实现生产者-消费者模型，也是线程池等并发组件的重要基础。

ArrayBlockingQueue 和 LinkedBlockingQueue 有什么区别？#

1. 先说结论#

ArrayBlockingQueue 和 LinkedBlockingQueue 都是 BlockingQueue 的常见实现类，都是线程安全的阻塞队列，都常用于生产者-消费者模型。
它们的核心区别主要在于：

ArrayBlockingQueue：底层是数组，有界
LinkedBlockingQueue：底层是链表，可以看作可选有界，默认近似无界

也可以简单记成：

一个是数组队列，一个是链表队列；一个天然固定容量，一个默认容量很大。

2. 底层数据结构不同#

ArrayBlockingQueue#

底层使用数组实现，本质上是一个循环数组队列。

特点：

元素存储在连续内存中
通过下标控制头尾位置
不需要为每个元素额外创建节点对象

LinkedBlockingQueue#

底层使用链表实现，准确来说是单向链表。

特点：

每个元素都封装成链表节点
插入时创建新节点
节点在内存中不连续

3. 容量是否固定不同#

ArrayBlockingQueue#

创建时必须指定容量，而且容量一旦确定就不能改变。

例如：

1
BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(100);

这表示队列最大只能放 100 个元素。

所以它是一个天然有界队列。

LinkedBlockingQueue#

可以指定容量，也可以不指定。

例如指定容量：

1
BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(100);

如果不指定容量：

1
BlockingQueue<Integer> queue = new LinkedBlockingQueue<>();

默认容量是：

1
Integer.MAX_VALUE

所以虽然理论上也是“有界”的，但默认非常大，实际开发中通常把它看作近似无界队列。

4. 锁机制不同#

ArrayBlockingQueue#

ArrayBlockingQueue 通常使用一把锁来控制入队和出队操作。

也就是说：

生产者入队要竞争这把锁
消费者出队也要竞争这把锁

因此生产和消费在并发情况下会互相影响更明显。

LinkedBlockingQueue#

LinkedBlockingQueue 通常使用两把锁：

一把锁控制入队（putLock）
一把锁控制出队（takeLock）

这样好处是：

生产者和消费者可以一定程度上并行执行
并发吞吐量通常更高

所以在高并发读写场景下，LinkedBlockingQueue 的并发性能往往更好。

5. 内存占用不同#

ArrayBlockingQueue#

因为底层是数组，创建时就会分配一段连续空间。
优点是：

内存结构紧凑
没有节点对象额外开销

所以整体内存利用率通常更高。

LinkedBlockingQueue#

底层是链表，每个元素都要额外创建节点对象。
因此会有：

节点对象开销
指针引用开销

所以同样数量的元素下，LinkedBlockingQueue 一般比 ArrayBlockingQueue 更占内存。

6. 吞吐量和性能区别#

ArrayBlockingQueue#

优点：

底层数组，缓存友好
内存连续，单次操作开销较小

缺点：

一把锁，生产和消费竞争同一把锁
高并发下吞吐量可能受限

LinkedBlockingQueue#

优点：

两把锁，生产和消费可并行
高并发场景下吞吐量通常更高

缺点：

链表节点创建和 GC 开销更大
内存占用更高

所以一般来说：

低并发、固定容量、内存敏感：更适合 ArrayBlockingQueue
高并发、吞吐优先：更适合 LinkedBlockingQueue

7. 是否容易造成内存问题#

ArrayBlockingQueue#

因为容量固定，所以不容易无限堆积任务。
这也是它的一个重要优点：更容易控制系统压力。

LinkedBlockingQueue#

如果使用无参构造，默认容量接近无限：

1
Integer.MAX_VALUE

在生产速度远高于消费速度时，队列中的元素可能不断堆积，最终导致：

内存占用持续上升
甚至出现 OOM

所以实际开发中，LinkedBlockingQueue 一般也建议显式指定容量。

8. 适用场景不同#

ArrayBlockingQueue 适合#

已知队列最大容量
希望严格限制内存占用
生产消费模型相对稳定
更强调有界缓冲

LinkedBlockingQueue 适合#

并发量较高
更关注吞吐量
生产和消费并发进行较多
可以接受更高的内存开销

9. 在线程池中的一个经典点#

面试里经常会追问线程池。

很多线程池如果使用 LinkedBlockingQueue 且不设容量，任务会大量堆积，导致：

线程数不会轻易扩到最大线程数
队列越来越大
最终可能拖垮系统

所以在实际工作中，往往会更谨慎地选择阻塞队列，并显式设置队列容量。

10. 总结对比表#

对比项	ArrayBlockingQueue	LinkedBlockingQueue
底层结构	数组	链表
容量	必须指定，固定有界	可指定，不指定默认近似无界
锁机制	一把锁	两把锁
并发性能	一般	通常更高
内存占用	较低	较高
是否容易任务堆积	不容易失控	默认更容易堆积
适用场景	固定容量、内存敏感	高并发、吞吐优先

11. 面试一句话回答#

ArrayBlockingQueue 和 LinkedBlockingQueue 都是线程安全的阻塞队列，区别在于前者底层是数组、必须指定固定容量、使用一把锁；后者底层是链表、容量可选且默认接近无界、通常采用两把锁，所以并发吞吐量通常更高，但内存开销也更大。

huhu的小世界

Java 集合#

1. 什么是 Java 集合#

2. Java 集合的整体体系#

Collection 体系#

Map 体系#

3. Collection 体系详解#

3.1 List#

（1）ArrayList#

（2）LinkedList#

（3）Vector#

3.2 Set#

（1）HashSet#

（2）LinkedHashSet#

（3）TreeSet#

3.3 Queue#

（1）LinkedList#

（2）PriorityQueue#

（3）Deque#

4. Map 体系详解#

（1）HashMap#

（2）LinkedHashMap#

（3）TreeMap#

（4）Hashtable#

（5）ConcurrentHashMap#

5. 面试一句话回答#

ArrayList 和 Array（数组）的区别？#

1. 本质区别#

2. 长度是否可变#

Array#

ArrayList#

3. 存储的数据类型#

Array#

ArrayList#

4. 功能丰富程度#

Array#

ArrayList#

5. 类型安全和泛型支持#

Array#

ArrayList#

6. 性能方面#

Array#

ArrayList#

7. 适用场景区别#

Array 适用场景#

ArrayList 适用场景#

8. 底层关系#

9. 面试一句话回答#

ArrayList 插入和删除元素的时间复杂度#

1. 结论先说#

插入#

删除#

2. 为什么尾插通常是 O(1)#

3. 为什么扩容后尾插会变成 O(n)#

4. 为什么中间或头部插入是 O(n)#

5. 删除为什么也可能是 O(n)#

（1）删除尾部元素#

（2）删除中间或头部元素#

6. 按值删除为什么最坏也是 O(n)#

7. 总结表#

8. 面试一句话回答#

LinkedList 插入和删除元素的时间复杂度？#

1. 结论先说#

插入#

删除#

2. 为什么头部和尾部插入是 O(1)#

头插#

尾插#

3. 为什么“已知节点位置”时插入和删除也是 O(1)#

4. 为什么按索引插入和删除是 O(n)#

5. 为什么按值删除也是 O(n)#

6. 总结表#

7. 面试一句话回答#

ArrayList 与 LinkedList 区别？#

1. 底层数据结构不同#

ArrayList#

LinkedList#

2. 查询性能不同#

ArrayList#

LinkedList#