Doubly linked list insert method

Question

I am currently doing an assignment to learn about doubly linked lists and iterators. I am making an insert() method that takes in an iterator type, as well as the data to add into the list. However, I'm getting an exception on the line I marked in the insert() method, saying:

Exception thrown: read access violation. iter.node was 0xFFFFFFFFFFFFFFEF

I'm not sure if this is a problem with the iterator or the linked list:

#include <cstdlib>
#include <iostream>
using namespace std;

class List {
    struct Node {
        int data;
        Node* next = nullptr;;
        Node* prev = nullptr;
    };

    friend ostream& operator<<(ostream& os, const List& rhs);

public:

    class iterator {
        friend class List;

        Node* node = nullptr;

    public:
        iterator(Node* node) : node(node) {}

        iterator& operator++() {
            node = node->next;
            return *this;
        }

        iterator& operator--() {
            node = node->prev;
            return *this;
        }

        bool operator==(const iterator& rhs) {
            if (node != rhs.node) {
                return false;
            }
            return true;
        }

        bool operator!=(const iterator& rhs) {
            return !(*this == rhs);
        }

        int operator*() const {
            return node->data;
        }

        iterator& operator->() {
            return *this;
        }
    };

    List() {
        header = new Node();
        trailer = new Node();
        header->next = trailer;
        header->prev = nullptr;
        trailer->prev = header;
        trailer->next = nullptr;
    }

    void push_back(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->prev = trailer->prev;
        newNode->prev->next = newNode;
        newNode->next = trailer;
        trailer->prev = newNode;
    }

    void pop_back() {
        Node* tempNode = trailer->prev->prev;
        tempNode->next = trailer;
        trailer->prev = tempNode;
    }

    void push_front(int data) {
        Node* newNode = new Node();
        newNode->data = data;
        header->next->prev = newNode;
        newNode->next = header->next;
        newNode->prev = header;
        header->next = newNode;
    }

    void pop_front() {
        Node* tempNode = header->next->next;
        tempNode->prev = header;
        header->next = tempNode;
    }

    int& front() {
        if (header->next == trailer) {
            cerr << "List is empty" << endl;
        }
        return header->next->data;
    }

    int& back() {
        if (trailer->prev == header) {
            cerr << "List is empty" << endl;
        }
        return trailer->prev->data;
    }

    int front() const {
        if (header->next == trailer) {
            cerr << "List is empty" << endl;
        }
        return header->next->data;
    }

    int back() const {
        if (trailer->prev == header) {
            cerr << "List is empty" << endl;
        }
        return trailer->prev->data;
    }

    int size() const {
        int count = 0;
        for (iterator i = begin(); i != end(); ++i) {
            ++count;
        }
        return count;
    }

    int& operator[](int index) {
        int ind = 0;
        for (iterator i = begin(); i != end(); ++i) {
            if (ind == index) {
                return i.node->data;
            }
            ++ind;
        }
    }

    int operator[](int index) const {
        int ind = 0;
        for (iterator i = begin(); i != end(); ++i) {
            if (ind == index) {
                return i.node->data;
            }
            ++ind;
        }
    }

    iterator& begin() {
        iterator iter(header->next);
        return iter;
    }

    iterator& end() {
        iterator iter(trailer);
        return iter;
    }

    iterator begin() const {
        iterator iter(header->next);
        return iter;
    }

    iterator end() const {
        iterator iter(trailer);
        return iter;
    }

    iterator& insert(iterator& iter, int data) {
        Node* newNode = new Node();
        newNode->data = data;
        iter.node->prev->next = newNode; //exception is thrown on this line
        newNode->prev = iter.node->prev;
        newNode->next = iter.node;
        iter.node->prev = newNode;
        iterator newIter(newNode);
        return newIter;
    }

    void clear() {
        Node* iter = header->next;
        Node* next;
        while (iter != trailer) {
            next = iter->next;
            delete iter;
            iter = nullptr;
            iter = next;
        }
        header->next = trailer;
        trailer->prev = header;
    }

    iterator& erase(iterator& iter) {
        for (iterator i = ++begin(); i != end(); ++i) {
            if (i == iter) {
                Node* tempNode = i.node;
                tempNode->prev->next = tempNode->next;
                tempNode->next->prev = tempNode->prev;
                delete tempNode;
                tempNode = nullptr;
                return ++i;
            }
        }
    }

public:
private:
    Node* header;
    Node* trailer;
};

ostream& operator<<(ostream& os, const List& rhs) {
    for (int i : rhs) {
        os << i << " ";
    }
    os << endl;
    return os;
}

void printListInfo(const List& myList) {
    cout << "size: " << myList.size()
        << ", front: " << myList.front()
        << ", back(): " << myList.back()
        << ", list: " << myList << endl;
}

int main() {
    List myList;
    for (int i = 0; i < 10; ++i) myList.insert(myList.end(), i * i);
    printListInfo(myList);
    myList.clear();
    for (int i = 0; i < 10; ++i) myList.insert(myList.begin(), i * i);
    printListInfo(myList);
}

Answer 1

iterator& iterator::begin() and iterator& iterator::end() are returning references to local variables. Since it's these functions that are being passed to List::insert(...) in main via myList.insert(myList.begin(), ..) etc, the insertion function is always going to be operating on an invalid iterator.

Similarly, iterator::insert has a similar issue in which it is returning a local variable by reference:

iterator& insert(...)
{
    ...
    iterator newIter(newNode);
    return newIter;
}

Once these functions exit, the local variables are destroyed and so those references that were returned are left dangling - pointing at memory where an object used to be.

A quick fix would be to make sure that those new iterators are not local to that function and are instead initialized on the heap e.g.

iterator& begin() {
    iterator* iter = new iterator(header->next);
    return *iter;
}

iterator& end() {
    iterator* iter = new iterator(trailer);
    return *iter;
}

However, this also means that you would have to introduce a way to keep track of those iterators so that you can free the memory once an iterator is no longer needed, perhaps by storing the iterators as a member variable of List instead of storing the begin/end Nodes of List and therefore only accessing the Nodes via the iterators.

---

I found this due to compiling with warnings on, which is highly recommended!

In member function 'List::iterator& List::begin()':
<source>:151:16: warning: reference to local variable 'iter' returned [-Wreturn-local-addr]
  151 |         return iter;
      |                ^~~~
<source>:150:18: note: declared here
  150 |         iterator iter(header->next);