linus 提到过的单链表删除节点算法
1 问题描述
在TED上做过一次访谈，linus提到了关于编程的品味，他举了一个例子：
见原视频15‘前后
这个例子要删掉一个链表的节点项
传入的参数是一个节点的引用
解法1，使用了prev
remove_list_entry(entry)
{
prev = NULL;
walk = head;
while (walk && walk!=entry)
{
prev = walk;
walk = walk->next;
}
// Remove the entry by
// updating the head or previous entry
if (!prev)
{
head = entry->next;
}
else
{
prev->next = entry->next;
}
// 释放节点空间
free(entry);
}
解法2，使用了二重指针
remove_list_entry(entry)
{
// The "inderect" pointer points to the
// *address* of of the thing we will update
indirect = &head;
// Walk the list, looking for the thing that points to
// entry we want to remove entry
while ((*indirect)&&(*indirect)!=entry)
{
indirect = &(indirect->next);
}
// just remove the entry
*indirect = entry->next;
free(entry);
}
2 思路
解法1，是常用的解法
一般情况
用一个前驱节点 prev 来寄存待删除节点之前的节点
用图形表示就是
这样，就能实现将prev指向entry的后继节点
特殊情况
为了保证可靠性，也需要考虑到
- 整个链表只有2个节点的情况
此时需要我们判断 prev=NULL
并让head->next直接指向entry->next
- 整个链表只有1个节点的情况
此时可能需要直接释放 head 所指向的节点空间
并让head指向NULL
解法2
二重指针
指针是一次寻址
二重指针是二重寻址
indirect=&head
head本身是指向一个节点的指针，而indirect存储了head的地址，所以是存储指针的容器
这里不得不提到节点的定义
typedef struct ListNode
{
ListNode* next;
int data;
} ListNode;
每个节点其实都存储了
- 下一个节点的地址
- 本身数据
大概类似这样
注意我在上面加了一个地址0x0000000
其实next的内容，就是地址，指针就是保存了地址的变量。
那么把整个链表放在一起看，是这样的：
每个节点的next字段，都保存了它下一个节点的地址
那么，我们可以认为，每个节点的next字段就是一个指针变量
而 indirect = &head
就是一个二重指针
indirect存放了head的地址
可以通过解引用运算获取head里面的值
具体操作
那么，究竟如何完成删除一个节点的功能？
为了方便叙述，给每个next字段都加上一个地址 ，分别记作ABCD
假设我们要删掉0x00000008这个节点
此时indirect已经指向head了
while (*indirect && *indirect != entry)
{
indirect = &(*indirect->next);
}
这段循环，让indirect指向了 存放entry地址 的next字段
即此时 indirect = B
此时，如果让B里面的内容，从0x00000008变为0x00000010
就能完成删除节点，维护链表的操作
代码如下
// just remove the entry
*indirect = entry->next;
free(entry);
示意图
特殊情况处理
像其他的情况，如
- 只有2个节点，head节点和entry节点
- 只有entry节点（即entry节点就是head节点）
也可以很好的解决，如有兴趣可以自己实现一下。
对编程的爱好，让我充满力量，加油！