Stack using linked list

Stack using an array - drawback

If we implement the stack using an array, we need to specify the array size at the beginning(at compile time).

We can't change the size of an array at runtime. So, it will only work for a fixed number of elements.

Solution

We can implement the stack using the linked list.

In the linked list, we can change its size at runtime.

Let's implement the stack using linked list

If you are not familiar with linked list and stack, kindly visit the below links before we get started.

Linked List Basics
Inserting a node at the beginning of a linked list
Stack using array

Node structure for stack

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

To point the last inserted node

struct node *head = NULL;

head = NULL indicates the empty stack.

Push function

We should create the linked in reverse order. So that the head node will always point the last inserted data.

Using this method, we can access the last inserted element in constant time.

Like,

push(10) = head->10->NULL

push(20) = head->20->10->NULL

push(30) = head->30->20->10->NULL

Push function Algorithm

2. Create a new node with given data.

3. Make the new node points to the head node.

4. Now make the new node as the head node.

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;
}

Visual representation of the above algorithm

insert 10

insert 20

insert 30

If we create linked in normal order.

Like,

push(10) = head->10->NULL

push(20) = head->10->20->NULL

push(30) = head->10->20->30->NULL

We need to iterate the linked list to access the last inserted element.

Pop function

1.Check whether the head node is NULL

2.if head == NULL

The stack is empty. we can't pop the element.

3.Otherwise,

Move to head node to the next node. head = head->next;

Free the head node's memory

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);
    }
}

Implementation of stack using linked list

/*
 * Program  : stack using linked list
 * Language : c
 */

#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 printList()
{
    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");
    printList();
    pop();
    printf("After the pop, the new linked list\n");
    printList();
    pop();
    printf("After the pop, the new linked list\n");
    printList();

    return 0;
}