🔗 Stack Implementation Using Linked Lists (Push, Pop, Peek, isEmpty & Display)
Welcome to Part 3 of our Stack in Java series.
In Part 1, we learned:
- ✅ What is a Stack?
- ✅ LIFO Principle
- ✅ Stack Terminologies
- ✅ Applications of Stack
In Part 2, we learned:
- ✅ Stack Implementation Using Arrays
- ✅ Push Operation
- ✅ Pop Operation
- ✅ Peek Operation
- ✅ isEmpty()
- ✅ isFull()
- ✅ Display Operation
Although an array implementation is simple and efficient, it has one major limitation:
The size of the stack is fixed.
If the array becomes full, no more elements can be inserted.
To overcome this limitation, we use a Linked List.
In this tutorial, you’ll learn how to implement a Stack using a Singly Linked List, where the stack can grow dynamically as memory is available.
📚 Table of Contents
- Why Use a Linked List?
- Stack Representation
- Node Structure
- Top Pointer
- Push Operation
- Pop Operation
- Peek Operation
- isEmpty()
- Display Operation
- Complete Java Program
- Dry Runs
- Time Complexity
- Advantages over Arrays
- Common Mistakes
- FAQs
- Conclusion
🤔 Why Implement Stack Using a Linked List?
Suppose an array-based stack has a capacity of 5.
10
20
30
40
50
Trying to push another element results in:
Stack Overflow
Even if your computer has plenty of free memory, the stack cannot grow because the array size is fixed.
A Linked List solves this problem.
Each new element is stored in a new node, so the stack grows dynamically.
🔗 Stack Representation Using a Linked List
Unlike arrays, a linked list does not store elements in contiguous memory.
Each element is stored inside a Node.
Example
Top
↓
+------+-----+
| 40 | •----|----+
+------+-----+ |
|
+------+-----+
| 30 | •----|----+
+------+-----+ |
|
+------+-----+
| 20 | •----|----+
+------+-----+ |
|
+------+-----+
| 10 | NULL |
+------+-----+
Notice that the Top always points to the first node.
🧠 Why is the Top at the Beginning?
Suppose the stack is
Top
↓
40
↓
30
↓
20
↓
10
If the top is stored at the beginning,
both Push and Pop require changing only one reference.
Therefore,
both operations become
O(1)
📦 Node Structure
Every node stores:
- Data
- Reference to the Next Node
Visual Representation
+------+------+
| Data | Next |
+------+------+
💻 Java Node Class
class Node{
int data;
Node next;
Node(int data){
this.data = data;
next = null;
}
}
📍 Top Pointer
Instead of storing an index,
we store a reference.
Node top;
Initially
top = null
This means
the stack is empty.
➕ Push Operation
Push inserts a new node at the beginning.
Suppose
Current Stack
Top
↓
30
↓
20
↓
10
Push
40
Result
Top
↓
40
↓
30
↓
20
↓
10
📝 Algorithm
- Create a new node.
- Point it to the current Top.
- Move Top to the new node.
🎨 Dry Run
Current
Top
↓
30
Create
40
Update
newNode.next = top
Update
top = newNode
Done.
💻 Java Program – Push
public void push(int value){
Node newNode = new Node(value);
newNode.next = top;
top = newNode;
}
➖ Pop Operation
Pop removes the top node.
Current
Top
↓
40
↓
30
↓
20
Pop
40
Result
Top
↓
30
↓
20
📝 Algorithm
- Check if the stack is empty.
- Store the top value.
- Move Top to the next node.
- Return the deleted value.
💻 Java Program – Pop
public int pop(){
if(top == null){
System.out.println("Stack Underflow");
return -1;
}
int value = top.data;
top = top.next;
return value;
}
👀 Peek Operation
Peek returns the top element
without removing it.
Current
Top
↓
40
↓
30
↓
20
Peek
40
Stack remains unchanged.
💻 Java Program – Peek
public int peek(){
if(top == null){
System.out.println("Stack is Empty");
return -1;
}
return top.data;
}
❓ isEmpty()
Checks whether the stack contains any elements.
💻 Java Program
public boolean isEmpty(){
return top == null;
}
📋 Display Operation
Display starts from Top.
Current
Top
↓
40
↓
30
↓
20
↓
10
Output
40
30
20
10
💻 Java Program – Display
public void display(){
if(top == null){
System.out.println("Stack is Empty");
return;
}
Node temp = top;
while(temp != null){
System.out.println(temp.data);
temp = temp.next;
}
}
💻 Complete Java Program
class Node{
int data;
Node next;
Node(int data){
this.data = data;
next = null;
}
}
public class Stack{
Node top;
public void push(int value){
Node newNode = new Node(value);
newNode.next = top;
top = newNode;
}
public int pop(){
if(top == null){
System.out.println("Stack Underflow");
return -1;
}
int value = top.data;
top = top.next;
return value;
}
public int peek(){
if(top == null){
System.out.println("Stack is Empty");
return -1;
}
return top.data;
}
public boolean isEmpty(){
return top == null;
}
public void display(){
if(top == null){
System.out.println("Stack is Empty");
return;
}
Node temp = top;
System.out.println("\nStack Elements:");
while(temp != null){
System.out.println(temp.data);
temp = temp.next;
}
}
public static void main(String args[]){
Stack s = new Stack();
s.push(10);
s.push(20);
s.push(30);
s.push(40);
s.display();
System.out.println("\nTop Element = " + s.peek());
System.out.println("\nDeleted = " + s.pop());
s.display();
System.out.println("\nIs Empty? " + s.isEmpty());
}
}
Output
Stack Elements:
40
30
20
10
Top Element = 40
Deleted = 40
Stack Elements:
30
20
10
Is Empty? false
📊 Time Complexity
| Operation | Time Complexity |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
| isEmpty | O(1) |
| Display | O(n) |
💾 Space Complexity
Suppose the stack contains n nodes.
Memory required
O(n)
Unlike arrays,
memory is allocated only when a new node is created.
⚖️ Array vs Linked List Implementation
| Feature | Array Stack | Linked List Stack |
|---|---|---|
| Memory Size | Fixed | Dynamic |
| Overflow | Possible | Only when memory is exhausted |
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
| Memory Usage | May waste unused space | Allocates memory only when needed |
| Implementation | Simple | Slightly more complex |
🌟 Advantages of Linked List Stack
✅ Dynamic size
✅ No fixed capacity
✅ No wasted array space
✅ Efficient Push and Pop operations
✅ Better memory utilization
❌ Disadvantages
❌ Extra memory is required for storing the next reference.
❌ Nodes are not stored contiguously, so cache performance may be lower than arrays.
❌ Slightly more complex implementation than an array-based stack.
⚠️ Common Mistakes
❌ Forgetting to update top
Wrong
newNode.next = top;
Correct
top = newNode;
❌ Forgetting the Underflow Check
Never access
top.data
without first checking
top == null
❌ Using the Last Node as Top
For a linked-list implementation, the Top should always be the first node, not the last. Otherwise, Push and Pop operations would require traversal and become O(n) instead of O(1).
❓ Frequently Asked Questions
Q1. Why is the Top stored at the beginning?
So that Push and Pop can be performed in O(1) time.
Q2. Can a Linked List Stack overflow?
It can only overflow when the system runs out of available memory.
Q3. Which implementation is better?
- Array: Better when the maximum size is known and memory locality is important.
- Linked List: Better when the stack size is unpredictable.
Q4. Is Push faster in a Linked List?
No. Push is O(1) in both array and linked-list implementations.
Q5. Why doesn’t a Linked List Stack require isFull()?
Because it grows dynamically and does not have a predefined size limit.
🎯 Key Takeaways
- 🔗 A Linked List provides a dynamic implementation of a Stack.
- 📍 The Top points to the first node.
- ➕ Push inserts a node at the beginning.
- ➖ Pop removes the first node.
- 👀 Peek returns the first node’s data.
- 🚀 Push, Pop, and Peek all take O(1) time.
- 💾 Memory is allocated dynamically, avoiding the fixed-size limitation of arrays.
🎉 Conclusion
Implementing a Stack using a Linked List eliminates the biggest drawback of an array-based stack—its fixed capacity. Since nodes are created dynamically, the stack can grow as needed, making it ideal for applications where the number of elements is not known in advance.
Although each node requires extra memory for storing the next reference, the flexibility and scalability often outweigh this overhead.
👉 In Part 4, we’ll explore the real-world applications of Stack, including:
- 🔁 Function Call Stack
- 🔄 Recursion
- 🧮 Expression Evaluation
- 📝 Parentheses Matching
- 🔤 Infix to Postfix Conversion
- 🔡 Infix to Prefix Conversion
- 🌐 Browser History
- ✏️ Undo & Redo
- 🌳 Depth First Search (DFS)
- 💻 Java Virtual Machine (JVM) Stack
- 🎯 Complete Java examples for important applications
