一、链式存储结构概述
1. 基本概念（逻辑分析）
核心思想：用指针将离散的存储单元串联成逻辑上连续的线性表
设计动机：解决顺序表 "预先分配空间" 与 "动态扩展" 的矛盾
关键特性：
- 结点空间动态分配，适应数据量动态变化
- 插入删除仅需修改指针，无需移动大量元素
- 存储单元离散，不要求连续内存空间
二、单链表（Single Linked List）
1. 结点与链表类定义（设计思路）
（1）LinkNode 结点类设计
- 数据域 data：存储元素值，采用泛型 E 实现类型通用化
- 指针域 next：指向下一结点，形成单向链表链
- 构造方法重载：提供无参（初始空结点）和有参（初始化数据）两种构造方式
（2）LinkListClass 链表类设计
- 头结点 head：哑结点设计，避免处理空表时的特殊情况
- 空表初始化：头结点的 next 指针置 null，形成 "头结点 + 空数据区" 的初始结构
// 单链表结点泛型类（逻辑：每个结点保存数据和后继指针）
class LinkNode<E> {
E data; // 数据域，存储元素值
LinkNode<E> next; // 指针域，指向下一结点
public LinkNode() {
next = null; // 无参构造：初始时不指向任何结点
}
public LinkNode(E d) {
data = d; // 有参构造：初始化数据域
next = null;
}
}
// 单链表泛型类（逻辑：通过头结点管理整个链表）
public class LinkListClass<E> {
LinkNode<E> head; // 头结点，不存储实际数据
public LinkListClass() {
head = new LinkNode<E>(); // 创建头结点
head.next = null; // 初始时头结点不指向任何数据结点
}
// 基本运算算法...
}2. 核心操作实现（逻辑解析）
（1）插入操作（在 p 结点后插入 s 结点）
- 核心难点：如何在不丢失原指针的前提下完成插入
- 操作步骤：
- 先让新结点 s 指向 p 的原后继（避免指针丢失）
- 再让 p 指向新结点 s（完成链表连接）
- 安全原则：始终遵循 "先连接新结点后继，再连接原结点后继" 的顺序
// 插入逻辑示意图（思路：两步指针修改完成插入）
s.next = p.next; // 步骤1：新结点先指向原后继，防止指针丢失
p.next = s; // 步骤2：原结点指向新结点，完成插入（2）删除操作（删除 p 结点的后继）
- 核心思路：通过修改 p 的 next 指针，直接跳过待删除结点
- 内存管理：Java 自动垃圾回收，无需手动释放结点内存
p.next = p.next.next; // 思路：让p直接指向原后继的后继，跳过待删除结点（3）头插法建表（CreateListF）
- 算法思想：
- 从空表开始，逐个处理数组元素
- 每个新结点始终插入到表头（头结点之后）
- 最终链表顺序与数组顺序相反
- 适用场景：需要逆序构建链表的场景
public void CreateListF(E[] a) {
LinkNode<E> s;
for (int i = 0; i < a.length; i++) {
s = new LinkNode<E>(a[i]);
s.next = head.next; // 新结点先指向原表头，保持链表连续性
head.next = s; // 头结点指向新结点，完成表头插入
}
}（4）尾插法建表（CreateListR）
- 算法思想：
- 用尾指针 t 跟踪链表尾部
- 新结点始终插入到 t 之后
- 每次插入后更新 t 为新的尾结点
- 关键优化：避免头插法的 O (n) 查找尾结点操作，时间复杂度优化为 O (1)
public void CreateListR(E[] a) {
LinkNode<E> s, t;
t = head; // t初始指向头结点，作为初始尾结点
for (int i = 0; i < a.length; i++) {
s = new LinkNode<E>(a[i]);
t.next = s; // 尾结点指向新结点
t = s; // 尾指针更新为新结点
}
t.next = null; // 最后一个结点的next置null，标识链表尾部
}3. 基本运算实现（逻辑拆解）
（1）获取指定序号的结点（geti）
- 算法思路：
- 从 head 开始遍历
- 用计数器 j 记录当前遍历到的序号
- 当 j 等于目标序号 i 时返回对应结点
- 边界处理：i=-1 时返回头结点（用于插入操作的前驱查找）
private LinkNode<E> geti(int i) {
LinkNode<E> p = head; // 从头结点开始遍历
int j = -1; // j=-1对应头结点，j=0对应首数据结点
while (j < i) {
j++;
p = p.next; // 指针后移
}
return p; // 返回序号为i的结点
}（2）添加元素到表尾（Add）
- 算法步骤：
- 新建结点 s 存储元素 e
- 查找当前尾结点（p.next==null）
- 将尾结点的 next 指向 s
- 时间复杂度：O (n)，需遍历链表查找尾结点
public void Add(E e) {
LinkNode<E> s = new LinkNode<E>(e);
LinkNode<E> p = head;
while (p.next != null) {
p = p.next; // 循环找到尾结点
}
p.next = s; // 尾结点指向新结点
}（3）求表长度（size）
- 计数思路：
- 从 head 开始遍历
- 每次遇到非空 next 时计数器 + 1
- 直到遇到 null 指针（链表尾部）
- 优化方向：若维护 size 变量，可将时间复杂度降为 O (1)
public int size() {
LinkNode<E> p = head;
int cnt = 0;
while (p.next != null) {
cnt++;
p = p.next; // 指针后移并计数
}
return cnt;
}4. 应用算法示例（问题解决思路）
（1）查找中间位置元素（两种算法对比）
计数法（Middle1）
- 问题分析：已知链表长度 n，中间位置为：
- 奇数长度：(n-1)/2+1（如 n=3，位置 2
- 偶数长度：(n-1)/2+1（如 n=4，位置 2）
- 本质：通过数学计算减少遍历次数
- 算法步骤：
- 计算长度 n
- 遍历 (n-1)/2 次到达中间结点
public static int Middle1(LinkListClass<Integer> L) {
int j = 1, n = L.size();
LinkNode<Integer> p = L.head.next; // p指向首结点（序号1）
while (j <= (n - 1) / 2) { // 需遍历(n-1)/2次
j++;
p = p.next;
}
return p.data;
}快慢指针法（Middle2）
- 核心思想：
- 快指针每次走 2 步，慢指针每次走 1 步
- 当快指针到达末尾时，慢指针恰好到达中间
- 时间优化：只需 O (n) 时间，无需两次遍历
public static int Middle2(LinkListClass<Integer> L) {
LinkNode<Integer> slow = L.head.next; // 慢指针
LinkNode<Integer> fast = L.head.next; // 快指针
while (fast.next != null && fast.next.next != null) {
slow = slow.next; // 慢指针走1步
fast = fast.next.next; // 快指针走2步
}
return slow.data; // 快指针无法再走2步时，慢指针指向中间
}（2）逆置链表（Reverse）
- 算法思路：
- 将原链表置为空表（head.next=null）
- 逐个取出原链表结点
- 每次将结点插入到新链表的表头
- 关键技巧：使用临时变量 q 保存后继结点，防止指针丢失
public static void Reverse(LinkListClass<Integer> L) {
LinkNode<Integer> p = L.head.next, q; // p指向首结点
L.head.next = null; // 清空原链表（仅保留头结点）
while (p != null) {
q = p.next; // 保存p的后继结点，防止断链
p.next = L.head.next; // 插入到表头（头结点之后）
L.head.next = p;
p = q; // p指向下一个待处理结点
}
}