Implementation of Stack using Linked List — Data Structures & Algorithms

Introduction

A stack is a fundamental data structure that follows the Last In, First Out (LIFO) principle. Implementing a stack using a linked list is an efficient way to manage dynamic data structures. In this article, we’ll explore the creation and basic operations of a stack using a linked list.

Stack Structure using Linked List

A linked list is a collection of nodes where each node contains data and a reference (link) to the next node in the sequence. For our stack implementation, each node represents an element in the stack.

// Structure definition in C
struct Stack {
    int data;
    struct Stack* next;
};

// Global variable declaration in C
struct Stack* top = NULL;

// Class definition in C++
class Stack {
public:
    int data;
    Stack* next;
};

// Global variable declaration in C++
Stack* top = nullptr;

Representation of Stack using Linked List

Photo by Sean Stratton on Unsplash

Representation of stack using linked list

When implementing a stack using a linked list, you typically perform insertions and deletions at the front of the linked list. This is because the top of the stack corresponds to the front (head) of the linked list.

Display Stack Elements

The display function checks if the stack is empty. If not, it traverses the stack and prints each element.

// Function to display elements of stack
void display() {
    // Check if stack is empty
    if (top == NULL) {
        printf("Stack is empty.\n");
        return;
    }

printf("Elements in the stack: ");
    // Initialize a pointer to traverse stack
    struct Stack* current = top;    // Traverse stack and print each element
    while (current != NULL) {
        printf("\n%d", current->data);
        current = current->next;
    }
}

Time & Space Complexity

• Time Complexity: O(n) — Linear time complexity is incurred when displaying each element in the stack
• Space Complexity: O(1) — Only a constant amount of additional space is required for the traversal and printing operations

Push Operation

The push function creates a new node, checks for overflow, sets the data, links the new node to the current top, and updates the top to the new node.

// Function to push an element onto stack
void push(int x)
{
    // Create a new node
    struct Stack* temp = (struct Stack*)malloc(sizeof(struct Stack)); 
    
    // Check for overflow condition
    if(temp == NULL) {
        printf("Stack Overflow");
        return; // Exit function in case of overflow
    }

temp->data = x; // Set data of new node to input value 'x'
    temp->next = top; // Link new node to current top
    top = temp; // Update top to new node
}int main() {
    // Push elements onto stack
    push(1);
    push(2);
    push(3);    // Display elements of stack
    display();    return 0;
}

Upon executing the program, the output displays the elements in the stack. In the provided example, the stack contains the values 3, 2, and 1. The order of display reflects the Last In, First Out (LIFO) nature of the stack, where the most recently added element (3) is presented first, followed by 2 and then 1.

Elements in the stack: 
3
2
1

Time & Space Complexity

Time Complexity: O(1) — The push operation has a constant time complexity as it involves a fixed number of steps

Space Complexity: O(1) — The memory required for the new node is constant and does not depend on the size of the stack

Pop Operation

The pop operation removes the top element from the stack. It checks for underflow conditions, and if the stack is not empty, it updates the top to the next node and frees the memory of the removed node.

// Function to pop an element from stack
int pop()
{
    // Check for underflow condition
    if (top == NULL) {
        printf("Stack Underflow");
        return -1; // Return -1 indicating underflow
    }

struct Stack* temp = top; // Save current top
    int poppedValue = temp->data; // Save data
    top = top->next; // Move top to next node
    free(temp); // Free memory of removed node
    
    // Assuming data is an integer, you can return popped value
    return poppedValue;
}int main() {
    // Push elements onto the stack
    push(1);
    push(2);
    push(3);    // Display elements before popping
    printf("Elements before popping: ");
    display();    // Pop an element from stack
    printf("Popped element: %d\n", pop());    // Display elements after popping
    printf("Elements after popping: ");
    display();
    
    return 0;
}

The output of the above provided code reflects the state of the stack before and after popping an element.

Elements before popping: 
3
2
1
Popped element: 3
Elements after popping: 
2
1

Time & Space Complexity

• Time Complexity: O(1) — Constant time is required for the pop operation as it involves a fixed number of steps
• Space Complexity: O(1) — The memory released by freeing the removed node is constant

Peek Operation

The peek operation returns the data of the element at a specific position in the stack. It traverses the linked list until reaching the desired position or the end.

// Function to peek at element at a specific position in stack
int peek(int pos) {
    struct Stack *p = top;
    int i;

// Traverse linked list until reaching desired position or end
    for (i = 0; p != NULL && i < pos - 1; i++) {
        p = p->next;
    }    // Check if position is valid and return data of node at that position
    if (p != NULL) {
        return p->data;
    } else {
        return -1; // Return -1 indicating an invalid position or an empty stack
    }
}

Time & Space Complexity

• Time Complexity: O(n) — Linear time is required to traverse the linked list until the desired position
• Space Complexity: O(1) — Constant space is used for the traversal

Returns the Top of Stack

The stackTop function returns the data of the top element of the stack if it’s not empty.

// Function to return top element of stack
int stackTop() {
    if (top) {
        // Return data of top node if the stack is not empty
        return top->data;
    } else {
        // Return -1 indicating an empty stack
        return -1;
    }
}

Time & Space Complexity

• Time Complexity: O(1) — Constant time is needed to access the data of the top node
• Space Complexity: O(1) — No additional space is required

Check if Stack is Empty

The isEmpty function checks if the stack is empty.

// Function to check if stack is empty
int isEmpty() {
    // Return 1 if stack is empty, 0 otherwise
    return top ? 0 : 1;
}

Time & Space Complexity

• Time Complexity: O(1) — Constant time is needed to check if the top is NULL
• Space Complexity: O(1) — No additional space is required

Check if Stack is Full

The isFull function checks if the stack is full, although in a linked list implementation, the stack is not limited by a fixed size.

// Function to check if stack is full
int isFull() {
    struct Stack* temp = (struct Stack*)malloc(sizeof(struct Stack));

// Check if memory allocation for a new node is successful
    int result = temp ? 1 : 0;    // Free allocated memory to avoid memory leaks
    free(temp);    return result;
}

Time & Space Complexity

• Time Complexity: O(1) — Constant time is required for memory allocation and de-allocation
• Space Complexity: O(1) — Constant space is used for the temporary node

Conclusion

Implementing a stack using a linked list provides a flexible and efficient way to manage dynamic data structures. Each operation has its own time and space complexity, making it suitable for various applications where a Last In, First Out (LIFO) approach is beneficial. The linked list allows for dynamic resizing, making the stack adaptable to changing needs.