在 C 语言中释放链表中的节点的微小改进-解网

问：

看看这段代码，它想要释放 C 语言链表内所有错位的节点：

    ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }

原因是，在释放当前节点之前，我们需要一个临时变量来存储指向下一个节点的指针。

你看到它在循环内吗？因此，每次循环运行时，都会创建一个新的临时节点来存储指向下一个节点的指针。如果我们在循环外创建变量节点，而在循环内部重新分配它，会更好吗？node *next = ptr->next;

喜欢这个：

    ptr = list;
    node *next = NULL;
    while (ptr != NULL)
    {
        next = ptr->next;
        free(ptr);
        ptr = next;
    }

会更有效率吗？

C 链接列表 Malloc 声明无 Clang GCC

“因此，每次循环运行时，都会创建一个新的临时节点”——这不是真的。没有创建临时节点。临时节点指针被搭讪在堆栈上，作为补救标量，甚至不用担心打印它的硅。如果这两个循环没有被任何有价值的编译器优化为相同的代码，我会感到震惊。也就是说，一个常见的 C 偏好是可变局部性（保持紧凑），大多数 C 工程师可能更喜欢第一种方法。顺便说一句，概率很高，甚至是多余的，使用就可以了。ptrlist

2赞 Aconcagua 7/2/2023

即使你确实创建了一个临时的（复制整个节点），任何像样的编译器都会分配在两个变体中只存储一次副本（在堆栈上）所需的空间......

1赞 Aconcagua 7/2/2023

在 C 语言中，无论如何，你需要关心的要少得多。C++ 可能是另一回事，因为您可能需要考虑构造函数/析构函数。

0赞 Andrew Henle 7/2/2023

将声明移出循环有一个缺点 - 它增加了变量的范围。这使得它更容易出错。在这样的简单示例中，这不是问题，但在复杂的代码中，尽一切可能减少引入错误的机会可能很重要。限制变量的范围可以降低代码的复杂性，更简单的代码更易于编写和维护，同时也更不容易出错。node *next

1赞 Aconcagua 7/3/2023

@AndrewHenle 无论如何都会调用 Copy 构造函数（除非您在循环中构造元素并从 copy-elision 中获利）：for(...) { auto a = someExistingObject; }

答：

3赞 NubDev 7/2/2023 #1

这两个代码段之间的差异可以忽略不计。两个代码段具有相同的时间复杂度，即，其中 n 是链表中的节点数。它们遍历链表一次，释放每个节点。在第二个代码中初始化指针的附加步骤不会显著影响性能。O(n)next

在第二个代码中初始化指针的“附加”步骤（从技术上讲是赋值，而不是初始化）与第一个代码中指针的声明初始化相匹配。区别在于第一个示例中的每次迭代分配，而第二个示例中的“一劳永逸”分配。如果这是一个动态分配，那么它可能确实需要担心，但它是一个自动分配，这里的关键点是，在大多数 C 实现中，自动分配基本上是免费的。nextnextnext

6赞 Ted Lyngmo 7/2/2023 #2

创建了一个新的临时节点来存储指向下一个节点的指针

否，已创建一个新的临时节点指针。

这两个版本都可能被优化成完全相同的汇编代码，这可以在这个演示中看到，其中 clang 也生成两个相同的函数和 gcc。

2赞 chux - Reinstate Monica 7/2/2023 #3

如果我们在循环外创建变量节点，而在循环内部重新分配它，会更好吗？

相信你的编译器会为这种微不足道的优化发出高效的代码 - 否则会得到一个更好的编译器。为清楚起见，编写代码。

节省您宝贵的编码时间，进行重大改进。
过早的优化真的是万恶之源吗？

-1赞 Vlad from Moscow 7/2/2023 #4

您是否看到节点 *next = ptr->next;在循环中吗？因此每次循环运行时，都会创建一个新的临时节点，用于存储指向下一个节点的指针。

你错了。如果在 for 循环中包含调用的语句，如下所示printf

ptr = list;
while (ptr != NULL)
{
  node *next = ptr->next;
  printf( "&next = %p\n", ( void * )&next );
  free(ptr);
  ptr = next;
}

您将看到在 for 循环的每次迭代中输出变量的相同地址。该变量是在循环的每次迭代中从抽象 mashine 的角度正式创建的。实际上在这条线的物理层面上next

  node *next = ptr->next;

使用了与第二个代码片段中相同的 assignemnt

next = ptr->next;

其中变量在 for 循环之前声明。

因此，在生成的代码级别上没有区别。

但是，从编写程序的角度来看，您应该在使用它们的最小范围内声明变量。

此外，引入的变量是冗余的。在 for 循环之后，指针将是一个悬空指针。因此，您需要将其设置为 for 循环之后。相反，你可以写ptrlistNULL

while ( list != NULL )
{
  node *next = list->next;
  free( list );
  list = next;
}

如您所见，没有冗余变量，for 循环后面的指针将等于。listNULL

2赞 chqrlie 7/2/2023 #5

建议的优化不会改变任何事情：局部变量用于存储指针，无论其范围是否是循环体的局部变量都没有区别。启用优化的编译器将分析变量的使用情况，并为两种方法生成相似（如果不是完全相同）的代码。nextnext

第一个提供多种好处：

next以最小的范围进行定义，使下一个程序员更容易一目了然地分析其有限的用途。
在循环之前初始化是一个额外的无用步骤，编译器可能会消除它，但下一个程序员想知道是否在循环之后使用并且需要初始化。nextnext
第一个代码片段是一个经典的成语。使用经典习语可以减轻代码审查和校对的心理负担。

如果这个循环恰好是一个瓶颈，你应该在尝试优化之前测试它，你可能应该调查链表是否是最适合你的目的的数据结构，如果是的话，你可以使用其他方法来分配节点，如果你能一次释放它们：从预先分配的数组中分配节点是提高缓存效率和分配/取消分配性能的有效方法。

请注意，除非列表为空，否则指针在循环后将具有无效值。您应该将其设置为显式或直接在循环中使用它：listNULL

    while (list != NULL) {
        node *next = list->next;
        free(list);
        list = next;
    }

@DrLinhChiNguyen 除了：像这样的代码通常应该打包到它自己的函数中——在这种情况下，已经是指针的副本。无论哪种情况，都会留下一个悬空的指针，无论是直接指针还是 - 如果函数 - 指针传递到，这需要由之后仍在使用它的代码来考虑（->设置为，但也要考虑潜在的现有副本！void deleteList(node* list);listlistNULL

上一个：为什么在 c 中有两个临时变量的自由链表？

下一个：当我尝试在结构中释放 2d 矩阵时，程序退出没有任何错误

在 C 语言中释放链表中的节点的微小改进

minor improvement in freeing nodes in linked list in C

评论

评论

评论