如何在 C++ 中正确删除链表的节点 [英] How do I properly delete nodes of linked list in C++

问题描述

我感觉好像我实际上并没有删除节点并释放内存.我想我只是在移动指针，所以当我打印链表时，列表不会打印我删除的元素.所以我的问题是我实际上是删除节点还是我只是简单地重新排列指针，所以看起来我正在删除节点(基本上只是断开链接而不是删除节点)?感谢您的帮助.

I feel as if I am not actually deleting the node and freeing up memory. I think I am just moving pointers around so when I print the linked list the list doesn't print the element I deleted. So my question is am I actually deleting the node or am I just simply rearranging the pointers so it looks like I am deleting the nodes(Essentially just breaking the links but not deleting the node)? Thank you for any help.

void SLL::deleteNode(int target){
Node *current = new Node;
Node *previous = new Node;

for (current = front->next, previous = front; current != NULL; current = current->next, previous=previous->next){
    if (previous->data == target && previous == front){
        front = previous->next;
        delete[] previous;
        return;
    //This if statement deletes the element if its the front
    }

    else {

        if (previous->data == target && previous->next == NULL){
            previous = NULL;
            delete[] current;
            return;
        //This if statement deletes the node if it is the back
        }


        else if (current->data==target)
        {
            previous->next = current->next;
            delete[] current;
            return;
        //This if statement deletes a node if it is in the middle
        }
    }
    }

    delete[] current;
    delete[] previous;
}

推荐答案

Node *current  = new Node;
Node *previous = new Node;

此代码会导致内存泄漏 - 您永远不会删除此内存.您可以在不分配内存的情况下声明指针:

This code causes memory leaks - you are never deleting this memory. You can declare pointers without memory allocation:

Node *current  = nullptr;
Node *previous = nullptr;

delete 将删除指针的内存，因此您实际上将删除节点.但是对 Node* 使用 delete[] 不正确，它应该只用于数组——用new[]分配的内存.使用不当会导致未定义的行为.因此，要正确删除节点，请使用 delete 运算符删除它们.

delete will delete the memory of the pointer so you will actually delete Nodes. But using delete[] for the Node* is incorrect, it should be used only for arrays - the memory allocated with new[]. Improper use leads to undefined behaviour. So, to properly delete nodes delete them with operator delete.

使用内存泄漏检测工具来了解您的程序中是否存在内存泄漏.

Use memory leaks detection tools to know are there memory leaks in you program.

删除列表元素的代码:比如说，我们有指向列表头部的pHead(但如果你自己写这样的东西会给你更多):

The code to delete a list element: say, we have pHead which points to the head of the list (but it would give you much more if you write such things yourself):

Node* pCur  = pHead;
Node* pPrev = pCur;

while (pCur && pCur->data != target) {
    pPrev = pCur;
    pCur  = pCur->next;
}

if (pCur==nullptr)  // not found
   return NOT_FOUND;

if (pCur == pHead) {   // first element matches
    pHead = pCur->next;
} else {
    pPrev->next = pCur->next;
}

// pCur now is excluded from the list

delete pCur;     // deallocate its memory

<小时>

使用指针到指针的替代方法(社区添加)

当您使用列表中的实际指针来执行枚举时，上面的内容可以呈现出新的亮点.下面从 pp 被分配头指针的地址开始(不是它指向的节点；实际的指针本身).我们遍历列表，直到 pp 持有指向要删除目标的节点的指针的地址(可能是头指针，也可能是一些节点，没有区别).被寻址的指针被设置为它自己节点的next值，然后目标节点被移除.

The above can take on new light when you use the actual pointers in the list to perform the enumeration. The following starts with pp being assigned the address of the head pointer (not the node it points to; the actual pointer itself). We walk the list until pp hold the address of a pointer that is pointing to a node with the target to delete (could be the head pointer, could be a next pointer in some node, makes no difference). The pointer being addressed is set to its own node's next value, then the target node is removed.

这确实应该在调试器中观察以了解其工作原理，但考虑到实际情况，该算法非常简单:

This really should be watched in a debugger to see how it works, but the algorithm is remarkably simple given what is really going on:

Node **pp = &pHead;
while (*pp && (*pp)->data != target)
    pp = &(*pp)->next;

if (*pp)
{
    Node *victim = *pp;
    *pp = victim->next;
    delete victim;
}

这就是全部.而且您无需特殊情况即可免费删除头节点.希望这也能有所帮助.

Thats all of it. And you get head-node removal without having to special case it for free. Hope this helps as well.

这篇关于如何在 C++ 中正确删除链表的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！