完全释放链表的麻烦

Question

我用 C 编写了一个简单的程序，试图更好地理解链表的工作原理，但我很难让我的程序释放链表使用的资源。

我实现了两个函数（push 和 apppend）在列表顶部添加一个元素，另一个在列表底部添加一个元素。我正在使用第三个函数来释放链表使用的 space。

我的程序只是用一些值填充链表，然后调用函数“destroy_list”来释放链表使用的内存。但是由于某种原因，当我用 append() 填充我的列表时，似乎并没有释放列表使用的所有内存。

这是代码+我在用 push() 和 append() 填充链表时记录的内存使用情况的一些截图：

#include <stdlib.h>
#include <stdio.h>
#include <Windows.h> // used for Sleep(), use <unistd.h> for linux(?)

typedef struct LinkedList
{
    void* data;
    struct LinkedList* next;
} LinkedList;

void push(LinkedList** head, void* data_ptr)
{
    LinkedList* new = malloc(sizeof(LinkedList));
    new->next = *head;
    new->data = data_ptr;

    *head = new;
}

void append(LinkedList* node, void* data_ptr)
{
    while (node->next != NULL)
        node = node->next;

    LinkedList* new = malloc(sizeof(LinkedList));
    new->data = data_ptr;
    new->next = NULL;

    node->next = new;
}

void destroy_list(LinkedList** head)
{
    LinkedList* current_node = *head;
    LinkedList* next_node;

    while (current_node != NULL)
    {
        next_node = current_node->next;
        free(current_node);
        current_node = next_node;
    }
    *head = NULL;
}

int main(void)
{
    // create initial head for the list
    LinkedList* list = malloc(sizeof(LinkedList));
    list->next = NULL;
    list->data = NULL;

    Sleep(1000); // added delay to better see the memory usage


    // trying to fill the list with both methods and compare the result of memory usage
    for (int i = 0; i < 20000; i++)
    {
        //append(list, NULL);

        push(&list, NULL);
    }

    Sleep(1000);

    // trying to free all struct LinkedList
    destroy_list(&list);

    system("Pause");
    return EXIT_SUCCESS;
}

（我没有把 malloc 指针检查放在代码中，让它更清楚一点。）

所以当我尝试用函数 push() 填充链表时，我得到了一种正常的行为，因为几乎所有在 filling/freeing 之前和之后的内存列表几乎是相同的（即使这不是完全相同的数量）。这是我截取的屏幕截图：

我在为每个测试向列表添加元素之前和之后添加了延迟，以便我们可以更好地看到差异。

因此，通过使用 push() 填充链表，我们在程序结束时获得了大约 900kb 的内存使用量。

现在这是完全相同程序的结果，但我们使用 append() 来填充列表：

正如我们所见，填充链表需要更多时间，因为 append() 方法必须遍历整个列表才能添加 push() 方法不需要的元素。最后，该程序释放的内存几乎没有以前的方法那么多。

所以我认为我的 append() 函数应该有问题，可能是某种内存泄漏导致链表中的节点脱离链。

然后我用 append() 函数做了更多测试，我注意到一个更奇怪的行为。当我尝试在 destroy_list() 函数中循环时增加一个变量，然后打印结果以查看程序调用 free() 的次数，突然释放了更多内存！

这里是修改后的 destroy_list() 函数：

void destroy_list(LinkedList** head)
{
    LinkedList* current_node = *head;
    LinkedList* next_node;

    int i = 0; // Added

    while (current_node != NULL)
    {
        next_node = current_node->next;
        free(current_node);
        current_node = next_node;
        i++; // Added
    }
    printf("%d\n", i); // Added
    *head = NULL;
}

使用这个函数并使用 append() 函数填充列表，我们得到：

我尝试了很多次，我提供的每个屏幕截图仍然得到相同的结果。

我真的不明白这怎么可能，但我花了很多时间在这上面，我真的很想知道我错过了什么？？？

Answer 1

检查进程使用的内存并不能很好地指示您是否正确释放了所有内存。当进程将内存返回给 OS 时，不必与对 free.

的调用同时进行

Linux 上有诸如 Valgrind 之类的工具，专门用于检查运行代码中的内存错误。当我通过 Valgrind 运行这段代码时，它回来了。没有无效的内存访问，所有分配的指针都被释放。

完全释放链表的麻烦

Troubles with completely freeing a linked list

c

linked-list

singly-linked-list