从双向链表中删除节点并释放其空间

I'm working on an assignment and there's a problem I'm stuck on. So I'm making a doubly linked list. I want a a delete function that will take item as argument, search for that argument in the list. when it has found the node which contains that item, I have to DELETE that node. I am aware of how I would change the previous and next pointers to the the nodes around that node. The problem that has been bugging me however, is that when I just change the next pointer of the node before it and the previous pointer of the node after it, like in the code below, the particular node will only be disconnected from the list but it will still remain in the freestore. How do I delete it from there so that the memory it is taking is also freed?

我正在完成任务，而且我遇到了一个问题。所以我正在制作一个双重链表。我想要一个删除函数，它将item作为参数，在列表中搜索该参数。当它找到包含该项的节点时，我必须删除该节点。我知道如何更改前一个和下一个指向该节点周围节点的指针。然而，一直困扰我的问题是，当我只更改节点之前的节点的下一个指针和之后的节点的前一个指针时，就像在下面的代码中一样，特定节点将仅从列表中断开但是它仍然会留在freestore中。如何从那里删除它，以便释放它所占用的内存？

The following is the code I have. Please take a look:

以下是我的代码。请看一下：

template <class T>
void LinkedList<T>::deleteElement(T item)
{
    ListItem<T> *curPtr;
    curPtr = searchFor(item); // this function returns the pointer to the node which contains the item.
    (curPtr->next)->prev = curPtr->prev;
    (curPtr->prev)->next = tempPtr->next;


}

So you see, the curPtr is being disconnected, but I believe it still exists somewhere on the freestore. How do I get rid of it permanantly?

所以你看，curPtr正在断开连接，但我相信它仍然存在于freestore的某个地方。我该如何彻底摆脱它？

1 个解决方案

#1

Could you make an erase_next() method for your ListItem type? I have something like the following in a similar class. Hope it helps.

你能为ListItem类型制作一个erase_next（）方法吗？我在类似的类中有类似的东西。希望能帮助到你。

void erase_next() {
    // ensure it is not the last item
    if(this->next != nullptr) {
        // create a temporary pointer
        ListItem<T>* tmp = this->next

        // link next to the next item to the next item and change the
        // next items previous item to this item
        this->next = this->next->next;
        next->prev = this;

        // delete the old next item
        delete tmp;
    }
}

In your function you could call it with something like the following. Thanks to @davmac edits have been made to delete the first item

在您的功能中，您可以使用以下内容调用它。感谢@davmac编辑已删除第一项

template <class T>
void LinkedList<T>::deleteElement(T item)
{
    ListItem<T> *curPtr = searchFor(item);
    if(curPtr->prev == nullptr) {
        curPtr->next->prev = nullptr;
        delete curPtr;
    } else {
        curPtr->prev->erase_next()
    }
 }

Edit:

编辑：

I played around with this again, and you should be able to optimize the erase_next() function with the following

我再次玩这个，你应该能够用以下方法优化erase_next（）函数

void erase_next() {
    if(this->next != nullptr) {
        this->next = this->next->next
        // We've already linked next so we can delete the handle
        // with prev Note: this method is not possible with a
        // single linked list and we would need the temp variable
        delete this->next->prev
        next->prev = this;
    }
}

That way you don't have to declare a temp variable.

这样您就不必声明临时变量。

#1