java-list源码分析
List底层：List 是 Java 中的一个接口，具体的底层实现取决于它的实现类。最常见的 List 实现类是 ArrayList 和 LinkedList，它们的底层原理完全差别。下面我们分别分析这两种实现类的底层原理。
ArryList原理：
ArrayList 是基于动态数组实现的，它的底层是一个可调整大小的数组。
核心特点
[*]底层数据布局：ArrayList 利用一个 Object[] 数组来存储元素。
[*]动态扩容：当数组容量不足时，ArrayList 会自动扩容（通常是当前容量的 1.5 倍）。
[*]随机访问：由于是基于数组实现的，ArrayList 支持通过索引快速访问元素，时间复杂度为 O(1)。
[*]插入和删除：在中心插入或删除元素时，需要移动后续元素，时间复杂度为 O(n)。
底层实现细节：
[*]初始化：
[*]默认情况下，ArrayList 的初始容量为 10。
[*]可以通过构造函数指定初始容量。
List<Integer> list = new ArrayList<>(); // 默认容量为 10
List<Integer> list = new ArrayList<>(20); // 指定初始容量为 20
[*]添加元素
[*]当调用 add(E e) 方法时，元素会被添加到数组的末尾。
[*]如果数组已满，ArrayList 会触发扩容机制：
[*]创建一个新的数组，大小为原数组的 1.5 倍（int newCapacity = oldCapacity + (oldCapacity >> 1)）。
[*]将原数组中的元素复制到新数组中。
[*]更新引用，指向新数组。
list.add(10); // 添加元素
[*]插入元素
[*]当调用 add(int index, E element) 方法时，ArrayList 会将指定位置及其后续元素向后移动一位，然后插入新元素。
[*]如果需要扩容，会先扩容再插入。
list.add(1, 20); // 在索引 1 处插入元素
[*]删除元素
[*]当调用 remove(int index) 方法时，ArrayList 会将指定位置之后的元素向前移动一位，覆盖被删除的元素。
[*]末了将数组的末了一个位置设置为 null，以便垃圾接纳。
list.remove(1); // 删除索引 1 处的元素
[*]随机访问：
[*]通过 get(int index) 方法可以直接访问数组中的元素，时间复杂度为 O(1)。
int value = list.get(0); // 获取索引 0 处的元素
LinkedList 的底层原理
LinkedList 是基于双向链表实现的，它的底层是一个由节点（Node）构成的链表。
核心特点
[*]底层数据布局：LinkedList 利用双向链表存储元素，每个节点包罗数据、前驱节点和后继节点的引用。
[*]动态大小：链表的大小可以动态调整，不需要扩容。
[*]插入和删除：在链表中插入或删除元素时，只需要修改节点的引用，时间复杂度为 O(1)。
[*]随机访问：访问链表中的元素需要重新或尾遍历，时间复杂度为 O(n)。
底层实现细节
[*]节点布局：
[*]每个节点是一个 Node 对象，包罗三个部分：
[*]E item：存储元素。
[*]Node next：指向下一个节点。
[*]Node prev：指向上一个节点。
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 指向新节点。
list.add(10); // 在链表末尾添加元素
[*]插入元素：
[*]当调用 add(int index, E element) 方法时，LinkedList 会遍历链表找到指定位置，然后插入新节点。
[*]插入操作只需要修改相邻节点的引用。
list.add(1, 20); // 在索引 1 处插入元素
[*]删除元素：
[*]当调用 remove(int index) 方法时，LinkedList 会遍历链表找到指定位置，然后修改相邻节点的引用，跳过被删除的节点。
[*]被删除的节点会被垃圾接纳。
list.remove(1); // 删除索引 1 处的元素
[*]随机访问：
[*]通过 get(int index) 方法访问元素时，LinkedList 需要重新或尾遍历链表，时间复杂度为 O(n)。
int value = list.get(0); // 获取索引 0 处的元素
其他 List 实现类
[*]Vector：与 ArrayList 雷同，但是线程安全的（同步的），性能较低。
[*]Stack：继承自 Vector，实现了栈数据布局（后进先出）。
[*]CopyOnWriteArrayList：线程安全的 List，适合读多写少的场景。
总结
[*]ArrayList 基于动态数组实现，适合随机访问和尾部操作。
[*]LinkedList 基于双向链表实现，适合频繁插入和删除操作。
[*]根据具体需求选择合适的 List 实现类，可以明显进步步伐性能。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]