struct object's pointer-member getting modified when passed to function

Question

I'm not much familiar with C++/pointers but trying to implement a singly linked list.

I'm simply creating a Node (head) and adding Node after head each time a new one is added to the list.

struct Node {
    int key;
    Node *next;

    Node() : key(-1), next(nullptr) { }
    Node(int k) : key(k), next(nullptr) { }
};

void AddNode(Node *head, int key) {    // Create a new node & add it after the head
    Node newNode(key);
    newNode.next = head->next;
    head->next = &newNode;
}

void PrintNode(Node *nptr, string pre, string post) {
    cout << pre << "(" << nptr << "), " << nptr->key << ", " << nptr->next << post;
}

void PrintLL(Node *nptr) {
    if (nptr) {
        PrintNode(nptr, "\n", "");
        nptr = nptr->next;
        while (nptr) {
            PrintNode(nptr, " -> ", "");
            nptr = nptr->next;
        }
    }
    cout << endl;
}

int main()
{
    Node n1(1);       // Node(1) or head
    Node *head = &n1;

    AddNode(head, 2); // Node(2)
    PrintLL(head);    // Node(2) gets modified with this call in VS 17

    AddNode(head, 3); // Node(3) turns out to be Node(2) with 3 as key in MinGW
    PrintLL(head);

    return 0;
}

When I run this program in VS 2017, this throws exception. Debugging shows that the Node(2) gets added correctly after head(Node(1)) but when PrintLL() is called Node(2)'s key gets changed to some random number & next from NULL to 0xcccccccc.

When this program is compiled using MinGW and run, it runs but assigns Node(2) & Node(3) same memory(?) as this output suggests -

(0x71fe30), 1, 0x71fdf0 -> (0x71fdf0), 2, 0

(0x71fe30), 1, 0x71fdf0 -> (0x71fdf0), 3, 0

I'm not sure what I'm missing and unable to figure out too. Please help.

Thanks.

You have a dangling reference in `AddNode`. `Node newNode(key);` is a local variable that cease to exist after `AddNode` returns. Hence, `head->next` points to nowhere. Either manually allocate on heap using `new` or, better, use a smart pointer like `std::unique_ptr`. — Evg, Aug 16 '18 at 15:49
Unrelated: If you change `Node(int k) : key(k), next(nullptr) { }` to `Node(int k, Node * link = nullptr) : key(k), next(link) { }`, you get a slightly more versatile constructor. No need for `newNode.next = head->next;`, for example. You can pass `head->next` into the `Node` constructor. — user4581301, Aug 16 '18 at 15:53
@Evgeny Oh, thanks. So I have work out some other way to get around this. I wonder using `new` would be too much. I can conclude (my familiarity with) JS the culprit in this case :D — PalashV, Aug 16 '18 at 15:54
It's not too much. You need to allocate memory for the new nodes, or they'll only exist in `addNode`'s scope. As such, you have to use `new`or any other memory allocation operator. Just don't forget to free the memory at the end. Related: https://stackoverflow.com/questions/679571/when-to-use-new-and-when-not-to-in-c — Ricardo Costeira, Aug 16 '18 at 15:57
@PalashV `new` is almost exactly what you want here. `std::unique_ptr` is usually a better option, but if you are coding your own linked list, it's probably for a class and the instructor would likely go nuts if you pulled in smart pointers at this point. But if you WANT to get into smart pointers, watch [Herb Sutter's presentation on Leak Freedom By Default](https://www.youtube.com/watch?v=JfmTagWcqoE) — user4581301, Aug 16 '18 at 15:58
@PalashV dynamic allocation is simply how this is done. What you have now invokes *undefined behavior*, leaving your program execution in indeterminate land. You don't want that (ever). Preferably, you'll use a smart pointer methodology, and ideally you'll do none of the above and just use the best fitting standard library sequence container for your needs and avoid reinventing the wheel. — WhozCraig, Aug 16 '18 at 15:59

Evg · Accepted Answer · 2018-08-16T16:52:15.873

5

You have a dangling reference in AddNode(). Node newNode(key); is a local variable that cease to exist after AddNode() returns. Hence, head->next points to nowhere. Either manually allocate on heap using new or, better, use a smart pointer like std::unique_ptr.

Node and AddNode could look like this:

struct Node {
    int key;
    std::unique_ptr<Node> next;

    Node(int k = -1, std::unique_ptr<Node> n = {})
        : key(k), next(std::move(n))
    { }
};

Node& AddNode(Node& head, int key)
{
    head.next = std::make_unique<Node>(key, std::move(head.next));
    return *head.next;
}

Edit. Please note the first comment below about a potential pitfall of this approach - stack overflow during automatic list deallocation.

edited Aug 16 '18 at 16:52

answered Aug 16 '18 at 16:00

Evg

25,259
5
41
83

5

Bump for the answer. And a word of caution: be careful when using smart pointers for chaining potentially deep containers. A linked list that may hold potentially *thousands* of nodes will easily blow through the activation stack ceiling/floor during the destruction chain. There are some simple ownership-passing iterative algorithms that address this. – WhozCraig Aug 16 '18 at 16:03
@WhozCraig, very good point. I wanted to mention it in the answer, but for a toy example of a linked list it is not relevant. – Evg Aug 16 '18 at 16:05
Of course. It's probably a little high in altitude for the OP right now anyway, but you never know who else will read this question someday. That's the reason I mentioned it. – WhozCraig Aug 16 '18 at 16:07
@user4581301, I see your point. It's not a micronag, it's a real nag. Corrected the answer. – Evg Aug 16 '18 at 16:53
Side note to those that follow: This makes Intelisense in MSVS2015 spit out a couple bogus errors. Ignore them. Can't speak for 2017. – user4581301 Aug 16 '18 at 16:59
In MSVS2017 it's fine. – Evg Aug 16 '18 at 17:12

struct object's pointer-member getting modified when passed to function

1 Answers1