单链表（Singly Linked List）
单链表是链表的一种基本形式，每个节点只包含一个后继指针（next），只能单向遍历。
节点结构
class ListNode {
int val; // 节点值
ListNode next; // 后继指针（指向下一个节点）
}
基本特性
| 特性 | 说明 |
|---|---|
| 指针数量 | 1个（next） |
| 遍历方向 | 单向（只能向后） |
| 内存开销 | 较小（每个节点只存一个指针） |
| 操作复杂度 | 较简单 |
操作时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查/改（给定索引） | O(N) | 必须从头遍历 |
| 头部插入 | O(1) | 新节点指向原头结点，更新头指针 |
| 尾部插入 | O(N)* | 需遍历到尾部；*若持有尾引用则为O(1) |
| 中间插入 | O(N) | 需先找到前驱节点 |
| 头部删除 | O(1) | 直接移动头指针 |
| 尾部删除 | O(N) | 需找到倒数第二个节点（前驱） |
| 中间删除 | O(N) | 需先找到前驱节点 |
工程实现要点
1. 持有尾引用优化
private Node<E> head;
private Node<E> tail; // 尾节点引用
private int size;
优点：
- 尾部添加可优化到 O(1)
- 删除尾节点时，正好需遍历找前驱，可顺便更新尾引用
注意：
- 删除尾节点后，尾引用失效，需更新
- 删除时需遍历到倒数第二个节点，此时可同时更新尾引用
2. 虚拟头节点
使用虚拟头节点（dummy head）简化边界处理：
private Node<E> head = new Node<>(null); // 虚拟头节点
private Node<E> tail = head; // 尾指针初始指向虚拟头
优点：统一头部、中间插入/删除的逻辑，避免空指针判断
3. 删除时的指针清理
Node<E> toRemove = prev.next;
prev.next = toRemove.next;
toRemove.next = null; // 清理指针（好习惯）
虽然 Java GC 不要求（只关心是否被引用，不关心引用别人），但清理指针是好习惯。
完整实现参考
参见：链表实现
与双链表对比
| 特性 | 单链表 | 双链表 |
|---|---|---|
| 指针数量 | 1个（next） | 2个（prev + next） |
| 遍历方向 | 单向 | 双向 |
| 内存开销 | 小 | 大（多一个指针） |
| 删除尾节点 | O(N) | O(1)（有前驱指针） |
| 实现复杂度 | 简单 | 稍复杂 |