List 集合
List 集合是 Java 编程中使用最频繁🔥的集合接口。这个知识点非常重要，请一定要掌握熟练。
什么是 List 集合？
List 是 Java 集合框架（Collection Framework）中的一个接口，它继承自 Collection 接口。List 表示一个有序的、可重复的元素序列。
你可以通过索引（下标）访问 List 中的元素，索引从 0 开始（是不是感觉和数组一样？）。
List 的主要特点包括：
- 元素是有序的（插入顺序保留）
- 元素可以重复
- 允许包含
null值 - 支持基于索引的访问和操作
与数组的区别
最大的区别是：
1. 数组：数组的长度是固定的，不能动态扩容。
2. List：List 长度可变，可以动态扩容。
为什么要使用 List 集合？
List 集合在以下场景中非常有用：
- 需要保留元素的插入顺序
- 需要根据索引快速访问元素
- 需要存储重复的元素
- 需要动态扩容的数组（相比数组，List 长度可变，无需手动扩容）
- 提供了丰富的内置方法，如添加、删除、遍历、搜索等，大大简化开发
例如，如果你要存储一个班级的学生名单、一批订单信息、日志记录等，List 都是一个很好的选择。
常见的 List 集合实现类
Java 提供了多个 List 接口的实现类，常用的包括：
| 实现类 | 特点 |
|---|---|
ArrayList | 基于动态数组，查询快（随机访问），增删慢（除非在尾部） |
LinkedList | 基于双向链表，增删快（尤其在首尾），查询慢（需要遍历） |
Vector | 线程安全的动态数组，性能较低，已被 Collections.synchronizedList 替代 |
Stack | 继承自 Vector，提供栈结构（LIFO） |
✅ 在大多数场景中，
ArrayList是最常用的 List 实现。
ArrayList
ArrayList 是 Java 中最常用的 List 实现🔥。
要点：
- ArrayList 是基于数组实现的，支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问。
- 数组的默认大小为 10。
- oldCapacity + (oldCapacity >> 1) 新容量大约是旧容量的 1.5 倍左右。
LinkedList
LinkedList 是基于链表实现的，支持快速插入和删除。
要点：
- LinkedList是双向链表实现的List。
- LinkedList是非线程安全的。
- LinkedList元素允许为null，允许重复元素。
- LinkedList是基于链表实现的，因此插入删除效率高，查找效率低（虽然有一个加速动作）。
- LinkedList是基于链表实现的，因此不存在容量不足的问题，所以没有扩容的方法。
- LinkedList还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用。
List 集合常用方法
以下列出 List 接口中常用的方法（以 ArrayList 为例）：
1. 添加元素
list.add("A"); // 在末尾添加
list.add(0, "B"); // 在指定索引处插入
2. 获取元素
String element = list.get(0); // 获取指定索引的元素
3. 删除元素
list.remove(0); // 按索引删除
list.remove("A"); // 按元素值删除（首次出现）
4. 修改元素
list.set(0, "C"); // 将指定索引处的元素替换
5. 获取大小
int size = list.size();
6. 判断是否包含元素
boolean contains = list.contains("A");
7. 查找元素索引
int index = list.indexOf("A"); // 返回首次出现的索引，不存在返回 -1
8. 判断是否为空
boolean isEmpty = list.isEmpty();
9. 遍历 List
// 使用 for 循环
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
// 使用增强 for 循环
for (String item : list) {
System.out.println(item);
}
// 使用迭代器
Iterator<String> it = list.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
10. 转换为数组
String[] array = list.toArray(new String[0]);
11. 清空列表
list.clear();
经典源码分析
ArrayList
-
ArrayList 是基于数组实现的，支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问。
-
数组的默认大小为 10。
-
oldCapacity + (oldCapacity >> 1) 新容量大约是旧容量的 1.5 倍左右。
属性
/**
* 默认初始化的大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
* 初始化0长度实例，共享于0长度的集合
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
* 第一次添加元素时知道该 elementData 从空的构造函数还是有参构造函数被初始化的。以便确认如何扩容
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
* 元素数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
* 实际元素个数
*/
private int size;
构造器
ArrayList有着3个构造器，分别是
- 无参构造一个长度为10的数组。
- 初始容量构造器，传入一个数字初始化一个指定长度的数组
- 集合构造器，将给定的集合转换为ArrayList
/**
* 无参构造器
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 长度参数构造器
* Constructs an empty list with the specified initial capacity.
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 集合构造器
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
将 Collection 转化为数组并赋值给 elementData，把 elementData 中元素的个数赋值给 size。 如果 size 不为零，则判断 elementData 的 class 类型是否为 Object[]，不是的话则做一次转换。 如果 size 为零，则把 EMPTY_ELEMENTDATA 赋值给 elementData，相当于new ArrayList(0)。
add 方法
//添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//确保内部容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//确保显式容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
📢由此可见：
每次添加元素到集合中时都会先确认下集合容量大小。然后将 size 自增 1。
ensureCapacityInternal 函数中判断如果 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA 就取 DEFAULT_CAPACITY 和 minCapacity 的最大值也就是 10。
这就是 EMPTY_ELEMENTDATA 与 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的区别所在。
使用无参构造函数时是在第一次添加元素时初始化容量为 10 的。
ensureExplicitCapacity 中对 modCount 自增 1，记录操作次数，然后如果 minCapacity 大于 elementData 的长度，则对集合进行扩容。显然第一次添加元素时 elementData 的长度为零。
扩容机制
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
* 增加容量以确保它至少可以容纳最小容量参数指定的元素数量。参数： minCapacity - 所需的最小容量
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
很简单明了的一个函数，默认将扩容至原来容量的 1.5 倍。
但是扩容之后也不一定适用，有可能太小，有可能太大。
所以才会有下面两个 if 判断。
1.如果1.5倍太小的话，则将我们所需的容量大小赋值给newCapacity，
2.如果1.5倍太大或者我们需要的容量太大，那就直接拿 newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE 来扩容。
然后将原数组中的数据复制到大小为 newCapacity 的新数组中，并将新数组赋值给 elementData。
Remove
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null; // clear to let GC do its work
}
当我们调用 remove(int index) 时，首先会检查 index 是否合法，然后再判断要删除的元素是否位于数组的最后一个位置。
如果 index 不是最后一个，就再次调用 System.arraycopy() 方法拷贝数组。说白了就是将从 index + 1 开始向后所有的元素都向前挪一个位置。
然后将数组的最后一个位置空，size - 1。如果 index 是最后一个元素那么就直接将数组的最后一个位置空，size - 1即可。 当我们调用 remove(Object o) 时，会把 o 分为是否为空来分别处理。
然后对数组做遍历，找到第一个与 o 对应的下标 index，然后调用 fastRemove 方法，删除下标为 index 的元素。其实仔细观察 fastRemove(int index) 方法和 remove(int index) 方法基本全部相同。
LinkedList
- LinkedList是双向链表实现的List
- LinkedList是非线程安全的
- LinkedList元素允许为null，允许重复元素
- LinkedList是基于链表实现的，因此插入删除效率高，查找效率低（虽然有一个加速动作）
- LinkedList是基于链表实现的，因此不存在容量不足的问题，所以没有扩容的方法
- LinkedList还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用
属性
//节点数量
transient int size = 0;
/**
* 基于双向链表实现，使用 Node 存储链表节点信息。
* Pointer to first node.头节点
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.尾节点
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
/**
* Node节点
*/
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
大体结构如下图所示
add方法
//在链表的最后添加元素
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
其实通过源码可以看出添加的过程如下：
1.记录当前末尾节点，通过构造另外一个指向末尾节点的指针l
2.产生新的节点：注意的是由于是添加在链表的末尾，next是为null的
3.last指向新的节点
4.这里有个判断，判断是否为第一个元素(当l==null时，表示链表中是没有节点的)，
那么就很好理解这个判断了，如果是第一节点，则使用first指向这个节点，若不是则当前节点的next指向新增的节点
5.size增加
例如，在上面提到的LinkedList["A","B","C"]中添加元素“D”，过程大致如图所示
扩容机制
扩容时机:
LinkedList的扩容时机相对简单：当当前容量不足以容纳新元素时，就会触发扩容操作。具体来说，当调用add()方法并且当前容量已满时，就会进行扩容。
扩容方式:
LinkedList的扩容方式是重新分配内存并复制原有元素。具体来说，会创建一个新的双向链表节点数组，大小通常是原来的两倍。然后，将原有元素逐个复制到新数组中。最后，将新节点添加到新数组中的适当位置。这个过程的时间复杂度是O(n)，其中n是当前元素数量。
性能影响:
扩容操作对性能的影响主要体现在两个方面：时间复杂度和空间复杂度。从时间复杂度角度来看，由于扩容涉及到重新分配内存和复制元素，因此其时间复杂度是O(n)。这意味着在频繁进行扩容的情况下，可能会对性能产生较大影响。
从空间复杂度角度来看，由于LinkedList扩容时通常会创建一个更大的数组来容纳原有元素和新元素，因此其空间复杂度也是O(n)。这意味着随着元素数量的增加，内存占用也会相应增加。
Remove方法
//方法1.删除指定索引上的节点
public E remove(int index) {
//检查索引是否正确
checkElementIndex(index);
//这里分为两步，第一通过索引定位到节点，第二删除节点
return unlink(node(index));
}
//方法2.删除指定值的节点
public boolean remove(Object o) {
//判断删除的元素是否为null
if (o == null) {
//若是null遍历删除
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
//若不是遍历删除
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
1.首先确定index的位置，是靠近first还是靠近last
2.若靠近first则从头开始查询，否则从尾部开始查询，可以看出这样避免极端情况的发生，也更好的利用了LinkedList双向链表的特征
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//删除的是第一个节点，first向后移动
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
//删除的是最后一个节点，last向前移
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
1.获取到需要删除元素当前的值，指向它前一个节点的引用，以及指向它后一个节点的引用。
2.判断删除的是否为第一个节点，若是则first向后移动，若不是则将当前节点的前一个节点next指向当前节点的后一个节点
3.判断删除的是否为最后一个节点，若是则last向前移动，若不是则将当前节点的后一个节点的prev指向当前节点的前一个节点
4.将当前节点的值置为null
5.size减少并返回删除节点的值
常见面试题
- LinkedList 和 ArrayList 的区别？
LinkedList 是基于链表实现的，而 ArrayList 是基于数组实现的。
LinkedList 的性能比 ArrayList 更高，因为 LinkedList 的插入和删除操作性能更高。新增、删除元素时ArrayList需要使用到拷贝原数组，而LinkedList只需移动指针，查找元素 ArrayList支持随机元素访问,而LinkedList只能一个节点的去遍历。
接口实现：ArrayList实现了RandomAccess可以支持随机元素访问，而LinkedList实现了Deque可以当做队列使用。
- ArrayList 和 Vector 的区别？
Vector 是同步的，因此开销就比 ArrayList 要大，访问速度更慢。最好使用 ArrayList 而不是 Vector，因为同步操作完全可以由程序员自己来控制； Vector 每次扩容请求其大小的 2 倍（也可以通过构造函数设置增长的容量），而 ArrayList 是 1.5 倍。
- ArrayList 初始化时候的容量大小？
ArrayList 的默认容量大小为 10，当添加第 11 个元素时，ArrayList 会自动扩容为 10 * 2 = 20。
- ArrayList 扩容机制？
ArrayList 的扩容机制是：oldCapacity + (oldCapacity >> 1)
- ArrayList 如何在循环中删除元素？
在循环中删除元素时，需要使用 Iterator 迭代器来删除元素，而不是直接使用索引来删除。
- ArrayList 线程安全？
ArrayList 线程不安全，如果需要线程安全，可以使用 Collections.synchronizedList() 方法来包装 ArrayList。或者使用JUC中的 CopyOnWriteArrayList