700207. Stack using Linked List
Easy
Implement Stack using Linked List
Summary
Create a stack data structure using a linked list in programming. The key concepts involved are linked lists and stacks.
Detailed Explanation
To implement a stack using a linked list, we will create a new node class Node with two attributes: the value of the node (val) and a pointer to the next node (next). We then create a class Stack that contains a pointer to the top element in the stack (top) and an empty linked list.
Here's a step-by-step breakdown of the solution:
- Initialize the stack by creating a new node with a value of null (indicating an empty stack).
- Define methods for pushing and popping elements onto the stack:
push(val): Create a new node with the given value, set its next pointer to the current top element, and update the top pointer.pop(): If the stack is not empty, return the value of the top element, remove it from the linked list (by updating the top pointer), and return null if the stack becomes empty.
Here's a diagram representation of the process:
+---------------+
| Node |
+---------------+
|
v
+---------------+ +---------------+
| Pushed Value | | Top Element |
+---------------+ +---------------+
|
v
+---------------+ +---------------+
| Next Node | | Linked List |
+---------------+ +---------------+
Time complexity for both push and pop operations is O(1), as we are simply updating the top pointer or removing a node. Space complexity is also O(1) since we are using a constant amount of space to store the stack's state.
Optimized Solutions
Java
class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
}
public class Stack {
private Node top;
public void push(int val) {
Node newNode = new Node(val);
if (top == null) {
top = newNode;
} else {
newNode.next = top;
top = newNode;
}
}
public int pop() {
if (top != null) {
int val = top.val;
top = top.next;
return val;
} else {
return -1; // or throw an exception
}
}
}