6a:T406,from typing import TypeVar, Generic, Optional T = TypeVar('T') class LinkedStack(Generic[T]): """Stack implementation using a singly linked list""" def __init__(self) -> None: self._top: Optional[StackNode[T]] = None # Points to the top self._count: int = 0 # Number of elements # Core stack operations (to be implemented) def push(self, element: T) -> None: """Add element to top of stack""" ... def pop(self) -> T: """Remove and return top element""" ... def peek(self) -> T: """Return top element without removing""" ... def is_empty(self) -> bool: """Check if stack is empty""" ... def size(self) -> int: """Return number of elements""" ... # Optional utility methods def clear(self) -> None: """Remove all elements""" ... def __str__(self) -> str: """String representation of stack""" ...62:{"json":{"id":"seed_fe778f5b126e5a612eb2f2d36460dd77","slug":"linked-list-based-stack-implementation","category":"Data Structures & Algorithms","topic":"Linked List-Based Stack Implementation","title":"Linked List-Based Stack Implementation","description":"Master the art of implementing stacks using singly linked lists. Understand how dynamic memory allocation eliminates overflow concerns, explore O(1) push and pop operations, and discover why linked list stacks are the preferred choice for unbounded stack sizes and memory-sensitive applications.","difficulty":"INTERMEDIATE","estimatedMinutes":50,"pages":[{"id":"seed_0187adb494205faa7d9d78029a0a95bd","title":"Using a Singly Linked List to Implement a Stack","order":0,"content":[{"id":"opening-hook","title":"The Natural Synergy Between Linked Lists and Stacks","content":[{"data":{"content":"In the previous module, we explored how arrays can serve as the underlying data structure for stacks. Array-based stacks are elegant, cache-friendly, and remarkably efficient—but they carry a fundamental limitation: **fixed capacity**. When you create an array-based stack with a capacity of 100 elements, that 101st push operation either fails catastrophically or triggers an expensive resizing operation.\n\nThis brings us to an elegant alternative: the **linked list-based stack**. By leveraging the dynamic nature of linked lists, we can create stacks that grow and shrink organically with demand, never running into capacity limits, and performing every operation in constant time—**guaranteed, not amortized**.\n\nThe marriage between singly linked lists and stacks isn't just convenient—it's *natural*. The very structure of a singly linked list mirrors the access pattern of a stack so precisely that implementing a stack becomes almost trivial once you understand both data structures."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand why singly linked lists are ideally suited for stack implementation. You'll see how the structural properties of linked lists map directly to stack semantics, explore the conceptual model that makes this implementation intuitive, and appreciate the trade-offs that inform when to choose linked lists over arrays for your stacks.","variant":"info"},"type":"callout"}]},{"id":"revisiting-singly-linked-list","title":"Revisiting the Singly Linked List","content":[{"data":{"content":"Before we bridge linked lists to stacks, let's refresh our understanding of the singly linked list—the data structure that will serve as our stack's foundation.\n\n**The singly linked list is a sequence of nodes where each node contains:**\n1. **Data**: The actual value stored in the node\n2. **Next pointer**: A reference to the next node in the sequence\n\nThe list maintains a **head pointer** that references the first node. The last node's `next` pointer is `null`, signifying the end of the list."},"type":"text"},{"data":{"height":"200px","mermaidSyntax":"graph LR\n HEAD[\"HEAD\npointer\"] --> A[\"Node\nvalue: 10\nnext: →\"]\n A --> B[\"Node\nvalue: 20\nnext: →\"]\n B --> C[\"Node\nvalue: 30\nnext: →\"]\n C --> NULL[\"null\"]\n style HEAD fill:#4CAF50,stroke:#2E7D32,color:#fff\n style A fill:#2196F3,stroke:#1565C0,color:#fff\n style B fill:#2196F3,stroke:#1565C0,color:#fff\n style C fill:#2196F3,stroke:#1565C0,color:#fff\n style NULL fill:#9E9E9E,stroke:#616161,color:#fff"},"type":"mermaid-excalidraw"},{"data":{"content":"**Key Properties of Singly Linked Lists:**"},"type":"text"},{"data":{"items":["**Sequential access only**: To reach node N, you must traverse nodes 0 through N-1. There's no random access.","**Dynamic size**: The list grows and shrinks by allocating/deallocating individual nodes. No resizing or capacity limits.","**O(1) insertion at head**: Adding a new node at the beginning requires only updating the head pointer—no shifting of existing elements.","**O(1) removal from head**: Removing the first node involves updating the head pointer to the second node—again, constant time.","**O(n) insertion at tail**: Without a tail pointer, reaching the end requires traversing the entire list."],"variant":"accent"},"type":"list"},{"data":{"icon":"Lightbulb","title":"The Critical Insight","content":"Notice that operations at the **head** of a singly linked list are O(1), while operations at the **tail** are O(n) without a tail pointer. This asymmetry is precisely why stacks map so naturally to linked lists—stacks only need efficient access to one end!","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"why-linked-lists-for-stacks","title":"Why Linked Lists for Stacks?","content":[{"data":{"content":"To understand why singly linked lists are a natural fit for stacks, let's revisit what a stack fundamentally requires:\n\n**Stack operations (ADT perspective):**\n1. `push(element)`: Add an element to the top\n2. `pop()`: Remove and return the element from the top\n3. `peek()` / `top()`: View the top element without removing it\n4. `isEmpty()`: Check if the stack is empty\n5. `size()`: Return the number of elements (optional)\n\n**Observe the pattern**: Every single operation involves only the **top** of the stack. We never need to access the middle or bottom. This is the LIFO (Last-In, First-Out) principle in action—and it maps perfectly to head operations in a linked list."},"type":"text"},{"data":{"rows":[["push(element)","Insert at head","O(1)"],["pop()","Remove from head","O(1)"],["peek() / top()","Read head node's value","O(1)"],["isEmpty()","Check if head is null","O(1)"],["size()","Maintain a counter (or traverse)","O(1) with counter"]],"caption":"Mapping Stack Operations to Linked List Operations","headers":["Stack Operation","Linked List Equivalent","Time Complexity"]},"type":"table"},{"data":{"content":"**The mapping is not just efficient—it's direct.**\n\nWhen we push onto a stack, we're conceptually placing an item on top of a pile. In a linked list, inserting at the head places a new node at the front of the chain. Both operations add to the 'top' end.\n\nWhen we pop from a stack, we remove the topmost item. In a linked list, removing the head node accomplishes exactly this—we're always working with the most recently added element.\n\nThis conceptual alignment isn't coincidental. It reflects a deep structural correspondence between the LIFO access pattern and the asymmetric efficiency of singly linked lists."},"type":"text"},{"data":{"icon":"Sparkles","title":"Design Elegance","content":"Good data structure design often involves recognizing when the structural properties of one abstraction naturally satisfy the requirements of another. The linked list stack is a textbook example: the inherent O(1) head operations of linked lists perfectly match the single-end access pattern of stacks.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"conceptual-model","title":"The Conceptual Model: Visualizing a Linked Stack","content":[{"data":{"content":"Let's build a mental model for how a linked list-based stack looks and behaves. Understanding this visualization is crucial for implementing and debugging linked stacks correctly.\n\n**The core idea**: The **head** of the linked list is the **top** of the stack.\n\nImagine a vertical stack of plates. The top plate (the one you'd grab first) corresponds to the head node of our linked list. Each plate below connects to the one above it through a 'next' pointer."},"type":"text"},{"data":{"height":"280px","mermaidSyntax":"graph TB\n subgraph Stack View\n TOP[\"TOP\n(most recent)\"] --> N3[\"30\"]\n N3 --> N2[\"20\"]\n N2 --> N1[\"10\"]\n N1 --> BOTTOM[\"BOTTOM\n(oldest)\"]\n end\n style TOP fill:#4CAF50,stroke:#2E7D32,color:#fff\n style N3 fill:#2196F3,stroke:#1565C0,color:#fff\n style N2 fill:#2196F3,stroke:#1565C0,color:#fff\n style N1 fill:#2196F3,stroke:#1565C0,color:#fff\n style BOTTOM fill:#9E9E9E,stroke:#616161,color:#fff"},"type":"mermaid-excalidraw"},{"data":{"content":"**Translating to linked list terminology:**"},"type":"text"},{"data":{"left":[{"data":{"items":["**Top of stack**: The element that will be popped next","**Bottom of stack**: The oldest element, first one pushed","**Push**: Add to top","**Pop**: Remove from top"],"title":{"icon":"Target","text":"Stack Terminology","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["**Head node**: First node in the list","**Last node (null terminator)**: Node with next = null","**Insert at head**: Create node, point to old head, update head","**Delete from head**: Update head to head.next"],"title":{"icon":"Code2","text":"Linked List Equivalent","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**State transitions during push:**\n\nWhen we push a new element (say, 40) onto our stack containing [30, 20, 10]:\n\n1. Create a new node with value 40\n2. Set the new node's `next` pointer to the current head (node with 30)\n3. Update the head pointer to reference the new node\n\nThe new node becomes the head, representing the new top of the stack. The operation completes in constant time regardless of stack size."},"type":"text"},{"data":{"height":"150px","mermaidSyntax":"graph LR\n subgraph After Push 40\n HEAD2[\"HEAD\"] --> D[\"40\"] --> C2[\"30\"] --> B2[\"20\"] --> A2[\"10\"] --> NULL2[\"null\"]\n end\n style HEAD2 fill:#4CAF50,stroke:#2E7D32,color:#fff\n style D fill:#FF9800,stroke:#F57C00,color:#fff\n style C2 fill:#2196F3,stroke:#1565C0,color:#fff\n style B2 fill:#2196F3,stroke:#1565C0,color:#fff\n style A2 fill:#2196F3,stroke:#1565C0,color:#fff\n style NULL2 fill:#9E9E9E,stroke:#616161,color:#fff"},"type":"mermaid-excalidraw"},{"data":{"icon":"Zap","title":"No Element Movement","content":"Unlike array-based stacks where resizing requires copying all elements, linked list pushes never move existing data. Each node stays in place—we simply update pointer references. This is a fundamental advantage when dealing with large elements or memory-constrained environments.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"structural-comparison","title":"Structural Comparison with Array-Based Stacks","content":[{"data":{"content":"To fully appreciate the linked list approach, let's contrast it structurally with array-based stacks. Both implement the same abstract data type (stack), but their internal organizations are fundamentally different."},"type":"text"},{"data":{"rows":[["Memory layout","Contiguous block","Scattered nodes connected by pointers"],["Capacity","Fixed or dynamically resized","Unbounded (limited only by system memory)"],["Memory per element","Element size only","Element size + pointer overhead (8 bytes on 64-bit)"],["Cache performance","Excellent (spatial locality)","Poor (nodes may be scattered in memory)"],["Top location","Tracked by index","Always at head pointer"],["Growth mechanism","Array copy/resize","Single node allocation"],["Shrinkage","Often doesn't release memory","Immediate memory release per pop"]],"caption":"Array Stack vs. Linked List Stack: Structural Comparison","headers":["Property","Array-Based Stack","Linked List Stack"]},"type":"table"},{"data":{"content":"**Memory layout visualized:**"},"type":"text"},{"data":{"left":[{"data":{"content":"**Array Stack Memory:**\n```\nAddress: 0x1000 0x1001 0x1002 0x1003 0x1004\n [ 10 ][ 20 ][ 30 ][ ][ ]\n ↑ ↑\n base top\n```\nAll elements occupy adjacent memory addresses. The `top` index tracks where the next push goes."},"type":"text"}],"right":[{"data":{"content":"**Linked List Stack Memory:**\n```\nAddress: 0x3000 → 0x5000 → 0x2000 → null\nValue: [ 30 ] [ 20 ] [ 10 ]\n ↑\n head\n```\nNodes can be anywhere in memory. Pointers maintain the logical order."},"type":"text"}]},"type":"two-column"},{"data":{"icon":"AlertCircle","title":"Cache Locality Trade-off","content":"The scattered memory layout of linked lists means cache misses are more likely when traversing or accessing elements. For stacks, where we only ever access the top element, this is less critical—but it can matter in performance-sensitive applications. Array stacks win on cache efficiency; linked stacks win on flexibility and guaranteed O(1) operations.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"when-to-choose","title":"When to Choose a Linked List Stack","content":[{"data":{"content":"Understanding when to use a linked list stack versus an array stack is crucial for practical software engineering. The choice depends on your specific requirements and constraints."},"type":"text"},{"data":{"items":["**Unpredictable stack size**: If you cannot estimate the maximum number of elements, linked lists avoid the risk of overflow or expensive resizes.","**Memory efficiency matters for sparse usage**: If the stack often contains few elements but occasionally grows large, linked lists only use memory for actual elements—no wasted allocated-but-unused capacity.","**Guaranteed O(1) is required**: Array dynamic resize is O(1) *amortized*, but individual operations can be O(n). Linked lists provide strict O(1) per operation.","**Elements are large**: Pointer overhead becomes negligible when element sizes are large (objects, records). Avoiding copies during resize becomes significant.","**Frequent push-pop with variable load**: If stack depth fluctuates wildly, linked lists naturally reclaim memory on pop, while arrays typically don't shrink."],"title":{"icon":"CheckCircle","text":"Choose Linked List Stack When:","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"items":["**Maximum size is known and fixed**: If you know you'll never exceed N elements, a static array is simpler and more efficient.","**Cache performance is critical**: For performance-critical code where memory access patterns matter, array locality wins.","**Elements are small primitives**: For integers, floats, or small values, pointer overhead in linked lists can double effective memory usage.","**Simplicity and debugging**: Arrays are easier to inspect and debug. Linked list pointer bugs can be subtle and hard to diagnose."],"title":{"icon":"XCircle","text":"Prefer Array Stack When:","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"icon":"Info","title":"Real-World Observation","content":"In practice, many standard library stack implementations use dynamic arrays (like Java's Stack extends Vector, or C++ std::stack with std::deque) because their amortized O(1) performance and cache benefits outweigh the occasional resize cost. However, linked list stacks remain valuable in specific domains: embedded systems, memory-constrained environments, and applications requiring strict real-time guarantees.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"node-structure","title":"The Node Structure: Building Block of Our Stack","content":[{"data":{"content":"Before we implement operations, let's define the fundamental building block: the **Node**.\n\nA node in our linked list stack is a simple container with two components:\n1. **data**: The value stored in this stack frame\n2. **next**: A reference to the node below it in the stack (or null if this is the bottom)\n\n**Generic Node Definition:**\n\nIn typed languages, we typically make the Node generic to support stacks of any element type:"},"type":"text"},{"data":{"languages":[{"code":"// Generic Node class for a linked list stack\nclass StackNode {\n data: T; // The value stored in this node\n next: StackNode | null; // Reference to the next node (below this one)\n \n constructor(data: T) {\n this.data = data;\n this.next = null;\n }\n}\n\n// Example usage:\n// For a stack of numbers:\nconst numberNode = new StackNode(42);\n\n// For a stack of strings:\nconst stringNode = new StackNode(\"hello\");\n\n// For a stack of custom objects:\ninterface Task {\n id: number;\n name: string;\n}\nconst taskNode = new StackNode({ id: 1, name: \"Complete project\" });","label":"TypeScript","value":"typescript"},{"code":"from typing import TypeVar, Generic, Optional\n\nT = TypeVar('T')\n\nclass StackNode(Generic[T]):\n \"\"\"Generic Node class for a linked list stack\"\"\"\n \n def __init__(self, data: T):\n self.data: T = data # The value stored in this node\n self.next: Optional['StackNode[T]'] = None # Reference to next node\n \n def __repr__(self) -> str:\n return f\"StackNode({self.data})\"\n\n# Example usage:\n# For a stack of numbers:\nnumber_node = StackNode(42)\n\n# For a stack of strings:\nstring_node = StackNode(\"hello\")\n\n# For a stack of custom objects:\nfrom dataclasses import dataclass\n\n@dataclass\nclass Task:\n id: int\n name: str\n\ntask_node = StackNode(Task(id=1, name=\"Complete project\"))","label":"Python","value":"python"},{"code":"// Generic Node class for a linked list stack\npublic class StackNode {\n T data; // The value stored in this node\n StackNode next; // Reference to the next node (below this one)\n \n public StackNode(T data) {\n this.data = data;\n this.next = null;\n }\n \n @Override\n public String toString() {\n return \"StackNode(\" + data + \")\";\n }\n}\n\n// Example usage:\n// For a stack of integers (using wrapper class):\nStackNode numberNode = new StackNode<>(42);\n\n// For a stack of strings:\nStackNode stringNode = new StackNode<>(\"hello\");\n\n// For a stack of custom objects:\nclass Task {\n int id;\n String name;\n \n Task(int id, String name) {\n this.id = id;\n this.name = name;\n }\n}\nStackNode taskNode = new StackNode<>(new Task(1, \"Complete project\"));","label":"Java","value":"java"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"**Memory footprint of a node:**\n\nEach node consumes:\n- Size of the data element (varies by type)\n- Size of a pointer/reference (typically 8 bytes on 64-bit systems)\n\nFor example, in a stack storing 32-bit integers:\n- Array stack: 4 bytes per element\n- Linked list stack: 4 bytes (int) + 8 bytes (pointer) = 12 bytes per element\n\nThis 3x overhead is the price we pay for dynamic flexibility. For larger objects, this overhead becomes proportionally smaller and often negligible."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Implementation Tip","content":"In some languages, the Node class can be defined as an inner class within the Stack class. This encapsulation prevents external code from directly manipulating nodes—preserving the stack abstraction. It's a good practice for maintaining invariants and hiding implementation details.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"stack-class-skeleton","title":"Stack Class Skeleton","content":[{"data":{"content":"With our Node structure defined, let's outline the LinkedStack class itself. This skeleton shows the fields and method signatures—we'll implement each method in detail in subsequent pages.\n\n**Key design decisions:**\n1. **top pointer**: We maintain only a `head` (or `top`) pointer—no tail pointer needed since we never access the other end.\n2. **size tracking**: We maintain a counter to provide O(1) size queries. Without this, we'd need O(n) traversal to count elements.\n3. **Generic typing**: The stack is parameterized by element type T for type safety and reusability."},"type":"text"},{"data":{"languages":[{"code":"class LinkedStack {\n private top: StackNode | null; // Points to the top of the stack\n private count: number; // Number of elements in the stack\n \n constructor() {\n this.top = null; // Empty stack starts with null top\n this.count = 0; // No elements initially\n }\n \n // Core stack operations (to be implemented)\n push(element: T): void { /* ... */ }\n pop(): T { /* ... */ }\n peek(): T { /* ... */ }\n isEmpty(): boolean { /* ... */ }\n size(): number { /* ... */ }\n \n // Optional utility methods\n clear(): void { /* ... */ }\n toString(): string { /* ... */ }\n}","label":"TypeScript","value":"typescript"},{"code":"$6a","label":"Python","value":"python"},{"code":"public class LinkedStack {\n private StackNode top; // Points to the top of the stack\n private int count; // Number of elements in the stack\n \n public LinkedStack() {\n this.top = null; // Empty stack starts with null top\n this.count = 0; // No elements initially\n }\n \n // Core stack operations (to be implemented)\n public void push(T element) { /* ... */ }\n public T pop() { /* ... */ }\n public T peek() { /* ... */ }\n public boolean isEmpty() { /* ... */ }\n public int size() { /* ... */ }\n \n // Optional utility methods\n public void clear() { /* ... */ }\n \n @Override\n public String toString() { /* ... */ }\n}","label":"Java","value":"java"}],"showLineNumbers":true},"type":"code"},{"data":{"content":"**Invariants we must maintain:**\n\n1. `top` is null if and only if the stack is empty\n2. `count` accurately reflects the number of nodes reachable from `top`\n3. The last node in the chain has `next = null`\n4. No cycles exist in the node chain (following `next` pointers always terminates)\n\nThese invariants are crucial for correctness. Every method we implement must preserve them, and we can use them to reason about our code's behavior."},"type":"text"},{"data":{"icon":"Info","title":"Encapsulation Matters","content":"Notice that `top` and `count` are private. External code should interact with the stack only through its public methods. This prevents invariant violations—for example, external code setting `count` to an incorrect value or modifying `top` directly.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary-path-forward","title":"Summary: The Foundation Is Set","content":[{"data":{"content":"We've established the conceptual foundation for implementing stacks using singly linked lists. Let's consolidate our key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**Natural mapping**: The singly linked list's O(1) head operations directly satisfy the stack's single-end access pattern.","**Head as top**: The head of the linked list represents the top of the stack—all operations occur here.","**Unbounded capacity**: Unlike array stacks, linked list stacks grow without limit (bound only by system memory).","**Guaranteed O(1)**: Every operation is truly constant time—no amortization, no occasional O(n) resizes.","**Memory trade-off**: Pointer overhead vs. immediate memory reclamation on pop and no wasted capacity.","**Use case alignment**: Linked list stacks excel when size is unpredictable or strict O(1) is required."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next:**\n\nWith the conceptual model firmly in place, we'll move to the practical implementation. The next page examines why the **head** position specifically is the optimal choice for representing the top of our stack—and what would happen if we tried a different approach."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand why singly linked lists are a natural and powerful choice for implementing stacks. The structural properties align perfectly with stack semantics, enabling guaranteed O(1) operations with unbounded capacity. Next, we'll explore why the head position specifically serves as the ideal stack top.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_2ae656982473177ab6ace16d955ce000","title":"Head as the Top of the Stack","order":1,"content":null,"isLocked":true},{"id":"seed_59db695548bc6011b05704e0b0a87ebb","title":"Push and Pop in O(1)","order":2,"content":null,"isLocked":true},{"id":"seed_71e928f912a7fa361ce27c0fca79865f","title":"No Overflow with Dynamic Memory","order":3,"content":null,"isLocked":true}]}}