Stack Using Linked List vs Array Stack Trade-offs in DSA Python - Build Both Approaches

Stack Using Linked List vs Array Stack Trade-offs

📖 Scenario: Imagine you are building a simple undo feature for a text editor. You want to store the actions in a stack. You can use either a linked list or an array to build this stack. This project will help you understand how to create a stack using a linked list and then compare it with an array-based stack.

🎯 Goal: You will build a stack using a linked list, then add a limit to the stack size, and finally print the stack contents. This will help you see the trade-offs between linked list and array stack implementations.

📋 What You'll Learn

Create a linked list node class called Node with value and next attributes

Create a stack class called LinkedListStack with push, pop, and print_stack methods

Add a maximum size limit to the stack using a variable called max_size

Print the stack contents from top to bottom

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, expression evaluation, and backtracking algorithms. Understanding different stack implementations helps choose the right one for your app.

💼 Career

Many software engineering roles require knowledge of data structures like stacks and their trade-offs for performance and memory.

1

Create Node class and LinkedListStack class with push and pop

Create a class called Node with an __init__ method that takes value and sets self.value and self.next to None. Then create a class called LinkedListStack with an __init__ method that sets self.top to None. Add a method push(self, value) that creates a new Node and puts it on top of the stack. Add a method pop(self) that removes and returns the top value or returns None if empty.

DSA Python

# Create Node and LinkedListStack classes with push and pop methods
# Your code here

Hint

Think of Node as a box holding a value and a pointer to the next box. The stack keeps track of the top box.

2

Add max_size variable to limit stack size

Inside the LinkedListStack class, add a variable called max_size in the __init__ method and set it to 3. Also add a variable called size initialized to 0 to track the current number of items in the stack.

DSA Python

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

class LinkedListStack:
    def __init__(self):
        self.top = None
        # Add max_size and size variables here
        # Your code here

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

    def pop(self):
        if self.top is None:
            return None
        popped_value = self.top.value
        self.top = self.top.next
        return popped_value

Hint

Use self.max_size to store the limit and self.size to count how many items are in the stack.

3

Update push to check max_size and update size

Modify the push(self, value) method in LinkedListStack to first check if self.size is equal to self.max_size. If yes, do not add the new node and return False. Otherwise, add the new node on top, increase self.size by 1, and return True. Also update pop(self) to decrease self.size by 1 when popping a value.

DSA Python

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

class LinkedListStack:
    def __init__(self):
        self.top = None
        self.max_size = 3
        self.size = 0

    def push(self, value):
        # Add size check and update size
        # Your code here

    def pop(self):
        if self.top is None:
            return None
        # Update size when popping
        # Your code here

Hint

Check the size before adding. Increase size after adding. Decrease size after removing.

4

Print stack contents from top to bottom

Add a method print_stack(self) to LinkedListStack that prints the stack values from top to bottom separated by -> and ends with None. For example, if the stack has values 3, 2, 1 from top to bottom, print 3 -> 2 -> 1 -> None. Then create a stack, push values 1, 2, 3, and 4 (the last push should fail due to max size). Finally, call print_stack().

DSA Python

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

class LinkedListStack:
    def __init__(self):
        self.top = None
        self.max_size = 3
        self.size = 0

    def push(self, value):
        if self.size == self.max_size:
            return False
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node
        self.size += 1
        return True

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

    # Add print_stack method here
    # Your code here

stack = LinkedListStack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)  # This push should fail

# Print the stack contents
# Your code here

Hint

Use a loop to follow the next pointers from top and build a string to print.