How to create pointer chains? I would like to create objects that have pointers pointing to further objects, that has pointers. Is this even possible?

Question

I've created this example code, but I just can't make it work. I want to create children from a parent node, in a way that every children has one parent, and each have a pointer to its parent. The first parent's pointer is the nullpointer. Now the question is, if I am somewhere at the end of the tree's branch, how can I return to the first parent step by step, and write out the history?

For the sake of simplicity, in this example I've created a linear graph with one simple path.

I discovered that if I want to dereference a node's parent's node for the second time, I already get fake results, and I can't reach further than the first parent. So I can only dereference the current node's parent. Why is that? I have seen that in linked-lists people store every pointer, but I would like to avoid that. The goal is, every node is stored in a list<Node>, and each of them stores only its parents pointer, so from every node we can trace back the first parent.

#include <iostream>
#include <list>

using namespace std;

struct Node
{
    int node;
    Node *parent;
};

void create (Node parent, list<Node>& graph)
{
    if (graph.size() < 10)
    {
        Node nn;
        nn.node = parent.node+1;
        nn.parent = &parent;
        graph.push_back(nn);
        create(nn, graph);
    }
}

int main()
{
    list<Node> graph;

    Node parent;
    parent.node = 0;
    parent.parent = nullptr;
    graph.push_back(parent);

    create(parent, graph);

    for (auto i : graph)
    {
        cout << i.node << " ";
    }
    cout << endl << endl;

    auto it = graph.begin();
    advance(it, 3);

    cout << (*it).node << endl;
    cout << (*(*(*it).parent).parent).node;

    return 0;
}

You can just keep adding `*`s but, as Beta points out, this doesn't scale very well. I recommend a re-think. Perhaps a loop? — user4581301, Jan 07 '20 at 01:57
Reason for the fake results: In `void create (Node parent, list& graph)`, `parent` [is passed by value](https://stackoverflow.com/questions/373419/whats-the-difference-between-passing-by-reference-vs-passing-by-value). This means it's a copy of the argument and a local variable that will expire at the end of the function. Keeping a pointer to this value leaves you with what's called a [Dangling Pointer](https://en.wikipedia.org/wiki/Dangling_pointer). Instead pass `parent` by reference: `void create (Node & parent, list& graph)`. — user4581301, Jan 07 '20 at 02:00
`(*it).node` -> `it->node`, `(*(*(*it).parent).parent).node` -> `it->parent->parent->node` — Thomas Sablik, Jan 07 '20 at 02:03
if you really want a structure where pointers are stored recursively, and you have thought about it and it's a good idea, the method of accesing these structures usually wants to be a recursive function as well — camelccc, Jan 07 '20 at 02:07

PajLe · Accepted Answer · 2020-01-07T04:06:32.340

You are creating Nodes as local variables in the create function. When you exit function's scope, addresses you save as Nodes' parent won't contain the Node which was previously there (every nn.parent becomes a dangling pointer).

If you wish to create Nodes in a function, it should look something like this:

void create(Node* parent, list<Node>& graph)
{
    if (graph.size() < 10)
    {
        Node* nn = new Node;
        nn->node = parent->node + 1;
        nn->parent = parent;
        graph.push_back(*nn);
        create(nn, graph);
    }
}

This, however, will cause several problems:

In this line graph.push_back(*nn); we are dereferencing nn which leads to unnecessary copying of int and Node* (struct attributes) values.
We are causing a memory leak since we are not saving nn value anywhere, so we can't delete its content later.

It would be better to keep a list of Node* instead of Node:

list<Node*> graph;

That way, we could just iterate through the list and delete dynamically allocated Nodes later on:

for (auto i : graph)
    delete i;

And instead of copying int and Node* values, we just push Node* nn to the list:

graph.push_back(nn);

Note that it is a pointer to a pointer now, so it would require double dereferencing:
cout << (**it).node << endl;
cout << (*(*(**it).parent).parent).node;

How to create pointer chains? I would like to create objects that have pointers pointing to further objects, that has pointers. Is this even possible?

1 Answers1