需要帮助理解C中的链表代码

Question

我从linus那里得到的关于理解指针的以下代码。

typedef struct list_entry {
   int val;
   struct list_entry *next;
} list_entry;    

list_entry **pp = &head; /* pointer to a pointer */
list_entry *entry = head;
while (entry) {
    if (entry->val == to_remove)
        *pp = entry->next;            //6      
    pp = &entry->next;                //8   
    entry = entry->next;
} 

有人能理解第6行和第8行吗？如果entry->val==to_remove，第6行被评估，*pp成为删除后的下一个条目，那么第8行在这之后会做什么？当前条目已被删除，如何在第8行中重新使用此条目？

此外，我理解*pp表示指针pp的值，并且&entry->next表示pp的地址，我总是对何时应该使用*以及何时&应该使用。具体来说，第6行可以是：吗

pp = &entry->next; 

第8行为：

*pp= entry->next; 

如果没有，为什么？

Answer 1

更新：

博客中的代码是不完整的，并且假设只有一个元素会被删除，并且没有必要免费。如果要移除两个或多个连续元素，则序列中的第二个元素将不会被移除。

正确的代码是，它还假设节点不必被释放：

while (entry) {
    if (entry->val == to_remove)
        *pp = entry->next;           
    else
        pp = &entry->next;  
    entry = entry->next;
} 

如果你必须释放节点：

while (entry) 
{
    if(entry->value == to_remove  )
    {
        *pp = entry->next;            
        free( entry ) ;
        entry = *pp ;
    }
    else
    {
        pp = &entry->next;               
        entry = entry->next;
    }
} 

---

写出整个结构确实有助于理解这一点。

struct Node
{
    int val ;
    struct Node* next ; //hint, this has an address too.
} ;

诀窍在于语句

pp = &entry->next ;

这看起来像是指向next节点，但实际上您只是获取当前节点的指针地址差别太大了

所以pp = &entry->next ;几乎等同于第一个例子中的prev = entry;，唯一的区别是你指向当前struct Node的成员next的地址，而不是指向整个当前struct Node。

Answer 2

在这个示例代码中，pp存储上一个链的"next"成员的地址，这样，在当前链被标记为要删除的情况下，可以修改前一个链中的"next"成员，使其指向现在要删除的链的"next"。间接修改是通过应用*运算符来完成的。

第6行和第8行不能根据您的问题进行修改，因为那样代码将无法达到所需的效果。

1. 保留上一个（或头）链的"下一个"成员的地址。

2. 检查当前链是否标记为要删除。

3. 如果是，则使用pp引用间接操作上一个链的"next"成员以指向当前链的"next"，因此实际上链表将跳过当前链，同时保持其完整性。

Answer 3

这里发生了什么：

list_entry **pp = &head; /* pointer to a pointer */
list_entry *entry = head;
// we start with entry being head and pp being an address of head
while (entry) {
// while there is a list_entry which is not NULL...
    if (entry->val == to_remove)
        // if entry points to value that should be removed, 
        // then store the address of the next entry in whatever pp points to now
        // (which effectively means removing that entry)
        *pp = entry->next;            //6      
    // pp is now an address of the next entry
    pp = &entry->next;                //8   
    // move to the next entry to start the next iteration
    entry = entry->next;
} 

这个代码的作用是：它遍历列表并消除所有标记为已删除的条目。

它是如何做到的：

• 最初pp指向头部。

• 它从头部开始，在列表中进行遍历。

• 每当当前条目所指向的值被标记为"已删除"时，pp就会在当前列表条目的地址中存储下一个列表条目的地址。如果pp指向头，则意味着头被丢弃，并开始指向下一个元素。如果pp指向列表中间的元素，则意味着该元素被移除（因为现在前一个元素将指向被移除的元素之后的元素）。

• 完成后，它移动entry点以检查列表中的下一个值。

Answer 4

&的意思是返回某个东西的地址。*表示访问指针指向的变量。

所以线路：

pp = &entry->next;
*pp= entry->next;

不同。

第一个将指针设置为包含entry->next的地址，而第二个将pp指向的变量的值设置为等于entry->next。

entry->next在被"删除"后可以被引用的原因是，当它从链表中删除时，它仍然存在于内存中，并且仍然可以访问。