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

Question

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

以下是我的代码。请看：

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;


}

所以你看，curPtr 正在断开连接，但我相信它仍然存在于自由商店的某个地方。我如何永久摆脱它？

Answer 1

你能为你的 ListItem 类型创建一个 erase_next() 方法吗？我在类似 class 中有类似以下内容。希望对你有帮助。

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;
    }
}

在您的函数中，您可以像下面这样调用它。感谢@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()
    }
 }

编辑：

我又试了一下，你应该可以用下面的

优化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;
    }
}

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

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

Deleting a node from a doubly linked list AND freeing up its space as well

c++

nodes

doubly-linked-list