使用二重指针进行单链表操作

NanaSakura

链表是一种非常基本的数据结构。链表结构十分简单，分为数据域与指针域。数据域存储了表中的数据，指针域则表示链表的连接方式。
单链表仅包含一个指针，即next指针，表示本节点的下一个节点的位置，链表因此也有了易修改的特性，文件系统也充分利用了该特性。
本帖将以Pure C为背景进行说明。

- 指针的本质
指针本身是一个变量，本身储存的值是其指向的对象的地址，可以通过改变指针的值来移动指针，也可以通过改变指针所指的值来间接修改变量。
本次要讲述的是利用上述性质，通过二重指针的操作来实现单链表删除。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. struct node{
   
5.     int data;
   
6.     struct node* next;
   
7. };
   
8. 
   
9. struct node* assign_linked_list(struct node* head);
   
10. void print_list(struct node* head);
    
11. void del_list(struct node* head,int val);
    
12. 
    
13. int main(int argc, const char * argv[]) {
    
14.     struct node* head=NULL;
    
15.     head=assign_linked_list(head);
    
16.    
    
17.     int val;
    
18.     scanf("%d",&val);
    
19.    
    
20.     del_list(head,val);
    
21.    
    
22.     print_list(head);
    
23.    
    
24.     return 0;
    
25. }
    
26. 
    
27. struct node* assign_linked_list(struct node* head){
    
28.     int n;
    
29.     scanf("%d",&n);
    
30.     if(n==0){
    
31.         return NULL;
    
32.     }
    
33.     struct node* ptr=(struct node*) calloc(1,sizeof(struct node));
    
34.     ptr->data=n;
    
35.     ptr->next=assign_linked_list(ptr->next);
    
36.     return ptr;
    
37. }
    
38. 
    
39. void print_list(struct node* head){
    
40.     for(struct node* curr=head;curr;){
    
41.         printf("%d ",curr->data);
    
42.         curr=curr->next;
    
43.     }
    
44. }
    
45. 
    
46. void del_list(struct node* head,int val){
    
47.     struct node* prev=NULL;
    
48.     for(struct node* curr=head;curr;){
    
49.         if(curr->data==val){
    
50.             if(prev){
    
51.                 prev->next=curr->next;
    
52.             }
    
53.             else{
    
54.                 prev=curr;
    
55.             }
    
56.             struct node* ptr=curr;
    
57.             curr=curr->next;
    
58.             free(ptr);
    
59.         }
    
60.         else{
    
61.             prev=curr;
    
62.             curr=curr->next;
    
63.         }
    
64.     }
    
65. }

复制代码

以上是一段再正常不过的单链表创建，删除，以及输出的一个程序，可以看到在链表删除的时候利用了prev指针，记录了上一个位点的地址，以方便链表的删除操作，即prev->next=curr->next，移动curr指针后再将现有节点占据的内存释放。这样的写法思想上非常好理解。

1. void del_list(struct node** head,int val){
   
2.     for(struct node** curr=head;*curr;){
   
3.         struct node* entry=*curr;
   
4.         if(entry->data==val){
   
5.             *curr=entry->next;
   
6.             free(entry);
   
7.         }
   
8.         else{
   
9.             curr=&entry->next;
   
10.         }
    
11.     }
    
12. }

复制代码

而在本例中，则利用二重指针的特性，基于此prev将不再必要。
在curr移动的过程中，如果需要释放二重指针所指向的当前节点，由于二重指针curr指向的是entry->next这个指针，所以可以直接对二重指针curr解引用获取entry->next的地址，并将其赋值为下一节点的地址，这就是通过指针间接修改值。在此情况下，entry和curr毫无联系，需要移动的也是curr而不是entry，所以可以直接调用free(entry)删除节点。又由于这是单链表，所以也不存在右边与左边连接的问题。
而如果不需要释放当前节点，这时候可以直接修改二重指针的地址，移动二重指针，让它指向entry->next这个指针，即下一节点。

参考：
Linus所述Low-Level Coding问题，信源并不惟一，这里给出一个参考过的文章：https://wordaligned.org/articles/two-star-programming
上述内容的思考是自己的体会，仅作记录。
代码由自己重写。
测试样例中，输入以空格分隔的多个数字，以0结尾作为结束输入标志；
然后再输入一个数字代表需要从链表中删除的值。

我是Pinkstone

链表算比较经典的C（pp）开发实例了，我还记得在链表里倒腾prev、data、next的痛苦时光...

NanaSakura

lihl 发表于 2024-2-4 21:16
链表算比较经典的C（pp）开发实例了，我还记得在链表里倒腾prev、data、next的痛苦时光... ...

不看建议不回复。