二级指针实现单链表的插入、删除

今天看了coolshell上关于二级指针删除单链表节点的文章。

文章中Linus 举例：

例如，我见过很多人在删除一个单项链表的时候，维护了一个”prev”表项指针，然后删除当前表项，就像这样：

if (prev)
    prev->next = entry->next;
else
    list_head = entry->next;

（当我看到这样的代码时，我就会想“这个人不了解指针”。令人难过的是这太常见了。）

People who understand pointers just use a “pointer to the entry pointer”, and initialize that with the address of the list_head.

And then as they traverse the list, they can remove the entry without using any conditionals, by just doing a “*pp = entry->next”.

（了解指针的人会使用链表头的地址来初始化一个“指向节点指针的指针”。当遍历链表的时候，可以不用任何条件判断（注：指prev

是否为链表头）就能移除某个节点，只要写)

 *pp = entry->next

那就是有效地利用二级指针，将其作为管理和操作链表的首要选项。

coolshell上这篇 Linus：利用二级指针删除单向链表 文章对二级指针操作单链表删除的精妙之处已经做了说明。

下面，我们来探讨下，为什么 使用二级指针能达到如此的效果？？

我们先来个简单的列子：

#include 
  
   
#include 
   
     void f(int v) { v = 1; } void f_(int *pv) { *pv = 1; } int main() { int n = 0; f(n); printf("%d\n", n); f_(&n); printf("%d\n", n); return 0; }
   
  

0

1

上面是个 简单的例子，即是我们常说的c/c++ 语言的函数 参数传递 一律为 值传递。要达到改变所传递的参数的值,我们只能想法把 存放

这个实际值的内存地址当做参数进行传递，然后我们操作内存地址，通过修改这个地址所指向的值，间接达到修改这个值的效果。如图

值传递，记住这条基本原理：形参相当于函数中定义的变量，调用函数传递参数的过程相当于定义形参变量并且用实参的值来初始化。

下面来说明下，单链表的操作。

单链表中，链表节点就是一个地址加上别的数据，这个地址指示着下一个节点的位置，只要我们有头节点head这个指针，用来指向第一个

节点。这样我们的链表中，每个节点都有一个指针指着，而且环环相扣。

为什么会想到二重指针操作的写法？因为我们意识到删除操作的本质是指针值的改变，这样用二重指针去操纵指针的值就是很自然的想法了。

好了，代码如下：

#include 
  
   
#include 
   
     typedef struct node { int data; struct node *next; }Node; void insert(Node **pphead, int v)//插入节点，采用头插法 { if(nullptr == *pphead)// 头节点为空 { *pphead = (Node *)malloc(sizeof(Node)); (*pphead)->data = v; (*pphead)->next = nullptr; return ; } Node *t = *pphead;// 记下头节点 *pphead = (Node*)malloc(sizeof(Node)); (*pphead)->data = v; (*pphead)->next = t;// 新头节的next节点为保存的插入之前的头节点t } void print(Node **pphead)//输出链表所有元素 { for(Node **cur = pphead; *cur;) { printf("%d ", (*cur)->data); cur = &(*cur)->next; } } void remove_if(Node **pphead, int v)//删除节点值为v的所有节点 { for(Node **cur = pphead; *cur;) { Node *en = *cur; if(en->data == v) { // *重要* *cur = en->next;//用二级指针去操纵指针的值,*cur现在为待删除节点的next节点 free(en);//释放待删除节点,此时存放地址en值的二级指针cur依然存在 且cur地址 //所指内存已经了存储了 删除节点的下一个节点 } else { cur = &en->next; } } } int main() { Node *pfirst=nullptr;//c++11 for(int i=0; i != 5; ++i) insert(&pfirst, i%2); print(&pfirst); printf("\n"); remove_if(&pfirst, 1); print(&pfirst); return 0; } 
   
  

输出：

0 1 0 1 0
0 0 0

二级指针 操作链表是不是精简了很多，很值得我们去学习、使用。