Abhishek Kumar Category: Data StructuresTags: 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.

``````class Node:
def __init__(self, data):
self.data = data
self.next = None

class Stack:
def __init__(self):

def is_empty(self):

def push(self, data):
new_node = Node(data)
else:

def pop(self):
return data
else:
raise Exception('Stack underflow')

def peek(self):
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())``````
``````class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}

class Stack {
constructor() {
}

isEmpty() {
}

push(data) {
const newNode = new Node(data);
} else {
}
}

pop() {
return data;
} else {
throw "Stack underflow";
}
}

peek() {
} 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

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)

• No wastage of space
• Easy to reduce or expand the size of stack

• Complex to implement than array based implementation
• Extra space will be occupied

AUTHOR ### Abhishek Kumar

Software engineer | Blogger | Keen learner
Python | Django | JavaScript | React | Next.js | Express.js | C
Passionate about learning and experimenting with new things and open to more opportunities and collaborations.