Pointer address does not change in a link list

Question

My problem is q->next always prints the same address, but I assigned q = &x;. Why it is not printing different addresses?

#include <stdio.h>


class Node
{
public:
    int val;
    Node *next;
    Node(int v,Node *p) { val=v, next=p; }
};


int main()
{
    Node head(0, NULL);
    Node *q = &head;

    int i = 5;
    while (i>0)
    {
        Node x(i * 10, q);
        q = &x;
        printf("# %d %p\n", q->val, q->next);
        i--;
    }
}

Answer 1

This has to do with the way x is allocated: It is a local variable inside the main function. That means it is allocated on the stack, at a specific position. You are reusing the same piece of memory all the time. Instead, try allocating memory for new nodes (new).

Answer 2

Node x is being created on the stack, each time you go round your loop it will be getting created and then destroyed again at the end of the block. And each time round the loop it will be being created in the same location.

You probably want:

Node *x = new Node( i*10, q );
q = x;

Answer 3

In the first iteration of the loop, q contains the address of head. On each subsequent iteration, q contains the address of x.

This means that on the first iteration, q->next yields the address of head and on each subsequent iteration, q->next yields the address of x. However, x is created inside the loop, on the stack. Since there is no change to the stack inbetween, the x object always appears at the same place on the stack.

So I'd expect the program to print first the address of head and then four times the address of the four x objects (which all happen to be allocated at the same position of the stack).

Answer 4

You keep setting next to q:

Node x(i * 10, q);

Answer 5

Your x node is allocated on the local stack, not on the heap, so as your variable gets recycled on each loop iteration it recieves the same local address. To create i = 5 uique nodes you need to allocate object on heap using new() operator. You would also to add code to destoy your allocated objects afterwards.

example:


Node * px = new  Node(i*10, 1);

Answer 6

I think the reason is that, within the while loop, you declare x on the stack. Then after the end of the while loop has been reached, the variable gets "destroyed". In the subsequent iteration, however, x gets reserved on the stack again using the exact same (stack) memory place.

Note that you won't get a linked list with valid pointers. You need to create Node instances on the heap using 'new' operator.

EDIT:

If you don't want to allocate memory on the heap you can use the "Linked lists using arrays of nodes" approach descriped here. The drawback is, however, that you need to know the maximum number of nodes in advance.