Stack Implementation using Linked List

Back to: Data Structures and Algorithms Tutorials

Stack Implementation using Linked List:

In this article, we will discuss Stack Implementation using Linked List. Please read our previous article discussing How to Perform Operations on a Stack using an Array in C Language with Examples.

Stack Implementation using Linked List

We have already studied linked lists in our previous articles. As you know, a linked list is a collection of nodes that hold a list or collection of elements. A stack is also a collection of elements. In a stack, insertion and deletion are done using the LIFO (Last In, First Out) discipline. Let us show you how the stack can be implemented using a linked list.

Here, we have the basic structure of a linked list.

This is the node structure of linked lists.

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

This is the structure defined in C language. So, first of all, let us discuss how we should insert and delete the elements. In a stack, elements are inserted and deleted from the same end. Now, a linked list has two ends, i.e., the right and left ends. If we select the left side for inserting and deleting the elements, then how much time does it take to insert and delete them on this side? It’s constant, O(1). If we want to select the right side, then from the first node, we have to traverse through the linked list, and only then can we insert or delete the element.

So, the time taken here is O(n) for insertion and deletion. Now, you can decide which side you should select for insertion & deletion. Definitely, the right side because it takes constant time to perform insertion and deletion operations on the linked list. When we create a linked list, at that time, we were adding a new node at the end, but here, we will add a new node on the front side or left side. Now, let us fill in a few elements in the linked list.

Push an element into the Stack using a Linked List:

Let us assume that 20 is the first element we have inserted in the stack,

Now, we want to insert 4.

Here, a new node is inserted for the value 4. Let’s insert 5.

Here again, a new node is created, and value 5 is inserted. Now, let’s insert 7.

“7 is the latest value that is inserted into this stack. In this way, we can insert more values into the linked list. So, the First pointer of the linked list will now be referred to as ‘Top’.”

The top is a pointer that points to the first node of the linked list. So, a new element will always be inserted from the top, which is on the left-hand side. Now, there are 4 elements in this stack. Which is the topmost element in the stack? The element where the top pointer is pointing, i.e., 7. It’s the first element in the stack and the most recently inserted element. Now, let us show you how we can push a new element onto the stack.

Step 1: First, we have to create a new node with the help of a temporary pointer.

Step 2: Insert the value and make this node point on the top node.

Step 3: The Top pointer should be updated to point to this new node.

This is the method of inserting, and we are familiar with it. Since it inserts at index 0, how much time does it take? Constant time.

Pop the Element from the Stack using the Linked List:

Following are the steps to delete a value from the above stack or linked list.

Step 1: We need to point the pointer to the first node.

Step 2: Move the top pointer to the next node of t.

Step 3: Delete the node pointed to by t.

In this way, we can delete the element that is present at index 0. So, how much time does it take? Constant time.

So, we have shown you how to push an element and how to pop an element, which is to delete an element, inside the stack using linked lists. Now, let us look at some conditions. Two important conditions are there.

First condition: When the stack is empty, the top pointer will be null because there are no elements in the stack. So, if the top is null, then the stack is empty. We can express this condition as: If (Top == NULL)

Second Condition: When the stack is full. We know that the size of an array is fixed, but we can expand a linked list as many times as we want. We can insert as many elements as we want. Then when will the stack be full? If you are unable to create any new node, meaning the heap is full, then the stack will be full. So, if you are trying to create a new node and it is not getting created, then the stack is full. We can express this condition as:

Node *t = new Node;
if (t == NULL)

Here, first, we tried to create a node t. If it is not created, it will be null, which means the stack is full. So, that’s all about implementing a stack using a linked list. 

In the next article, I will discuss how to Perform Operations on Stack using a Linked List in C. In this article, I explain Stack Implementation using Linked Lists in C Language. I hope you enjoy this Stack Implementation using a Linked List article.