Stack Implemented As Linked List

Stack Implemented as Linked List

In my previous post, i presented you the C-code of a stack implemented as an array. Now the same stack can be implemented with the help of a linked list. The major advantage is that there is no stack FULL condition when implemented as a linked list as compared to implementation with array.

Below is the working C code of a STACK implemented with the help of linked list.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

// Stack implementation as a link list. #include<stdio.h> #include<stdlib.h> struct Node { int data; struct Node *next; }*top=NULL; void push(int query) { struct Node *node=(struct Node *) malloc(sizeof(struct Node)); // type casting in malloc is not required in C, even then just to make sure things run OK. node->data=query; node->next=top; top=node; } int pop() { int n=top->data; top=top->next; return n; } void display() { struct Node *temp=top; printf("Elements of the STACK, from the top are: "); for(;temp!=NULL;temp=temp->next) printf("%d ",temp->data); printf("\n"); } int main() { int choice,query; while(1) { printf("Enter the operation for the stack.\n"); printf("1. PUSH\n"); printf("2. POP\n"); printf("3. DISPLAY\n"); printf("4. EXIt\n"); scanf("%d",&choice); switch(choice) { case 1: printf("Enter the element to be pushed: \n"); scanf("%d",&query); push(query); printf("The node with data %d is pushed in the STACK. :)\n",query); break; case 2: if(top==NULL) { printf("Empty STACK. :(\n"); break; } printf("Element %d poped from the STACK. :)\n",pop()); break; case 3: if(top==NULL) { printf("Empty STACK. :(\n"); break; } display(); break; case 4: return 0; } } } // There is no stack full condition in implementation of a stack as a linked list.

Stacks as an Array

Stacks as an Array

First i am going to explain what is a 'stack', a stack is a Data structures with a predefined method of storing , retrieving and deleting the elements stored in it. 

Stacks follows Last In First Out(LIFO) mechanism, i.e., The element 'pushed' last into a stack will be the first one to be 'poped' out of the stack.
Push: The operation of inserting an element into the stack is familiarized as 'PUSH' in the world of stack.
Pop: The operation of removing an element from the stack is familiarized as 'POP'.

Below is a working C code for implementing stack as an array.
Stacks can also be implemented as linked list which i am going to discuss in my next post.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

// STACK implemented as an array. #include<stdio.h> #define MAX 10 int a[MAX],top=-1; void push(int n) { printf("The element %d is PUSHED into the stack. :)\n",(a[++top]=n)); } void pop() { printf("the element %d is POPED. :)\n",a[top--]); } void display() { int i; printf("The elements of stack are: "); for(i=0;i<=top;i++) printf("%d ",a[i]); printf("\n"); } int main() { int choice,n; while(1) { printf("Enter the operation to be done with STACK\n"); printf("1.PUSH\n"); printf("2.POP\n"); printf("3.DISPLAY\n"); printf("4.EXIT\n"); scanf("%d",&choice); switch(choice) { case 1: if(top==MAX-1) { printf("The stack is FULL. :(\n"); break; } printf("Enter the elemnt to be pushed\n"); scanf("%d",&n); push(n); break; case 2: if(top==-1) { printf("The stack is EMPTY. :(\n"); break; } pop(); break; case 3: if(top==-1) { printf("The stack is EMPTY. :(\n"); break; } display(); break; case 4: return 0; default: printf("Please enter a valid option.\n"); break; } } }

Selection Sort - Recursive approach

Selecting Sort - Recurcive

Just like Bubble sort, selection sort has also a time complexity of O(n²) . Selection sort scans through the list iteratively, selects one item and places that item at its correct position in the list.

The efficiency of the algorithm is compared in terms of number of comparisons.
In selection sort algorithm there is (n-1) comparisons in first loop, (n-2) comparisons in second loop and so on.
So, there is total of (n-1) + (n-2) + ..... + 2 + 1 comparisons. Thus, the total no. of comparisons are
n*(n-1)/2. Thus, leading to the time complexity of O(n²).

The code for the selection sort with recursive algorithm is as follows:

// SELECTION SORT using Recursion  
#include<stdio.h>
#define MAX 5
void selectionsort(int *,int *);
void display(int *,int *);
int main()
{
    int a[MAX],n,i;
    printf("Enter the no. of elements in the array,where MAX=%d: ",MAX);
    scanf("%d",&n);
    for(;n>MAX;scanf("%d",&n))
    printf("The value entered is greater than MAX.Please re-enter the value: ");
    printf("Enter the elements of the array: \n");
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    printf("The unsorted array: ");
    display(a,a+n);
    printf("\n");
    selectionsort(a,a+n);
    printf("The sorted array: ");
    display(a,a+n);
    return 0;
}

void selectionsort(int *p,int *q)
{
    if(p!=q)
    {
    int i,temp,min_index=0;
    for(i=1;p+i<q;i++)
    if(*(p+i)<*(p+min_index))
    min_index=i;
    temp=*(p+min_index);
    *(p+min_index)=*p;
    *p=temp;
    selectionsort(p+1,q);
    }
}

void display(int *p,int *q)
{
    for(;p<q;p++)
    printf("%d ",*p);
}

Selection Sort - Sorting Techniques

Selecting Sort

Just like Bubble sort, selection sort has also a time complexity of O(n²) . Selection sort scans through the list iteratively, selects one item and places that item at its correct position in the list.

The efficiency of the algorithm is compared in terms of number of comparisons.
In selection sort algorithm there is (n-1) comparisons in first loop, (n-2) comparisons in second loop and so on.
So, there is total of (n-1) + (n-2) + ..... + 2 + 1 comparisons. Thus, the total no. of comparisons are
n*(n-1)/2. Thus, leading to the time complexity of O(n²).

The code for the selection sort is as follows:

//SELCETIONSORT
#include<stdio.h>
#define MAX 5
void selectionsort(int *,int *);
void display(int *,int *);
int main()
{
    int a[MAX],n,i;
    printf("Enter the no. of elements in the array,where MAX=%d: ",MAX);
    scanf("%d",&n);
    for(;n>MAX;scanf("%d",&n))
    printf("The value entered is greater than MAX.Please re-enter the value: ");
    printf("Enter the elements of the array: \n");
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    printf("The unsorted array: ");
    display(a,a+n);
    printf("\n");
    selectionsort(a,a+n);
    printf("The sorted array: ");
    display(a,a+n);
    return 0;
}

void selectionsort(int *p,int *q)
{
    if(p!=q)
    {
    int i,j,temp,min_index;
    for(j=0;p+j<q-1;j++)
    {
        min_index=j;
        for(i=j+1;p+i<q;i++)
        if(*(p+i)<*(p+min_index))
        min_index=i;
        temp=*(p+min_index);
        *(p+min_index)=*(p+j);
        *(p+j)=temp;
    }
    }
}

void display(int *p,int *q)
{
    for(;p<q;p++)
    printf("%d ",*p);
}

Insertion Sort

Insertion Sort

The Code provided below is the C-code for bubble sorting technique of an array.

//Insertionsort

#include<stdio.h>

#define MAX 5

void insertionsort(int *,int *);

void display(int *,int *);

int main()

{

    int a[MAX],n,i;

    printf("Enter the no. of elements in the array,where MAX=%d: ",MAX);

    scanf("%d",&n);

    for(;n>MAX;scanf("%d",&n))

    printf("The value entered is greater than MAX.Please re-enter the value: ");

    printf("Enter the elements of the array: \n");

    for(i=0;i<n;i++)

    scanf("%d",&a[i]);

    printf("The unsorted array: ");

    display(a,a+n);

    printf("\n");

    insertionsort(a,a+n);

    printf("The sorted array: ");

    display(a,a+n);

    return 0;

}



void insertionsort(int *p,int *q)

{

    if(p!=q)

    {

        int i,j,temp;

        for(i=1;p+i<q;i++)

        {

            j=i-1;

            temp=*(p+i);

            for(;j>=0 && *(p+j)>temp;j--)

            *(p+j+1)=*(p+j);

            *(p+j+1)=temp;

        }

    }

}



void display(int *p,int *q)

{

    for(;p<q;p++)

    printf("%d ",*p);

}

Bubble Sort

Bubble Sort

The Code provided below is the C-code for bubble sorting technique of an array.
Bubble sort is considered as the most simplest of the sorting algorithms with a time complexity of O(n²) and is mostly used for sorting the arrays of limited elements.

The efficiency of the algorithm is compared in terms of number of comparisons.
In bubble sort algorithm there is (n-1) comparisons in first loop, (n-2) comparisons in second loop and so on.
So, there is total of (n-1) + (n-2) + ..... + 2 + 1 comparisons. Thus, the total no. of comparisons are
n*(n-1)/2. Thus, leading to the time complexity of O(n²).

//Bubblesort without recursion

#include<stdio.h>

#define MAX 5

void bubblesort(int *,int *);

void display(int *,int *);

int main()

{

    int a[MAX],n,i;

    printf("Enter the no. of elements in the array,where MAX=%d: ",MAX);

    scanf("%d",&n);

    for(;n>MAX;scanf("%d",&n))

    printf("The value entered is greater than MAX.Please re-enter the value: ");

    printf("Enter the elements of the array: \n");

    for(i=0;i<n;i++)

    scanf("%d",&a[i]);

    printf("The unsorted array: ");

    display(a,a+n);

    printf("\n");

    bubblesort(a,a+n);

    printf("The sorted array: ");

    display(a,a+n);

    return 0;

}



void bubblesort(int *p,int *q)

{

    if(p!=q)

    {

        int temp,j,i;

        for(i=0;p<q-i-1;i++)

        for(j=0;p<q-j-i-1;j++)

        if(*(p+j)>*(p+j+1))

        {

            temp=*(p+j+1);

            *(p+1+j)=*(p+j);

            *(p+j)=temp;

        }

    }

}



void display(int *p,int *q)

{

    for(;p<q;p++)

    printf("%d ",*p);

}

Bubble Sort - Recurrsion

Provided below is the Bubble Sorting C-Code based on a recursive algorithm instead of a iteration algorithm. It is the most basic and novice sorting algorithm.
The time complexity is O(n²).

The worst case time complexity is O(n2).

The average case time complexity is also O(n2).

The Bubble sort algo provided below has two functions other than main function namely, bubble sort - for sorting of the array and display - for the printing of the sorted array.

The code provided below uses recursive algorithm for the sorting purpose instead of itterative algorithm. 

//Bubblesort with recurrsion

#include<stdio.h>

#define MAX 10

void bubblesort(int *,int *);

void display(int *,int *);

int main()

{

    int a[MAX],n,i;

    printf("Enter the no. of elements in the array,where MAX=%d: ",MAX);

    scanf("%d",&n);

    for(;n>MAX;scanf("%d",&n))

    printf("The value entered is greater than MAX.Please re-enter the value: ");

    printf("Enter the elements of the array: \n");

    for(i=0;i<n;i++)

    scanf("%d",&a[i]);

    printf("The unsorted array: ");

    display(a,a+n);

    printf("\n");

    bubblesort(a,a+n);

    printf("The sorted array: ");

    display(a,a+n);

    return 0;

}



void bubblesort(int *p,int *q)

{

    if(p!=q)

    {

        int temp,i;

        for(i=0;p+i<q-1;i++)

        if(*(p+i)>*(p+i+1))

        {

            temp=*(p+i+1);

            *(p+1+i)=*(p+i);

            *(p+i)=temp;

        }

        bubblesort(p,q-1);

    }

}



void display(int *p,int *q)

{

    for(;p<q;p++)

    printf("%d ",*p);

}