Java中ArrayList和LinkedList的比较

注：Joshua Bloch 就是 LinkedList 的作者

在Java中，ArrayList和LinkedList都是常用的列表实现类，它们都实现了List接口，但在内部工作原理和性能方面有显著差异。

ArrayList：基于动态数组实现。随着元素的增加，数组的大小会动态调整。如果数组容量不足时，会分配一个新的更大的数组并复制元素。
LinkedList：基于双向链表实现。每个元素是一个节点，包含指向前后元素的引用。

访问速度

ArrayList：支持通过索引进行随机访问（get(int index)），由于是基于数组，所以访问速度很快，时间复杂度为O(1)。
LinkedList：随机访问时，需要从头部或尾部遍历链表，时间复杂度为O(n)，因此访问速度较慢。

内存消耗

ArrayList：由于是数组实现，元素仅存储数据，因此内存利用率较高，但在动态扩容时可能会浪费一些内存。
LinkedList：每个节点不仅存储数据，还存储两个引用（前一个和后一个节点），因此需要更多的内存。

关于 ArrayList 和 LinkedList 在添加 (add) 和删除 (remove) 操作上的性能比较，传统观点认为由于 ArrayList 需要移动数据，而 LinkedList 只需调整链表指针，因此 LinkedList 更快。然而，实际性能并不是这么简单，两者在不同情况下的表现差异较大，

ArrayList中的随机访问、添加和删除部分源码如下：

// 获取 index 位置的元素值
public E get(int index) {rangeCheck(index); // 首先判断 index 的范围是否合法return elementData(index); // 返回 elementData 数组中 index 位置的元素
}// 将 index 位置的值设为 element，并返回原来的值
public E set(int index, E element) {rangeCheck(index); // 检查索引的有效性E oldValue = elementData(index); // 保存旧值elementData[index] = element; // 将新值 element 赋给 elementData 数组的 index 位置return oldValue; // 返回旧值
}// 将 element 添加到 ArrayList 的指定位置
public void add(int index, E element) {rangeCheckForAdd(index); // 检查索引是否适合添加操作ensureCapacityInternal(size + 1);  // 确保内部容量足够存储新增的元素，并增加 modCount// 将 index 及其后的数据复制到 index+1 的位置，即从 index 开始向后挪了一位System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; // 在 index 处插入 elementsize++; // 增加列表大小
}// 删除 ArrayList 指定位置的元素
public E remove(int index) {rangeCheck(index); // 检查索引的有效性modCount++; // 增加 modCountE oldValue = elementData(index); // 记录被移除元素的旧值int numMoved = size - index - 1;if (numMoved > 0) {// 向左挪一位，index 位置原来的数据已经被覆盖System.arraycopy(elementData, index + 1, elementData, index, numMoved);}// 清空最后一个元素elementData[--size] = null; return oldValue; // 返回被移除的旧值
}

LinkedList中的随机访问、添加和删除部分源码如下：

// 获得第 index 个节点的值
public E get(int index) {checkElementIndex(index); // 检查索引的有效性return node(index).item; // 返回第 index 个节点的值
}// 设置第 index 个元素的值
public E set(int index, E element) {checkElementIndex(index); // 检查索引的有效性Node<E> x = node(index); // 定位到第 index 个节点E oldVal = x.item; // 保存旧值x.item = element; // 设置新值return oldVal; // 返回旧值
}// 在 index 个节点之前添加新的节点
public void add(int index, E element) {checkPositionIndex(index); // 检查索引的有效性if (index == size) {linkLast(element); // 如果在末尾添加，直接调用 linkLast 方法} else {linkBefore(element, node(index)); // 否则，在指定位置之前添加新节点}
}// 删除第 index 个节点
public E remove(int index) {checkElementIndex(index); // 检查索引的有效性return unlink(node(index)); // 删除指定节点并返回旧值
}// 定位 index 处的节点
Node<E> node(int index) {// assert isElementIndex(index); // 断言索引的有效性// 当 index < size / 2 时，从头开始查找if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++) {x = x.next;}return x;} else { // 当 index >= size / 2 时，从尾部开始查找Node<E> x = last;for (int i = size - 1; i > index; i--) {x = x.prev;}return x;}
}

随机访问（get 和 set）：ArrayList 远远优于 LinkedList。ArrayList 能在 O(1) 的时间复杂度内完成，而 LinkedList 的查找时间复杂度是 O(n)，性能远不如 ArrayList。
插入和删除：这两种操作的性能没有简单的结论。对于 ArrayList，如果插入或删除发生在数组的末尾，操作效率非常高（O(1)）；但是如果操作发生在数组的中间或开头，则需要移动大量元素（O(n)）。LinkedList 的插入和删除操作在理论上更快（O(1)），但由于需要遍历链表查找目标位置，因此查找阶段（O(n)）会拖慢整体性能。对于插入或删除操作，LinkedList 在极端情况下（如频繁在中间插入或删除）可能优于 ArrayList，但通常两者的效率没有明显的优劣。

下面通过程序来测试一下两者插入的速度：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;/*** 列表插入测试类* 本类用于测试在不同类型的列表（ArrayList和LinkedList）中插入元素的性能*/
public class ListInsertionTest {/*** 插入测试方法，在指定索引位置插入元素* * @param list 待测试的列表* @param insertions 插入的元素数量* @param index 插入的索引位置* @param listType 列表类型，用于输出信息*/private static void testInsertion(List<Integer> list, int insertions, int index, String listType) {long startTime = System.nanoTime();// 在指定索引位置插入元素for (int i = 0; i < insertions; i++) {list.add(index, i);}long endTime = System.nanoTime();long duration = (endTime - startTime) / 1_000_000; // 转换为毫秒System.out.println(listType + " 在 index=" + index + " 插入 " + insertions + " 个元素，耗时: " + duration + " 毫秒");}public static void main(String[] args) {int initialSize = 10_000; // 初始容量int insertions = 10_000;  // 插入的元素数量// 初始化 ArrayList 和 LinkedListList<Integer> arrayList = new ArrayList<>(initialSize);List<Integer> linkedList = new LinkedList<>();// 初始化数据，使得列表的初始容量为 initialSizefor (int i = 0; i < initialSize; i++) {arrayList.add(i);linkedList.add(i);}// 测试 ArrayListSystem.out.println("ArrayList:");testInsertion(arrayList, insertions, 1000, "ArrayList");  // 在 index=1000 处插入testInsertion(arrayList, insertions, 5000, "ArrayList");  // 在 index=5000 处插入testInsertion(arrayList, insertions, 9000, "ArrayList");  // 在 index=9000 处插入// 测试 LinkedListSystem.out.println("\nLinkedList:");testInsertion(linkedList, insertions, 1000, "LinkedList");  // 在 index=1000 处插入testInsertion(linkedList, insertions, 5000, "LinkedList");  // 在 index=5000 处插入testInsertion(linkedList, insertions, 9000, "LinkedList");  // 在 index=9000 处插入}
}

ArrayList:
ArrayList 在 index=1000 插入 10000 个元素，耗时: 17 毫秒
ArrayList 在 index=5000 插入 10000 个元素，耗时: 21 毫秒
ArrayList 在 index=9000 插入 10000 个元素，耗时: 29 毫秒LinkedList:
LinkedList 在 index=1000 插入 10000 个元素，耗时: 21 毫秒
LinkedList 在 index=5000 插入 10000 个元素，耗时: 77 毫秒
LinkedList 在 index=9000 插入 10000 个元素，耗时: 148 毫秒

从测试结果来看，ArrayList 在不同插入位置的性能表现明显优于 LinkedList。