Stack Using Linked List
The major problem with the stack implemented using an array is, it works only for a fixed number of data
values. That means the amount of data must be specified at the beginning of the implementation itself.
Stack implemented using an array is not suitable, when we don't know the size of data which we are
going to use.
A stack data structure can be implemented by using a linked list data structure. The stack implemented
using linked list can work for an unlimited number of values. That means, stack implemented using
linked list works for the variable size of data. So, there is no need to fix the size at the beginning of the
implementation. The Stack implemented using linked list can organize as many data values as we want.
In linked list implementation of a stack, every new element is inserted as 'top' element. That means every
newly inserted element is pointed by 'top'. Whenever we want to remove an element from the stack,
simply remove the node which is pointed by 'top' by moving 'top' to its previous node in the list.
The next field of the first element must be always NULL.
Adding a node to the stack (Push operation)
Adding a node to the stack is referred to as push operation. Pushing an element to a stack in linked list
implementation is different from that of an array implementation. In order to push an element onto the
stack, the following steps are involved.
1. Create a node first and allocate memory to it.
2. If the list is empty then the item is to be pushed as the start node of the list. This includes
assigning value to the data part of the node and assign null to the address part of the node.
3. If there are some nodes in the list already, then we have to add the new element in the beginning
of the list (to not violate the property of the stack). For this purpose, assign the address of the
starting element to the address field of the new node and make the new node, the starting node of
the list.
Deleting a node from the stack (POP operation)
Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked
list implementation of stack is different from that in the array implementation. In order to pop an element
from the stack, we need to follow the following steps :
1. Check for the underflow condition: The underflow condition occurs when we try to pop from
an already empty stack. The stack will be empty if the head pointer of the list points to null.
2. Adjust the head pointer accordingly: In stack, the elements are popped only from one end,
therefore, the value stored in the head pointer must be deleted and the node must be freed. The
next node of the head node now becomes the head node.
Stack Operations using Linked List
To implement a stack using a linked list, we need to set the following things before implementing actual
operations.
Step 1 - Include all the header files which are used in the program. And declare all the user
defined functions.
Step 2 - Define a 'Node' structure with two members data and next.
Step 3 - Define a Node pointer 'top' and set it to NULL.
Step 4 - Implement the main method by displaying Menu with list of operations and make
suitable function calls in the main method.
push (value) - Inserting an element into the Stack
We can use the following steps to insert a new node into the stack...
Step 1 - Create a newNode with given value.
Step 2 - Check whether stack is Empty (top == NULL)
Step 3 - If it is Empty, then set newNode → next = NULL.
Step 4 - If it is Not Empty, then set newNode → next = top.
Step 5 - Finally, set top = newNode.
pop() - Deleting an Element from a Stack
We can use the following steps to delete a node from the stack...
Step 1 - Check whether stack is Empty (top == NULL).
Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and
terminate the function
Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
Step 4 - Then set 'top = top → next'.
Step 5 - Finally, delete 'temp'. (free(temp)).
display() - Displaying stack of elements
We can use the following steps to display the elements (nodes) of a stack...
Step 1 - Check whether stack is Empty (top == NULL).
Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize with top.
Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same
until temp reaches to the first node in the stack. (temp → next != NULL).
Step 5 - Finally! Display 'temp → data ---> NULL'.
Program on Stack using Linked List
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
}*top = NULL;
void push(int);
void pop();
void display();
void main()
{
int choice, value;
printf("\n:: Stack using Linked List ::\n");
while(1){
printf("\n****** MENU ******\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
push(value);
break;
case 2: pop();
break;
case 3: display();
break;
case 4:
exit(0);
default:
printf("\nWrong selection!!! Please try again!!!\n");
}
}
}
void push(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(top == NULL)
newNode->next = NULL;
else
newNode->next = top;
top = newNode;
printf("\nInsertion is Success!!!\n");
}
void pop()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else
{
struct Node *temp = top;
printf("\nDeleted element: %d", temp->data);
top = temp->next;
free(temp);
}
}
void display()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else{
struct Node *temp = top;
while(temp->next != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL",temp->data);
}
}
Queue Using Linked List
The major problem with the queue implemented using an array is, It will work for an only fixed number
of data values. That means, the amount of data must be specified at the beginning itself.
Queue using an array is not suitable when we don't know the size of data which we are going to use.
A queue data structure can be implemented using a linked list data structure. The queue which is
implemented using a linked list can work for an unlimited number of values. That means, queue using
linked list can work for the variable size of data (No need to fix the size at the beginning of the
implementation). The Queue implemented using linked list can organize as many data values as we want.
In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each
element of the queue points to its immediate next element in the memory.
In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer.
The front pointer contains the address of the starting element of the queue while the rear pointer contains
the address of the last element of the queue.
In linked list implementation of a queue, the last inserted node is always pointed by 'rear' and the first
node is always pointed by 'front'.
Insertion and deletions are performed at rear and front end respectively. If front and rear both are NULL,
it indicates that the queue is empty.
In above example, the last inserted node is 50 and it is pointed by 'rear' and the first inserted
node is 10 and it is pointed by 'front'. The order of elements inserted is 10, 15, 22 and 50.
Operations on Linked Queue
There are two basic operations which can be implemented on the linked queues. The operations are
Insertion(enqueue) and Deletion(dequeue).
Insert operation
The insert operation append the queue by adding an element to the end of the queue. The new element
will be the last element of the queue.
Firstly, allocate the memory for the new node ptr by using the following statement.
Ptr = (struct node *) malloc (sizeof(struct node));
There can be the two scenario of inserting this new node ptr into the linked queue.
In the first scenario, we insert element into an empty queue. In this case, the condition front =
NULL becomes true. Now, the new element will be added as the only element of the queue and the next
pointer of front and rear pointer both, will point to NULL.
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
In the second case, the queue contains more than one element. The condition front = NULL becomes
false. In this scenario, we need to update the end pointer rear so that the next pointer of rear will point to
the new node ptr. Since, this is a linked queue, hence we also need to make the rear pointer point to the
newly added node ptr. We also need to make the next pointer of rear point to NULL.
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
In this way, the element is inserted into the queue. The algorithm and the C implementation is given as
follows.
Algorithm
Step 1: Allocate the space for the new node PTR
Step 2: SET PTR -> DATA = VAL
Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
Step 4: END
C Function
void insert(struct node *ptr, int item; )
{
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
}
else
{
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
Deletion
Deletion operation removes the element that is first inserted among all the queue elements. Firstly, we
need to check either the list is empty or not. The condition front == NULL becomes true if the list is
empty, in this case , we simply write underflow on the console and make exit.
Otherwise, we will delete the element that is pointed by the pointer front. For this purpose, copy the node
pointed by the front pointer into the pointer ptr. Now, shift the front pointer, point to its next node and
free the node pointed by the node ptr. This is done by using the following statements.
ptr = front;
front = front -> next;
free(ptr);
Algorithm
Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
Step 2: SET PTR = FRONT
Step 3: SET FRONT = FRONT -> NEXT
Step 4: FREE PTR
Step 5: END
C Function
void delete (struct node *ptr)
{
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
Program on Queue using Linked List
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front;
struct node *rear;
void insert();
void delete();
void display();
void main ()
{
int choice;
while(choice != 4)
{
printf("\n*************************MainMenu*****************************\n");
printf("\n========================================================\n");
printf("\[Link] an element\[Link] an element\[Link] the queue\[Link]\n");
printf("\nEnter your choice ?");
scanf("%d",& choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
void insert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
void delete ()
{
struct node *ptr;
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
printf("deleted element=%d",ptr->data);
free(ptr);
}
}
void display()
{
struct node *ptr;
ptr = front;
if(front == NULL)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
while(ptr != NULL)
{
printf("\n%d\n",ptr -> data);
ptr = ptr -> next;
}
}
}