无分支链表删除C中的条目

Question

在this TED talk中，Torvalds提出了一个没有if条件的remove entry函数。我试图在下面的代码中进行模拟，但如果要删除的条目是列表的头部，它就不起作用。 1.) 为什么这不能专门移除头部？ 2.) 由于我们从未释放条目，此方法不会产生内存泄漏吗？

/** a data structure representing a node **/
struct node {
        int data;
        struct node* next;
};

/** create a new node and return a pointer to it**/
struct node* new_Node(int data)
{
        struct node* newP = malloc(sizeof(struct node));
        newP-> data = data;
        newP-> next = NULL;
        return newP;
}
/** function to print out a list**/
void list_print(struct node* head)
{
        printf("Begin List Print:\n");
        struct node* tmp = malloc(sizeof(struct node));
        tmp = head;

        while(tmp != NULL ) {
                printf("%d\n", tmp->data);
                tmp = tmp->next;
        }
        printf("End List Print\n\n");

}
 /** function to delete one node **/
void list_remove_entry(struct node* head, struct node* entry)
{
        struct node** indirect = &head;
    
        while((*indirect) != entry) {
                indirect = &(*indirect)->next;
        }
        *indirect = (*indirect)->next;
}
    
/** the program entry point**/
int main()
{
        struct node* head = new_Node(1);
        struct node* n1 = new_Node(2);
        struct node* n2 = new_Node(3);
        head->next = n1;
        n1->next = n2;
    
        list_print(head);
    
        list_remove_entry(head, head);
        list_print(head);
    
        return 0;
}

Answer 1

你在这里做了很多巫术编程：

void list_remove_entry(struct node* head, struct node* entry)
{
  // Takes the address of a local argument
  struct node** indirect = &head;
    
  while((*indirect) != entry) {
    indirect = &(*indirect)->next;
  }

  // Updates local variable, no impact on caller's version of same
  *indirect = (*indirect)->next;
}

如果你没有得到一个间接变量作为开始，那么在函数中将它变成一个就太晚了。这是需要在调用者级别建立的东西。

您想要的是间接接受该变量（例如指向指针的指针）以便您可以对其进行操作：

void list_remove_entry(struct node** head, struct node* entry)
{
  // Use the "indirect" argument directly
  while(*head != entry) {
    indirect = &(*head)->next;
  }

  // Updates caller's variable
  *head = (*head)->next;
}

现在你正确地称呼它：

list_remove_entry(&head, head);

值得注意的是，如果您可以提供 return 值，您也可以在没有双指针的情况下执行此操作：

struct node* list_remove_entry(struct node* head, struct node* entry)
{
  while(head != entry) {
    head = head->next;
  }

  // Caller can update with this value
  return head->next;
}

现在的调用方式如下：

head = list_remove_entry(head, head);

除此之外，您的 list_remove_entry 函数只能删除第一个元素。理论上它应该能够删除链中的 any 元素。

Answer 2

TED演讲中的代码没有将head作为参数，它是一个全局变量。

因此，当它发生时

*indirect = entry->next;

如果要删除的条目等于head，它将修改head变量，因为while循环立即停止并且indirect仍然包含&head.

当您将 head 设为参数时，这并不相同，因为现在您只是在修改局部变量，而不是调用者的变量。请参阅 Changing address contained by pointer using function 以了解如何重新设计函数来解决此问题（它也在 @tadman 的回答中）。

在回答你的第二个问题时，是的，这会造成内存泄漏。 Linus 的示例只是为了说明编写此函数的两种方法的一个特定方面，因此他省略了与该差异无关的所有内容。您可以通过将作业替换为：

来解决此问题

(*indirect)->next = (*indirect)->next->next;
free(*indirect);

请注意，他还遗漏了错误检查。他的代码假定会找到该条目，因此他在取消引用之前从不检查 *indirect == NULL（并且我的上述分配不检查双重间接）。

这不是编码课，它只是一个需要放在幻灯片上的简单示例。

无分支链表删除C中的条目

Branchless linked list remove entry in C

c

pointers

singly-linked-list