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 实现类，可以显著提高程序性能。