遍历链表并删除元素的写法

发表于 | 分类于

记得有次看采访linus的视频，提到在链表中查找某个元素并删除应该采用下面的写法，而不是用前后两个指针的写法，后来在UCB上操作系统课ta在复习c语言的recitation上也提到了这个，于是就记录下来：

链表与二级指针

1
2
3
4
5
6
7
8
9
10
11
void remove_nodes (LinkNode **node_addr, char *str) {
    while (*node_addr != NULL) { // Iterate through list
      	if (!strcmp((*node_addr)->value, str)) { // 0 is a match
          	LinkNode *to_free = *node_addr;
          	*node_addr = to_free->next; // Change the pointer
          	free (to_free);
      	} else {
          	node_addr = &(*node_addr)->next; // Make next changes
      	}
    }
}

链表的迭代如果涉及到删除请用二级指针。

  • 首先梳理一下变量名作为一种抽象的意义，变量名本身表示一块内存空间（即一个地址）。同时所代表的空间中存储的值可以是另一个块空间的地址。
    • 作为右值使用的时候，相当于使用变量名对应地址中的值。因此，对于上方代码。使用node_addr，相当于使用其内存储的二级指针。
    • 作为左值使用的时候，相当于对对应的存储空间的操作。
  • 二级指针的使用，如上例所示:
    • 当匹配失败，将node_addr设置为指向下一个next域。因此可以发现，二级指针始终指向next域，而非整个节点，next域指向下一个节点。
    • 当匹配成功，将当前next域的值跳过下一个设置。
  • 二级指针的优势：
    • 更优雅：一级指针局限于判断当前节点，如果匹配成功，需要prev指针，才能修改上一个节点。二级指针则没有这个问题。
    • 处理边界：如果第一个节点即判断成功，则应该删除第一个节点，如果一级指针，则传入的原始一级指针最终不可用。但是二级指针会同时修改传入的一级指针，因此也没有这个问题。