Stack using Linked List in Python
Implementation of Stack using Linked List in Python
To implement a Stack using Linked List in Python, you can modify the linked list code from the previous response. In a stack, elements are added and removed from the top, following the Last-In-First-Out (LIFO) principle.
In this page, we will delve deep into the implementation of stacks using linked list in python, offering you a clear and detailed understanding of this topic.
Implementation of Stack using Linked List
Using a linked list for implementing a stack provides several advantages. Unlike arrays, linked lists allow for dynamic memory allocation, making it easier to manage the stack’s size. Additionally, linked lists are more flexible and efficient when it comes to inserting and deleting elements, which aligns with the nature of stack operations.
Implementing a Stack Using a Linked List in Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
self.size = 0
def push(self, data):
new_node = Node(data)
new_node.next = self.top
self.top = new_node
self.size += 1
def pop(self):
if self.is_empty():
return None
popped = self.top.data
self.top = self.top.next
self.size -= 1
return popped
Implementation of Stack using Linked List in Python;
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None # Initialize an empty stack
def is_empty(self):
return self.top is None # Check if the stack is empty
def push(self, data):
new_node = Node(data)
new_node.next = self.top
self.top = new_node # Push data onto the stack
def pop(self):
if self.is_empty():
return None # Return None if the stack is empty
popped_data = self.top.data
self.top = self.top.next # Pop the top element from the stack
return popped_data
def peek(self):
if self.is_empty():
return None # Return None if the stack is empty
return self.top.data # Return the top element without removing it
# Example usage:
if __name__ == "__main__":
my_stack = Stack()
my_stack.push(5)
my_stack.push(10)
my_stack.push(15)
print("Top of the stack:", my_stack.peek()) # Output: Top of the stack: 15
popped_item = my_stack.pop()
print("Popped item:", popped_item) # Output: Popped item: 15
print("Top of the stack after popping:", my_stack.peek()) # Output: Top of the stack after popping: 10
The key differences between implementing a stack using an array and using a linked list:
This table summarizes the main distinctions between using an array and a linked list for implementing a stack, highlighting factors such as dynamic sizing, memory allocation, time complexity, and more.
| Aspect | Stack Implementation with Array | Stack Implementation with Linked List |
|---|---|---|
| Dynamic Sizing | Fixed size, may require resizing | Dynamic sizing; grows or shrinks as needed |
| Memory Allocation | Contiguous block of memory | Non-contiguous, nodes scattered in memory |
| Insertion/Deletion | Push/pop operations have O(1) time complexity (amortized) | Push/pop operations have O(1) time complexity |
| Memory Overhead | Fixed size; may have unused space or lead to overflow | Each element has an associated node, leading to slightly higher memory overhead |
| Implementation Complexity | Simpler implementation | More complex due to node management |
Advantages of Using Linked Lists for Stacks
Using linked lists to implement a stack provides several advantages:
- Dynamic Size: Linked lists can grow or shrink dynamically, making them suitable for implementing a dynamic-sized stack.
- Efficient Operations: Push and pop operations have a time complexity of O(1) since they involve modifying only the top element.
- Ease of Implementation: Linked lists provide a straightforward way to manage stack operations without the need for fixed-size arrays.
Conclusion
In this page, we’ve explored the concept of stacks, learned about linked lists, and seen how to implement a stack using linked lists in Python. Stacks are versatile data structures with a wide range of applications in computer science. Mastering the art of implementing stacks will undoubtedly enhance your programming skills.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment