Implementing Stack in Python using Linked List

What is a Stack?

A stack is a data structure in which items are added and removed from the same point. It is kind of a one way storage system. It is also known as Last In First Out data structure, which simply means that the item added last will be removed at first.

People often address it like a pile of plates, we add plates from the top and we remove plates from the top. If we need the bottom most plate we'd have to remove all the plates above it.

So, stack is kind of a single entrance cum exit hiding place in which the first person who goes in is the last to come out and the last person who goes in is the first to come out.

Now something about linked list and our implementation of stack :)

Linked list is a data structure made up of small nodes each of which can store a data item and an address to the next such node. Apart from these nodes, the main node in our implementation is the top node which is just like all other nodes but also acts as a gateway for addition and deletion of elements and therefore our program must keep track of this node specifically.

The following is a simple stack:

4 <- 5 <- 6 <-7 (top)

If we add an element, let’s take 8, then our stack will look like:

4 <- 5 <- 6 <- 7 <-8 (top)

Adding an element to a stack is called a Push operation. Now, if we wish to remove an element (i.e. it is always going to be the topmost element), then our stack will look like:

4 <- 5 <- 6 <-7 (top)

8 has been removed from the stack. Removal is known as a Pop.

Let's code it out!

Firstly, we are going to create the node object that will form our stack:

class Node:
    '''
    This class will represent a unit node of the stack
    '''
        
    def __init__(self,value):    # the initializer is going to take a value which will be stored in the node
      self.value = value
      self.next = None    # this stores the address for the next such node and it is set to none cause this will be assigned by the stack class

That's it, now let’s implement the object which is going to chain up the nodes into a stack and provide us with the operations for the stack:

class Stack:
    '''
    This class will use the node objects to create a node
    '''

    def __init__(self,value = None):    # value is set to none so that we can initialize our stack with or without a value
        self.top = None   # initially the top points to None
        if(value):    # the following code will run only if the value has been passed
            self.push(value)    # this calls the push method which we will define in a while
        
    def push(self,value):    # takes the value to be inserted as an argument 
        node = Node(value)    # creates a node object
        if(self.top == None):    # checks if the top exists already or not, if not run's the following code
            self.top = node
        else:
            node.next = self.top    # assigns the address of top to the next variable of the node object
            self.top = node    # top now points to the new node

    def pop(self):
        if(self.top == None):    # checks if stack is empty or not
            return 'Empty Stack..!'
        else:
            node = self.top    # assigning the node that top holds to a new node
            self.top = node.next    # setting the node next to top as the new top 
            node.next = None    # erasing the address of the new top from the old one 
            value = node.value    # getting the data item of the old top 
            del node    # deletes the node object
            return f'Popped {value}'
    
    def traverse(self):    # this method just prints all the values in the stack
        if(self.top == None):    # checks if the stack is empty
            print('Empty..!')
        else:
            temp = self.top    # referencing the top with a temporary value
            while(temp != None):    # this loop will run unless the temp variable equals None 
                print(f'{temp.value}->',end = '')
                emp = temp.next    # renews temp node
            print()

Let's test our stack:

stack = Stack()
stack.push(9)
stack.push(8)
stack.push(10)
stack.traverse()
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
stack.push(8)
stack.traverse()

Outputs:

10->8->9->
Popped 10
Popped 8
Popped 9
Empty Stack..!
8->

That's it! We successfully implemented the stack data structure using linked list.

Let’s Revisit

We implemented the stack data structure in Python using linked list and OOP (object oriented programming) concepts. We used the following approach while doing so:

We devised an object node which stores a value and an address to another node.
We created another object which would enable use to perform operations on our node object.
The second object we created enabled us to insert/push, remove/pop and traverse the stack.

The key note while implementing a stack data structure using linked list is to keep track of the top node or else we might create nodes that aren’t interlinked but segregated.

I hope I was able to deliver quality with this brief article.