Stack using linked list
Category: Data Structures
Tags: #datastructures#stack
In this tutorial, we will implement a stack using linked list with their time and space complexity.
In case of array based implementation of stack size of stack is fixed and if we use growable array then it may lead to wastage of space in some situations but this situation will never occur for linked list based implementation.
Implementation of stack using Linked List
In case of Linked List based implementation of stack, size of stack can be increased and decreased easily that's why situation of Stack overflow will never occur but Stack underflow is possible.
Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def is_empty(self):
return self.head == None
def push(self, data):
if self.head:
new_node = Node(data)
new_node.next = self.head
self.head = new_node
else:
self.head = Node(data)
def pop(self):
if self.head:
data = self.head.data
self.head = self.head.next
return data
else:
raise Exception('Stack underflow')
def peek(self):
if self.head:
return self.head.data
else:
raise Exception('Stack underflow')
stack = Stack()
print(stack.is_empty())
stack.push(5)
stack.push(9)
stack.push(6)
print(stack.pop())
print(stack.peek())
stack.push(5)
print(stack.is_empty())
JavaScript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Stack {
constructor() {
this.head = null;
}
isEmpty() {
return this.head === null;
}
push(data) {
if (this.head) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
} else {
this.head = new Node(data);
}
}
pop() {
if (this.head) {
const data = this.head.data;
this.head = this.head.next;
return data;
} else {
throw "Stack underflow";
}
}
peek() {
if (this.head) {
return this.head.data;
} else {
throw "Stack underflow";
}
}
}
const stack = new Stack();
console.log(stack.isEmpty());
stack.push(5);
stack.push(9);
stack.push(6);
console.log(stack.pop());
console.log(stack.peek());
stack.push(5);
console.log(stack.isEmpty());
Output
True
6
9
False
| Space complexity (for n push) | O(n) |
| Time complexity of push() | O(1) |
| Time complexity of pop() | O(1) |
| Time complexity of is_empty() | O(1) |
Advantages of implementing stack using linked list
- No wastage of space
- Easy to reduce or expand the size of stack
Disadvantages of implementing stack using linked list
- Complex to implement than array based implementation
- Extra space will be occupied
