java-list源码分析

List底层：

List 是 Java 中的一个接口，具体的底层实现取决于它的实现类。最常见的 List 实现类是 ArrayList 和 LinkedList，它们的底层原理完全不同。下面我们分别分析这两种实现类的底层原理。

ArryList原理：

ArrayList 是基于动态数组实现的，它的底层是一个可调整大小的数组。

核心特点

底层数据结构：ArrayList 使用一个 Object[] 数组来存储元素。
动态扩容：当数组容量不足时，ArrayList 会自动扩容（通常是当前容量的 1.5 倍）。
随机访问：由于是基于数组实现的，ArrayList 支持通过索引快速访问元素，时间复杂度为 O(1)。
插入和删除：在中间插入或删除元素时，需要移动后续元素，时间复杂度为 O(n)。

底层实现细节：

初始化：

默认情况下，ArrayList 的初始容量为 10。
可以通过构造函数指定初始容量。

java">List<Integer> list = new ArrayList<>(); // 默认容量为 10
List<Integer> list = new ArrayList<>(20); // 指定初始容量为 20

添加元素
- 当调用 add(E e) 方法时，元素会被添加到数组的末尾。
- 如果数组已满，ArrayList 会触发扩容机制：
  - 创建一个新的数组，大小为原数组的 1.5 倍（int newCapacity = oldCapacity + (oldCapacity >> 1)）。
  - 将原数组中的元素复制到新数组中。
  - 更新引用，指向新数组。
```
java">list.add(10); // 添加元素
```
插入元素
- 当调用 add(int index, E element) 方法时，ArrayList 会将指定位置及其后续元素向后移动一位，然后插入新元素。
- 如果需要扩容，会先扩容再插入。
```
java">list.add(1, 20); // 在索引 1 处插入元素
```
删除元素
- 当调用 remove(int index) 方法时，ArrayList 会将指定位置之后的元素向前移动一位，覆盖被删除的元素。
- 最后将数组的最后一个位置设置为 null，以便垃圾回收。
```
java">list.remove(1); // 删除索引 1 处的元素
```
随机访问：
- 通过 get(int index) 方法可以直接访问数组中的元素，时间复杂度为 O(1)。
```
java">int value = list.get(0); // 获取索引 0 处的元素
```

LinkedList 的底层原理

LinkedList 是基于双向链表实现的，它的底层是一个由节点（Node）组成的链表。

核心特点

底层数据结构：LinkedList 使用双向链表存储元素，每个节点包含数据、前驱节点和后继节点的引用。
动态大小：链表的大小可以动态调整，不需要扩容。
插入和删除：在链表中插入或删除元素时，只需要修改节点的引用，时间复杂度为 O(1)。
随机访问：访问链表中的元素需要从头或尾遍历，时间复杂度为 O(n)。

底层实现细节

节点结构：

每个节点是一个 Node 对象，包含三个部分：
- E item：存储元素。
- Node next：指向下一个节点。
- Node prev：指向上一个节点。

java">	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(E e) 方法时，LinkedList 会在链表末尾添加一个新节点。
- 如果链表为空，新节点既是头节点也是尾节点。
- 如果链表不为空，新节点的 prev 指向原尾节点，原尾节点的 next 指向新节点。
```
java">list.add(10); // 在链表末尾添加元素
```
插入元素：
- 当调用 add(int index, E element) 方法时，LinkedList 会遍历链表找到指定位置，然后插入新节点。
- 插入操作只需要修改相邻节点的引用。
```
java">list.add(1, 20); // 在索引 1 处插入元素
```
删除元素：
- 当调用 remove(int index) 方法时，LinkedList 会遍历链表找到指定位置，然后修改相邻节点的引用，跳过被删除的节点。
- 被删除的节点会被垃圾回收。
```
java">list.remove(1); // 删除索引 1 处的元素
```
随机访问：
- 通过 get(int index) 方法访问元素时，LinkedList 需要从头或尾遍历链表，时间复杂度为 O(n)。
```
java">int value = list.get(0); // 获取索引 0 处的元素
```