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.

Stack Representation Of Linked list

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:

  1. Data: The value of the stack element.
  2. 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
typedef struct Node {
int data;
struct Node* next;
} Node;

Node* top = NULL; // Top of the stack

// Function to check if the stack is empty
int isEmpty() {
return top == NULL;
}

// Function to push an element onto the stack
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);
}

// Function to pop an element from the stack
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;
}
}

// Function to peek the top element of the stack
int peek() {
if (isEmpty()) {
printf(“Stack is empty! Cannot peek\n”);
return -1;
} else {
return top->data;
}
}

// Function to count the total number of elements in the stack
int count() {
int count = 0;
Node* temp = top;
while (temp != NULL) {
count++;
temp = temp->next;
}
return count;
}

// Function to change an element at a specific position in the stack
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);
}
}

// Function to display all elements in the stack
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”);
}
}

int main() {
push(5);
push(10);
push(40);

printf(“Top element is %d\n”, peek());

printf(“%d popped from stack\n”, pop());
printf(“%d popped from stack\n”, pop());

change(0, 100); // Update the element at position 0
display(); // Display all elements in the stack

printf(“Number of elements in the stack: %d\n”, count());

if (isEmpty()) {
printf(“Stack is empty\n”);
}

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