Stack Using Linked List in C

Stack is a linear data structure that follows the Last-In-First-Out

(LIFO) order of operations. This means the last element added to the
stack will be the first one to be removed.
Implementation of Stack using Linked List in
C
Stack is generally implemented using an array but the limitation of
this kind of stack is that the memory occupied by the array is fixed
no matter what are the numbers of elements in the stack. In the
stack implemented using linked list implementation, the size
occupied by the linked list will be equal to the number of elements
in the stack. Moreover, its size is dynamic. It means that the size is
goanna change automatically according to the elements present.

Representation of Linked Stack in C

In C, the stack that is implemented using a linked list can be
represented by the pointer to the head node of the linked list. Each
node in that linked list represents the element of the stack. The type
of linked list here is a singly linked list in which each node consists
of a data field and the next pointer.
struct Node {
type data;
Node* next;
}
The type of data can be defined according to the requirement.
Note: Even being the better method of stack implementation, the
linked list implementation only used when it is absolutely necessary
because we have to implement the linked list also as there are no
built in data structure for it in C Programming Language.
Basic Operations of Linked List Stack in C
Following are the basic operation of the stack data structure that
helps us to manipulate the data structure as needed:
Time Space
Operation Description Complexity Complexity

Returns true if the stack is empty,

O(1) O(1)
isEmpty false otherwise.

This operation is used to

O(1) O(1)
Push add/insert/push data into the stack.

This operation is used to

O(1) O(1)
Pop delete/remove/pop data into the stack.

This operation returns the top element

O(1) O(1)
Peek in the stack.

Let’s see how these operations are implemented in the stack.

Push Function
The push function will add a new element to the stack. As the pop
function require the time and space complexity to be O(1), we will
insert the new element in the beginning of the linked list. In multiple
push operations, the element at the head will be the element that is
most recently inserted.
We need to check for stack overflow (when we try to push into stack
when it is already full).
Algorithm for Push Function
Following is the algorithm for the push function:
 Create a new node with the given data.
 Insert the node before the head of the linked list.
 Update the head of the linked list to the new node.

Here, the stack overflow will only occur if there is some error
allocating the memory in the heap so the check will be done in the
creation of the new node.
Pop Function
The pop function will remove the topmost element from the stack.
As we know that for stack, we need to first remove the most
recently inserted element. In this implementation, the most recently
inserted element will be present at the head of the linked list.
We first need to check for the stack underflow (when we try to pop
stack when it is already empty).
Algorithm for Pop Function
Following is the algorithm for the pop function:
 Check if the stack is empty.
 If not empty, store the top node in a temporary variable.
 Update the head pointer to the next node.
 Free the temporary node.

Peek Function
The peek function will return the topmost element of the stack if the
stack is not empty. The topmost element means the element at the
head.
Algorithm for Peek Function
The following is the algorithm for peek function:
 Check if the stack is empty.
 If its empty, return -1.
 Else return the head->data.

IsEmpty Function
The isEmpty function will check if the stack is empty or not. This
function returns true if the stack is empty otherwise, it returns false.
Algorithm of isEmpty Function
The following is the algorithm for isEmpty function:
 Check if the top pointer of the stack is NULL.
 If NULL, return true, indicating the stack is empty.
 Otherwise return false indicating the stack is not empty.

C Program to Implement a Stack Using Linked

List
// C program to implement a stack using linked list
#include <stdio.h>
#include <stdlib.h>

// ________LINKED LIST UTILITY FUNCITON____________

// Define the structure for a node of the linked list

typedef struct Node {
int data;
struct Node* next;
} node;

// linked list utility function

node* createNode(int data)
{
// allocating memory
node* newNode = (node*)malloc(sizeof(node));

// if memory allocation is failed

if (newNode == NULL)
return NULL;

// putting data in the node

newNode->data = data;
 newNode->next = NULL;
return newNode;
}

// fuction to insert data before the head node

int insertBeforeHead(node** head, int data)
{
// creating new node
node* newNode = createNode(data);
// if malloc fail, return error code
if (!newNode)
return -1;

// if the linked list is empty

if (*head == NULL) {
*head = newNode;
return 0;
}

newNode->next = *head;
*head = newNode;
return 0;
}

// deleting head node

int deleteHead(node** head)
{
// no need to check for empty stack as it is already
// being checked in the caller function
node* temp = *head;
*head = (*head)->next;
free(temp);
return 0;
}

// _________STACK IMPLEMENTATION STARTS HERE_________

// Function to check if the stack is empty or not

int isEmpty(node** stack) { return *stack == NULL; }

// Function to push elements to the stack

void push(node** stack, int data)
{
// inserting the data at the beginning of the linked
// list stack
// if the insertion function returns the non - zero
// value, it is the case of stack overflow
if (insertBeforeHead(stack, data)) {
printf("Stack Overflow!\n");
}
}

// Function to pop an element from the stack

int pop(node** stack)
{
// checking underflow condition
 if (isEmpty(stack)) {
printf("Stack Underflow\n");
return -1;
}

// deleting the head.

deleteHead(stack);
}

// Function to return the topmost element of the stack

int peek(node** stack)
{
// check for empty stack
if (!isEmpty(stack))
return (*stack)->data;
else
return -1;
}

// Function to print the Stack

void printStack(node** stack)
{
node* temp = *stack;
while (temp != NULL) {
printf("%d-> ", temp->data);
temp = temp->next;
}
printf("\n");
}

// driver code
int main()
{
// Initialize a new stack top pointer
node* stack = NULL;

// Push elements into the stack

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);
push(&stack, 50);

// Print the stack

printf("Stack: ");
printStack(&stack);
// Pop elements from the stack
pop(&stack);
pop(&stack);
// Print the stack after deletion of elements
printf("\nStack: ");
printStack(&stack);

return 0;
}
Output
Stack: 50-> 40-> 30-> 20-> 10->
Stack: 30-> 20-> 10->

Benifits of Linked List Stack in C

The following are the major benifits of the linked list implementation
over the array implementation:
1. The dynamic memory management of linked list provide dynamic
size to the stack that changes with the change in the number of
elements.
2. Rarely reaches the condition of the stack overflow.

===========================================================================

Linked list implementation of stack

Instead of using array, we can also use linked list to implement stack. Linked list allocates
the memory dynamically. However, time complexity in both the scenario is same for all the
operations i.e. push, pop and peek.

In linked list implementation of stack, the nodes are maintained non-contiguously in the
memory. Each node contains a pointer to its immediate successor node in the stack. Stack
is said to be overflown if the space left in the memory heap is not enough to create a node.

The top most node in the stack always contains null in its address field. Lets discuss the
way in which, each operation is performed in linked list implementation of stack.

Adding a node to the stack (Push operation)

Adding a node to the stack is referred to as push operation. Pushing an element to a stack
in linked list implementation is different from that of an array implementation. In order to
push an element onto the stack, the following steps are involved.
1. Create a node first and allocate memory to it.
2. If the list is empty then the item is to be pushed as the start node of the list. This includes
assigning value to the data part of the node and assign null to the address part of the node.
3. If there are some nodes in the list already, then we have to add the new element in the
beginning of the list (to not violate the property of the stack). For this purpose, assign the
address of the starting element to the address field of the new node and make the new node,
the starting node of the list.

Time Complexity : o(1)

C implementation :
1. void push ()
2. {
3. int val;
4. struct node *ptr =(struct node*)malloc(sizeof(struct node));
5. if(ptr == NULL)
6. {
7. printf("not able to push the element");
8. }
9. else
10. {
11. printf("Enter the value");
12. scanf("%d",&val);
13. if(head==NULL)
14. {
15. ptr->val = val;
16. ptr -> next = NULL;
17. head=ptr;
18. }
19. else
20. {
21. ptr->val = val;
22. ptr->next = head;
23. head=ptr;
24.
25. }
 26. printf("Item pushed");
27.
28. }
29. }

Deleting a node from the stack (POP operation)

Deleting a node from the top of stack is referred to as pop operation. Deleting a
node from the linked list implementation of stack is different from that in the array
implementation. In order to pop an element from the stack, we need to follow the
following steps :

30. Check for the underflow condition: The underflow condition occurs when we try to
pop from an already empty stack. The stack will be empty if the head pointer of the
list points to null.
31. Adjust the head pointer accordingly: In stack, the elements are popped only from
one end, therefore, the value stored in the head pointer must be deleted and the
node must be freed. The next node of the head node now becomes the head node.

Time Complexity : o(n)

1. void pop()
2. {
3. int item;
4. struct node *ptr;
5. if (head == NULL)
6. {
7. printf("Underflow");
8. }
9. else
10. {
11. item = head->val;
12. ptr = head;
13. head = head->next;
14. free(ptr);
15. printf("Item popped");
16.
17. }
18. }

Display the nodes (Traversing)

Displaying all the nodes of a stack needs traversing all the nodes of the linked list
organized in the form of stack. For this purpose, we need to follow the following
steps.

19. Copy the head pointer into a temporary pointer.

20. Move the temporary pointer through all the nodes of the list and print the value field
attached to every node.

Time Complexity : o(n)

1. void display()
2. {
3. int i;
4. struct node *ptr;
5. ptr=head;
6. if(ptr == NULL)
7. {
8. printf("Stack is empty\n");
9. }
10. else
11. {
12. printf("Printing Stack elements \n");
13. while(ptr!=NULL)
14. {
15. printf("%d\n",ptr->val);
16. ptr = ptr->next;
17. }
18. }
19. }

Menu Driven program in C implementing all the stack operations

using linked list :
1. #include <stdio.h>
2. #include <stdlib.h>
3. void push();
4. void pop();
5. void display();
6. struct node
7. {
8. int val;
9. struct node *next;
10. };
11. struct node *head;
12.
13. void main ()
14. {
15. int choice=0;
16. printf("\n*********Stack operations using linked list*********\n");
17. printf("\n----------------------------------------------\n");
18. while(choice != 4)
19. {
20. printf("\n\nChose one from the below options...\n");
21. printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
22. printf("\n Enter your choice \n");
23. scanf("%d",&choice);
24. switch(choice)
25. {
26. case 1:
27. {
28. push();
29. break;
30. }
31. case 2:
32. {
33. pop();
34. break;
35. }
36. case 3:
37. {
38. display();
39. break;
40. }
41. case 4:
42. {
43. printf("Exiting....");
44. break;
45. }
46. default:
47. {
48. printf("Please Enter valid choice ");
49. }
50. };
51. }
52. }
53. void push ()
54. {
55. int val;
56. struct node *ptr = (struct node*)malloc(sizeof(struct node));
57. if(ptr == NULL)
58. {
59. printf("not able to push the element");
60. }
61. else
62. {
63. printf("Enter the value");
64. scanf("%d",&val);
65. if(head==NULL)
66. {
67. ptr->val = val;
68. ptr -> next = NULL;
69. head=ptr;
70. }
71. else
72. {
73. ptr->val = val;
74. ptr->next = head;
75. head=ptr;
76.
77. }
78. printf("Item pushed");
79.
80. }
81. }
82.
83. void pop()
84. {
85. int item;
86. struct node *ptr;
87. if (head == NULL)
88. {
89. printf("Underflow");
90. }
91. else
92. {
93. item = head->val;
94. ptr = head;
95. head = head->next;
96. free(ptr);
97. printf("Item popped");
98.
99. }
100. }
101. void display()
102. {
103. int i;
104. struct node *ptr;
105. ptr=head;
106. if(ptr == NULL)
107. {
108. printf("Stack is empty\n");
109. }
110. else
111. {
112. printf("Printing Stack elements \n");
113. while(ptr!=NULL)
114. {
115. printf("%d\n",ptr->val);
116. ptr = ptr->next;
117. }
118. }
119. }