Back to Basics

Stack: Linked List Implementation

Explore how a stack works using dynamic linked list implementation. Watch how nodes are created, linked, and managed with flexible memory allocation.

Interactive Operations
Linked List Implementation
O(1) Operations

Stack Visualization

HEAD
NULL
Size: 0
Memory: Dynamic allocation
Head: NULL

Current Step:

Select an operation to begin visualization

Complexity Analysis

O(1)
Push
O(1)
Pop
O(1)
Peek
O(n) Space
Dynamic allocation + pointer overhead

Advantages over Array

Dynamic Size: No fixed maximum capacity
Memory Efficient: Only allocates what's needed
No Overflow: Limited only by available memory
Memory Overhead: Extra storage for pointers

Operations

Push

Create new node, link to current head, update head pointer

Pop

Store head value, move head to next, deallocate old head

Peek

Return head node value without modification

Memory Management

• Dynamic Allocation: Nodes created on-demand
• Garbage Collection: Automatic in Java/Python/JS
• Manual Management: Required in C/C++
• Cache Performance: Generally worse than arrays
• Memory Fragmentation: Possible with frequent alloc/dealloc

Implementation

class Node:
    def __init__(self, value):
        self.value = value      # Data stored in the node
        self.next = None        # Reference to next node

class StackLinkedList:
    def __init__(self):
        self.head = None        # Reference to top of stack
        self.size = 0          # Track number of elements
    
    def push(self, value):
        # Create new node
        new_node = Node(value)
        
        # Link new node to current head
        new_node.next = self.head
        
        # Update head to point to new node
        self.head = new_node
        self.size += 1
        return value
    
    def pop(self):
        # Check for stack underflow
        if self.head is None:
            raise Exception("Stack Underflow")
        
        # Get value from head node
        value = self.head.value
        
        # Update head to next node
        self.head = self.head.next
        self.size -= 1
        
        # Note: In languages without garbage collection,
        # you would need to free the memory of the old head
        return value
    
    def peek(self):
        # Check if stack is empty
        if self.head is None:
            raise Exception("Stack is Empty")
        
        return self.head.value
    
    def is_empty(self):
        return self.head is None
    
    def get_size(self):
        return self.size
    
    def display(self):
        # Traverse and display all elements
        current = self.head
        elements = []
        while current:
            elements.append(current.value)
            current = current.next
        return elements