当前位置：首页 > news >正文

数据结构：在链表中查找（Searching in a Linked List）

news 2025/8/2 7:59:52

第一步：思考搜索的本质是什么？

第二步：从数据结构角度推导搜索流程

用递归来写查找

递归必须包含两个核心成分：

链表查找的优化

换位法（transposition）

🔍 具体交换步骤

完整过程总结图解

移到表头（Move-to-Head）

🔍 具体实现步骤

我们先明确问题是什么

你现在有一个链表，例如：

head → [10 | * ] → [25 | * ] → [38 | * ] → [NULL]

你想查找某个“值”（value），例如 25。

我们要回答：

这个值在链表中有没有？
如果有，它在哪个节点？
如果没有，返回什么？

第一步：思考搜索的本质是什么？

搜索的本质是：

依次访问链表中的每个节点，判断当前节点是否是目标值。

由于链表不像数组那样有下标，也不能用二分法（链表不能随机访问），我们只能从头走到尾。

这引出两个核心限制：

链表只能按顺序访问（顺着 next 指针跳）
查找必须从第一个节点开始，直到找到或走到 NULL

举个例子：我们想查找目标值 25，链表是：

head → [10] → [25] → [38] → NULL

我们访问过程是：

访问 head → data = 10，不等于 25
跳到下一个 → data = 25，找到了！
结束搜索

第二步：从数据结构角度推导搜索流程

我们有节点结构如下：

struct Node {int data;struct Node* next;
};

你已经有一个链表头指针：

struct Node* head;

搜索步骤：

从 head 开始
判断 head->data 是否等于目标值
如果不是，就跳到 head->next
重复这个过程，直到：
- 找到：返回找到的节点
- 或者遇到 NULL：表示没找到

✅ 我们可以写成 while 循环

struct Node* temp = head;
while (temp != NULL) {if (temp->data == key) {// 找到了}temp = temp->next;
}

如何设计函数接口？

最基础的设计是：

struct Node* search(struct Node* head, int key);

输入：

链表头指针 head
要查找的整数值 key

输出：

如果找到了，返回指向该节点的指针
如果找不到，返回 NULL

背后逻辑总结

问题	答案（第一性）
为什么不能用下标？	链表不支持随机访问，只能靠指针跳转
为什么要从头到尾遍历？	因为链表没有索引，也不能跳跃访问
为什么返回指针？	因为节点不在数组里，不能返回下标，只能返回地址
为什么要判断 temp != NULL？	如果跳到 NULL，表示已经到达链表尾部

完整代码

#include <stdio.h>
#include <stdlib.h>// 节点结构
struct Node {int data;struct Node* next;
};// 查找函数：返回包含 key 的节点指针，找不到返回 NULL
struct Node* search(struct Node* head, int key) {struct Node* temp = head;while (temp != NULL) {if (temp->data == key) {return temp;}temp = temp->next;}return NULL;
}int main() {// 构建链表：10 → 25 → 38struct Node* head = (struct Node*) malloc(sizeof(struct Node));struct Node* second = (struct Node*) malloc(sizeof(struct Node));struct Node* third = (struct Node*) malloc(sizeof(struct Node));head->data = 10; head->next = second;second->data = 25; second->next = third;third->data = 38; third->next = NULL;// 测试查找int key = 25;struct Node* result = search(head, key);if (result != NULL) {printf("Found %d at node address %p\n", key, result);} else {printf("%d not found in the list.\n", key);}// 释放内存free(head);free(second);free(third);return 0;
}

用递归来写查找

如何把链表查找从循环形式转化为递归（recursion）形式？

本质逻辑是：

依次从 head 开始往下走，每次判断当前节点是不是目标
如果是就返回指针
否则继续查下一节点

现在我们问一个本质问题：

每一次查找，其实都是：“看当前节点是不是目标；如果不是，就在剩下的链表中继续查找”

❗这是一种自相似结构（self-similar structure）：

原问题：在链表中查找 key
子问题：在 head->next 链表中查找 key

这种“自己包含自己的结构”是递归的本质特征，所以，我们可以用递归来写查找！

递归必须包含两个核心成分：

1️⃣ 递归终止条件（base case）

我们必须规定：

如果链表为空：head == NULL → 说明没找到 → return NULL
如果当前节点是目标：head->data == key → 找到了 → return head

2️⃣ 递归调用（reduction step）

如果当前节点不是目标，且链表未结束：

就在剩下的链表中继续找：

return search(head->next, key);

完整递归函数

struct Node* search(struct Node* head, int key) {if (head == NULL)return NULL;  // 空链表，找不到if (head->data == key)return head;  // 找到目标return search(head->next, key);  // 在剩下的链表中找
}

链表查找的优化

在标准单链表中：

我们为了查找一个值，只能：

从 head 开始，一步步走
最坏情况下访问 n 次（O(n)）

但是现实中：

某些数据被频繁查找，例如：

最近访问过的网页
最近用过的文件

那我们有没有方法让“常查找的元素”更快被找到？

我们能不能把常用的值移到靠前的位置？

答案是：可以。

于是诞生了两种经典的启发式（heuristic）查找优化策略：

名称	核心思想
transposition	每次找到元素后，把它和前一个元素交换
move-to-head	每次找到元素后，把它移到表头

同样的思路也适用于数组：数据结构：数组：线性查找（Linear Search）-CSDN博客

换位法（transposition）

每当我们在链表中成功找到一个节点后，就把它和它的“前一个节点”交换位置。

举例：现在有链表：

head → [a] → [b] → [c] → [d] → NULL

你查找的是 c

普通查找就是找到它就完了，什么也不变。

换位法查找找到 c 后，把它和前一个 b 交换位置：

head → [a] → [c] → [b] → [d] → NULL

下次如果你又查 c，它更靠前了！

❓为什么这样做？

因为我们认为：

被查到的值，很可能会再次被查找

换位法是一种局部提升，通过一点点移动常用元素向前靠，让以后更快被访问。

我们现在来实现 transposition 搜索

首先，我们要解决一个问题：

单链表中不能“反向走”，那我们怎么知道“当前节点的前一个节点”是谁？

答：我们在查找过程中必须保存两个指针：

struct Node* prev = NULL;
struct Node* curr = head;

curr：当前正在判断的节点
prev：curr 前一个节点，用来交换

🔁 每一步：

判断 curr->data == key
如果不是，往下走一格：

prev = curr;
curr = curr->next;

如果找到了 key，怎么办？

我们就要把 curr 和 prev 的位置交换。

假设：

prev → [b] → [c] → curr->next → ...

要变成：

prev → [c] → [b] → curr->next → ...//等价于
prev->next = curr->next;
curr->next = prev;

但还不够 —— 谁来指向 curr？你还要修改“prev 的前一个节点”的指针！

✅ 所以我们还需要一个：prePrev（prev 的前一个）

struct Node* prePrev = NULL;
struct Node* prev = NULL;
struct Node* curr = head;

🔍 具体交换步骤

在链表中，“交换节点”不是交换它们的数据内容（那是数组思维），而是重新安排它们之间的指针关系。

原状态：

prePrev → prev → curr → afterprev->next == curr
curr->next == after

第一步：让 prev 跳过 curr，直接指向 after

prev->next = curr->next;  // 现在 prev → after

此时链表变成：

prePrev → prev    curr → after↘→ after

curr 暂时还没有连上前面的节点

第二步：让 curr->next 指向 prev

curr->next = prev;

prePrev → prev    curr↘ ↗→ after

但注意，此时 prePrev → prev 还是旧的指向，我们还没有把 curr 插入前面。

第三步：修复前一个前驱的指针

我们要让：

prePrev->next = curr;

prePrev → curr → prev → after

如果 prePrev == NULL 呢？

那就说明 prev 是头节点，要特别处理，把 head 本身更新为 curr：

*head = curr;

最终操作顺序

prev->next = curr->next;
curr->next = prev;if (prePrev != NULL)prePrev->next = curr;
else*head = curr;

步骤	本质意义
保存前驱指针	单链表不能反向走，必须显式保存
找到目标后交换节点	用指针操作完成 curr 和 prev 的调换
更频繁访问的节点向前移动	增加将来访问速度

完整过程总结图解

初始状态：

prePrev → prev → curr → after

第一步：

prev->next = curr->next;prePrev → prev    curr → after↘→ after

第二步：

curr->next = prev;prePrev → prev ← curr↘→ after

第三步：

prePrev->next = curr;prePrev → curr → prev → after

完整代码

#include <stdio.h>
#include <stdlib.h>// 节点结构
struct Node {int data;struct Node* next;
};// 打印链表
void printList(struct Node* head) {struct Node* temp = head;while (temp != NULL) {printf("%d → ", temp->data);temp = temp->next;}printf("NULL\n");
}// 使用换位法查找 key
struct Node* searchTransposition(struct Node** head, int key) {if (*head == NULL) return NULL;struct Node* prePrev = NULL;struct Node* prev = NULL;struct Node* curr = *head;while (curr != NULL) {if (curr->data == key) {// 找到了，和前一个节点交换if (prev == NULL) {// 第一个节点，不需要换位return curr;}// 一般情况：交换 prev 和 currprev->next = curr->next;curr->next = prev;if (prePrev == NULL) {// prev 是头节点*head = curr;} else {prePrev->next = curr;}return curr;}// 没找到，继续往后走prePrev = prev;prev = curr;curr = curr->next;}return NULL;  // 没找到
}// 构建链表
struct Node* buildList() {struct Node* a = (struct Node*) malloc(sizeof(struct Node));struct Node* b = (struct Node*) malloc(sizeof(struct Node));struct Node* c = (struct Node*) malloc(sizeof(struct Node));struct Node* d = (struct Node*) malloc(sizeof(struct Node));a->data = 10; a->next = b;b->data = 20; b->next = c;c->data = 30; c->next = d;d->data = 40; d->next = NULL;return a;  // head
}int main() {struct Node* head = buildList();printf("Original list:\n");printList(head);int key = 30;searchTransposition(&head, key);printf("After searching %d (transposition):\n", key);printList(head);return 0;
}

移到表头（Move-to-Head）

从第一性出发，讲解 Move-to-Head（移到表头）策略：每次查找到一个节点之后，将其移到链表最前面。

第一性推导：为什么要这么做？

在实际应用中，有些元素被访问的频率非常高。我们希望这些“常被访问的节点”靠前，这样下次能更快地被找到。

Move-to-Head 的核心思想：

一旦某个节点被找到，就直接把它移动到表头，这样下次查找就最快（O(1)）

head → [10] → [20] → [30] → [40] → NULL

你查找 30，找到了它。操作后：

head → [30] → [10] → [20] → [40] → NULL

30 被提到了表头
原来它后面的节点顺序没有改变
原来在它前面的节点整体往后推

为什么这样做是合法的？

链表中节点之间是通过指针连接的
你只需要修改三条指针：
1. 断开原位置上的连接
2. 将目标节点插入表头
3. 更新 head 指针

🔍 具体实现步骤

假设你已经找到了节点 curr，它不是第一个节点

你在查找过程中保存了两个指针：

struct Node* prev = ...;   // curr 的前一个节点
struct Node* curr = ...;   // 当前查找到的节点

当前链表结构为：

head → ... → prev → curr → curr->next → ...

Step 1: 断开 curr 原来的位置

我们要让 prev 跳过 curr，指向 curr->next：

prev->next = curr->next;

此时链表是：

head → ... → prev → curr->next↘curr

Step 2: 把 curr 插入表头

curr->next = head;

Step 3: 更新 head 指针

*head = curr;

现在链表是：

head → curr → 原来的头 → ...

完成 ✅

❗边界情况：如果 curr 本来就是头节点呢？

if (curr == *head)return curr;

什么都不做，直接返回

代码实现

// 在链表中查找 key，并将其移到表头
struct Node* searchMoveToHead(struct Node** head, int key) {if (*head == NULL) return NULL;// 如果第一个节点就是目标if ((*head)->data == key)return *head;struct Node* prev = *head;struct Node* curr = prev->next;while (curr != NULL) {if (curr->data == key) {// Step 1: 从原位置断开prev->next = curr->next;// Step 2: 插到头部curr->next = *head;*head = curr;return curr;}// 向后移动prev = curr;curr = curr->next;}return NULL;  // 没找到
}

步骤	操作代码	含义
断开 curr	`prev->next = curr->next`	把 curr 从原位置拿出来
插入表头	`curr->next = head`	把 curr 指向原头节点
更新头指针	`*head = curr`	把 curr 变成新的头节点

两种方式对比

特性	Move-to-Head	Transposition
移动距离	一次到表头	每次前移一步
修改影响	对链表影响大	对链表影响小
查找性能提升速度	快	慢
适合数据访问模式	极端热点（少数项频繁访问）	中等热点（多项中等频率）