Stack using linked list

In this tutorial, we will implement a stack using linked list with their time and space complexity.

Implementation of stack using linked list

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