Reviewing my implementation of a stack using linked list

Question

I have been studying data structures, and I'm new to this. Here is my code for the push and pop operations.

1. I considered using a node=top, so that I can avoid O(n) operations for the push (i.e. finding the last node every time).

2. I can't seem to find a better implementation for the pop operation.

Let me know if my code is good or bad. You can be harsh. I'll take it positively and learn from it.

typedef struct stack_ {
 int data;
 struct stack_ *next;
}stack;
stack *push(stack *head, stack **top, int val){
 //if stack is empty
 if(head == NULL){
 head = (stack *)malloc(sizeof(stack *));
 head -> data = val;
 head -> next = NULL;
 *top = head; //make current node the top of stack
 return head;
 }
 stack *newnode;
 newnode = (stack *)malloc(sizeof(stack *));
 (*top)->next = newnode; //append new node to what top points to
 newnode -> data = val;
 newnode -> next = NULL;
 *top = newnode; //make current node the top of stack
 return head;
}
stack *pop(stack *head, stack **top){
 if(head == NULL){
 printf("Stack is empty\n");
 return NULL;
 }
 stack *cur, *prev;
 cur = head;
 while(cur -> next){ //Traverse to the end
 prev = cur;
 cur = cur -> next;
 }
 prev -> next = NULL;
 *top = prev; //make this node the top of stack
 free(cur);
 return head;
}

Here's the main function:

int main ()
{
 stack *head, *top;
 head = top = NULL;
 while(1){
 int choice;
 printf("1.Push\n2.Pop\n3.Exit\n");
 scanf("%d", &choice);
 if(choice == 3)
 break;
 else if(choice == 2){
 head = pop(head, &top); 
 showstack(head); 
 }
 else if(choice == 1){
 int val;
 printf("Enter the value to be pushed\n");
 scanf("%d", &val);
 head = push(head, &top, val);
 showstack(head);
 }
 else
 printf("Enter the correct choice\n");
 }
 if(head)
 free(head);
 if(top)
 free(top);
 return 0;
}

• Jamal: The free() should go before the return, otherwise the former will not be called.
• Jamal: pop() should either be void or handle an empty stack differently. It shouldn't be returning NULL because NULL is not of type stack.
• UditMukherjee: Yeah right, my bad, I should free cur before i return.
• UditMukherjee: in main I have head = pop(head, top); so that way if I return NULL, head will be NULL thus marking that the list is empty.
• Jamal: Okay. For better context, you could include this code as well.

Answer 1

Your implementation suffers from the fact that the user of the stack is required to carry around several pieces of information around (head and top) which can make it easy to get wrong. Also your stack struct does not actually represent a stack in itself, just a node in the stack and one of them just happens to be the head.

For almost any data structure your need to keep meta data about it because it will usually make operations on the structure more efficient. Also you should have a single object which holds the information so you can pass it around easily. Last but not least you should think about the API of the data structure and what the user really cares about. In your case the user does not care about nodes or that it's a linked list. The user cares about that he/she can push values onto it and pop them of later.

Therefore I suggest the following design:

// holds an entry in the stack and point to the next element if there is any
typedef struct stacknode_
{
 int value;
 struct stacknode_* next;
} stacknode;
// the actual stack, holds the reference to the top and other meta information
// all operation will only require a reference to this
typedef struct stack_
{
 stacknode *top;
 int size;
} stack;

Next define your operations:

// create a new stack
stack *new_stack()
{
 stack *s = malloc(sizeof(stack));
 s->top = NULL;
 s->size = 0;
 return s;
}
// delete a stack and all its nodes
void delete_stack(stack *s)
{
 stacknode *ptr = s->top;
 while (ptr != NULL)
 {
 stacknode *next = ptr->next;
 free(ptr);
 ptr = next;
 }
 free(s);
}
// pushes a value onto the stack, 
// return 1 if element was pushed on successfully, 0 otherwise
int push(stack *s, int value)
{
 if (s == NULL) return 0;
 stacknode *n = malloc(sizeof(stacknode));
 if (n == NULL) return 0;
 n->value = value;
 n->next = s->top;
 s->top = n;
 s->size += 1;
 return 1;
}
// removes top element from stack, 
// return 1 if an element was removed and 0 otherwise
// return value is passed through value reference
int pop(stack *s, int *value)
{
 if (s == NULL || s->top == NULL) return 0;
 *value = s->top->value;
 stacknode *doomed = s->top;
 s->top = s->top->next;
 s->size -= 1;
 free(doomed);
 return 1;
}

This way the user doesn't have to care how you implement the stack, just that they need a stack object to pass around and use.

• UditMukherjee: Okay, thanks. Just what I needed. Although I've been meddling with the code and as pointed by dbarnes, if I'm inserting new nodes to the head of the list, then both the push and pop will be O(1) because the head will be the top of the list. But I find your design very efficient and real with context of stacks.
• William Morris: Nice answer. Remember to increment/decrement size though.
• ChrisWue: @WilliamMorris, good point, fixed

Answer 2

Some minor comments to add to what others have said.

• Adding an underscore to the end of struct stack is just noise. It achieves nothing, so leave it out.
• Omit the spaces around -> and add them after keywords (if, while etc)

• you are allocating only enough memory to hold a pointer to a stack node (stack*). Instead you should be allocating a node:

  head = malloc(sizeof(stack));
  

  or:

  head = malloc(sizeof *head);
  

  Note also that there is no cast (we are writing C, not C++)

---

The version suggested by @ChrisWue is elegant, but it does need two structures. You could achieve the same thing but with only a single struct (your existing stack) like this:

stack* push(stack *head, int data, int *result)
{
 stack *s = malloc(sizeof *s);
 if (s) {
 s->data = data;
 s->next = head;
 *result = 1;
 }
 else *result = 0;
 return s;
}
stack* pop(stack *head, int *data, int *result)
{
 if (!head) {
 *result = 0;
 return head;
 }
 *result = 1;
 stack *next = head->next;
 *data = head->data;
 free(head);
 return next;
}

But note that you must then be careful always to assign the return value to head in the caller:

 int data;
 int ok;
 stack *head = NULL;
 ...
 head = push(head, data, &ok);
 if (ok) {
 ...
 }
 head = pop(head, &data, &ok);
 if (ok) {
 ...
 }

• UditMukherjee: I must say, Beautiful code. Short and simple.
• UditMukherjee: And thank you, I wish if i could +1 you, but my reps are too low to do that :)

Answer 3

After looking at this, I'm not sure you should be freeing cur since you are freeing it before it is returned. You should always see NULL, then.

As for this static implementation, I'm not sure you're even doing this correctly. From the code, it looks like you're doing a queue. Why are you looping through the list? You should just be grabbing the first item, removing the pointer to next, then returning it.

Current List: A->B
Push(C) : C->A->B
POP : remove C List: A->B return C
// (c should no longer have a reference to A or any part of the list)

Stacks are supposed to be O(1). You should not be iterating through any list at all.

• UditMukherjee: As per my implementation, I am adding nodes at the end of the list, so it'l be 'current List: A -> B push(c): A -> B -> C' thus c is the top of the list, that's the reason I'm traversing the list till the end.
• UditMukherjee: On a second note, adding nodes to the head is a way better implementation. Thank you for pointing that out.

Answer 4

As dbarnes stated, a stack should be O(1) in terms of implementation. With this in mind you could consider increasing the memory foot print, and maintaining a pointer to the previous node at each node, or just a pointer to top-1.

In terms of maintainability it might be worth considering changing your push implementation to use an if/else block and have a single exit point.

Also, I would recommend always using {} for code blocks, such as ifs/loops etc. This will help prevent future accidents of code being in the wrong code blocks.

• Christopher J: I would also like to add, that if the user doesn't explicitly pop all the elements from the stack, they will never be free'd.
• UditMukherjee: Ah, thanks for pointing that out. So I guess a better implementation would be to use a function instead, which would traverse till the end and free the allocated space. void del_stack(stack *head){ stack *prev = NULL; while(head -> next){ prev = head; head = head -> next; free(prev); } free(head); }
• UditMukherjee: I'm sorry, I'm new to this, but I really don't know how to indent / format code in comments. That was supposed to be a code :D
• Christopher J: Yes that would be the safest bet, @ChrisWue has provided a good base for this. He takes it a step further by using a stack & stacknode, which is a cleaner solution and removes a lot of extra baggage.