Stack Using Linked List in C

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:

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:

You can run and check your code here.