1 概述

LinkedList 和 ArrayList 是 Java 集合框架中的两个重要类，它们分别基于链表和动态数组实现。LinkedList 选择链表作为其底层数据结构的原因在于链表在某些操作上具有显著的优势。

1.1 链表的优势

• 动态大小：链表不需要预先分配固定大小的内存，可以根据需要动态扩展或缩小，避免了数组扩容时的性能开销。
• 插入和删除操作高效：在链表中插入或删除元素时，只需要调整相邻节点的指针，而不需要像数组那样移动大量元素。例如，删除中间的元素时，链表只需要修改前后节点的指针，而数组需要移动大量元素。

1.2 链表的层次

• 单向链表：每个节点只有一个指针，指向下一个节点
• 双向链表：每个节点有两个指针，分别指向前一个节点和后一个节点
• 二叉树：将链表的指针结构进一步扩展，形成树状结构，用于更复杂的操作和数据组织

2 LinkedList核心数据结构

2.1 Node类

Node 类是 LinkedList 的私有静态内部类，用于表示链表中的节点。每个节点包含三个部分：

• 节点上的元素：存储在节点中的数据
• 下一个节点：指向下一个节点的指针
• 上一个节点：指向上一个节点的指针

Node类代码

/**
 * 链表中的节点类。
 */
private static class Node<E> {
    E item; // 节点中存储的元素
    Node<E> next; // 指向下一个节点的指针
    Node<E> prev; // 指向上一个节点的指针

    /**
     * 构造一个新的节点。
     *
     * @param prev 前一个节点
     * @param element 节点中要存储的元素
     * @param next 后一个节点
     */
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element; // 存储元素
        this.next = next; // 设置下一个节点
        this.prev = prev; // 设置上一个节点
    }
}

2.2 结点结构图示

链表中节点的关系：

• 第一个节点：prev 为 null
• 最后一个节点：next 为 null
• 其余节点：prev 指向前一个节点，next 指向下一个节点

3 LinkedList的增删改查方法

3.1 初始化

在 Java 中，LinkedList 和 ArrayList 的初始化方式有所不同。ArrayList 在初始化时可以指定大小，也可以不指定，等到添加第一个元素时进行第一次扩容。而 LinkedList 则没有大小限制，只要内存足够大，它可以无限扩展。

LinkedList<String> list = new LinkedList();

3.2 增加

• 调用 add() 方法添加元素
• addFirst() 方法将元素添加到第一位
• addLast() 方法将元素添加到末尾

3.2.1 add() 方法

• 调用 add() 方法添加元素

 // 调用 add 方法添加元素
 list.add("zhangsan1");
 list.add("zhangsan2");
 list.add("zhangsan3");

• add 方法内部其实调用的是 linkLast 方法

/**
 * 将指定的元素添加到列表的尾部。
 *
 * @param e 要添加到列表的元素
 * @return 始终为 true（根据 Java 集合框架规范）
 */
public boolean add(E e) {
    linkLast(e); // 在列表的尾部添加元素
    return true; // 添加元素成功，返回 true
}

• linkLast方法在链表的尾部添加元素

/**
 * 在列表的尾部添加指定的元素。
 *
 * @param e 要添加到列表的元素
 */
void linkLast(E e) {
    final Node<E> l = last; // 获取链表的最后一个节点
    final Node<E> newNode = new Node<>(l, e, null); // 创建一个新的节点，并将其设置为链表的最后一个节点
    last = newNode; // 将新的节点设置为链表的最后一个节点
    if (l == null) // 如果链表为空，则将新节点设置为头节点
        first = newNode;
    else
        l.next = newNode; // 否则将新节点链接到链表的尾部
    size++; // 增加链表的元素个数
}

3.2.2 addFirst() 方法

• addFirst() 方法将元素添加到第一位

// addFirst() 方法将元素添加到第一位
list.addFirst("wangwu1");

• add 方法内部其实调用的是 linkFirst 方法

/**
 * 在列表的开头添加指定的元素。
 *
 * @param e 要添加到列表的元素
 */
public void addFirst(E e) {
    linkFirst(e); // 在列表的开头添加元素
}

• linkFirst 负责把新的节点设为 first，并将新的 first 的 next 更新为之前的 first

/**
 * 在列表的开头添加指定的元素。
 *
 * @param e 要添加到列表的元素
 */
private void linkFirst(E e) {
    final Node<E> f = first; // 获取链表的第一个节点
    final Node<E> newNode = new Node<>(null, e, f); // 创建一个新的节点，并将其设置为链表的第一个节点
    first = newNode; // 将新的节点设置为链表的第一个节点
    if (f == null) // 如果链表为空，则将新节点设置为尾节点
        last = newNode;
    else
        f.prev = newNode; // 否则将新节点链接到链表的头部
    size++; // 增加链表的元素个数
}

3.2.3 addLast() 方法

• addLast() 方法将元素添加到末尾

// addLast() 方法将元素添加到末尾
list.addLast("wangwu2");

• addLast 的内核其实和 addFirst 差不多，内部调用的是 linkLast 方法，linkLast方法详解见3.2.1

/**
 * 在列表的尾部添加指定的元素。
 *
 * @param e 要添加到列表的元素
 * 
 */
public boolean addLast(E e) {
    linkLast(e); // 在列表的尾部添加元素
}

3.3 删除

• remove()：删除第一个节点
• remove(int)：删除指定位置的节点
• remove(Object)：删除指定元素的节点
• removeFirst()：删除第一个节点
• removeLast()：删除最后一个节点

3.3.1 remove()方法

• remove()：删除第一个节点

// remove()：删除第一个节点
list.remove();

• 调用removeFirst()方法

public E remove() {
    return removeFirst();
}

• removeFirst 内部调用的是 unlinkFirst 方法

/**
 * 从链表中删除第一个元素并返回它。
 * 如果链表为空，则抛出 NoSuchElementException 异常。
 *
 * @return 从链表中删除的第一个元素
 * @throws NoSuchElementException 如果链表为空
 */
public E removeFirst() {
    final Node<E> f = first; // 获取链表的第一个节点
    if (f == null) // 如果链表为空
        throw new NoSuchElementException(); // 抛出 NoSuchElementException 异常
    return unlinkFirst(f); // 调用 unlinkFirst 方法删除第一个节点并返回它的元素
}

• unlinkFirst 负责的就是把第一个节点毁尸灭迹，并且捎带把后一个节点的 prev 设为 null

/**
 * 删除链表中的第一个节点并返回它的元素。
 *
 * @param f 要删除的第一个节点
 * @return 被删除节点的元素
 */
private E unlinkFirst(Node<E> f) {
    final E element = f.item; // 获取要删除的节点的元素
    final Node<E> next = f.next; // 获取要删除的节点的下一个节点
    f.item = null; // 将要删除的节点的元素设置为 null
    f.next = null; // 将要删除的节点的下一个节点设置为 null
    first = next; // 将链表的头节点设置为要删除的节点的下一个节点
    if (next == null) // 如果链表只有一个节点
        last = null; // 将链表的尾节点设置为 null
    else
        next.prev = null; // 将要删除节点的下一个节点的前驱设置为 null
    size--; // 减少链表的大小
    return element; // 返回被删除节点的元素
}

3.3.2 remove(int)方法

• remove(int)：删除指定位置的节点

// remove(int)：删除指定位置的节点
list.remove(2);

• remove(int) 内部其实调用的是unlink方法

/**
 * 删除指定位置上的元素。
 *
 * @param index 要删除的元素的索引
 * @return 从列表中删除的元素
 * @throws IndexOutOfBoundsException 如果索引越界（index < 0 || index >= size()）
 */
public E remove(int index) {
    checkElementIndex(index); // 检查索引是否越界
    return unlink(node(index)); // 删除指定位置的节点，并返回节点的元素
}

• unlink 方法其实就是更新当前节点的 next 和 prev，然后把当前节点上的元素设为 null

/**
 * 从链表中删除指定节点。
 *
 * @param x 要删除的节点
 * @return 从链表中删除的节点的元素
 */
E unlink(Node<E> x) {
    final E element = x.item; // 获取要删除节点的元素
    final Node<E> next = x.next; // 获取要删除节点的下一个节点
    final Node<E> prev = x.prev; // 获取要删除节点的上一个节点

    if (prev == null) { // 如果要删除节点是第一个节点
        first = next; // 将链表的头节点设置为要删除节点的下一个节点
    } else {
        prev.next = next; // 将要删除节点的上一个节点指向要删除节点的下一个节点
        x.prev = null; // 将要删除节点的上一个节点设置为空
    }

    if (next == null) { // 如果要删除节点是最后一个节点
        last = prev; // 将链表的尾节点设置为要删除节点的上一个节点
    } else {
        next.prev = prev; // 将要删除节点的下一个节点指向要删除节点的上一个节点
        x.next = null; // 将要删除节点的下一个节点设置为空
    }

    x.item = null; // 将要删除节点的元素设置为空
    size--; // 减少链表的元素个数
    return element; // 返回被删除节点的元素
}

3.3.3 remove(Object)方法

• remove(Object)：删除指定元素的节点

// remove(Object)：删除指定元素的节点
list.remove("zhangsan3");

• remove(Object) 内部也调用了 unlink 方法，只不过在此之前要先找到元素所在的节点

/**
 * 从链表中删除指定元素。
 *
 * @param o 要从链表中删除的元素
 * @return 如果链表包含指定元素，则返回 true；否则返回 false
 */
public boolean remove(Object o) {
    if (o == null) { // 如果要删除的元素为 null
        for (Node<E> x = first; x != null; x = x.next) { // 遍历链表
            if (x.item == null) { // 如果节点的元素为 null
                unlink(x); // 删除节点
                return true; // 返回 true 表示删除成功
            }
        }
    } else { // 如果要删除的元素不为 null
        for (Node<E> x = first; x != null; x = x.next) { // 遍历链表
            if (o.equals(x.item)) { // 如果节点的元素等于要删除的元素
                unlink(x); // 删除节点
                return true; // 返回 true 表示删除成功
            }
        }
    }
    return false; // 如果链表中不包含要删除的元素，则返回 false 表示删除失败
}

元素为 null 的时候，必须使用 == 来判断；元素为非 null 的时候，要使用 equals 来判断。

• unlink方法详解见3.3.2

3.3.4 removeFirst()方法

• removeFirst()：删除第一个节点

// removeFirst()：删除第一个节点
list.removeFirst();

• removeFirst 内部调用的是 unlinkFirst 方法，removeFirst方法详情见3.3.1。
• unlinkFirst 负责的就是把第一个节点毁尸灭迹，并且捎带把后一个节点的 prev 设为 null，unlinkFirst方法详情见3.3.1。

3.3.5 removeLast()方法

• removeLast()：删除最后一个节点

// removeLast()：删除最后一个节点
list.removeLast();

• removeLast方法内部调用unlinkLast方法

/**
 * 移除并返回此列表中的最后一个元素。
 *
 * @return 此列表中的最后一个元素
 * @throws NoSuchElementException 如果此列表为空
 */
public E removeLast() {
    // 获取最后一个节点
    final Node<E> l = last;
    
    // 如果最后一个节点为空，说明列表为空，抛出 NoSuchElementException 异常
    if (l == null)
        throw new NoSuchElementException();
    
    // 调用 unlinkLast 方法移除最后一个节点，并返回被移除的元素
    return unlinkLast(l);
}

• unlinkLast 方法用于移除链表中的最后一个节点，并返回被移除的元素。该方法会更新链表的 last 指针，处理链表为空的情况，并清理被移除节点的引用以帮助垃圾回收。最后，它返回被移除的元素，并更新链表的大小

/**
 * 移除非空的最后一个节点 l。
 *
 * @param l 要移除的最后一个节点
 * @return 被移除的元素
 */
private E unlinkLast(Node<E> l) {

    
    // 获取最后一个节点的元素
    final E element = l.item;
    
    // 获取最后一个节点的前一个节点
    final Node<E> prev = l.prev;
    
    // 将最后一个节点的元素和前指针置为 null，帮助 GC 回收
    l.item = null;
    l.prev = null; // help GC
    
    // 更新 last 指针，使其指向最后一个节点的前一个节点
    last = prev;
    
    // 如果前一个节点为 null，说明链表中只有一个节点，移除后链表为空
    if (prev == null)
        first = null; // 将 first 指针置为 null
    else
        prev.next = null; // 否则，将前一个节点的 next 指针置为 null
    
    // 减少链表的大小
    size--;
    
    // 返回被移除的元素
    return element;
}

3.4 修改

3.4.1 set()方法

• 调用 set() 方法来更新元素

list.set(0, "lisi");

• set() 方法将链表中指定位置的元素替换为指定元素，并返回原来的元素

/**
 * 将链表中指定位置的元素替换为指定元素，并返回原来的元素。
 *
 * @param index 要替换元素的位置（从 0 开始）
 * @param element 要插入的元素
 * @return 替换前的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围（index < 0 || index >= size()）
 */
public E set(int index, E element) {
    checkElementIndex(index); // 检查索引是否超出范围
    Node<E> x = node(index); // 获取要替换的节点
    E oldVal = x.item; // 获取要替换节点的元素
    x.item = element; // 将要替换的节点的元素设置为指定元素
    return oldVal; // 返回替换前的元素
}

• node方法获取链表中指定位置的节点

/**
 * 获取链表中指定位置的节点。
 *
 * @param index 节点的位置（从 0 开始）
 * @return 指定位置的节点
 * @throws IndexOutOfBoundsException 如果索引超出范围（index < 0 || index >= size()）
 */
Node<E> node(int index) {
    if (index < (size >> 1)) { // 如果索引在链表的前半部分
        Node<E> x = first;
        for (int i = 0; i < index; i++) // 从头节点开始向后遍历链表，直到找到指定位置的节点
            x = x.next;
        return x; // 返回指定位置的节点
    } else { // 如果索引在链表的后半部分
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) // 从尾节点开始向前遍历链表，直到找到指定位置的节点
            x = x.prev;
        return x; // 返回指定位置的节点
    }
}

size >> 1：也就是右移一位，相当于除以 2。
换句话说，node 方法会对下标进行一个初步判断，如果靠近前半截，就从下标 0 开始遍历；如果靠近后半截，就从末尾开始遍历，这样可以提高效率，最大能提高一半的效率。
找到指定下标的节点就简单了，直接把原有节点的元素替换成新的节点就 OK 了，prev 和 next 都不用改动

3.5 查询

3.5.1 indexOf(Object)方法

• indexOf(Object)：查找某个元素所在的位置

list.indexOf("zhangsan1")

• indexOf()方法：返回链表中首次出现指定元素的位置，如果不存在该元素则返回 -1。

/**
 * 返回链表中首次出现指定元素的位置，如果不存在该元素则返回 -1。
 *
 * @param o 要查找的元素
 * @return 首次出现指定元素的位置，如果不存在该元素则返回 -1
 */
public int indexOf(Object o) {
    int index = 0; // 初始化索引为 0
    if (o == null) { // 如果要查找的元素为 null
        for (Node<E> x = first; x != null; x = x.next) { // 从头节点开始向后遍历链表
            if (x.item == null) // 如果找到了要查找的元素
                return index; // 返回该元素的索引
            index++; // 索引加 1
        }
    } else { // 如果要查找的元素不为 null
        for (Node<E> x = first; x != null; x = x.next) { // 从头节点开始向后遍历链表
            if (o.equals(x.item)) // 如果找到了要查找的元素
                return index; // 返回该元素的索引
            index++; // 索引加 1
        }
    }
    return -1; // 如果没有找到要查找的元素，则返回 -1
}

3.5.2 get(int)方法

• get(int)：查找某个位置上的元素

list.get(2)；

• get 方法的内核其实还是 node 方法，node 方法之前已经说明过了，详细说明见3.4.1

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

3.5.3 其它查询方法

• getFirst() 方法用于获取第一个元素
• getLast() 方法用于获取最后一个元素
• poll() 和 pollFirst() 方法用于删除并返回第一个元素
• pollLast() 方法用于删除并返回最后一个元素
• peekFirst() 方法用于返回但不删除第一个元素

4 LinkedList的挑战

4.1 时间复杂度比较

• ArrayList

  • 添加元素：在末尾添加元素的时间复杂度为 O(1)，但在中间或开头添加元素时，需要移动后续元素，时间复杂度为 O(n)
  • 删除元素：删除元素时，需要移动后续元素，时间复杂度为 O(n)
  • 查找元素：通过索引查找元素的时间复杂度为 O(1)，但通过值查找元素的时间复杂度为 O(n)

• LinkedList

  • 添加元素：在任意位置添加元素的时间复杂度为 O(1)，因为只需要调整相邻节点的指针
  • 删除元素：在任意位置删除元素的时间复杂度为 O(1)，因为只需要调整相邻节点的指针
  • 查找元素：通过索引查找元素的时间复杂度为 O(n)，因为需要从头或尾遍历链表

4.2 应用场景

• 游戏道具栏
  在游戏中，道具栏需要频繁地添加和删除道具。使用 LinkedList 可以快速完成这些操作，因为只需要调整相邻节点的指针，而不需要移动大量元素

• LRU 缓存淘汰算法
  LRU（Least Recently Used）缓存淘汰算法是一种常用的缓存淘汰策略，当缓存空间不够时，优先淘汰最近最少使用的缓存数据。使用 LinkedList 可以高效地实现 LRU 缓存淘汰算法，每次访问缓存数据时，将其移动到链表头部，链表尾部即为最近最少使用的缓存数据，当缓存空间不够时，只需淘汰链表尾部的数据

5 思维导图

6 参考链接

LinkedList控诉：我爹都嫌弃我！