【4】单链表（有虚拟头节点）

1、虚拟头节点

📕 为了让代码更精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟头节点

🖊 头指针指向的永远是虚拟头节点
🖊 虚拟头节点不存储数据

2、构造方法

📕 在 单链表 代码的基础上需要进行修改

🖊 头指针 first 永远指向虚拟头节点，所以在 VirtualHeadLinkedList 的构造方法中要让 first 指针虚拟头节点

    public VirtualHeadLinkedList() {
        // 头指针指向虚拟头节点
        // 虚拟头节点的next默认指向null
        first = new Node<>(null, null);
    }

3、node(int index) 返回索引位置的节点

🖊 该方法会返回索引位置的节点，它原本的实现思路是：若需要 index 位置的节点，则从 first 头指针指向的头节点开始 next index 次

🖊 加入了虚拟头节点后，就不能从 first 头指针指向的头节点开始 next index 次了，而是从虚拟头节点的 next 指向的节点开始 next

    /**
     * 返回index索引处的节点
     */
    private Node<E> node(int index) {
        checkIndex(index);

        // first头指针指向的是虚拟头节点
        // first.next就是具体存储数据的第一个节点
        Node<E> node = first.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

4、添加

🖊 之前的添加逻辑：
① 假如是往头节点位置添加元素：first 指向新节点，新节点的 next 指向之前的头节点
② 若不是往头节点位置添加元素：找到 index-1 索引处的节点 prev，然后新节点的 next 指向 prev.next，然后 prev.next 指向新节点

🖊 增加虚拟头节点后： 如果 index == 0，prev 就是虚拟头节点（first)

    /**
     * 往索引位置添加元素
     */
    @Override
    public void add(int index, E element) {
        checkIndex4Add(index);

        // 如果index==0, prev是虚拟头节点
        Node<E> prev = (index == 0) ? first : node(index - 1);
        prev.next = new Node<>(element, prev.next);
        size++;
    }

5、删除

🖊 假如删除的是 index == 0 位置的节点，则 prev 就是虚拟头节点

    /**
     * 删除索引位置的元素
     *
     * @return 被删除的元素
     */
    @Override
    public E remove(int index) {
        checkIndex(index);

        Node<E> prev = (index == 0) ? first : node(index - 1);
        Node<E> node = prev.next;
        prev.next = node.next;

        size--;
        return node.element;
    }

6、ArrayList 复杂度分析

(1) 复杂度分析

◼ 最好情况复杂度
◼ 最坏情况复杂度
◼ 平均情况复杂度

📕 add：
🖊 假如 index == size（往最后面添加元素）：无需挪动元素（时间复杂度是 O(1)）最好时间复杂度
🖊 假如 index == 0：整个数组需要往后挪动（时间复杂度是 O(n)）最坏时间复杂度
🖊 平均时间复杂度：(1 + 2 + ... + n) / n = n/2【挪动1次、2次、...、 n次】

(2) 数组的随机访问

🖊 数组的随机访问速度非常快
🖊 elements[n] 的效率与 n 是多少无关

📕 假设存放的是 int 类型的元素（每个元素的地址相差四个字节）：
🖊 地址值 = index * 4 + 数组首元素的地址

(3) 动态数组 add(E element) 复杂度分析

◼ 最好：O(1)
◼ 最坏：O(n)
◼ 平均：O(1)
◼ 均摊：O(1)

🖊 add(E element) 永远是往数组的最后面添加元素，可能会有扩容的情况产生
🖊 扩容的时间复杂度是 O(n)
🖊 但是该方法大部分情况下的时间复杂度都是 O(1)，只有极少数情况是O(n)【均摊复杂度】

📕 什么情况下适合使用均摊复杂度❓
🖊经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况

(4) 动态数组的缩容

📕 如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作
🖊 比如剩余空间占总容量的一半时，就进行缩容

  /**
   * 缩容
   */
  private void trim() {
      // 当前容量：elements数组最多可以存储的元素个数
      int curCap = elements.length;
      int newCap = curCap >> 1;

      if (size >= newCap || newCap <= DEFAULT_CAPACITY) return; // 不缩容

      E[] newElements = (E[]) new Object[newCap];
      // 把旧数组元素复制到新数组中
      for (int i = 0; i < size; i++) {
          newElements[i] = elements[i];
      }

      elements = newElements;
      System.out.println("🖊缩容：" + curCap + "→" + newCap);
  }

(5) 复杂度震荡

📕 如果扩容倍数、缩容时机设计不得当，有可能会导致复杂度震荡

🖊 上图假如一直执行增、删、增、删、增、删…操作的话，就会出现扩容、缩容、扩容、缩容、扩容、缩容…的情况
🖊 出现此情况是因为：扩容为2倍（2）和剩余空间大于等于总容量一半（1/2）的时候缩容【扩容倍数和缩容时机的乘积不要等于1】

7、单链表复杂度分析

🖊 单链表效率比较低主要是因为 node(int index) 方法，它有 for 循环（数据规模可能是 n）

🖊 有的资料说链表添加和删除的复杂度是O(1)，这说的是添加和删除的 “哪一刻”，但找到 prev 的时间复杂度可能是 O(n)

8、完整代码

🖊 带有虚拟头节点的单链表完整代码