CODEWITHSUNDEEP
c++
PalashV
PalashV

Reputation: 799

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

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.

Upvotes: 1

Views: 83

Answers (1)

Evg
Evg

Reputation: 26282

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.

Upvotes: 5

Related Questions