Removing an element in the middle of a singly linked list?

Question

I'm currently implementing a linked list and I'm having a bit of trouble on a function that erases an element. Below is the function in its entirety. If the list is empty, I exit the program. If the list only has a single element, then I just use another function pop_back(); which is functional. Lastly, if the element is in the middle of the list, I iterate through the list until I find the link right before it. I then assign the pointer to the next link to the next link of the node to be erased. The function does remove an element, but it runs into a problem.

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

I used the test code below to make sure my function works, but it seems to break after removing the element from the list.

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

Here are the steps that the code goes through:

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

Through the debugger I was able to see that after deleting 31, the iterator is positioned in a NULL/illegal position in memory and terminates.

Does anyone have any thoughts or suggestions?

Here are the overloaded ++ operators:

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

Can you share the entire code including the List and Node templates? — Adi Levin, Jan 24 '16 at 19:09
`Node * nextNode = pos.current->next;` Note that this might trigger a dereference of a null pointer, since you allow for pos.current == 0. — Yam Marcovic, Jan 24 '16 at 19:25
I expect the iterator to remain at the next node after the node to be deleted is removed. @YamMarcovic I'll move that declaration after the `else if` and change the check in `else if` to `(pos.current->next == 0)`. — TheLongDark, Jan 24 '16 at 19:32
The specific reason your program's crashing here might have to do with the overloaded ++ operator of your iterator. You can edit your question and add it in so we can have a look. — Yam Marcovic, Jan 24 '16 at 19:36
@TheLongDark And that indeed exposes the issue. You delete `current`, and after that you go `current->next`. — Yam Marcovic, Jan 24 '16 at 19:50

score 0 · Answer 1 · answered Jan 24 '16 at 19:08

0

This loop is no safe: After l.erase(it), the iterator "it" is no longer valid, but the loop keeps trying to increment it.

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

One way to make it safe is to break after erasing the element:

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

answered Jan 24 '16 at 19:08

Adi Levin

5,165
1
17
26

So the code for the removal of an element in a list is fine, just not the loop in which I used it? – TheLongDark Jan 24 '16 at 19:17
Maybe. There might be another bug. To be sure, I will have to get the entire code and run it. – Adi Levin Jan 24 '16 at 19:19

score 0 · Answer 2 · edited May 23 '17 at 12:31

0

I believe that this is the answer you're looking for.

Its basically explaining how you can delete items from a list while you're iterating through it, without losing reference to the currently next iterator.

edited May 23 '17 at 12:31

Community

1
1

answered Jan 24 '16 at 19:14

score 0 · Answer 3 · answered Jan 25 '16 at 20:18

First of all, please only implement your own linked list as an educational project. In production code you should prefer std::list wherever reasonably possible, because it is well tested, has a well thought out interface, and saves you from doing that work.

You could simply set the iterator accordingly at the end of the function.

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

BTW.: do we really need all those temporaries?

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

Consider to throw exceptions instead of exiting somewhere in the middle of your application. When noone catches the exception, the program will terminate as well, but it leaves the user of your class a chance to handle that error somehow.

Please consider to use std::unique_ptr for the `next pointers and head. It will not create any code, that you would't have created, if you were able to always correctly call delete, where necessary. So there is no runtime overhead and it makes your code simpler - sometimes only a little bit, sometimes a lot.

Removing an element in the middle of a singly linked list?

3 Answers3