一、链式存储结构概述

1. 基本概念（逻辑分析）

核心思想：用指针将离散的存储单元串联成逻辑上连续的线性表

设计动机：解决顺序表 "预先分配空间" 与 "动态扩展" 的矛盾

关键特性：

1. 结点空间动态分配，适应数据量动态变化
2. 插入删除仅需修改指针，无需移动大量元素
3. 存储单元离散，不要求连续内存空间

二、单链表（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 结点）

• 核心难点：如何在不丢失原指针的前提下完成插入

• 操作步骤：

1. 先让新结点 s 指向 p 的原后继（避免指针丢失）
2. 再让 p 指向新结点 s（完成链表连接）

• 安全原则：始终遵循 "先连接新结点后继，再连接原结点后继" 的顺序

// 插入逻辑示意图（思路：两步指针修改完成插入）s.next = p.next; // 步骤1：新结点先指向原后继，防止指针丢失p.next = s; // 步骤2：原结点指向新结点，完成插入

（2）删除操作（删除 p 结点的后继）

• 核心思路：通过修改 p 的 next 指针，直接跳过待删除结点

• 内存管理：Java 自动垃圾回收，无需手动释放结点内存

p.next = p.next.next; // 思路：让p直接指向原后继的后继，跳过待删除结点

（3）头插法建表（CreateListF）

• 算法思想：

1. 从空表开始，逐个处理数组元素
2. 每个新结点始终插入到表头（头结点之后）
3. 最终链表顺序与数组顺序相反

• 适用场景：需要逆序构建链表的场景

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）

• 算法思想：

1. 用尾指针 t 跟踪链表尾部
2. 新结点始终插入到 t 之后
3. 每次插入后更新 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）

• 算法思路：

1. 从 head 开始遍历
2. 用计数器 j 记录当前遍历到的序号
3. 当 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）

• 算法步骤：

1. 新建结点 s 存储元素 e
2. 查找当前尾结点（p.next==null）
3. 将尾结点的 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）

• 计数思路：

1. 从 head 开始遍历
2. 每次遇到非空 next 时计数器 + 1
3. 直到遇到 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）
• 本质：通过数学计算减少遍历次数
• 算法步骤：

1. 计算长度 n
2. 遍历 (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）

• 算法思路：

1. 将原链表置为空表（head.next=null）
2. 逐个取出原链表结点
3. 每次将结点插入到新链表的表头

• 关键技巧：使用临时变量 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指向下一个待处理结点}}