Stack using Linked List in C

Stacks

Stack As a Linked List

On this page we will discuss about representation of Stack As a Linked List in C  . Generally, the implementation is LIFO i.e. Last in First out, also used for FILO, i.e. First in Last out

Representation of a Stack as a Linked List

First, we have to understand what a linked list is, to understand linked list representation of a stack. A Linked List is a Data Structure which consists of two parts:
  • The data/value part.
  • The pointer which gives the location of the next node in the list.
Stack can also be represented by using a linked list. We know that in the case of arrays we face a limitation , i.e , array is a data structure of limited size. Hence before using an array to represent a stack we will have to consider an enough amount of space to suffice the memory required by the stack.
Representation of Stack As Linked linked in C

However, a Linked List is a much more flexible data structure. Both the push and pop operations can be performed on either ends.. But We prefer performing the Push and pop operation at the beginning.

 The Stack operations occur in constant time. But if we perform the push and pop operations at the end of the linked list it takes time O(n).

But performing the operations at the beginning occurs in constant time. Let us understand this with the help of an example.

Let us consider a linked list as shown here.

In the given data we can see that we have-

  • Head = 200.
  • Top = 33.
Representation of Stack As Linked List in C 1

Push / Pop At the end Of a Linked List

Consider the Linked List as shown above. Now if we want to push/pop a node at the end, we have to traverse all the n number of nodes, until we reach the end of the linked list.

We traverse the whole list from the beginning to the end.

Representation of Stack As Linked List in C 2
  • Now if we want to insert a node at the end of the linked list, we traverse from the first node to the second node to the last node.
  • We find the end of the list where the node points to the null and the node to be inserted is as shown here.
Representation of Stack As Linked List in C 3
  • The new node is pushed at the end of the list.
  • The second last node , i.e, 08 now points to the location of the last node.
  • The newly inserted node at the end now points to null.
Representation of Stack As Linked List in C 4

Push / Pop operation at the beginning of the Linked List

Pushing a new node at the beginning of a linked list takes place in constant time. When inserting the new node the number of traversals that occur is equal to 1. So it  is much faster than the previous method of insertion

The time complexity of inserting a new node at the beginning of the linked list is O(1).

Let us consider the previous example only. We are given a Linked List as follows:

Representation of Stack As Linked List in C 5
  •  A new node to be inserted to the Linked List is shown here.
  • The new node 40 is to be inserted at the beginning of the list.
Representation of Stack As Linked List in C 6
  •  The new node is inserted at the beginning where we have just a single traversal after spotting the head of the Linked List.
  • The value of head changes from 200 to 100.
  • The pointer of the new node stores the address of the next node.
  • The final linked list is shown here.
Representation of Stack As Linked List in C 7

Implementation of a Stack using a Linked List

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

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

struct Node *head = NULL;

void push(int val)
{
    //create new node
    struct Node *newNode = malloc(sizeof(struct Node));
    newNode->data = val;

    //make the new node points to the head node
    newNode->next = head;

    //make the new node as head node
    //so that head will always point the last inserted data
    head = newNode;
}

void pop()
{
    //temp is used to free the head node
    struct Node *temp;

    if(head == NULL)
        printf("Stack is Empty\n");
    else
    {
        printf("Poped element = %d\n", head->data);

        //backup the head node
        temp = head;

        //make the head node points to the next node.
        //logically removing the node
        head = head->next;

        //free the poped element's memory
        free(temp);
    }
}

//print the linked list
void display()
{
    struct Node *temp = head;

    //iterate the entire linked list and print the data
    while(temp != NULL)
    {
         printf("%d->", temp->data);
         temp = temp->next;
    }
    printf("NULL\n");
}

int main()
{
    push(10);
    push(20);
    push(30);
    printf("Linked List\n");
    display();
    pop();
    printf("After the pop, the new linked list\n");
    display();
    pop();
    printf("After the pop, the new linked list\n");
    display();

    return 0;
}

Output:

Linked List
30->20->10->NULL
Poped element = 30
After the pop, the new linked list
20->10->NULL
Poped element = 20
After the pop, the new linked list
10->NULL

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java