How do I correctly perform a pop function in a linked list?

Question

I ran GDB on my program and I think there is something wrong with my pop function but I'm not completely sure what's wrong with my logic in that function?

Everything seems to pushed onto the stack fine, but you can see the program fails when we start popping values from the stack.

I create a temporary ptr to the head of the linked list and then set the head of the link list to the next node and then free my temporary pointer.

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

#define SIZE 10
#define FALSE 0
#define TRUE  1

struct linkedStruct {
    int elem;
    struct linkedStruct *next;
};
 
typedef struct linkedStruct linked;
typedef linked *linkedPtr; 

void push(linkedPtr *hd, int val) {
    linkedPtr ptr = (linkedPtr)malloc(sizeof(linked));
    ptr->elem = val;
    ptr->next = *hd;
    *hd = ptr;
}

int isEmpty(linkedPtr hd) {
    if (hd == NULL)
        return TRUE;
    else
        return FALSE;
}
 
int top(linkedPtr hd) {
    return (hd->elem);
}

void pop(linkedPtr hd) {
    linkedPtr tmp = hd;
    hd = hd->next;
    free (tmp);
}

void show(linkedPtr hd) {
    while (hd != NULL) {
        printf("%d, ", hd->elem);
        hd = hd->next;
    }
    printf("\n");
}

int main(int argc, char **argv) {
    linkedPtr head = NULL;
    int i;
    int temp;

    /* push 10 random values onto the stack showing the stack growing */
    for (i = 0; i < SIZE; ++i) {
        temp = rand() % 100;
        printf("In main(): temp: %6d\n", temp);
        push(&head, temp);
        show(head);
   }

   printf("\n");

   /* remove the value from the stack */
   while (!isEmpty(head)) {
       printf("Top of stack value is: %d\n", top(head));
       pop(head);
   }
}

Output

In main(): temp:     83
83, 
In main(): temp:     86
86, 83, 
In main(): temp:     77
77, 86, 83, 
In main(): temp:     15
15, 77, 86, 83, 
In main(): temp:     93
93, 15, 77, 86, 83, 
In main(): temp:     35
35, 93, 15, 77, 86, 83, 
In main(): temp:     86
86, 35, 93, 15, 77, 86, 83, 
In main(): temp:     92
92, 86, 35, 93, 15, 77, 86, 83, 
In main(): temp:     49
49, 92, 86, 35, 93, 15, 77, 86, 83, 
In main(): temp:     21
21, 49, 92, 86, 35, 93, 15, 77, 86, 83, 

Top of stack value is: 21
Top of stack value is: 0
Top of stack value is: 17254288
Top of stack value is: 17254288
Top of stack value is: 17254288
Top of stack value is: 17254288
Top of stack value is: 17254288
Top of stack value is: 17254288
Top of stack value is: 0
double free or corruption (fasttop)

Answer 1

The pop function should take a pointer to a pointer to the head element and return the popped value:

int pop(linkedPtr *headp) {
    linkedPtr tmp = *headp;
    int elem = tmp->elem;
    *headp = tmp->next;
    free(tmp);
    return elem;
}

Hiding pointers behind typedefs as in typedef linked *linkedPtr; is confusing and error prone. It is much preferred to use the pointer syntax explicitly and handle the double pointers as linked **hd.

Here is a modified version:

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

#define SIZE 10
#define FALSE 0
#define TRUE  1

struct linkedStruct {
   int elem;
   struct linkedStruct *next;
};
 
typedef struct linkedStruct linked;

void push(linked **headp, int val) {
    linked *ptr = (linked *)malloc(sizeof(*ptr));
    ptr->elem = val;
    ptr->next = *headp;
    *headp = ptr;
}

int isEmpty(const linked *hd) {
    return (hd == NULL);
}
 
int top(const linked *hd) {
    return hd->elem;
}

int pop(linked **headp) {
    linked *tmp = *headp;
    int elem = tmp->elem;
    *headp = tmp->next;
    free(tmp);
    return elem;
}

void show(const linked *hd) {
    while (hd != NULL) {
        printf("%d, ", hd->elem);
        hd = hd->next;
    }
    printf("\n");
}

int main(int argc, char **argv) {
    linkedPtr head = NULL;
    int i;
    int temp;

    /* push 10 random values onto the stack showing the stack growing */
    for (i = 0; i < SIZE; ++i) {
        temp = rand() % 100;
        printf("In main(): temp: %6d\n", temp);
        push(&head, temp);
        show(head);
    }

    printf("\n");

    /* remove the value from the stack */
    while (!isEmpty(head)) {
        printf("Top of stack value is: %d\n", top(head));
        pop(&head);
    }
    return 0;
}

Answer 2

Your pop function doesn't provide any way to return the new value of head to the caller. So in your loop, the second time in the loop, head still points to the object you freed the first time in the loop.

Notice how instead of passing head, to push, you pass a pointer to head to the push function? That way, push can modify head. Do the same with pop.

void pop (linkedPtr hd)
{
 linkedPtr tmp = hd;
 hd = hd->next; // This line doesn't do anything
 free (tmp);
}

Notice how the marked line modifies hd, but hd is about to go out of scope when pop completes. Nothing is done with the new value of hd.