删除单链表中间的元素

Question

我目前正在实现一个链表，我在擦除元素的函数上遇到了一些麻烦。下面是整个函数。如果列表为空，我退出程序。如果列表只有一个元素，那么我只使用另一个函数pop_back();它是功能性的。最后，如果元素位于列表的中间，我会遍历列表，直到找到它前面的链接。然后，我将指针分配给要擦除的节点的下一个链接的下一个链接。该函数确实删除了一个元素，但它遇到了问题。

template <class T>
void List<T>::erase(iterator & pos) {
    Node<T> * currentNode = pos.current;
    Node<T> * nextNode = pos.current->next;
    Node<T> * searchNode = head;
    if (currentNode == 0) {
        cout << "LIST EMPTY. (ERASE)" << endl;
        exit(0);
    }
    else if (nextNode == 0) {
        pop_back();
    }
    else {
        while (searchNode->next != currentNode) {
            searchNode = searchNode->next;
        }
        searchNode->next = nextNode;
        delete currentNode;
        listsize--;
    }
}

我使用了下面的测试代码来确保我的函数正常工作，但在从列表中删除元素后它似乎中断了。

int main() {
    List<int> l;
    l.push_front(5);
    l.push_front(3);
    l.push_back(31);
    l.push_back(354);
    l.push_front(63);
    l.displayList();
    for (Listiterator<int>::iterator it = l.begin(); it != l.end(); it++) {
        if (*it == 31) {
            l.erase(it);
            l.displayList();
        }
    }
    l.displayList();
    return 0;
}

以下是代码执行的步骤：

63 -> 3 -> 5 -> 31 -> 354 -> NULL
(ERASE ELEMENT 31)
63 -> 3 -> 5 -> 354 -> NULL

通过调试器，我能够看到删除 31 后，迭代器位于内存中的 NULL/非法位置并终止。

有人有什么想法或建议吗？

以下是重载的++运算符：

template <class T>
Listiterator<T> & Listiterator<T>::operator++() {
    current = current->next;
    return *this;
}
template <class T>
Listiterator<T> & Listiterator<T>::operator++(int) {
    Listiterator<T> saveList = Listiterator(this);
    current = current->next;
    return saveList;
}

Answer 1

这个循环是不安全的：在 l.erase（it） 之后，迭代器 "it" 不再有效，但循环不断尝试递增它。

for (Listiterator<int>::iterator it = l.begin(); it != l.end(); it++) {
    if (*it == 31) {
        l.erase(it);
        l.displayList();
    }
}

确保其安全的一种方法是在擦除元素后断开：

for (Listiterator<int>::iterator it = l.begin(); it != l.end(); it++) {
    if (*it == 31) {
        l.erase(it);
        break;
    }
}

Answer 2

我相信

这就是你要找的答案。

它基本上解释了如何在循环访问列表时从列表中删除项目，而不会丢失对当前下一个迭代器的引用。

Answer 3

首先，请只实现你自己的链表作为一个教育项目。在生产代码中，您应该尽可能选择std::list，因为它经过了良好的测试，具有经过深思熟虑的界面，并且使您免于执行该工作。

您只需在函数结束时相应地设置迭代器即可。

template <typename T> // I think, typename is less confusing than class here.
void List<T>::erase(iterator & pos) {
    Node<T>* currentNode = pos.current;
    Node<T>* nextNode = pos.current->next;
    Node<T>* searchNode = head;
    if (currentNode == nullptr) { // prefer nullptr in modern C++
        cout << "LIST EMPTY. (ERASE)" << endl;
        exit(0);
    }
    else if (nextNode == nullptr) {
        pop_back();
    }
    else {
        while (searchNode->next != currentNode &&
               // Protect yourself against false parameter passing
               searchNode != nullptr) {
            searchNode = searchNode->next;
        }
        if (searchNode == nullptr) {
            cout << "Iterator not for this list. (ERASE)" << endl;
            exit(0);
        }
        searchNode->next = nextNode;
        delete currentNode;
        listsize--;
        pos.current = nextNode;
    }
}

顺便说一句：我们真的需要所有这些临时人员吗？

template <typename T>
void List<T>::erase(iterator & pos) {    
    if (pos.current == nullptr) {
        cout << "LIST EMPTY. (ERASE)" << endl;
        exit(0);
    }
    else if (pos.current->next == nullptr) {
        pop_back();
    }
    else {
        Node<T>* searchNode = head;
        while (searchNode->next != pos.current &&
               // Protect yourself against false parameter passing
               searchNode != nullptr) {
            searchNode = searchNode->next;
        }
        if (searchNode == nullptr) {
            cout << "Iterator not for this list. (ERASE)" << endl;
            exit(0);
        }
        searchNode->next = pos.current->next;
        delete pos.current;
        listsize--;
        pos.current = nextNode;
    }
}

考虑抛出异常，而不是在应用程序中间的某个位置退出。当没有人捕获异常时，程序也会终止，但它使类的用户有机会以某种方式处理该错误。

请考虑使用std::unique_ptr作为"下一个指针和头部"。它不会创建任何代码，如果您能够始终在必要时正确调用 delete，则不会创建任何代码。因此，没有运行时开销，它使您的代码更简单 - 有时只是一点点，有时很多。