Stack structure pointing to itself - What's going on here?

Question

typedef struct _s {     // same definition as before   
    int         value;
    struct _s   *next;
}  STACKITEM;

STACKITEM    *stack = NULL;

 ....

void push_item(int newvalue)
{
    STACKITEM  *new = malloc( sizeof(STACKITEM) );  

    if(new == NULL) {     // check for insufficient memory   
        perror("push_item");
        exit(EXIT_FAILURE);
    }

    new->value   = newvalue;
    new->next    = stack;
    stack        = new;
}

What is the purpose of the two lines:

new->next    = stack;
stack        = new;

From what I can see, the next field of the new STACKITEM structure is set to point to stack. Stack is then set to point to the STACKITEM structure new? Is this correct?

If so, I do not understand what the point of this is. It seems like it is 'wrapping' the stack around and 'closing' it. In other words, when we attempt to access the next structure in the stack, since this is actually the last structure available, it can only access itself?

Thank you.

Answer 1

Keep focus on this:

• stack will always be (a) pointing to the dynamic node at the "top" of your stack, or (b) NULL if the stack is empty.
• When a newely allocated STACKSTRUCT node is to be pushed, in the end stack must point to that node, but first that newly allocated structure's next pointer must point to previous prior value of stack before the add (and change to stack).

My ascii art is terrible, so I'm not going to bother. Rather, I've prepared a simple example that uses your code, but adds a print_stack to dump the current state of the stack when each new node is added:

#include <stdio.h>
#include <stdlib.h>

typedef struct _s {     // same definition as before
    int         value;
    struct _s   *next;
}  STACKITEM;

STACKITEM    *stack = NULL;

void print_stack()
{
    STACKITEM const* item = stack;
    for (; item != NULL; item = item->next)
        printf("%p : { value=%d; next=%p }\n", item, item->value, item->next);
    fputc('\n', stdout);
}

void push_item(int newvalue)
{
    STACKITEM *new = malloc( sizeof(STACKITEM) );

    if(new == NULL) // check for insufficient memory
    {
        perror("push_item");
        exit(EXIT_FAILURE);
    }

    printf("push.1: stack = %p, new = %p\n", stack, new);
    new->value = newvalue;
    new->next = stack;
    stack = new;
    printf("push.2: stack = %p, new->next = %p\n", stack, new->next);
    print_stack();
}

int main()
{
    for (int i=1; i<=5; ++i)
        push_item(i);
}

_{Note: this knowingly leaks every node. memory management isn't the point of this; node management is.}

The output of this will vary from implementation and machine (lots of pointer values being printed). Follow the pointer values to see how this all wires together. Remember, this output shows the stack in top-down order (i.e. the first item in each printout is the "top" of the stack). Also note that each of these dumps starts with the node pointed to by stack after the push has been completed.

Sample Output

push.1: stack = 0x0, new = 0x1001054f0
push.2: stack = 0x1001054f0, new->next = 0x0
0x1001054f0 : { value=1; next=0x0 }

push.1: stack = 0x1001054f0, new = 0x100105500
push.2: stack = 0x100105500, new->next = 0x1001054f0
0x100105500 : { value=2; next=0x1001054f0 }
0x1001054f0 : { value=1; next=0x0 }

push.1: stack = 0x100105500, new = 0x100105510
push.2: stack = 0x100105510, new->next = 0x100105500
0x100105510 : { value=3; next=0x100105500 }
0x100105500 : { value=2; next=0x1001054f0 }
0x1001054f0 : { value=1; next=0x0 }

push.1: stack = 0x100105510, new = 0x100105520
push.2: stack = 0x100105520, new->next = 0x100105510
0x100105520 : { value=4; next=0x100105510 }
0x100105510 : { value=3; next=0x100105500 }
0x100105500 : { value=2; next=0x1001054f0 }
0x1001054f0 : { value=1; next=0x0 }

push.1: stack = 0x100105520, new = 0x100200000
push.2: stack = 0x100200000, new->next = 0x100105520
0x100200000 : { value=5; next=0x100105520 }
0x100105520 : { value=4; next=0x100105510 }
0x100105510 : { value=3; next=0x100105500 }
0x100105500 : { value=2; next=0x1001054f0 }
0x1001054f0 : { value=1; next=0x0 }

Notice how in each case, the new structure's next pointer is assigned the current value of stack, then the stack pointer is assigned the new structure's address. Once complete, the structure has been "pushed" onto the stack and the new stack top reflect this. Further, the next pointer of that structure now provides a pointer to the original stack top, thereby providing the linked-list chain needed for the data structure.

Answer 2

new->next    = stack;
stack        = new;

Above lines of code are very important to create link between two nodes. Here what happens is lets understand with an example.

Let's assume you are creating a link-list for values 1,2 and 3 only. So what will happen when you pass the first value as 1 is, value 1 will be stored at node1 new->value =1 and the next member of your node the pointer will be given value as new->next = stack;, which means the pointer is null for the first node right now and the global stack has the address of the first node.

Now you are entering the second value as 2 so now, first memory will be allocated for the new and then value 2 will be assigned as new->value =2 and the next pointer will contain the address of the first node as stack contains address of first node. And the stack is being assigned with the address of the second node. So now link between the first node and second node has been created.

For the third value 3 it goes same as above.

Basically this the add_at_begin method of single linklist. Here everytime stack is been assigned with the address of the current node and next time is being assigned to the next pointer which is creating the link.