Linked Lists in Stack Implementation
- Linked lists offer a dynamic memory allocation alternative to arrays.
- Despite different data structures, time complexities for stack operations remain consistent.
- Nodes are non-contiguously maintained in memory, each with a pointer to its successor node.
- Stack overflow occurs when insufficient memory heap space is available for node creation.
- Singly linked lists align standard linked list operations with stack operations, adhering to the Last In, First Out (LIFO) principle.
- Top variable guides operations like Pop, Push, Peek, and Display.
- Unlike arrays, linked lists offer flexibility, eliminating risk of overflow.
Stack Implementation vs. Array vs. Linked List
- Array-based stacks work for a fixed number of data values, making them unsuitable for unknown data sizes.
- Linked list stacks can work for unlimited data values, eliminating the need to fix the initial size.
- Linked list stacks insert new elements as 'top' elements, pointing to the 'top' node.
- To remove an element, move 'top' to its previous node in the list.
- The first element's next field must always be NULL.
Operations performed on Stack
Following operations can be performed on a stack:
- push(): It inserts an element to the top of the stack. It takes O(1) time, as each node is inserted at the head/top of the linked list.
- pop(): It removes an element from the top of the stack. It takes O(1) time, as the top always points to the newly inserted node.
- peek(): It returns the top element of the stack.
- size(): It returns the size of the stack, i.e., the total number of items in a stack.
- isEmpty(): Returns a boolean value. It returns true if the stack is empty. Else, it returns false.
Before performing all the above operations, lets first define node structure