Stacks using Linked Lists in C

Question

I tried to implement a stack using Linked Lists. How could I make it more efficient? Any other suggestions will be greatly appreciated. I am a beginner C programmer.

Any other tips to clean up my code?

#include <stdio.h>
#include <stdlib.h>
typedef struct NODE {
 int data;
 struct NODE* next;
}node;
node* top = NULL;
// Push Function
void push(int x)
{
 node *temp;
 temp = (node *) malloc(sizeof(node));
 temp -> data = x;
 temp -> next = top;
 top = temp;
}
// Pop function
int pop()
{
 node* temp;
 int num=0;
 temp = top;
 num = temp -> data;
 top = top -> next;
 free(temp);
 return num;
}
int Top()
{
 return top -> data;
}
void display(node *head)
{
 if(head == NULL) printf("NULL!\n");
 else
 {
 printf("%d\n", head -> data);
 display(head->next);
 }
}
int main() {
 int element,choice,val,tp;
 do
 {
 printf("---Stack Operations---\n");
 printf("1.PUSH\n");
 printf("2.POP\n");
 printf("3.DISPLAY\n");
 printf("4.Top element\n");
 printf("5.EXIT\n");
 printf("Enter an option\n");
 scanf("%d",&choice);
 switch(choice)
 {
 case 1:
 printf("Enter the element to push\n");
 scanf("%d",&val);
 push(val);
 break;
 case 2:
 element = pop();
 printf("Popped element is: %d\n",element);
 break;
 case 3:
 display(top);
 break;
 case 4:
 tp = Top();
 printf("Top element is:%d\n",tp);
 break;
 case 5:
 exit(0);
 default:
 printf("Enter a valid option\n");
 }
 }while(choice != 5);
}

Answer 1

Consider alternatives to linked lists

You are wondering whether this is the most efficient way to implement a stack. If you store ints, then the overhead of maintaining a linked list is quite large. Another option would be to keep the integer values in a dynamically allocated array. That way, the only other piece of information you need to store is the size of your stack. The drawback of an array is that if you grow the stack, you have to grow the memory for it, which can be expensive, but if you do this in a smart way the overhead will probably still be less than with linked lists.

You can also go for a hybrid approach: have struct NODE contain a fixed number of ints, say 8 or 16, and only allocate another struct NODE when the previous one is full.

Don't use all-capital names for types

All-capital identifiers are normally used for macros. It's always best to follow conventions. When defining a new struct, I recommend this pattern:

typedef struct foo {
 ...
} foo_t;

Avoid recursion if it is easy to do so

Your function display() cleverly uses recursion to display all the elements in the stack. However, without any optimizations enabled, if your stack is very large, this will actually cause a lot of real stack space to be used! With optimization enabled, the compiler will most likely perform a tail call optimization, but in this case you can easily rewrite the function as a loop:

void display(node *head)
{
 for(node *it = head; it; it = it->next)
 printf("%d\n", it->data);
}

Ensure a pointer is not NULL before dereferencing it

Your functions pop() and Top() blindly dereference the pointer top. If you would call these functions when the stack is empty, your program will crash.

Rename the variable top

This variable is effectively a private variable that you shouldn't access directly, only via the stack manipulation functions that you created (push(), pop() and Top()). Already there is the issue that it has the same name as the function Top(), and while C is case-sensitive, this solution is not pretty. Rename the function Top() to top(), so it matches the other functions, and rename the pointer top to something like stack_top or top_.

Answer 2

• Do not cast what malloc returns. If malloc is correctly prototyped (and you ensured that by #include <stdlib.h>) then casting is redundant. If it is not, casting could lead to a hard-to-find bugs.

• malloc can fail. Always test the return value for NULL.

• It is a good practice to always initialize the variables. Even better practice is to initialize it to a value you need:

   int num = temp->data;
  

  is cleaner than

   int num = 0;
   ....
   num = temp->data;
  

  In the latter case the reviewer wonders what is the significance of that 0, just to find out that there is no significance.

• Indent the case body:

   switch(choice)
   {
   case 1:
   printf("Enter the element to push\n");
   ....
   break;
  

  makes it clear where the case ends. IMHO it is OK to not indent the case line itself.

• By declaring the global top you limit yourself to no more than one stack. Consider going an extra mile: declare a

   typedef struct {
   node * top;
   } stack;
  

  and pass a stack * to your functions.

• There is an ongoing (削除) holy war (削除ここまで) debate on whether pop should return the node value, or not. Among the valid reasons against returning it are:

  • A client pays for the memory fetch (num = temp -> data) even if he does not need it.

  • There is no way to signal the client that pop was called on an empty list.

  I am not advocating either one. This is just to let you know.

• chux: Note: the concern about "no way to signal the client ... empty list." applies to int Top() too.

Answer 3

const

With functions that do not alter the value of objects pointed to, consider using const. It allows for some optimizations and conveys code's intent.

// void display(node *head)
void display(const node *head)

Allocate to the referenced object, not type

Review the following code. Is the right size allocated? Maybe. To be sure, one needs to review other code for the declaration of temp.

Note the cast serves no purpose in C here.

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

Now review this. Is the right size allocated? Yes, other code does not need to be consulted. This style of coding is easier right, review and maintain.

// vvvvv 
temp = malloc(sizeof *temp);