一、鏈式存儲結構概述

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指向下一個待處理結點}}