linus提到过的单链表删除节点算法

linus 提到过的单链表删除节点算法

1 问题描述

在TED上做过一次访谈,linus提到了关于编程的品味,他举了一个例子:

linus在TED演讲_哔哩哔哩_bilibili

见原视频15‘前后

linus提到过的单链表删除节点算法

解法1

linus提到过的单链表删除节点算法

解法2

这个例子要删掉一个链表的节点项

传入的参数是一个节点的引用

解法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 来寄存待删除节点之前的节点

用图形表示就是

linus提到过的单链表删除节点算法

这样,就能实现将prev指向entry的后继节点

特殊情况

为了保证可靠性,也需要考虑到

  • 整个链表只有2个节点的情况

linus提到过的单链表删除节点算法

此时需要我们判断 prev=NULL

并让head->next直接指向entry->next

  • 整个链表只有1个节点的情况

linus提到过的单链表删除节点算法

此时可能需要直接释放 head 所指向的节点空间

并让head指向NULL

解法2

二重指针

指针是一次寻址

二重指针是二重寻址

indirect=&head

head本身是指向一个节点的指针,而indirect存储了head的地址,所以是存储指针的容器

这里不得不提到节点的定义

typedef struct ListNode
{
    ListNode* next;
    int data;
} ListNode;

每个节点其实都存储了

  1. 下一个节点的地址
  2. 本身数据

大概类似这样

linus提到过的单链表删除节点算法

注意我在上面加了一个地址0x0000000

其实next的内容,就是地址,指针就是保存了地址的变量。

那么把整个链表放在一起看,是这样的:

linus提到过的单链表删除节点算法

每个节点的next字段,都保存了它下一个节点的地址

那么,我们可以认为,每个节点的next字段就是一个指针变量

而 indirect = &head

就是一个二重指针

indirect存放了head的地址

可以通过解引用运算获取head里面的值

具体操作

那么,究竟如何完成删除一个节点的功能?

linus提到过的单链表删除节点算法

为了方便叙述,给每个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);

示意图

linus提到过的单链表删除节点算法

特殊情况处理

像其他的情况,如

  • 只有2个节点,head节点和entry节点
  • 只有entry节点(即entry节点就是head节点)

也可以很好的解决,如有兴趣可以自己实现一下。

对编程的爱好,让我充满力量,加油!

linus提到过的单链表删除节点算法

上一篇:Windows Azure使用VS 2010的云应用开发过程


下一篇:idea中的目标字节码版本总是自动更改为1.5