java.util.LinkedList 是 Java 集合框架的核心类，底层基于双向链表实现，实现了 List 和 Deque 接口，兼具列表、队列、双端队列、栈的功能。

1.核心特点

• 双向链表结构：每个节点存储前一个节点、数据、后一个节点，支持快速的首尾增删
• 非线程安全：多线程环境下需手动加锁或使用并发集合
• 访问效率低：随机访问（通过索引找元素）需要遍历链表，时间复杂度 O (n)
• 增删效率高：已知节点位置时，增删仅需修改节点引用，时间复杂度 O (1)
• 允许 null 值：可以存储 null 元素
• 有序、可重复：元素存储顺序与插入顺序一致，允许重复元素

2.常用构造方法

// 1. 创建空的 LinkedList
LinkedList<String> list = new LinkedList<>();

// 2. 通过已有集合创建 LinkedList
List<String> arrayList = new ArrayList<>(List.of("a", "b"));
LinkedList<String> list2 = new LinkedList<>(arrayList);

3.核心常用方法

1.增（添加元素）

LinkedList<String> list = new LinkedList<>();
list.add("Java");         // 尾部添加（List 标准方法）
list.addFirst("C++");     // 头部添加
list.addLast("Python");   // 尾部添加（等价于 add()）
list.offer("Go");         // 尾部添加（队列方法）
list.offerFirst("PHP");   // 头部添加
list.offerLast("Rust");   // 尾部添加

2.删（删除元素）

list.removeFirst();       // 删除并返回头部元素
list.removeLast();        // 删除并返回尾部元素
list.remove(0);           // 根据索引删除
list.remove("Java");      // 根据元素删除（删除第一个匹配项）
list.poll();              // 删除并返回头部元素（空链表返回null，不抛异常）
list.pollFirst();         // 删除并返回头部
list.pollLast();          // 删除并返回尾部

3.查（获取元素）

list.getFirst();          // 获取头部元素
list.getLast();           // 获取尾部元素
list.get(2);              // 根据索引获取元素（效率低）
list.peek();              // 获取头部元素（不删除）
list.peekFirst();         // 获取头部
list.peekLast();          // 获取尾部
list.contains("Python");  // 判断是否包含元素

4.改（修改元素）

list.set(1, "JavaScript"); // 修改索引1的元素为 JavaScript

5.其他常用方法

list.size();              // 获取元素个数
list.isEmpty();           // 判断是否为空
list.clear();             // 清空链表
list.toArray();           // 转为数组

4.遍历方式

LinkedList 不推荐用普通 for 循环遍历（效率极低），优先使用以下方式：

LinkedList<String> list = new LinkedList<>(List.of("A", "B", "C"));

// 1. 增强 for 循环（最常用）
for (String s : list) {
    System.out.println(s);
}

// 2. 迭代器遍历
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

// 3. forEach() 方法（Java 8+）
list.forEach(System.out::println);

5.LinkedList 与 ArrayList 对比

特性	LinkedList	ArrayList
底层结构	双向链表	动态数组
随机访问效率	低（O (n)）	高（O (1)）
增删效率（首尾）	高（O (1)）	低（需扩容 / 移动元素）
内存占用	高（每个节点存前后引用）	低（连续内存）
使用场景	频繁增删、少查询、队列 / 栈	频繁查询、少增删

 

6.使用场景

• 需要频繁在首尾添加 / 删除元素（如消息队列、任务队列）
• 需要实现栈、队列、双端队列（LinkedList 是 Deque 最常用实现类）
• 对随机访问效率要求不高的场景

7.源码

1.Node内部类

LinkedList底层通过双向链表实现

//Node内部类
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;
    }
}

2.方法剖析

add()

add()方法有两个版本，一个是add(E e)，该方法在LinkedList的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是add(int index, E element)，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。

 

结合上图，可以看出add(E e)的逻辑非常简单。

//add(E e)
public boolean add(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++;
    return true;
}

add(int index, E element)的逻辑稍显复杂，可以分成两部，1.先根据index找到要插入的位置；2.修改引用，完成插入操作

//add(int index, E element)
public void add(int index, E element) {
	checkPositionIndex(index);//index >= 0 && index <= size;
	if (index == size)//插入位置是末尾，包括列表为空的情况
        add(element);
    else{
    	Node<E> succ = node(index);//1.先根据index找到要插入的位置
        //2.修改引用，完成插入操作。
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//插入位置为0
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
}

上面代码中的node(int index)函数有一点小小的trick，因为链表双向的，可以从开始往后找，也可以从结尾往前找，具体朝那个方向找取决于条件index < (size >> 1)，也即是index是靠近前端还是后端。

remove()

两个删除操作都要1.先找到要删除元素的引用，2.修改相关引用，完成删除操作。在寻找被删元素引用的时候remove(Object o)调用的是元素的equals方法，而remove(int index)使用的是下标计数，两种方式都是线性时间复杂度。在步骤2中，两个revome()方法都是通过unlink(Node<E> x)方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

//unlink(Node<E> x)，删除一个Node
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;//let GC work
    size--;
    return element;
}

get()

get(int index)得到指定下标处元素的引用，通过调用上文中提到的node(int index)方法实现。

public E get(int index) {
    checkElementIndex(index);//index >= 0 && index < size;
    return node(index).item;
}

set()

set(int index, E element)方法将指定下标处的元素修改成指定值，也是先通过node(int index)找到对应下表元素的引用，然后修改Node中item的值。

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;//替换新值
    return oldVal;
}