Java LinkedList（千字长文）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

在 Java 的集合框架中，LinkedList 是一个兼具实用性与学习价值的数据结构。它不仅能够灵活处理动态数据的增删操作，还为开发者提供了链表这一经典数据结构的直观实现。对于编程初学者而言，理解 LinkedList 的工作原理是掌握数据结构与算法的重要一步；而中级开发者则可以通过深入分析其底层逻辑，进一步优化代码性能。本文将从基础概念、实现原理到实际应用，系统性地解析 LinkedList 的核心知识点，并通过案例演示其应用场景。

一、什么是 Java LinkedList？

LinkedList 是 Java 集合框架中 List 接口的一个实现类，它基于双向链表（Doubly Linked List）结构。与 ArrayList 不同，LinkedList 的元素并非连续存储在内存中，而是通过每个节点（Node）保存数据和指向前后节点的指针（即引用）。这种设计使得 LinkedList 在插入和删除操作上具有高效性，但对随机访问（如通过索引直接获取元素）的效率较低。

链表 vs 火车车厢：一个形象比喻

想象一列火车的车厢：每个车厢（节点）都包含一个载货区（数据域）和两个挂钩（前后指针），前挂钩指向前面的车厢，后挂钩指向后面的车厢。当需要在中间插入新车厢时，只需调整相邻车厢的挂钩即可，无需移动整列火车的其他部分。这正是 LinkedList 的核心优势——动态扩展性强。

二、LinkedList 的内部结构解析

1. 节点（Node）的组成

每个 Node 对象包含三个关键部分：

• item：存储实际数据的字段（类型为 Object）。
• next：指向下一个节点的引用。
• prev：指向上一个节点的引用。

通过双向指针的设计，LinkedList 可以高效地从任意位置向前或向后遍历。

2. 链表的头尾指针

LinkedList 类中维护了两个核心指针：

• first：指向链表的第一个节点。
• last：指向链表的最后一个节点。

这两个指针帮助 LinkedList 快速定位链表的两端，从而在添加或删除元素时减少遍历次数。

三、LinkedList 的核心操作与性能分析

1. 常用方法与实现逻辑

以下列举 LinkedList 的核心方法及其底层实现逻辑：

（1）添加元素

• add(E e)：默认将元素添加到链表末尾。

  public boolean add(E e) {  
      linkLast(e); // 调用私有方法，直接连接到 last 节点的 next  
      return true;  
  }  
  

  时间复杂度：平均 O(1)，因为无需移动其他元素。

• addFirst(E e)：将元素添加到链表头部。

  public void addFirst(E e) {  
      linkFirst(e); // 直接修改 first 指针的 prev  
  }  
  

  时间复杂度：O(1)。

（2）删除元素

• remove()：删除并返回第一个元素。
• removeFirst()：与 remove() 功能相同。
• removeLast()：删除并返回最后一个元素。

（3）访问元素

• get(int index)：通过索引访问元素。

  public E get(int index) {  
      // 从头或尾开始遍历，选择距离较近的方向  
      Node<E> x = (index < (size >> 1))  
          ? node(index, 0) // 从头遍历  
          : node(size - 1 - index, 1); // 从尾遍历  
      return x.item;  
  }  
  

  时间复杂度：O(n)，因为需要遍历到目标节点。

2. 性能对比表格

以下表格对比了 ArrayList 和 LinkedList 在不同操作上的性能差异：

四、LinkedList 的典型应用场景

1. 频繁插入和删除操作的场景

当需要在列表中间频繁增删元素时，LinkedList 是更优选择。例如：

// 模拟队列：先进先出  
LinkedList<String> queue = new LinkedList<>();  
queue.addLast("任务1");  
queue.addLast("任务2");  
System.out.println(queue.removeFirst()); // 输出"任务1"  

2. 实现 LRU 缓存算法

LinkedList 的双向特性使其适合实现 LRU（最近最少使用）缓存：

class LRUCache<K, V> {  
    private final Map<K, Node<K, V>> map;  
    private final LinkedList<Node<K, V>> list;  
    // ...  
    public V get(K key) {  
        Node<K, V> node = map.get(key);  
        if (node != null) {  
            list.remove(node); // 删除旧位置  
            list.addFirst(node); // 移动到头部  
            return node.value;  
        }  
        return null;  
    }  
}  

3. 需要双向遍历的场景

由于 LinkedList 的双向指针特性，可以轻松实现“上一条”和“下一条”的导航功能：

LinkedList<String> songs = new LinkedList<>(Arrays.asList("Song1", "Song2", "Song3"));  
Node<String> current = songs.getFirst();  
System.out.println(current); // 输出Song1  
current = current.next; // 下一首  
System.out.println(current); // 输出Song2  
current = current.prev; // 返回上一首  
System.out.println(current); // 输出Song1  

五、常见误区与最佳实践

1. 误区：盲目选择 LinkedList

虽然 LinkedList 在增删操作上高效，但若应用以随机访问为主（如频繁使用 get(index)），则 ArrayList 的 O(1) 时间复杂度更优。

2. 最佳实践：根据需求选择数据结构

• 需要快速增删且访问较少 → 选择 LinkedList。
• 需要频繁访问且顺序存储 → 选择 ArrayList。

3. 注意空指针和越界异常

在操作 LinkedList 时，需确保索引或元素存在，否则会抛出 IndexOutOfBoundsException 或 NullPointerException。例如：

LinkedList<Integer> list = new LinkedList<>();  
// list.get(0); // 抛出异常：列表为空  
if (!list.isEmpty()) {  
    System.out.println(list.get(0));  
}  

六、总结

通过本文的讲解，我们系统性地剖析了 Java LinkedList 的核心概念、实现原理及应用场景。其基于双向链表的结构使其在动态数据管理中表现出色，但开发者需结合具体需求选择合适的数据结构。无论是实现队列、缓存，还是需要灵活的增删操作，LinkedList 都是一个值得掌握的工具。未来的学习中，建议进一步探索链表的变体（如循环链表、跳表）以及更复杂的算法实现，以深化对数据结构的理解。