Stack Using Linked List in C Loaded: 0.

42%

Linked lists provide an alternative to arrays for implementing a stack, dynamically allocating
memory. Despite using different data structures, time complexities for stack operations (push,
pop, peek) remain consistent. In linked list implementation, nodes are non-contiguously
maintained in memory, each with a pointer to its successor node in the stack. Stack overflow
occurs when insufficient memory heap space is available for node creation. In this approach, the
topmost node's address field contains null. Implementing a stack using singly linked lists
involves aligning standard linked list operations with stack operations, adhering to the Last In,
First Out (LIFO) principle. A top variable guides operations like Pop, Push, Peek, and Display.
The stack's top pointer, acting as the head of the stack, facilitates pushing and popping at the
list's head. Unlike arrays, linked lists offer flexibility as the stack can dynamically grow or shrink,
eliminating the risk of overflow imposed by array capacity restrictions. Dynamic allocation for
each new node mitigates overflow concerns in this linked list implementation.
Operations performed on Stack
Following operations can be performed on a stack:
● push(): It inserts an element to the top of the stack. It takes O(1) time, as each node is
inserted at the head/top of the linked list.
● pop(): It removes an element from the top of the stack. It takes O(1) time, as the top
always points to the newly inserted node.
● peek(): It returns the top element of the stack.
● size(): It returns the size of the stack, i.e., the total number of items in a stack.
● isEmpty(): Returns a boolean value. It returns true if the stack is empty. Else, it returns
false.
A stack is represented using nodes of a linked list. Each node consists of two parts: data and
next(storing the address of the next node). The data part of each node contains the assigned
value, and the next points to the node containing the next item in the stack. The top refers to the
topmost node in the stack. Both the push() and pop() operations are carried out at the front/top
of the linked list and hence take O(1) time.
A stack can also be implemented using arrays. But arrays are of limited size, and the size of the
stack has to be predetermined, whereas, in a linked list, implementation nodes can be added
according to the user's requirements.
Node Structure:
// Structure to create a node with data and the next pointer
struct Node {
int data;
struct Node *next;
};
Node* top = NULL;

How to push() elements in the stack using linked list in C

Adding or inserting a new element to a stack is known as the Push() operation in the stack.
Elements can only be pushed at the top of the stack.
Steps to push an element into a Stack:
● Create a new node using dynamic memory allocation and assign value to the node.
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 10;

● Check if stack is empty or not, i.e, (top == NULL).

● If it is empty, then set the next pointer of the node to NULL.
newNode->next = NULL;

● If it is not empty, the newly created node should be linked to the current top element of
the stack, i.e.,
newNode->next = top;

● Make sure that the top of the stack should always be pointing to the newly created node.
top = newNode;

Algorithm for push()

if the top is equal to NULL
newNode -> next = NULL
else
newNode -> next = top

Example of Push() Operation:

// Structure to create a node with data and the next pointer

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

Node* top = NULL;

int pop() {
if (top == NULL) {
printf("\nEMPTY STACK");
} else {
struct Node *temp = top;
int temp_data = top->data; //to store data of top node
top = top->next;
free(temp); //deleting the node
return temp_data;
}
}

How to pop() elements from the stack using linked list in

C
Removing or deleting an element from a stack is known as the Pop() operation in the stack.
Elements are popped from the top of the stack. There should be at least one element in the
stack to perform the pop() operation.
Steps to pop an element from a Stack:
● Check if stack is empty or not, i.e, (TOP == NULL).
● If it is empty, then print Stack Underflow.
print "Stack Underflow"

●If it is not empty, then create a temporary node and set it to top. Now, create another
variable and copy the data of top element to this variable.
struct Node *temp = top;
int temp_data = top->data;

● Now, make top point to the next node.

top = top->next;

● Delete the temporary node and return the value stored in temp_data.
free(temp);
return temp_data;

Algorithm for pop()

if top == NULL
print "Stack Underflow"
else
create temporary node, *temp = top
create temporary variable, temp_data = top->data
top = top->next
free(temp)

return temp_data

Example of Pop() Operation:

//Structure to create a node with data and the next pointer

struct Node {
int data;
struct Node *next;
}
 Node* top = NULL;

int pop() {
if (top == NULL) {
printf("\nEMPTY STACK");
} else {
struct Node *temp = top;
int temp_data = top->data; //to store data of top node
top = top->next;
free(temp); //deleting the node
return temp_data;
}
}

Program to implement Stack using Linked List in C

language
#include <stdio.h>
#include <stdlib.h>

// Structure to create a node with data and the next pointer

struct node {
int info;
struct node *ptr;
}*top,*top1,*temp;

int count = 0;
// Push() operation on a stack
void push(int data) {
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
printf("Node is Inserted\n\n");
}

int pop() {
top1 = top;

if (top1 == NULL)
{
printf("\nStack Underflow\n");
return -1;
}
else
top1 = top1->ptr;
int popped = top->info;
free(top);
top = top1;
count--;
return popped;
}

void display() {
// Display the elements of the stack
top1 = top;

if (top1 == NULL)
{
printf("\nStack Underflow\n");
return;
}

printf("The stack is \n");

while (top1 != NULL)
{
printf("%d--->", top1->info);
top1 = top1->ptr;
}
printf("NULL\n\n");

int main() {
int choice, value;
printf("\nImplementation of Stack using Linked List\n");
while (1) {
printf("\n1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("\nEnter your choice : ");
 scanf("%d", &choice);
switch (choice) {
case 1:
printf("\nEnter the value to insert: ");
scanf("%d", &value);
push(value);
break;
case 2:
printf("Popped element is :%d\n", pop());
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nWrong Choice\n");
}
}
}

Output:

Push Operation:
Implementation of Stack using Linked List
1. Push
2. Pop
3. Display
4. Exit

Enter your choice : 1

Enter the value to insert: 12

Node is Inserted

1. Push
2. Pop
3. Display
4. Exit

Enter your choice : 1

Enter the value to insert: 45

Node is Inserted

1. Push
2. Pop
3. Display
4. Exit

Enter your choice : 1

Enter the value to insert: 56

Node is Inserted

1. Push
2. Pop
3. Display
4. Exit

Enter your choice : 3

The stack is
56--->45--->12--->NULL

Pop Operation:
The stack is
56--->45--->12--->NULL

1. Push
2. Pop
3. Display
4. Exit

Enter your choice : 2

Popped element is :56
1. Push
2. Pop
3. Display
4. Exit

Enter your choice : 2

Popped element is :45
1. Push
2. Pop
3. Display
4. Exit

Enter your choice : 3

The stack is
12--->NULL

1. Push
2. Pop
3. Display
4. Exit

Enter your choice : 2

Popped element is :12
1. Push
2. Pop
3. Display
4. Exit

Conclusion
● Stack is a linear data structure that follows the Last in, First Out Principle (LIFO).
● Stack can be represented using nodes of a linked list.
● Stack supports operations such as push, pop, size, peek, and is Empty.
● Elements can be pushed or popped from one end only.
● Push and Pop operations take O(1) time.