C风格C++链表管理函数优化及指针相关问题解答

我需要C语言链表管理代码方案的相关帮助。先说明这份代码的特殊性：文件为C++编写，但核心使用C语言标准库资源（malloc()、free()等），给出的基础代码逻辑直白，不存在理解门槛。
我希望实现能覆盖所有边界场景的链表尾部追加元素函数、链表元素删除函数。开发过程中删除函数是我遇到阻碍最多的部分，也让我意识到自己对指针的理解仍有不足。
以下是我编写的可正常运行的代码，但我认为存在以下可改进空间：

• 代码在清晰度、性能层面都有较大优化空间
• 希望通过评审指出当前方案中存在的缺陷

// The plan is to create a linked list and to be able to add and delete its elements

#include <iostream>
using namespace std; // I can write output lines as cout << "Hi!", rather than std::cout < "Hi!"
#include <cstdlib> // needed for malloc() in C++

struct node {
    int data;
    node* nextPtr; //"struct node* nextPtr;" : This would be the syntax for plain old C: you always have to type the "struct" keyword
};

node* createElement(int data) {
    node* newElemPtr = (node*)malloc(sizeof(node)); // the "(node*)" cast is required by C++, and is not used in C
    newElemPtr->data = data;
    newElemPtr->nextPtr = NULL;
    return newElemPtr;
}

void appendElement(int data, node** head) { // Adds a new node at the end of the list
    // I pass as argument a pointer to pointer (double pointer) to node, so that I can edit the head node
    // if the list is empty, without having to return a new node pointer as head: my function indeed features
    // "void" in its signature
    node* elemPtr = NULL;
    elemPtr = createElement(data); // elemPtr is a pointer to the new node

    if (*head == NULL) {
        *head = elemPtr;
    }
    else {
        node* currPtr = *head; // currPtr is the temporary variable that visits each node of the linked list
        while (currPtr->nextPtr != NULL)
            currPtr = currPtr->nextPtr;
        currPtr->nextPtr = elemPtr; // Set last element's nextPtr to "elem", i.e., a pointer to the new element
    }
};

void removeElement(int data, node** head) { // Remove all the nodes whose data content matches the "data" argument
    int presence_flag = 0; // Flag used to check whether the required data is present at all in the linked list
    if (*head == NULL) {
        return;
    }
    else {
        node* currPtr = *head;
        node* prevPtr = *head;
        while (currPtr != NULL) {
            // This is the case in which I find a node to delete (it matches the "data" query), and it is not the first of the list
            if (data == currPtr->data && currPtr != *head) {
                prevPtr->nextPtr = currPtr->nextPtr; // Link the node ahead of the one to delete with the one behind
                free(currPtr);
                currPtr = prevPtr; // In the next loop, I will resume the analysis from the previous node, which now points to an unvisited one
                presence_flag = 1;
            }
            // This is the case in which I find a node to delete and it is the first of the list
            else if (data == currPtr->data && currPtr == *head) {
                // This is the case in which I have to delete the first node, but the list features other nodes
                if (currPtr->nextPtr != NULL){
                    *head = currPtr->nextPtr; // Move *head forward
                    currPtr = *head; // Do the same with currPtr, in order not to break the while() loop
                    free(prevPtr); // As *head has already been re-assigned, I leverage prevPtr to delete the old *head
                    presence_flag = 1;
                }
                // This is the case in which I have to delete the first and only node of the list
                else {
                    *head = NULL;
                    currPtr = *head;
                    presence_flag = 1;
                }
            }
            // This is the case in which the current node does not match the queried "data" value
            else{
                prevPtr = currPtr; // Update prevPtr
                currPtr = currPtr->nextPtr; // Move currPtr forward
            }
        }
    }
    if (presence_flag == 0)
        cout << "There is not any node with value " << data << " in the linked list.\n\n";

    // Q1: Am I causing any memory leak by using *head == NULL instead of free(*head)?
    // Q2: Should I free() everythin before ending the main(), at least as a good practice?
    // Q3: Is there a way to make this function by not using a double pointer as input and by also keeping "void" as return value?
    //     Of course, it should still work in the tricky edge case of the last element in the list that has to be deleted
};

void printLinkedList(node* head) { // Here I return nothing, so I can freely edit "head" (i.e., there is no need for a temporary pointer)
    if (head == NULL) {
        cout << "The linked list is empty.\n";
    }
    else {
        int elemCounter = 0;
        while (head != NULL) {
            elemCounter += 1;
            cout << "elem N. " << elemCounter << ": data value = " << head->data << "\n"; // head->data is equal to (*head).data
            head = head->nextPtr;
        }
    }
};

int main(int argc, char* argv[])
{
    //cout << "Size of a single node of the list = " << sizeof(node) << "\n";
    // == 16. On a 64 bits machine, an int ("data") requires 4 bytes.
    // The pointer requires 8 bytes; the remaining 4 bytes are padding

    node* head = NULL;

    appendElement(1, &head);
    appendElement(2, &head);
    appendElement(3, &head);
    printLinkedList(head);

    cout << "\nRemoving element with data value = 1...\n\n";
    removeElement(1, &head);
    printLinkedList(head);
    cout << "\nRemoving element with data value = 2...\n\n";
    removeElement(2, &head);
    printLinkedList(head);
    cout << "\nRemoving element with data value = 3...\n\n";
    removeElement(3, &head);
    printLinkedList(head);
    cout << "\nRemoving element with data value = 4...\n\n";
    removeElement(4, &head);
    printLinkedList(head);
    cout << "\nRemoving element with data value = 1...\n\n";
    removeElement(1, &head);
    printLinkedList(head);
    cout << "\nRemoving element with data value = 2...\n\n";
    removeElement(2, &head);
    printLinkedList(head);

    return 0;
}

我在编写节点删除函数时有三个核心疑问：

• Q1：删除唯一头节点时直接将*head赋值为NULL而不调用free(*head)，是否会造成内存泄漏？
• Q2：作为良好编码实践，是否需要在main()函数结束前调用free()释放所有已分配的节点内存？
• Q3：是否可以不使用二级指针作为函数入参，同时保持函数返回值为void，且仍能正确处理删除链表最后一个节点的边界场景？
  我列出这些疑问，也是希望未来有同样困惑的开发者能获得参考。我知道网上有很多可直接复制使用的链表实现方案，但我希望通过了解自己当前设计选择的不足与错误原因，真正掌握相关知识点。

问题解答 #

Q1：删除唯一头节点时直接将*head赋值为NULL而不调用free(*head)，是否会造成内存泄漏？ #

会，你当前的代码在这个分支就存在明确的内存泄漏。
你可以看删除唯一头节点的逻辑：此时currPtr和prevPtr都指向那个唯一的头节点，你直接把*head设为NULL，没有调用free()释放之前malloc申请的那块内存，这块内存会一直被占用到程序退出，属于典型的内存泄漏。你在删除非头节点、删除带后继节点的头节点时都正确调用了free()，唯独这个分支漏了，在把*head设为NULL之前补上free(currPtr)即可修复。

Q2：作为良好编码实践，是否需要在main()函数结束前调用free()释放所有已分配的节点内存？ #

必须要。不要信“程序退出后操作系统会自动回收内存，所以不用手动free”的错误说法，这是非常坏的编码习惯：

• 如果这段链表代码后续被嵌入长期运行的程序（比如服务端进程、桌面客户端），不手动释放内存会导致内存占用持续上涨，最终触发OOM崩溃
• 手动编写内存释放逻辑的过程，本身就是在梳理内存生命周期，能帮你提前发现野指针、重复释放、泄漏等隐蔽bug
• 使用内存检测工具（比如Valgrind、ASAN）排查问题时，未主动释放的内存会抛出泄漏警告，干扰你定位真正的问题
  你可以单独实现一个freeList(node** head)函数，遍历所有节点逐一释放，最后把头指针设为NULL，在main函数退出前调用一次即可。

Q3：是否可以不使用二级指针作为函数入参，同时保持函数返回值为void，且仍能正确处理删除链表最后一个节点的边界场景？ #

可以，但本质都是间接寻址的不同实现，可读性上不如二级指针直观，常见的两种方案：

1. 哨兵节点（哑节点）方案：固定一个不存储有效业务数据的节点作为永久链表头，所有存有效数据的节点都挂在这个哨兵节点之后。这样永远不需要修改头指针本身，所有插入、删除操作都是修改普通节点的nextPtr，传一级指针就能实现。缺点是每个链表会多占一个节点的内存，所有操作都要多走一层哨兵节点的逻辑。
2. 链表封装结构体方案：定义一个链表结构体，比如struct LinkedList { node* head; };，函数传入这个结构体的一级指针，需要修改头节点时直接修改结构体内部的head成员即可，不需要传二级指针。但本质上你还是拿到了存储头指针的内存地址，和二级指针的原理完全一致，只是用结构体做了一层封装，代码看起来更规整。

额外的代码优化建议 #

• 当前appendElement每次追加元素都要从头遍历到链表尾部，链表长度大时性能很差，可以额外维护一个尾指针，追加时直接操作尾指针，时间复杂度可以从O(n)降到O(1)
• malloc的返回值必须做判空处理，内存申请失败时会返回NULL，直接解引用会触发段错误
• 既然用C编译，没必要硬用malloc/free，用new/delete更符合C的内存管理规范；如果要写纯C风格代码可以忽略这条
• 你当前维护prevPtr和currPtr两个指针的删除逻辑，在处理连续匹配的头节点时存在冗余遍历，可以优化为用一个指向节点指针的变量直接遍历，省掉前向指针的维护，逻辑更简洁不容易出错。

内容的提问来源于stack exchange，提问作者Jetboy