前言
链表是数据结构中非常基础且重要的线性表结构。在 Java 集合框架中,LinkedList 是对这一结构的经典实现。如果你已经掌握了顺序表(如 ArrayList)的基础,理解 LinkedList 会更容易上手。我们将从集合框架出发,结合底层原理和代码实战来展开。
一、Java 集合框架概览
Java 集合体系主要分为 Collection(单列)和 Map(双列)。
- Collection:所有单列集合的根接口,定义了增删改查、遍历等基本操作。主要子接口包括 List(有序可重复)、Set(无序不可重复)和 Queue(队列)。
- Map:存储键值对(Key-Value),Key 唯一,Value 可重复。
今天重点聚焦于 LinkedList,它位于 Collection 体系下的 List 分支。
LinkedList 的核心特性
-
实现的接口
List:具备列表的增删改查能力,支持索引访问。Deque:具备双端队列特性,可作为栈或队列使用。
-
底层结构
- 基于双向链表,每个节点存储前驱和后继节点的引用。
- 无容量限制,动态扩容。
-
性能特点
- 随机访问:效率较低(O(n)),因为需要从头遍历到指定索引。
- 增删操作:在链表两端或已知节点附近效率高(O(1)),无需移动元素。
- 线程安全:非线程安全,多线程环境下需手动同步。
二、链表的数据结构原理
在数据结构层面,链表通过非连续的存储单元连接元素。理解其节点构成是掌握 LinkedList 的关键。
- 节点(Node):基本存储单元,包含数据域(业务数据)和指针域(指向下一个/上一个节点的引用)。
- 头指针:指向第一个节点的引用,是访问入口。
- 尾节点:最后一个节点,指针域通常指向 null(单向)或头节点(循环)。
图:单向链表结构示意图
三、手动实现单链表逻辑
虽然 Java 提供了现成的 LinkedList,但手动实现能帮助我们深刻理解其内部机制。这里我们以无头结点的单向链表为例,涵盖基本成员变量、核心方法及辅助方法。
1. 节点定义与初始化
static class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public class MyLinkedList {
private ListNode head;
ListNode {
();
();
();
();
();
node0.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
head = node0;
head;
}


