Linked List Representation of Stack
A stack is a data structure that can be implemented using arrays or linked lists. This article focuses on the linked list representation of a stack, its advantages, implementation, and practical usage.
- Linked List: A linked list is a linear data structure where each element (called a node) contains data and a reference (or pointer) to the next node in the sequence. Linked lists are ideal for situations where the size of the data structure can vary, as they allow dynamic memory allocation.
- Stack: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means the last element added to the stack is the first one to be removed. Stacks can be implemented using linked lists or arrays and are commonly used in tasks such as expression evaluation, backtracking, and function call management.
Key Similarities Between Linked List and Stack
Here’s a summary of the key similarities between linked lists and stacks:
Aspect | Linked List | Stack |
---|---|---|
Element Structure | Each node in a linked list consists of two parts: data (stores the value) and a pointer (to the next node). | Each node in a stack implemented as a linked list contains data and a pointer to the next node. |
Next Element | You traverse the linked list starting from the head, moving through nodes using their “next” pointers. | The “next” pointer of a node in a stack is used to link it to the previous node (below it in the stack). |
Key Differences Between Linked List and Stack
Key Feature | Linked List | Stack |
---|---|---|
Access | Traverse the list to access elements sequentially. | Access only the top element (LIFO). |
Insertion/Removal | Insert or remove elements at any position. | Insert (push) and remove (pop) only at the top of the stack. |
Stack Representation Using Linked List
In the linked-list-based implementation, a stack is represented using nodes. Each node contains:
- Data: The value of the stack element.
- Next: A pointer to the next node in the stack.
The top of the stack refers to the last node that was added. This approach is ideal for applications where the size of the stack is not fixed in advance.
This implementation is efficient for dynamic stacks where the size is not fixed. The time and space complexities for stack operations remain constant as in the array implementation.
Key Advantages of Linked List Representation of Stack
When implemented using a linked list, the stack operations achieve similar efficiency as arrays:
Operation | Description | Time Complexity | Space Complexity |
---|---|---|---|
isEmpty | Checks if the stack is empty. Returns true if empty, false otherwise. | O(1) | O(1) |
Push | Adds an element to the top of the stack. | O(1) | O(1) |
Pop | Removes the top element from the stack. | O(1) | O(1) |
Peek | Returns the top element without removing it. | O(1) | O(1) |
Stack Operations Using Linked List
Here’s the C implementation of stack operations using a linked list:
1. Push Operation: Adding Elements to the Stack
This operation creates a new node and places it at the top of the stack. It ensures that the stack grows dynamically by allocating memory for the new node.
void push(int value) { Node* newNode = (Node*)malloc(sizeof(Node)); if (!newNode) { printf(“Heap overflow! Cannot push %d\n”, value); return; } newNode->data = value; newNode->next = top; top = newNode; printf(“%d pushed onto stack\n”, value); } |
2. Pop Operation: Removing Elements from the Stack
This operation removes the topmost element from the stack and frees its memory. It returns the value of the removed element.
int pop() { if (isEmpty()) { printf(“Stack is empty! Cannot pop\n”); return -1; } else { int poppedValue = top->data; Node* temp = top; top = top->next; free(temp); return poppedValue; } } |
3. Peek Operation: Viewing the Top Element
This operation allows you to view the value of the topmost element in the stack without removing it, providing quick access to the stack’s top.
int peek() { if (isEmpty()) { printf(“Stack is empty! Cannot peek\n”); return -1; } else { return top->data; } } |
4. Size and Count Operations
Tracking the size of a dynamic stack is not necessary as the linked list grows/shrinks. However, you can count the elements by traversing the stack.
int count() { int count = 0; Node* temp = top; while (temp != NULL) { count++; temp = temp->next; } return count; } |
5. Change Operation: Modifying an Element in the Stack
Modifies a specific element in the stack by position.
void change(int position, int value) { Node* temp = top; int index = 0; while (temp != NULL && index < position) { temp = temp->next; index++; } if (temp == NULL) { printf(“Invalid position!\n”); } else { temp->data = value; printf(“Element at position %d updated to %d\n”, position, value); } } |
6. Display Operation: Showing All Stack Elements
Traverses the stack and prints all the elements.
void display() { if (isEmpty()) { printf(“Stack is empty!\n”); } else { Node* temp = top; printf(“Stack elements: “); while (temp != NULL) { printf(“%d “, temp->data); temp = temp->next; } printf(“\n”); } } |
Complete C Program: Linked List Representation of Stack
#include <stdio.h> #include <stdlib.h> // Node structure Node* top = NULL; // Top of the stack // Function to check if the stack is empty // Function to push an element onto the stack // Function to pop an element from the stack // Function to peek the top element of the stack // Function to count the total number of elements in the stack // Function to change an element at a specific position in the stack // Function to display all elements in the stack int main() { printf(“Top element is %d\n”, peek()); printf(“%d popped from stack\n”, pop()); change(0, 100); // Update the element at position 0 printf(“Number of elements in the stack: %d\n”, count()); if (isEmpty()) { return 0; |
Example Output
5 pushed onto stack
10 pushed onto stack
40 pushed onto stack
Top element is 40
40 popped from stack
10 popped from stack
Element at position 0 updated to 100
Stack elements: 100
Number of elements in the stack: 1
Stack is empty