删除单链表中间的一个元素？

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之后，迭代器在内存中的位置为空/非法，并终止。

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

以下是重载的运算符：

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

首先，请把你自己的链表作为一个教育项目来实施。在生产代码中，您应该尽可能选择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作为下一个指针和头。它不会创建任何代码，如果您能够在必要时始终正确调用删除，您就不会创建这些代码。因此，没有运行时开销，它使您的代码更简单——有时只有一点点，有时很多。

Answer 2

我相信这就是你想要的答案。

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

Answer 3

这个循环不安全：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;
    }
}