# 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.