Implementing Stack using Linked List

The core property of a Stack data structure is that it allows adding and removing elements only from one endpoint i.e, there is only one opening through which we can add or remove elements. To make it intuitive and easy to understand, we generally visualize stack as a pile of elements stacked on top of each other. Adding or removing elements will be done from the top end of pile.

Also we want all operations — push, pop, top and is_empty— to be done in constant time O(1)

Using Linked lists, there are two different ways in which we can replicate the core behavior of stack (i.e., adding or removing elements has to be done from only one end).

1. Add and pop elements at the tail end of linked list
   • push operation can be done in O(1) time if the tail node is tracked. We just need to set next element of tail pointer to the newly added element and set the tail to new element.
   • pop operation takes O(N) time as we need to get to the previous element to the removed element and set it’s next node to null.
   • top and is_empty operation can be done in O(1) time. Why?
2. Add and pop elements at the head end of linked list
   • push operation can be done in O(1) time as the pushed element can be set as the new head of linked list and point it’s next to the existing head.
   • Also pop operation can be done in O(1) time as the head element can be popped out and the next element of head can be set as new head.
   • Similarly top and is_empty can also be done in O(1) time.

2nd option is more efficient, so we chose to go with it and create a stack data structure by pushing and popping element from the head end of linked list. Below is code implementation for the same:

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

class Stack:
    def __init__(self):
        self.head = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head:
            popped = self.head
            self.head = self.head.next
            return popped.data
        else:
            return None

    def top(self):
        if self.head:
            return self.head.data
        else:
            return None

    def is_empty(self):
        return self.head is None