Java LinkedList（一文讲透）

Java LinkedList：链表结构的底层原理与实战应用

在 Java 的集合框架中，LinkedList 是一个非常重要的数据结构实现。它与 ArrayList 不同，不是基于数组，而是基于双向链表的结构。这种设计让 LinkedList 在某些特定场景下表现优异，比如频繁的插入和删除操作。对于初学者来说，理解 LinkedList 的工作方式，有助于更深入地掌握 Java 集合框架的底层逻辑。

如果你把数组想象成一排整齐的书架，那么 LinkedList 就像是用绳子串起来的一串书。每一本书（节点）都包含内容和指向前后书的指针。这种结构意味着你不需要移动其他书就能随时插入或移除某本书，非常灵活。

什么是 Java LinkedList？

Java LinkedList 是 java.util 包下的一个类，实现了 List 接口，同时也实现了 Deque 接口，这意味着它既可以作为列表使用，也可以作为双端队列使用。它内部使用双向链表结构，每个节点包含三个部分：

• 存储的数据（元素）
• 指向下一个节点的引用（next）
• 指向前一个节点的引用（prev）

这种结构使得 LinkedList 在插入和删除操作时，只需修改几个指针，而不需要像数组那样移动大量元素。

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        // 创建一个空的 LinkedList
        LinkedList<String> list = new LinkedList<>();

        // 向链表末尾添加元素
        list.add("苹果");
        list.add("香蕉");
        list.add("橙子");

        // 输出当前链表内容
        System.out.println("链表内容：" + list);
        // 输出：链表内容：[苹果, 香蕉, 橙子]
    }
}

注释：这里创建了一个 LinkedList<String>，表示链表中存储的是字符串类型。add() 方法会将元素添加到链表的末尾，底层通过修改指针完成，无需移动其他元素。

基本操作详解：增删改查

Java LinkedList 提供了丰富的操作方法，支持在任意位置插入、删除和访问元素。我们来逐一讲解。

添加元素

add() 方法将元素添加到链表末尾，addFirst() 和 addLast() 分别在头部和尾部添加元素。

LinkedList<Integer> numbers = new LinkedList<>();

// 添加到末尾
numbers.add(10);
numbers.add(20);

// 添加到头部
numbers.addFirst(5);

// 添加到尾部（等价于 add）
numbers.addLast(30);

System.out.println("添加后：" + numbers);
// 输出：添加后：[5, 10, 20, 30]

注释：addFirst(5) 会将 5 放在链表的第一个位置，addLast(30) 与 add(30) 效果相同，都是添加到末尾。

删除元素

删除操作有多种方式，removeFirst() 删除第一个元素，removeLast() 删除最后一个，remove(Object) 删除指定对象。

LinkedList<String> fruits = new LinkedList<>();
fruits.add("草莓");
fruits.add("蓝莓");
fruits.add("樱桃");

// 删除第一个元素
fruits.removeFirst();
System.out.println("删除第一个后：" + fruits);
// 输出：删除第一个后：[蓝莓, 樱桃]

// 删除指定元素
fruits.remove("蓝莓");
System.out.println("删除蓝莓后：" + fruits);
// 输出：删除蓝莓后：[樱桃]

注释：remove(Object) 方法会查找链表中第一个匹配的元素并删除，如果不存在则返回 false。

查找与访问

get(int index) 可以根据索引获取元素，indexOf() 返回元素第一次出现的位置。

LinkedList<String> colors = new LinkedList<>();
colors.add("红色");
colors.add("绿色");
colors.add("蓝色");
colors.add("绿色");

// 根据索引获取元素
String color = colors.get(1);
System.out.println("索引 1 的颜色：" + color);
// 输出：索引 1 的颜色：绿色

// 查找元素位置
int index = colors.indexOf("绿色");
System.out.println("绿色第一次出现的位置：" + index);
// 输出：绿色第一次出现的位置：1

注释：get() 方法会从头或尾开始遍历链表，找到对应索引的节点。由于链表不是随机访问结构，性能低于数组。

高级用法：作为双端队列使用

由于 LinkedList 实现了 Deque 接口，它可以作为双端队列（Deque）使用，支持在两端进行插入和删除操作，非常适合实现栈（LIFO）和队列（FIFO）。

import java.util.Deque;
import java.util.LinkedList;

public class DequeExample {
    public static void main(String[] args) {
        // 将 LinkedList 当作双端队列使用
        Deque<String> queue = new LinkedList<>();

        // 模拟队列：先进先出
        queue.offerFirst("任务 A");  // 从头部插入
        queue.offerLast("任务 B");   // 从尾部插入
        queue.offerLast("任务 C");

        System.out.println("队列内容：" + queue);
        // 输出：队列内容：[任务 A, 任务 B, 任务 C]

        // 从头部取出任务（FIFO）
        String task = queue.pollFirst();
        System.out.println("取出任务：" + task);
        // 输出：取出任务：任务 A
    }
}

注释：offerFirst() 和 offerLast() 是安全的插入方法，即使在某些情况下插入失败也不会抛出异常。pollFirst() 会移除并返回第一个元素，如果链表为空则返回 null。

性能对比：LinkedList vs ArrayList

注释：虽然 LinkedList 在首尾插入删除上表现优异，但它的随机访问性能较差。如果你经常按索引读取元素，ArrayList 更合适。

实际应用场景与最佳实践

在实际开发中，Java LinkedList 适合以下场景：

• 需要频繁在列表开头或结尾插入/删除元素
• 实现缓存机制（如 LRU 缓存，用链表记录访问顺序）
• 构建栈或队列结构
• 数据量大且插入删除频繁，但访问较少

但要注意，LinkedList 的内存开销较大，每个节点都需要额外的空间存储前后指针。因此，除非有明确的性能需求，否则建议优先使用 ArrayList。

// 示例：使用 LinkedList 实现简单的 LRU 缓存
public class LRUCache {
    private final LinkedList<String> cache = new LinkedList<>();
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public void put(String key) {
        // 如果已存在，先删除旧位置
        if (cache.contains(key)) {
            cache.remove(key);
        }

        // 如果容量满，删除最久未使用的（头部）
        if (cache.size() >= capacity) {
            cache.removeFirst();
        }

        // 将新元素放到尾部（最新使用）
        cache.addLast(key);
    }

    public void printCache() {
        System.out.println("当前缓存：" + cache);
    }
}

注释：这个简单的 LRU 缓存利用了 LinkedList 的顺序特性。每次访问元素时将其移到末尾，头部就是最久未使用的，适合用作缓存淘汰策略。

总结

Java LinkedList 是一个功能强大且灵活的数据结构。它通过双向链表实现，特别适合在头部或尾部频繁插入和删除的场景。虽然它在随机访问方面性能不如 ArrayList，但其指针操作的高效性在特定场景下具有不可替代的优势。

掌握 Java LinkedList，不仅能提升你对集合框架的理解，还能在实际项目中做出更合理的数据结构选择。建议你在设计数据结构时，先思考操作模式：是频繁插入删除？还是频繁读取？再根据实际需求选择合适的数据结构。

最后提醒：不要盲目追求“高性能”，选择合适才是最好的。在大多数情况下，ArrayList 已经足够优秀，只有在明确需要链表特性时，才考虑使用 LinkedList。