Stack using Linked List | Optimal Solution

Learning to implement a Stack using a Linked List is an essential step in mastering data structures. It’s not only a popular interview question but also a real-world use case in memory management and application call stacks. Here’s a clear, practical explanation with a ready-to-use code sample.

Here’s the [Problem Link] to begin with.

Problem Statement

You are tasked to build a stack data structure using a singly linked list. Your stack should support:

• push(data): Insert an integer onto the top of the stack.
• pop(): Remove and return the element from the top; return -1 if the stack is empty.

Example

Input:
push(2)
push(3)
pop()    # Output: 3
push(4)
pop()    # Output: 4

Stack Contents after each operation:
push(2)   → 2
push(3)   → 3(top), 2
pop()     → returns 3; top points to 2
push(4)   → 4(top), 2
pop()     → returns 4

Constraints:

• Stack is empty after initialization.
• You must use a linked list, no arrays or builtin stack objects.

Intuition & Approach

A stack is a LIFO (last-in, first-out) data structure. With a linked list, you can efficiently add and remove elements at the beginning of the list, making it perfect for stack operations.

• Push: Insert new elements at the start (head) of the list.
• Pop: Remove elements from the start (head).

A dedicated pointer (top) always references the current first node.
If top is None, the stack is empty.

Code Implementation

class Node:
    # Constructor to initialize a new node
    def __init__(self, data):
        self.data = data
        self.next = None    # next is the link to the next node

class MyStack:
    def __init__(self):
        # Stack top pointer (None means stack is empty)
        self.top = None

    # Push operation: insert data at the top of the stack
    def push(self, data):
        new_node = Node(data)      # create a new node
        new_node.next = self.top   # next of new node points to old top
        self.top = new_node        # move top to new node

    # Pop operation: remove and return data from top of stack
    def pop(self):
        if self.top is None:
            return -1              # stack is empty
        popped = self.top.data     # get top data
        self.top = self.top.next   # move top to next node
        return popped

Code Explanation

• Node: Basic singly linked list node with data and a pointer to the next node.
• MyStack:
  • On push, make a new Node, point its next to current top, and re-assign top.
  • On pop, if not empty, retrieve the value, move top pointer forward, return the popped value. If empty, return -1.

Time and Space Complexity

• push: O(1) – Only pointer manipulation.
• pop: O(1) – Only pointer manipulation.
• Space: O(n) – Where n is the number of elements, each node occupies space.

In simple words:
Each stack operation happens instantly, no loops or traversals.

Conclusion

Implementing a Stack using a Linked List is fundamental for building strong basics in data structures, an especially favorite topic in coding interviews! Once you grasp this, you’re better equipped to understand more complex structures and problems.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.