链表(二)：删除节点、查找节点、修改节点、双向链表、循环链表
好，咱们接着聊链表。上一章我们把单链表的基本操作——创建、插入、遍历——都过了一遍。今天要讲的这几个操作，说实话，才是真正让你在项目里「用得上」的东西。
删除、查找、修改，这三个动作，说白了就是链表的「增删改查」里的后三个。我当年刚学的时候，觉得删除节点特别绕，指针指来指去的，一不小心就丢了节点。后来写多了才发现，其实就那么几步，关键是要画图。
另外，双向链表和循环链表，这两个是单链表的「升级版」。我个人习惯是，只要数据量不大、不需要频繁逆序遍历，我就用单链表。但一旦涉及到「从后往前找」或者「环形数据」，那双向链表和循环链表就是你的不二之选。
删除节点
删除节点，核心就一句话：让前一个节点跳过当前节点，直接指向后一个节点。然后释放当前节点的内存。
嗯，这里要注意：删除头节点和删除中间节点，处理方式不一样。我见过不少新手在这栽跟头。
删除节点的三种情况：
- 删除头节点：直接把 head 指向第二个节点，释放原头节点。
- 删除中间节点：找到待删节点的前一个节点，让它指向待删节点的下一个节点。
- 删除尾节点：让倒数第二个节点的 next 指向 NULL，释放尾节点。
// 删除指定值的节点（单链表）
Node* deleteNode(Node* head, int value) {
if (head == NULL) return NULL;
// 如果要删的是头节点
if (head->data == value) {
Node* temp = head;
head = head->next;
free(temp);
return head;
}
// 查找待删节点的前一个节点
Node* current = head;
while (current->next != NULL && current->next->data != value) {
current = current->next;
}
// 如果找到了
if (current->next != NULL) {
Node* temp = current->next;
current->next = temp->next;
free(temp);
}
return head;
}
我曾经犯过的错： 删除节点后忘了 free()，导致内存泄漏。在嵌入式项目中，内存泄漏是致命的。后来我养成了习惯：每次 free 之后，顺手把指针置为 NULL，防止野指针。
查找节点
查找其实最简单。单链表不支持随机访问，只能从头开始，一个一个往后找。时间复杂度 O(n)，没什么好说的。
但我想分享一个经验：查找操作往往不是单独存在的。比如你要删除一个节点，得先找到它；你要修改一个节点，也得先找到它。所以查找函数写好了，后面两个操作就省事多了。
// 查找第一个值为 value 的节点
Node* findNode(Node* head, int value) {
Node* current = head;
while (current != NULL) {
if (current->data == value) {
return current;
}
current = current->next;
}
return NULL; // 没找到
}
小技巧： 如果你需要频繁查找，可以考虑把链表改成「有序链表」，查找时可以提前终止。或者干脆用哈希表 + 链表组合，比如 LRU 缓存就是这么干的。
修改节点
修改节点，说白了就是「先查找，再赋值」。找到节点后，直接改它的 data 字段就行。
你想想看，修改操作本身不涉及指针变动，所以比删除简单多了。但有一个坑：如果你修改的是节点的「关键字段」（比如链表是按 data 排序的），那修改后可能会破坏链表的有序性。这时候你得重新调整节点位置，甚至重新插入。
// 修改第一个值为 oldVal 的节点，改为 newVal
void modifyNode(Node* head, int oldVal, int newVal) {
Node* target = findNode(head, oldVal);
if (target != NULL) {
target->data = newVal;
}
}
我在项目中遇到过： 有一次做学生成绩管理系统，链表按学号排序。有个功能要修改学生成绩，结果我直接改了 data 里的成绩字段，没动学号，所以没问题。但如果要改学号，那就得先删除再重新插入了。
双向链表
双向链表，每个节点有两个指针：一个指向前一个节点（prev），一个指向后一个节点（next）。
为什么要用双向链表？说白了，就是为了「反向遍历」。单链表只能从头走到尾，双向链表可以从尾走到头。我当年做文本编辑器的时候，用双向链表来管理「撤销/重做」操作，非常顺手。
// 双向链表节点定义
typedef struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
} DNode;
// 在双向链表尾部插入
DNode* insertAtEnd(DNode* head, int value) {
DNode* newNode = (DNode*)malloc(sizeof(DNode));
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
newNode->prev = NULL;
return newNode;
}
DNode* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
return head;
}
注意： 双向链表删除节点时，要同时更新 prev 和 next 两个指针。我曾经漏掉了 prev 的更新，结果链表出现了「断链」，调试了半天才发现。
循环链表
循环链表，就是让尾节点的 next 指向头节点，形成一个环。它没有真正的「尾节点」，遍历时要注意防止死循环。
循环链表最适合处理「环形数据」，比如约瑟夫环问题、操作系统的进程调度（时间片轮转）。我记得有一次做音乐播放器的「循环播放」功能，就是用循环链表实现的。
// 循环链表遍历（需要记录起始点）
void traverseCircular(Node* head) {
if (head == NULL) return;
Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head); // 回到头节点时停止
printf("\n");
}
避坑指南： 循环链表的插入和删除，要特别注意「头节点」的处理。如果你删除了头节点，记得更新 head 指针，否则整个链表就丢了。
知识体系总览
下面这张图，把今天讲的内容串起来了。你可以看到，删除、查找、修改是单链表的三大操作，而双向链表和循环链表是两种重要的变体。
总结
今天的内容，说白了就是三件事：
- 删除、查找、修改——单链表的三大基本操作，查找是基础，删除最复杂。
- 双向链表——多了一个 prev 指针，换来的是双向遍历的能力。
- 循环链表——首尾相连，适合处理环形数据。
我个人觉得，链表这东西，光看代码是学不会的。你得在纸上画图，把每个指针的指向画清楚，然后再写代码。我当年就是这么过来的，画了上百张图之后，链表就再也没出过 bug。
好，今天就到这儿。下一章我们讲栈和队列，这两个东西其实可以用链表来实现，到时候你会发现，链表真的是「万能积木」。