Stack using Linked List in C
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
- The data/value part.
- The pointer which gives the location of the next node in the list.
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.
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.
- 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.
- 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.
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:
- 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.
- 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.
Implementation of a Stack using a Linked List
#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
Stacks
- Introduction to Stack in Data Structure
- Operations on a Stack
- Stack: Infix, Prefix and Postfix conversions
- 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)
- Queues Program in C and implementation
- Implementation of Queues using Arrays | C Program
- Types of Queues in Data Structure
- Application of Queue Data Structure
- 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
- Circular queue in Data Structure
- Applications of Circular Queues
- Circular queue in – C | C++ | Java
- Circular queue using Array – C | C++ | Java
- Circular Queue using Linked Lists – C | C++ | Java
Priority Queue
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
- Circular queue in Data Structure
Click Here - Applications of Circular Queues
Click Here - Circular queue in –
C | C++ | Java - Circular queue using Array –
C | C++ | Java - Circular Queue using Linked Lists –
C | C++ | Java
Login/Signup to comment