Implementing a Stack Using a Linked List in Python: Top 5 Methods

Rate this post

πŸ’‘ Problem Formulation: A stack is a linear data structure that follows a particular order in which the operations are performed. The order is LIFO (Last In First Out). This article illustrates how to implement a stack using a linked list in Python, ensuring efficient O(1) time complexity for push and pop operations. We will start with an empty stack and show how elements can be pushed onto the stack and popped off, verifying the LIFO property.

Method 1: Basic Linked List Stack

This method uses the concept of node-based representation for linked list to implement stack operations. Each node contains data and a reference to the next node. The stack maintains a reference to the topmost node and ensures that push and pop operations update this reference accordingly.

Here’s an example:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.top is None:
            return None
        popped_node = self.top
        self.top = self.top.next
        return popped_node.data

# Example Usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())
print(stack.pop())

The output of this code snippet will be:

3
2

In the code example, we defined a Node class and a Stack class with push and pop methods, creating a basic linked list stack. We pushed three elements onto the stack and popped twice, demonstrating the LIFO behavior with the outputs being 3 and 2, the last and second-to-last elements pushed to the stack.

Method 2: Stack with Size Limit

This enhancement to the basic stack implementation includes a size limit, which allows the stack to avoid excessive growth and potential memory issues. The stack cannot exceed a predetermined number of elements, ensuring controlled usage of resources.

Here’s an example:

class Stack:
    def __init__(self, limit=10):
        self.top = None
        self.size = 0
        self.limit = limit

    def push(self, data):
        if self.size < self.limit:
            new_node = Node(data)
            new_node.next = self.top
            self.top = new_node
            self.size += 1
        else:
            print('Stack overflow!')

    def pop(self):
        if self.top is None:
            return None
        popped_node = self.top
        self.top = self.top.next
        self.size -= 1
        return popped_node.data

# Example Usage
stack = Stack(limit=2)
stack.push(1)
stack.push(2)
stack.push(3)  # This should display 'Stack overflow!'
print(stack.pop())

The output of this code snippet will be:

Stack overflow!
2

The same Node class is used from Method 1. The Stack class now includes a limit to restrict the number of elements, and a size attribute to keep track of the current number of elements. The third push call results in “Stack overflow!”, indicating that the stack limit has been reached, and the subsequent pop call returns 2.

Method 3: Stack with Peek Operation

This variation of the stack implementation includes an additional operation: peek. The peek method allows us to look at the top item without removing it from the stack, which can be particularly useful in certain algorithms and stack-based parsing techniques.

Here’s an example:

class Stack:
    # ... (previous code from Method 1)

    def peek(self):
        if self.top is None:
            return None
        return self.top.data

# Example Usage
stack = Stack()
stack.push('a')
stack.push('b')
stack.push('c')
print(stack.peek())
stack.pop()
print(stack.peek())

The output of this code snippet will be:

c
b

In this scenario, the Stack class is extended to include a peek method. After pushing three characters onto the stack, the peek method reveals ‘c’ at the top of the stack. After popping once, a second call to peek reveals ‘b’, showcasing the non-destructive nature of the peek operation.

Method 4: Stack with Support for Iterable

This version of the stack allows you to iterate over the stack elements without removing them. It implements the __iter__ and __next__ magic methods in the Stack class, providing compatibility with Python’s iterator protocol.

Here’s an example:

class Stack:
    # ... (previous code from Method 1)

    def __iter__(self):
        current = self.top
        while current:
            yield current.data
            current = current.next

# Example Usage
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
for item in stack:
    print(item)

The output of this code snippet will be:

30
20
10

By implementing the __iter__ and __next__ methods, our Stack class enables iteration where items are encountered in LIFO order. The example usage iterates over the stack, obtaining and printing each element on the stack without altering the stack’s state.

Bonus One-Liner Method 5: List-Based Stack

Though not utilizing a linked list, this one-liner stack method leverages Python’s built-in list and its methods to fulfill the same purpose as a stack with a linked list. It’s simple, quick to implement, and utilizes Python’s efficient list handling.

Here’s an example:

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop())
print(stack.pop())

The output of this code snippet will be:

3
2

This code snippet remains the simplest form of stack implementation in Python. The operations append and pop on a list mimic the behavior of push and pop operations of a stack. However, it uses Python’s dynamic array implementation under the hood instead of a linked list.

Summary/Discussion

  • Method 1: Basic Linked List Stack. Offers simplicity and true stack behavior with O(1) operations.
  • Method 2: Stack with Size Limit. Adds safeguards against overflows, but introduces complexity to handle limits.
  • Method 3: Stack with Peek Operation. Enhances functionality without impacting performance, providing additional utility.
  • Method 4: Stack with Support for Iterable. Allows for stack iteration while maintaining stack structure, though iteration can be seen as “non-standard” for stack usage.
  • Method 5: List-Based Stack. Quick and straightforward, leverages Python’s lists, but does not utilize linked list structures.