C++ linked list reverse traversal memory corruption

Question

I'm learning C++. As part of a mapping project, I'm trying to (reverse) traverse a linked list from a particular node to the start node via a parent address pointer attribute in the node class. I'm trying to figure out why a parent's address value consistently becomes corrupted, which causes an error and prevents the traversal.

I've extracted the essential components of the project below, along with some helper code that allows the error to be recreated easily.

#include <iostream>
#include <stdio.h>
#include <vector>
using std::vector;
using std::cout;
using std::endl;

class Node
{
    public:
        int idx;
        Node * addr = nullptr;
        Node * parent_addr = nullptr;
    
        Node (int init_idx, Node * init_parent) {
            idx = init_idx;
            parent_addr = init_parent;
        }
};

void PrintNode(Node & n) {
    cout << "idx: " << n.idx << " addr: " << n.addr << " parent_addr: " << n.parent_addr << endl;
}

void PrintNodeList (vector<Node> & path) {
    for (Node n : path) {PrintNode(n);}
}

void CreateNodeList (const int node_count, vector<Node> & node_list) {
    for (int i=0; i<=(node_count - 1); i++) {
        if (i==0) {
            //  first node parent is null
            node_list.push_back(Node(i, nullptr));
        } else {
            // subsequent nodes parent is previous node
            node_list.push_back(Node(i, &node_list[i-1]));
        }
        // store address of node to clearly follow forward and reverse traversals
        node_list[i].addr = &node_list[i];
    }
    cout << "Node List..." << endl;
    PrintNodeList(node_list);
}

void TraverseNodeList(Node * current_node) {
    cout << endl << "Traversing node list in reverse..." << endl;
    while (current_node != nullptr) {
        PrintNode(*current_node);
        current_node = current_node->parent_addr;
    }
    cout << endl << "Completed reverse traversal." << endl;
}

int main() {
    // generate list of nodes
    const int node_count = 5;
    vector<Node> node_list;
    CreateNodeList (node_count, node_list);
        
    // reverse traverse the list of nodes
    const int last_node = node_count - 1;
    TraverseNodeList(&node_list[last_node]);
    
    return 0;
}

Here is a sample node list (node index, address of the node, address of node's parent):

Here is a traversal corrupting at the start node:

Here is a traversal corrupting before the start node:

Actual CreateNodeList function:

This code is extracted from an A* search project. As the map is traversed, the neighbors of the node being examined (current_node) are updated (the parent attribute is set and they are marked as visited) and pushed onto the std::vector<node *> node_list via the following:

for (auto neighbor : current_node->neighbors) {
    neighbor->parent = current_node; 
    node_list.push_back(neighbor); 
    neighbor->visited = true;
}

Answer 1

node_list.push_back(Node(i, &node_list[i-1]));

A pointer to the previous element in the vector gets passed to a constructor of a new Node's element.

This immediately becomes undefined behavior. It is a fundamental property of std::vectors that when std::vector reallocates this invalidates all existing pointers and iterators to the vector.

After constructing this new Node, it gets passed as a parameter to push_back, which may result in reallocation of the vector's contents, thus invalidating this and all previous pointers to the vector.

If it is necessary to juggle pointers to elements in a vector, additional work must be done to ensure that the vector will never reallocate. This is outside the scope of this question, and would be rather cumbersome so probably the best thing to do here is to rethink the overall design of your linked list so that it does not use std::vectors, perhaps std::list will be an alternative (however since std::list is, itself, a linked list, that would be somewhat dubious). In any case, the reason for the crash is undefined behavior due to referencing pointers to values in a vector that gets reallocated, invalidating all pointers to the values in the vector.