3
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$
  • 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);
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.