Stack Using Linked List

How to Implement Stack Using Linked List?.

How to Implement Stack Using Linked List?

Earlier, whenever we discussed stacks, we used arrays. While arrays have constant time complexity for each of the operations, today we’ll begin implementing stacks using a different data structure: linked lists.

Linked lists are not a new term for all of you. You have arrived here after discussing the basics. If you haven’t encountered linked lists, I highly recommend reviewing the relevant videos in the playlist. Assuming you are familiar with them, let's proceed.

Implementing Stacks Using Linked Lists:

Now, consider a singly linked list. Follow the illustration below.

Consider this linked list functioning as a stack. As you know, a linked list has two sides: one is the head, and the other points to NULL. Which side do you think should be considered as the top of the stack, from where we push and pop? After following along so far, you would say the head side.

And why the head side, that is side 1?

Because that’s the head node of the linked list, and insertion and deletion of a node at the head occur in constant time complexity, O(1). In contrast, inserting or deleting a node at the last position takes linear time complexity, O(n).

So, the stack equivalent of the above illustrated linked list looks something like this:

Let’s revise how used to define a struct Node in linked lists. had a struct, and two structure members, data and a struct Node pointer to store the address of the next node.

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

Code Snippet 1: Structure of a Node in a Linked List

When is our stack empty or full?

Stacks implemented with linked lists never get full; you can always add a node to it. There is no limit on the number of nodes a linked list can contain until you run out of space in heap memory. However, a stack becomes empty when there is no node in the linked list, hence when the top equals NULL.

Condition for stack full: When heap memory is exhausted
Condition for stack empty: top == NULL

One change to note before we proceed is that the head node we had in linked lists is now the top of our stack. So, from now on, the head node will be referred to as the top node.

Even though a stack implemented with a linked list has no upper limit to its size, you can always set a custom size for it.

These interpretations will help us implement the operations isEmpty and isFull. I encourage you to try to practice these operations on your own.

Implementing all the Stack Operations using Linked List (With Code in C)

In the last document, we started learning about implementing stacks using linked lists and the benefits of using the head side of the linked list as the stack top. We figured out the conditions for the stack linked lists to be empty or full. Today, we’ll discuss more operations and write their codes in C.

Before writing the codes, let’s discuss the algorithms we’ll implement for each operation:

1. isEmpty:

It checks if our top element is NULL.

2. isFull:

A stack is full only if no more nodes can be created using malloc, which happens when heap memory is exhausted.

3. Push:

Before pushing an element, create a new node. Check if the stack is not already full. Then, follow the same concept learned while inserting an element at the head or at index 0 in a linked list: set the address of the current top in the next member of the new node, and update the top element with this new node.

4. Pop:

The first step is to check if the stack is not already empty. If the stack is empty, you cannot pop any elements. Now, follow the same concept learned while deleting an element at the head or at index 0 in a linked list: simply update the top pointer to point to the next node, effectively skipping the current top node.

Understanding the Code Snippet Below:

Create the Structure for Nodes: Use struct in C, name it Node, and include two members:
- An integer variable to store the data.
- A struct Node pointer to store the address of the next element.
Implement the isEmpty and isFull Functions:
- isEmpty():
  - Create an integer function isEmpty, passing the pointer to the top node as a parameter.
  - If this top node equals NULL, return 1; otherwise, return 0.

int isEmpty(struct Node* top){
    if (top==NULL){
        return 1;
    }
    else{
        return 0;
    }
}

Code Snippet 1: Implementing isEmpty function

isFull():
- Create an integer function isFull, and pass the pointer to the top node as the parameter.
- Create a new struct Node* pointer p, and assign it a new memory location in the heap. If this newly created node p is NULL, return 1, else 0.

int isFull(struct Node* top){
    struct Node* p = (struct Node*)malloc(sizeof(struct Node));
    if(p==NULL){
        return 1;
    }
    else{
        return 0;
    }
}

Code Snippet 2: Implementing isFull function

Push():

Create a struct Node* function push, which will return the pointer to the new top node.
Pass the current top pointer and the data to push onto the stack into the function.
Check if the stack is already full; if so, return a condition indicating stack overflow.
Create a new struct Node* pointer n and assign it a new memory location in the heap.
Assign the current top to the next member of the n structure using n->next = top, and assign the given data to its data member.
Return this pointer n, since this is our new top node.

struct Node* push(struct Node* top, int x){
    if(isFull(top)){
        printf("Stack Overflow\n");
    }
    else{
        struct Node* n = (struct Node*) malloc(sizeof(struct Node));
        n->data = x;
        n->next = top;
        top = n;
        return top;
    }
}

Code Snippet 3: Implementing Push function

Pop() :

Create an integer function pop, which will return the element removed from the top.
Pass the reference of the current top pointer into the function. We are passing the reference this time because we are not returning the updated top from the function.
Check if the stack is not empty; if it is empty, return a condition indicating stack underflow.
Create a new struct Node* pointer n, and make it point to the current top. Store the data of this node in an integer variable x.
Assign top to the next member of the list by using top = top->next, because this is going to be our new top.
Free the pointer n and return x.

int pop(struct Node** top){
    if(isEmpty(*top)){
        printf("Stack Underflow\n");
    }
    else{
        struct Node* n = *top;
        *top = (*top)->next;
        int x = n->data;
        free(n);
        return x; 
    }
}

Code Snippet 4: Implementing pop function

Now, since would always need a traversal function to see if our operations are functioning all ll, ’ll just bring our codes from the linked list Docs, named linkedListTraversal.

void linkedListTraversal(struct Node *ptr)
{
    while (ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next; 
    }
}

Code Snippet 5: LinkedListTraversal function

Here is the whole source code:

#include<stdio.h>
#include<stdlib.h>
 
struct Node{
    int data;
    struct Node * next;
};
 
void linkedListTraversal(struct Node *ptr)
{
    while (ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next; 
    }
}
 
int isEmpty(struct Node* top){
    if (top==NULL){
        return 1;
    }
    else{
        return 0;
    }
}
 
int isFull(struct Node* top){
    struct Node* p = (struct Node*)malloc(sizeof(struct Node));
    if(p==NULL){
        return 1;
    }
    else{
        return 0;
    }
}
 
struct Node* push(struct Node* top, int x){
    if(isFull(top)){
        printf("Stack Overflow\n");
    }
    else{
        struct Node* n = (struct Node*) malloc(sizeof(struct Node));
        n->data = x;
        n->next = top;
        top = n;
        return top;
    }
}
 
int pop(struct Node** top){
    if(isEmpty(*top)){
        printf("Stack Underflow\n");
    }
    else{
        struct Node* n = *top;
        *top = (*top)->next;
        int x = n->data;
        free(n);
        return x; 
    }
}
 
int main(){
    struct Node* top = NULL;
    return 0;
}

Code Snippet 6: Implementing a stack and its operations using linked list

Have just created a stack using a linked list. have assigned NULL to the top node. Let’s first push some elements and see if the changes reflect in the stack. ’ll use traversal for that.

    top = push(top, 78);
    top = push(top, 7);
    top = push(top, 8);
    
    linkedListTraversal(top);

Code Snippet 7: Pushing elements in a stack.

The output received was:

Element: 8
Element: 7
Element: 78
PS D:\Code>

Figure 1: Output of the above program

So, the push function worked all good. Let’s pop one element out from the stack. And then again traverse through it.

    int element = pop(&top);
    printf("Popped element is %d\n", element);
    linkedListTraversal(top);

Code Snippet 8: Popping elements from a stack.

The output received then was:

Popped element is 8
Element: 7
Element: 78
PS D:\Code>

Figure 2: Output of the above program

You must have observed used the pointer to a pointer while popping elements from the stack. referenced and unreferenced twice. So, to avoid all these complexities, I still have a better way to implement that thing. can declare the top pointer globally. Earlier used to declare it under main. Declaring it globally gives its access to all our functions without passing them as a parameter.

Refer to the second implementation of stacks below. They are more or less the same, just subtle changes. Follow them carefully. You are wise enough to understand them on your own.

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

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

struct Node* top = NULL;

void linkedListTraversal(struct Node *ptr)
{
   while (ptr != NULL)
   {
       printf("Element: %d\n", ptr->data);
       ptr = ptr->next; 
   }
}

int isEmpty(struct Node* top){
   if (top==NULL){
       return 1;
   }
   else{
       return 0;
   }
}

int isFull(struct Node* top){
   struct Node* p = (struct Node*)malloc(sizeof(struct Node));
   if(p==NULL){
       return 1;
   }
   else{
       return 0;
   }
}

struct Node* push(struct Node* top, int x){
   if(isFull(top)){
       printf("Stack Overflow\n");
   }
   else{
       struct Node* n = (struct Node*) malloc(sizeof(struct Node));
       n->data = x;
       n->next = top;
       top = n;
       return top;
   }
}

int pop(struct Node* tp){
   if(isEmpty(tp)){
       printf("Stack Underflow\n");
   }
   else{
       struct Node* n = tp;
       top = (tp)->next;
       int x = n->data;
       free(n);
       return x; 
   }
}

int main(){
   top = push(top, 78);
   top = push(top, 7);
   top = push(top, 8);
   
   // linkedListTraversal(top);

   int element = pop(top); 
   printf("Popped element is %d\n", element);
   linkedListTraversal(top);
   return 0;
}

Code Snippet 8: Implementing a Stack and Its Operations Using Linked List

Done! That was all I had to do to make these operations function. Only a few more operations remain, which I will finish in the next Docs. I avoid repeating things to reduce redundancy in this course. If you found this Docs challenging or too fast, I believe you haven't gone through the previous videos. I covered linked lists very well. You must go through them if you haven't yet.

peek( ), stackTop( ) and Other Operations on Stack Using Linked List

We saw how efficiently we can push and pop elements in a stack-linked list. We discussed a few other operations: isEmpty, isFull, and traversal. Today, I will cover the remaining operations: peek, stackTop, etc.

Similar to what I did last time, I will first explain the algorithm behind the operations, followed by the coding section. Let’s see them individually, but before that, let’s have an example illustration of the stack.

peek: This operation is meant to return the element at a given position. Do mind that the position of an element is not the same as the index of an element. In fact, there is nothing as an index in a linked list. Refer to the illustration below.

Peeking in a stack linked list is not as efficient as when we worked with arrays. Peeking in a linked list takes O(n) because it first traverses to the position where you want to peek. So, you will just have to move to that node and return its data.

stackTop: This operation just returns the topmost value in the stack, which is simply the data member of the top pointer.
stackBottom:

I will leave the last operation, stackBottom, for your homework. Try implementing this on your own, and let me know if you could. You should be able to code this since we have covered the concepts already in the stack arrays.

So, these are the only operations I had in mind to discuss with you all. You will come across several variations of these. Nevertheless, you are intelligent enough to be able to change your codes if necessary.

I’ll now move to our editors to code the operations discussed today. I have attached the code snippet below. Refer to them while you code:

Understanding the Code Snippet Below:

Copy everything you did in the last document. This will save us some time and prevent repetitions in the course. Our main focus for today is to discuss these three operations. So, creating the stack and other operations can be ignored since they have already been covered.
I’ll start with the peek function.
peek():
- Create an integer function peek, and pass the position you want to peek in as a parameter.
- Since we have made the stack pointer global, you should not use that pointer to traverse; otherwise, you will lose the pointer to the top node. Rather, create a new struct Node pointer ptr and give it the value of top.
- Run a loop from 0 to pos - 1, since you are already at the first position.
- If your pointer reaches NULL at some point, you must have reached the last node, and the position asked was beyond the available positions, hence breaking the loop.
- If the current pointer found the position and it is not equal to NULL, return the data at that node; else return -1.

int peek(int pos){
    struct Node* ptr = top;
    for (int i = 0; (i < pos-1 && ptr!=NULL); i++)
    {
        ptr = ptr->next;
    }
    if(ptr!=NULL){
        return ptr->data;
    }
    else{
        return -1;
    }
}

Code Snippet 1: Implementing peek function

stackTop():
- Create an integer function stackTop, and are no longer passing any parameter since the top pointer is declared globally.
- Simply return the data member of the struct Node pointer top, and that’s it.

int stackTop(){
    return top->data;
}

Code Snippet 2: Implementing stackTop function

Here is the whole source code:

#include<stdio.h>
#include<stdlib.h>
 
struct Node{
    int data;
    struct Node * next;
};
 
struct Node* top = NULL;
 
void linkedListTraversal(struct Node *ptr)
{
    while (ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next; 
    }
}
 
int isEmpty(struct Node* top){
    if (top==NULL){
        return 1;
    }
    else{
        return 0;
    }
}
 
int isFull(struct Node* top){
    struct Node* p = (struct Node*)malloc(sizeof(struct Node));
    if(p==NULL){
        return 1;
    }
    else{
        return 0;
    }
}
 
struct Node* push(struct Node* top, int x){
    if(isFull(top)){
        printf("Stack Overflow\n");
    }
    else{
        struct Node* n = (struct Node*) malloc(sizeof(struct Node));
        n->data = x;
        n->next = top;
        top = n;
        return top;
    }
}
 
int pop(struct Node* tp){
    if(isEmpty(tp)){
        printf("Stack Underflow\n");
    }
    else{
        struct Node* n = tp;
        top = (tp)->next;
        int x = n->data;
        free(n);
        return x; 
    }
}
 
int peek(int pos){
    struct Node* ptr = top;
    for (int i = 0; (i < pos-1 && ptr!=NULL); i++)
    {
        ptr = ptr->next;
    }
    if(ptr!=NULL){
        return ptr->data;
    }
    else{
        return -1;
    }
}
 
int main(){
    top = push(top, 28);
    top = push(top, 18);
    top = push(top, 15);
    top = push(top, 7);
    
    linkedListTraversal(top);
    for (int i = 1; i <= 4; i++)
    {
        printf("Value at position %d is : %d\n", i, peek(i));
    }
    return 0;
}

Code Snippet 3: Using peek function

Let’s now push some elements into the stack and see if the operations work all good.

    top = push(top, 28);
    top = push(top, 18);
    top = push(top, 15);
    top = push(top, 7);

Code Snippet 4: Using push function to put some elements inside the stack

Since have pushed the elements, can call our peek function in a loop, printing the whole array.

    for (int i = 1; i <= 4; i++)
    {
        printf("Value at position %d is : %d\n", i, peek(i));
    }

Code Snippet 5: Using peek function to print the whole stack

The output received was:

Value at position 1 is : 7
Value at position 2 is : 15
Value at position 3 is : 18
Value at position 4 is : 28
PS D:\Code>

Figure 1: Output of the above program

Time Complexity of Operations

Applications of Stack

Stack Using Linked List

How to Implement Stack Using Linked List?

Implementing Stacks Using Linked Lists:

And why the head side, that is side 1?

Code Snippet 1: Structure of a Node in a Linked List

When is our stack empty or full?

Implementing all the Stack Operations using Linked List (With Code in C)

1. isEmpty:

2. isFull:

3. Push:

4. Pop:

Understanding the Code Snippet Below:

Code Snippet 1: Implementing isEmpty function

Code Snippet 2: Implementing isFull function

Code Snippet 3: Implementing Push function

Code Snippet 4: Implementing pop function

Code Snippet 5: LinkedListTraversal function

Code Snippet 6: Implementing a stack and its operations using linked list

Code Snippet 7: Pushing elements in a stack.

Code Snippet 8: Implementing a Stack and Its Operations Using Linked List

peek( ), stackTop( ) and Other Operations on Stack Using Linked List

Understanding the Code Snippet Below:

On this page