How do you make a stack using a linked list?

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).

Table of Contents Show

Stack using linked list
Linked list implementation of stack
Stack using Linked List

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.

Linked list implementation of stack

Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.

In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.

The top most node in the stack always contains null in its address field. Lets discuss the way in which, each operation is performed in linked list implementation of stack.

Stack using Linked List

Stack as we know is a Last In First Out(LIFO) data structure. It has the following operations :

push: push an element into the stack
pop: remove the last element added
top: returns the element at top of stack

C

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include <stdio.h>

#include <stdlib.h>

// A Linked List Node

struct Node

{

int data; // integer data

struct Node* next;// pointer to the next node

};

int nodesCount;

// Utility function to add an element `x` to the stack

void push(struct Node **top, int x)// insert at the beginning

{

// allocate a new node in a heap

struct Node* node = NULL;

node = (struct Node*)malloc(sizeof(struct Node));

// check if stack (heap) is full. Then inserting an element would

// lead to stack overflow

if (!node)

{

printf("Heap Overflow\n");

exit(-1);

}

printf("Inserting %d\n", x);

// set data in the allocated node

node->data = x;

// set the .next pointer of the new node to point to the current

// top node of the list

node->next = *top;

// update top pointer

*top = node;

// increase stack's size by 1

nodesCount += 1;

}

// Utility function to check if the stack is empty or not

int isEmpty(struct Node* top) {

return top == NULL;

}

// Utility function to return the top element of the stack

int peek(struct Node *top)

{

// check for an empty stack

if (!isEmpty(top)) {

return top->data;

}

else {

printf("The stack is empty\n");

exit(EXIT_FAILURE);

}

// Utility function to pop a top element from the stack

int pop(struct Node** top)// remove at the beginning

{

struct Node *node;

// check for stack underflow

if (*top == NULL)

{

printf("Stack Underflow\n");

exit(EXIT_FAILURE);

}

// take note of the top node's data

int x = peek(*top);

printf("Removing %d\n", x);

node = *top;

// update the top pointer to point to the next node

*top = (*top)->next;

// decrease stack's size by 1

nodesCount -= 1;

// free allocated memory

free(node);

return x;

}

// Utility function to return the nodesCount of the stack

int size() {

return nodesCount;

}

int main(void)

{

struct Node* top = NULL;

push(&top, 1);

push(&top, 2);

push(&top, 3);

printf("The top element is %d\n", peek(top));

pop(&top);

if (isEmpty(top)) {

printf("The stack is empty\n");

}

else {

printf("The stack is not empty\n");

}

return 0;

}

DownloadRun Code

Top List List

How do you make a stack using a linked list?

Stack using linked list

Stack using an array - drawback

Solution

Linked list implementation of stack

Stack using Linked List

C

Pos Terkait

Periklanan

BERITA TERKINI

Toplist Popular

Periklanan

Terpopuler

Token Data

Periklanan

Tentang Kami

Legal

Dukungan

Social