A Stack Implementation In C

Question

I've written a very simple linked list based stack implementation and was wondering if this is the standard way to do it in C.

typedef struct Node {
    int value;
    struct Node *prev;
} Node;


Node * push(Node *top, int value) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->value = value;
    node->prev = top;
    return node;
}

Node * pop(Node *top, int *val_addr) {
    *val_addr = top->value;
    Node *new_top = top->prev;
    free(top);
    return new_top;
}

int is_empty(Node *top) {
    return top == NULL;
}

Before deciding to post on code review I decided to check google for stack implementations to see if mine was okay. But most of the decent sources that I checked used an array implementation. I was wondering in what situation is it better to use a dynamic array based stack?

Answer 1

A dynamic array based stack will use less memory, as it does not have to store an address with each element. It will probably be faster for push because it doesn't need to make an allocation each time.

The main benefit of using a linked list is immutability. With a linked list, you can make stack operations that leave the previous stack as it is. However this is difficult without garbage collection.

Since you are not going for an immutable stack, I would recommend changing the signatures of you push() and pop() functions to something like this:

void push(Node **top, int value);
int pop(Node **top);

This way, you don't leave users of your utility with pointers to freed values, so they can't screw up their stack by popping and using the original stack, which is now invalid.

Answer 2

• Do not cast the result of malloc (start here for details). Which leads to the next point:

• Use necessary #includes. Since your code calls malloc, you need to #include <stdlib.h>.

• Avoid repeating type information: prefer

      Node * node = malloc(sizeof(*node));
  

  Spelling out type in both variable declaration and malloc invocation potentially leads to the double maintenance problem.

• Test for malloc failures.

• You may want to guard against popping from an empty stack. Consider

      assert(top != 0);