释放链表中节点的内存

Question

我正在处理一个单链表，我想尝试另一种方法来练习我的删除函数算法：

template<class T>
inline void LinkedList<T>::remove(T v)
{
    Node<T>** indirect = &head;
    while (*indirect && (*indirect)->value != v) {
        indirect = &((*indirect)->next);
    }
    *indirect = ((*indirect)->next);
}

我的所有节点都是通过 new 创建的。最后一行只是将指针更改为指向下一个节点。但是我应该释放 *indirect 之前指向的内存，对吗？

我更改了我的代码，以便释放底层节点指针的节点内存。我还跟踪前一个节点以维护尾指针：

template<class T>
inline void LinkedList<T>::remove(T v)
{
    Node<T>** indirect = &head;
    Node<T>* prev = nullptr;
    while (*indirect && (*indirect)->value != v) {
        prev = *indirect;
        indirect = &((*indirect)->next);
    }
    if (*indirect) {
        if (*indirect == tail) {
            tail = prev;
        }
        Node<T>* tmp = *indirect;
        *indirect = (*indirect)->next;
        delete tmp;
    }
}

Answer 1

是的，如果节点是用new分配的，应该用delete删除。

就是说，您错过了节点删除，更重要的是在最终取消引用之前检查了 null。您的实际枚举循环看起来很可靠（对此表示感谢；对于某些人来说，指向指针的指针并非易事）。

template<class T>
inline void LinkedList<T>::remove(T v)
{
    Node<T>** indirect = &head;
    while (*indirect && (*indirect)->value != v)
        indirect = &((*indirect)->next);

    if (*indirect)
    {
        Node<T> *tmp = *indirect;
        *indirect = tmp->next;
        delete tmp;
    }
}

警告：确保您的 Node 析构函数不会做一些愚蠢的事情，比如尝试删除它的链接链。

具有 head 和 tail 指针的托管列表

如果list同时有head和tail指针，方便两端插入O(1)，算法稍微复杂一点，但复杂度不变。您必须在枚举循环期间维护一个 prev 指针，初始值为 nullptr，并从主迭代向后移动一个节点：

template<class T>
inline void LinkedList<T>::remove(T v)
{
    Node<T>** indirect = &head, *prev = nullptr;
    while (*indirect && (*indirect)->value != v)
    {
        prev = *indirect;
        indirect = &((*indirect)->next);
    }

    if (*indirect)
    {
        Node<T> *tmp = *indirect;

        // if the victim of the delete is also the tail
        //  then set it to the prior node pointer, which
        //  may be null if this was a single node list and
        //  both head and tail refer to the same node.
        if (tail == tmp)
            tail = prev;

        *indirect = tmp->next;
        delete tmp;
    }
}

剩下的唯一事情就是用以下条件验证上面的机器。当...

时会发生什么

列表中没有匹配的节点？[=48=]
列表中有一个节点匹配？
有多个节点，第一个节点匹配？
有多个节点，最后个节点匹配？
有多个节点，某个中间节点匹配？

每一个的答案都值得进行脑力锻炼，可能还需要一些纸、pen/pencil、一些方框和一些箭头。在每种情况下浏览上面的代码，看看会发生什么。如果一切看起来都是正确的，它可能是可靠的。当然，编写一堆单元测试来为上述每个条件制作列表并测试功能始终是一个不错的主意。

总之，就是这样。

释放链表中节点的内存

deallocate memory of Node in Linked List

c++

memory

allocation