一、Java 集合框架
Java 集合框架是 Java 中用于存储和操作一组对象的体系，核心分为 Collection（单列集合）和 Map（双列集合）。
核心接口与分类
- Collection（单列集合）：是所有单列集合的根接口，定义了集合的基本操作（增删改查、遍历等）。子接口包括 List（有序可重复）、Set（无序不可重复）、Queue（队列）。
- Map（双列集合）：存储键值对（Key-Value），Key 唯一、Value 可重复。子接口包括 SortedMap（键有序）。
LinkedList 简介
- 实现的接口
- 实现了 List 接口（具备列表的增删改查能力）；
- 实现了 Deque 接口（同时具备双端队列的特性，可作为栈、队列使用）。
- 核心特性
- 结构：基于双向链表，每个节点存储前驱、后继节点的引用，无容量限制；
- 访问效率：随机访问（通过索引 get(i)）效率低（时间复杂度 O(n)），需遍历链表；
- 增删效率：在链表两端 / 已知节点附近增删元素效率高（时间复杂度 O(1)）；
- 线程不安全：多线程环境下需手动同步。
List 接口
这是 LinkedList 作为列表的核心接口，它继承自 Collection 接口，定义了有序集合的基础行为。
- 核心约定：元素有序可重复，支持通过索引访问（如 get(int index)、set(int index, E element)）；支持增删改查的全量列表操作，例如 add(E e)、remove(int index)、contains(Object o) 等。
- 对 LinkedList 的影响：LinkedList 必须实现索引相关的方法，但由于其底层是双向链表，索引访问需要遍历链表（时间复杂度 O(n)），这也是它和 ArrayList（数组实现，索引访问 O(1)）的核心区别。
Deque 接口
这是 LinkedList 区别于 ArrayList 的关键接口，它是双端队列的核心接口。
- 核心约定：允许在队列两端进行元素的插入、删除和获取操作，同时兼容队列和栈的行为。
- 队列行为：遵循先进先出（FIFO），如 offer(E e)（队尾入队）、poll()（队首出队）；
- 双端操作：支持队首 / 队尾双向操作，如 addFirst(E e)（队首添加）、addLast(E e)（队尾添加）、getFirst()（获取队首）、getLast()（获取队尾）；
- 栈行为：遵循后进先出（LIFO），可通过 push(E e)（等效于 addFirst，入栈）、pop()（等效于 removeFirst，出栈）实现栈功能。
- 对 LinkedList 的影响：由于 LinkedList 是双向链表，天然支持首尾节点的 O(1) 时间复杂度操作，因此它是 Deque 接口的最优实现之一。
Cloneable 与 Serializable 接口
- Cloneable：标记接口，表示类的实例可以通过 clone() 方法实现浅拷贝。
- Serializable：标记接口，表示类的实例可以进行序列化（将对象转化为字节流）和反序列化。
Iterable 接口
所有集合类的顶层接口之一，定义了迭代遍历的能力。实现 iterator() 方法，返回一个 Iterator 迭代器，支持对集合元素的遍历。
二、链表数据结构
在数据结构中，链表是用非连续的存储单元存储元素的线性表。
基本组成
- 节点（Node）：链表的基本存储单元，通常包含两部分数据：
- 数据域：存储实际的业务数据；
- 指针域：存储下一个（或上一个）节点的内存地址 / 引用，用于建立节点间的关联。
- 头节点 / 头指针：头指针指向链表第一个节点的引用，是访问整个链表的入口；头节点（可选）在第一个数据节点前额外添加的空节点，作用是统一链表首尾的操作逻辑。
- 尾节点：链表的最后一个节点，其指针域通常指向 null（单向链表）或头节点（循环链表）。
三、手动实现单链表
以下展示无头结点的单项链表的手动实现逻辑。
基本成员变量
static class ListNode {
int val;
ListNode next;
// 构造方法实例化节点
public ListNode(int val) {
this.val = val;
}
}
// 定义 listNode 的头结点
public ListNode head;
基本方法
// 创建链表示例
public ListNode createList() {
ListNode node0 = new ListNode(11);
ListNode node1 = new ListNode(11);
ListNode node2 = new ListNode(11);
ListNode node3 = new ListNode(11);
ListNode node4 = new ListNode(11);
node0.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
head = node0;
return head;
}
// 头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
// 尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
// 链表为空直接插入
if (head == null) {
head = node;
return;
}
// 找到最后一个
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
// 任意位置插入，第一个数据节点为 0 号下标
public void addIndex(int index, int data) {
// 检查 index
if (index < 0 || index > size()) {
System.out.println("index 不合法");
return;
}
// 头插入
if (index == 0) {
addFirst(data);
return;
}
// 尾插入
if (index == size()) {
addLast(data);
return;
}
// 中间插入
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
public ListNode findIndex(int index) {
ListNode cur = head;
int count = 0;
while (count != index - 1) {
cur = cur.next;
count++;
}
return cur;
}
// 查找是否包含关键字 key 是否在单链表当中
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
// 删除第一次出现关键字为 key 的节点
public void remove(int key) {
// 空链表情况
if (head == null) {
System.out.println("空链表异常");
return;
}
// 删除第一个元素
if (head.val == key) {
head = head.next;
return;
}
// 处理中间部分
// 找到 del 之前的 ret
ListNode ret = search(key);
if (ret == null) {
System.out.println("没有要删除元素");
return;
}
ListNode del = ret.next;
ret.next = del.next;
}
public ListNode search(int val) {
ListNode cur = head;
while (cur.next != null) {
if (cur.next.val == val) {
return cur;
}
cur = cur.next;
}
return null;
}
// 删除所有值为 key 的节点
public void removeAllKey(int key) {
// 第一空链表情况
if (head == null) {
System.out.println("空链表异常");
return;
}
ListNode prev = head;
ListNode cur = head.next;
// 处理中间部分
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
} else {
prev = cur;
cur = cur.next;
}
}
// 最后处理头节点
if (head.val == key) {
head = head.next;
}
}
// 得到单链表的长度
public int size() {
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
public void clear() {
ListNode cur = head;
while (cur != null) {
ListNode crn = cur.next;
// 在删除节点之前保存之后的节点
cur.next = crn;
cur = crn;
}
head = null;
}
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
四、LinkedList 使用
构造方法
- 无参构造器 LinkedList() 仅初始化一个空的双向链表：头指针（first）和尾指针（last）默认都为 null；元素个数（size）初始化为 0。
- 带集合参数的 LinkedList(Collection<? extends E> c) 调用无参构造器初始化空链表，然后调用 addAll 方法将传入的 Collection 集合中的元素按迭代顺序批量添加到链表尾部。
官方常用方法
需要注意每个方法的返回类型、方法名和形参。建议动手操作以熟悉 API。
五、LinkedList 的遍历
直接打印
System.out.println(list);
For 循环
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
for (Integer x : list) {
System.out.print(x + " ");
}
迭代器
在 Java 集合框架中，迭代器（Iterator）是用于遍历集合元素的统一接口，提供了一种不依赖集合底层结构的遍历方式。
- hasNext()：判断是否还有下一个元素。
- next()：返回下一个元素。
// 普通迭代器
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
// List 专用迭代器（支持反向遍历）
ListIterator<Integer> iterator1 = list.listIterator(list.size());
while (iterator1.hasPrevious()) {
System.out.print(iterator1.previous() + " ");
}
总结
本文涵盖了 Java 集合框架中 LinkedList 的原理、接口分析及手动实现代码，对比了不同操作的性能差异，并展示了常用的遍历方式。