LinkedList 是 Java 集合框架中一个非常重要且常用的实现类，它内部基于双向链表数据结构,这使得它在插入和删除操作上具有非常高的效率。

核心概念：什么是双向链表？

在理解 LinkedList 之前，必须先理解它背后的数据结构——双向链表。

与数组（ArrayList 的基础）不同，链表不要求元素在内存中是连续存储的，它由一系列节点 组成。

• 节点: 每个节点包含三部分：

  1. 数据: 存储的元素本身。
  2. 前驱指针: 指向前一个节点的引用。
  3. 后继指针: 指向后一个节点的引用。

• 结构:

  
  （图片来源网络，侵删）

  [Data|Prev|Next] <-> [Data|Prev|Next] <-> [Data|Prev|Next]
     (head)                                      (tail)

  • head (头节点): 指向链表的第一个节点。
  • tail (尾节点): 指向链表的最后一个节点。
  • null: 链表的第一个节点的前驱指针和最后一个节点的后继指针都指向 null。

这种结构决定了 LinkedList 的所有特性。

LinkedList 类的层次结构

LinkedList 实现了多个接口,这决定了它的行为和能力。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

• List<E>: 表明它是一个列表，可以存放有序、可重复的元素，支持通过索引访问（尽管效率不高）。
• Deque<E>: 表明它是一个“双端队列”，可以把它当作队列或栈来使用，这使得 LinkedList 非常灵活。
• AbstractSequentialList<E>: 提供了基于“顺序访问”（即通过迭代器遍历）的 List 接口的骨干实现，LinkedList 继承了它来简化代码。

LinkedList 的主要特点

优点

1. 高效的插入和删除:

   • 场景: 在已知位置的节点（通过迭代器定位的节点）进行插入或删除。
   • 时间复杂度: O(1)。
   • 原因: 只需要修改前后节点的指针即可，要在节点 A 和 B 之间插入节点 C，只需让 A.next 指向 C，C.prev 指向 A，B.prev 指向 C，C.next 指向 B,这个过程与链表的长度无关。

2. 没有初始容量限制:

   
   （图片来源网络，侵删）
   • 与 ArrayList 不同，LinkedList 不需要预先分配一块连续的内存空间，它按需动态地创建和添加节点,因此内存的使用更加灵活。

3. 可以作为双端队列、栈或队列使用:

   • 由于实现了 Deque 接口，它提供了丰富的方法：
     • 栈: push(), pop() (操作头部)
     • 队列: offer(), poll() (操作头部)
     • 双端队列: offerFirst(), pollLast() 等。

缺点

1. 较慢的随机访问:

   • 场景: 通过索引 get(index) 或 set(index, element) 访问元素。
   • 时间复杂度: O(n)。
   • 原因: 链表中的元素不是连续存储的，要访问第 index 个元素，必须从头节点（或尾节点，取决于 index 的位置）开始，一个一个地遍历，直到找到目标位置，当 index 接近链表中间时,效率最低。

2. 内存开销较大:

   • 每个节点除了存储数据外，还需要额外存储两个指针（prev 和 next），这比 ArrayList 仅存储数据要多一定的内存开销。

3. 缓存不友好:

   • ArrayList 的元素在内存中是连续的，CPU 的预取机制可以一次性将相邻的数据加载到缓存中，访问速度极快，而 LinkedList 的节点分散在内存各处，每次访问都可能引发缓存未命中,导致性能下降。

常用方法详解

LinkedList vs ArrayList (核心区别)

这是一个面试中非常经典的问题。

代码示例

示例 1：基本操作

import java.util.LinkedList;
public class LinkedListExample {
    public static void main(String[] args) {
        // 创建一个 LinkedList
        LinkedList<String> friends = new LinkedList<>();
        // 添加元素到尾部
        friends.add("Alice");
        friends.add("Bob");
        friends.add("Charlie");
        System.out.println("初始列表: " + friends); // [Alice, Bob, Charlie]
        // 添加元素到头部
        friends.addFirst("David");
        System.out.println("添加头部后: " + friends); // [David, Alice, Bob, Charlie]
        // 添加元素到尾部 (另一种方式)
        friends.addLast("Eve");
        System.out.println("添加尾部后: " + friends); // [David, Alice, Bob, Charlie, Eve]
        // 在指定位置插入
        friends.add(2, "Frank");
        System.out.println("在索引2插入后: " + friends); // [David, Alice, Frank, Bob, Charlie, Eve]
        // 获取元素
        String firstFriend = friends.getFirst();
        System.out.println("第一个朋友: " + firstFriend); // David
        // 移除元素
        String removed = friends.remove(); // 默认移除头部
        System.out.println("移除头部元素: " + removed); // David
        System.out.println("移除后列表: " + friends); // [Alice, Frank, Bob, Charlie, Eve]
        // 移除指定元素
        friends.remove("Bob");
        System.out.println("移除 Bob 后: " + friends); // [Alice, Frank, Charlie, Eve]
    }
}

示例 2：作为队列和栈使用

import java.util.LinkedList;
import java.util.Queue;
import java.util.Deque;
public class LinkedListAsQueueAndStack {
    public static void main(String[] args) {
        // --- 作为队列 使用 ---
        Queue<String> queue = new LinkedList<>();
        queue.offer("A"); // 入队
        queue.offer("B");
        queue.offer("C");
        System.out.println("队列: " + queue); // [A, B, C]
        System.out.println("队首元素 (peek): " + queue.peek()); // A
        System.out.println("出队 (poll): " + queue.poll()); // A
        System.out.println("出队后队列: " + queue); // [B, C]
        System.out.println("--------------------");
        // --- 作为栈 使用 ---
        Deque<String> stack = new LinkedList<>();
        stack.push("X"); // 入栈
        stack.push("Y");
        stack.push("Z");
        System.out.println("栈: " + stack); // [Z, Y, X]
        System.out.println("栈顶元素 (peek): " + stack.peek()); // Z
        System.out.println("出栈 (pop): " + stack.pop()); // Z
        System.out.println("出栈后栈: " + stack); // [Y, X]
    }
}

总结与最佳实践

何时选择 LinkedList？

1. 频繁的头部/中间插入和删除: 当你的应用场景主要是对数据进行频繁的增删操作，并且这些操作大多发生在列表的头部或中间位置时，LinkedList 的性能远超 ArrayList。
2. 作为队列或栈使用: 当你需要一个 Deque 或 Queue 的实现时，LinkedList 是一个简单且高效的选择。
3. 数据量不确定且变化剧烈: 如果你无法预估最终的数据量，LinkedList 的动态特性避免了 ArrayList 频繁扩容带来的性能抖动。

何时避免使用 LinkedList？

1. 频繁的随机访问: 如果你需要通过索引频繁地读取或修改元素，ArrayList 是不二之选。
2. 主要是尾部操作: 对于以尾部添加和删除为主的场景，ArrayList 的性能通常更好（因为 add(E e) 是 O(1)）,并且内存更紧凑。
3. 追求极致性能: 在大多数情况下，ArrayList 是更通用的选择，除非你有明确的理由需要 LinkedList 的特性。

一句话总结:

ArrayList 像一个数组，擅长“查”；LinkedList 像一串珠子，擅长“增删”。 根据你的主要操作类型来选择合适的工具。