Overview
A linked-list stack is an implementation of the stack abstract data type using dynamically connected nodes. Each node stores data and a reference to the next node, while the top reference identifies the most recently inserted node.
Purpose
This implementation is useful when the stack size changes dynamically and a fixed array capacity is undesirable.
Key concepts
name: Core idea; description: The central focus of stack implementation using linked lists is the capability described here: A linked-list-based stack stores each element in a node and uses a reference to the first node as the stack top. Push and pop operations are normally performed at the head of the linked list.; name: Problem context; description: Stack Implementation Using Linked Lists is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using stack implementation using linked lists, check its assumptions, input requirements, expected output, and resource constraints.
Time complexity
push: O(1); pop: O(1); peek: O(1); isEmpty: O(1); size: O(1) when a size counter is maintained; search: O(n)
Space complexity
O(n) for n nodes, including one next reference per node and node-allocation overhead.
Example
operations: PUSH(10); PUSH(20); afterPush: TOP → 30 → 20 → 10 → NULL; afterPop: TOP → 20 → 10 → NULL; removedElement: 30; explanation: Each push adds a node at the head. Each pop removes the head node.
Advantages
Can grow dynamically as nodes are allocated.; Does not require a predetermined maximum capacity.; Push and pop at the top take O(1) time.; Does not require shifting existing elements.; Uses memory according to the number of stored nodes, subject to allocation overhead.