有什么好看的网站,wordpress英文站,高端玩家,租空间做网站ArrayList 和 LinkedList 是 Java 集合框架中两种常用的列表实现，它们在底层数据结构、性能特点和适用场景上有显著的区别。以下是它们的详细对比以及 ArrayList 的扩容机制。 1. ArrayList 和 LinkedList 的底层区别
(1) 底层数据结构 ArrayList： 基于动态数组（Dynamic Ar…ArrayList 和 LinkedList 是 Java 集合框架中两种常用的列表实现，它们在底层数据结构、性能特点和适用场景上有显著的区别。以下是它们的详细对比以及 ArrayList 的扩容机制。 1. ArrayList 和 LinkedList 的底层区别
(1) 底层数据结构 ArrayList： 基于动态数组（Dynamic Array）实现。元素在内存中是连续存储的。实现了 RandomAccess 接口，支持随机访问，可以通过索引快速定位元素。 LinkedList： 基于双向链表（Doubly Linked List）实现。每个元素（节点）包含数据和两个指针，分别指向前后节点。不支持随机访问，必须从头或尾遍历链表才能访问指定位置的元素。 RandomAccess是标志性接口，标识某个 List 实现支持快速随机访问。 (2) 性能特点
特性ArrayListLinkedList随机访问快速（时间复杂度为 O(1)）。慢（时间复杂度为 O(n)，需要遍历链表）。插入/删除较慢（时间复杂度为 O(n)，可能需要移动元素）。快速（时间复杂度为 O(1)，只需调整指针）。内存占用较低（仅存储元素和少量额外信息）。较高（每个节点需要存储数据和两个指针）。(3) 使用场景 ArrayList： 适用于频繁随机访问元素的场景。适合读多写少的场景。示例：存储一组用户 ID，并根据索引快速查找某个用户。 LinkedList： 适用于频繁插入和删除操作的场景。适合写多读少的场景。示例：实现队列或栈等数据结构。 2. ArrayList 的扩容机制
(1) 动态数组的特点
ArrayList 内部使用一个数组来存储元素。当数组容量不足时，ArrayList 会自动扩容以容纳更多元素。(2) 扩容过程 初始容量： 默认初始容量为 10。可以通过构造方法指定初始容量。ArrayListInteger list = new ArrayList(20); // 初始容量为 20扩容触发条件： 当添加新元素时，如果当前数组容量不足以容纳新元素，则触发扩容。 扩容策略： 新容量通常是原容量的 1.5 倍（即原容量 + 原容量的一半）。扩容后，会创建一个新的数组，并将原数组中的所有元素复制到新数组中。源码示例（JDK 8 中的部分代码）：private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity 1); // 扩容为原来的 1.5 倍if (newCapacity - minCapacity 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity); // 复制到新数组
} private static int hugeCapacity(int minCapacity) { if (minCapacity 0) // 溢出（int 整型最大值溢出） throw new OutOfMemoryError(); return (minCapacity MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } 性能影响： 扩容操作涉及数组的复制，因此是一个耗时的操作。如果可以预估元素数量，建议在初始化时指定合适的容量，避免频繁扩容。 步骤 计算新容量：新容量通常是旧容量的 1.5 倍（即 oldCapacity + (oldCapacity 1)）。例如，若当前容量为 10，则扩容后为 15。 比较最小需要容量：如果计算得到的新容量仍小于所需的最小容量（minCapacity），则将新容量设为 minCapacity。 检查最大容量限制：如果新容量超过了 ArrayList 能支持的最大容量（Integer.MAX_VALUE - 8），则将新容量设为 Integer.MAX_VALUE。 数组复制：最终，使用 Arrays.copyOf() 方法将原数组的元素复制到新数组中，并将新数组赋值给 elementData。 JDK 作者 Mark Reinhold 在 OpenJDK 邮件讨论中也提到，“减 8”是经验值，历史兼容留下的设置，它不是必须是 8，但不能是 0。 是为了防止堆内存溢出，大多数 JVM 对象是 8 字节对齐，加上对象头等等,但实际上大概率也是会堆内存溢出。 JDK21 的源码和 JDK8 稍有不同，但大致一样， JDK8 是硬编码，JDK21 是引入方法传入参数。 源码展示 private Object[] grow(int minCapacity) { int oldCapacity = elementData.length; if (oldCapacity 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = ArraysSupport
