Creating a push() method for a singly linked list with two parameters

Question

I need to create the push method for a program that push an element into a stack. I have created this typedef:

typedef struct node{
    int value;
    struct node *next;
} Node;

With this snippet of code in my main:

Node *stackptr;
stackptr = NULL;

This is where I have a problem and am not sure exactly what is going on - In my push method im not sure if I am returning the updated pointer to the top of the stack. Im suppose to check if it is empty as well but I am going to get to that last. Here is the push() function:

void push(Node *stkptr, int i){
   Node *temp;
   temp = malloc(sizeof(Node));
   temp->value = i;
   temp->next = *stkptr;
   return *stkptr = temp;
}

Hope this makes some sort of sense what I am trying to get across. Thanks for any advice you are able to give me. Hope all is well.

Last I am in need of fixing my int pop() function! I have to return the value of the node that was popped. I believe I am almost there - my compiler is still throwing errors. This is what I have so far:

int pop(Node** stkptr){
Node *temp;
temp = malloc(sizeof(Node));

if((*stkptr) == NULL){
    fprintf(stderr, "The stack is empty. Pop is not allowed\n");
    return 0;
}
else{
    temp = *stkptr;
    stkptr = *temp;
}
return stkptr;
free(temp);
}

However, the compiler is throwing the error: incompatible types when assigning to type ‘struct Node **’ from type ‘Node’

warning: return makes integer from pointer without a cast

Can someone please help me fix my problem! Thanks!

Answer 1

There must be a lot of duplicates for this (for example, Implementing stack with linked list in C from the related questions section), but basically, you need to pass a pointer to a pointer into the function:

void push(Node **stkptr, int i)
{
    Node *temp;
    temp = malloc(sizeof(Node));
    temp->value = i;
    temp->next = *stkptr;
    *stkptr = temp;
}

You also can't return a value from a function that returns void. You should also check that the memory allocation worked.

You'd call this from, for example, your main program:

Node *stack = NULL;
int i;

while (get_an_integer(&i) != EOF)
    push(&stack, i);

where get_an_integer() is a hypothetical function that reads an integer from somewhere and assigns it to i, while returning a status (0 — got an integer; EOF — didn't get an integer).

An alternative design returns the new head of the stack from the function:

Node *push(Node *stkptr, int i)
{
    Node *node;
    node = malloc(sizeof(Node));
    node->value = i;
    node->next = stkptr;
    return node;
}

with calling sequence:

Node *stack = NULL;
int i;

while (get_an_integer(&i) != EOF)
    stack = push(stack, i);

A question about pop()

The pop() function appears to remove and destroy the first item on the stack, rather than returning it. However, there are a number of flaws in it, such as it allocates space, then overwrites the pointer with information from the stack, then returns before freeing the data. So, assuming that the demolition job is required, the code should be:

int pop(Node **stkptr)
{
    assert(stkptr != 0);
    Node *temp = *stkptr;

    if (temp == NULL)
    {
        fprintf(stderr, "The stack is empty. Pop is not allowed\n");
        return 0;
    }
    else
    {
        *stkptr = temp->next;
        free(temp);  // Or call the function to deallocate a Node
        return 1;
    }
}

This now returns 1 when successful and 0 when the stack was empty. Alternatively, if you wanted the value from the top of the stack returned rather than freed, then:

Node *pop(Node **stkptr)
{
    assert(stkptr != 0);
    Node *temp = *stkptr;

    if (temp == NULL)
    {
        fprintf(stderr, "The stack is empty. Pop is not allowed\n");
        return 0;
    }
    else
    {
        *stkptr = temp->next;
         return temp;
    }
}

Or, since you are told by the return value whether there was anything to pop, and printing in a library function can be objectionable, maybe even:

Node *pop(Node **stkptr)
{
    assert(stkptr != 0);
    Node *temp = *stkptr;

    if (temp != NULL)
        *stkptr = temp->next;
    return temp;
}

---

^{Warning: none of the code has been submitted to a compiler for verification.}