Stack Using Linked List in C

Introduction

Stack is a linear data structure that follows the Last in, First out principle(LIFO). Stack supports various operations like push, pop, peek, empty, and size. It can be implemented using an array and linked list. The benefit of implementing a stack using a linked list in C over arrays is that it allows to grow of the stack as per the requirements, i.e., memory can be allocated dynamically.

What is Stack?

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, i.e., the item which is added at last is removed first. The best analogy for a stack is either a pile of coins or a pile of books kept one above the other. You can add or remove an item from the top only.

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:

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.

• 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.

• If it is not empty, the newly created node should be linked to the current top element of the stack, i.e.,

• Make sure that the top of the stack should always be pointing to the newly created node.

Algorithm for push()

Example of Push() Operation:

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.

• 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.

• Now, make top point to the next node.

• Delete the temporary node and return the value stored in temp_data.

Algorithm for pop()

Example of Pop() Operation:

Program to implement Stack using Linked List in C language

Output:

Push Operation:

Pop Operation:

FAQs

1. What is stack using a linked list in C?

Stack using a linked list means we are implementing stack using the linked list instead of using arrays. Through a linked list, we can allocate the memory dynamically.

2. How is the stack represented in the linked list?

A stack is represented using nodes of a linked list. Each node consists of two fields: data and next(storing address of next node). The data field of each node contains the assigned value, and the next points to the node containing the next item in the stack.

3. Is the linked list the same as the stack?

No. Linked list and stack are both linear data structures. The main difference is that Stack follows the LIFO(Last in, First out) principle, i.e., insertion and deletion can take place only at one end, whereas in a linked list, insertion and deletion can take place from any position.

4. What happens when we implement a stack using a linked list?

When implementing a stack using a linked list in C, the data is stored in the data part of the node, and the next part stores the address of the next node. The head of the linked list refers to the topmost node in the stack. Both the push() and pop() operations are carried out at the top of the linked list. The linked list gives us the advantage of increasing the size of the stack as much as required.