How to implement stack and queue using linked list

Data Structures are used to store large amounts of data in an efficient and categorical manner. For example in lists, arrays, tuples, dictionaries, and sets.

We are now gonna look into Linear Data Structures:

  • Linked Lists
  • Stacks
  • Queues

Linked list

A linked list consists of nodes/elements where each element contains a data field and a reference to the next node in the list.

# the node class is used to create an element holder and the respective reference pointers.
class Node:
def __init__(self, data=None, next=None):
self.data = data # the value part of the node
self.next = next # the pointer part of the node
# this is the main class that that is used to create the linked list data struture which contains many functions.
class LinkedList:
def __init__(self):
self.head = None # creating an empty linked list
# the below function is used to insert the nodes/element holders at the begining of the list
def Insert_at_beginning(self, data):
# creating a node with a data part and the pointer to the next value i.e . the now head
node = Node(data, self.head)
self.head = node # now the head points towards the new inserted element pushing the previous element behind
# the below function is used to insert the nodes/element holders at the ending of the list
def Insert_at_ending(self, data):
if self.head is None:
self.head = Node(data)
return
itr = self.head
while itr.next:
itr = itr.next
itr.next = Node(data)
# this function inserts a list of values to the linked list at the end
def insert_values(self, value_list):
self.head = None
for value in value_list:
self.Insert_at_ending(value)
# this function is used to get the length of the linked list.
def get_length(self):
count = 0
itr = self.head
while itr:
count += 1
itr = itr.next
return count
# the below function is used to insert a value just after an existing value in the list
def insert_after_value(self, data_after, data_to_insert):
if self.head is None:
return
if self.head.data == data_after:
self.head.next = Node(data_to_insert, self.head.next)
return
itr = self.head
while itr:
if itr.data == data_after:
itr.next = Node(data_to_insert, itr.next)
break
itr = itr.next
# the below function is used to remove a particular value which in present in the list.
def remove_by_value(self, data):
if self.head is None:
return
if self.head.data == data:
self.head = self.head.next
return
itr = self.head
while itr.next:
if itr.next.data == data:
itr.next = itr.next.next
break
itr = itr.next
# this function simply orints all the values present inthe list.
def display(self):
if self.head is None:
print('list is empty')
return
itr = self.head
llstr = ''
while itr:
llstr += str(itr.data) + '-->'
itr = itr.next
print(llstr)
if __name__ == "__main__":
ll = LinkedList()
ll.insert_values(["banana", "mango", "grapes", "orange"])
ll.display()
ll.insert_after_value("mango", "apple") # insert apple after mango
ll.display()
ll.remove_by_value("orange") # remove orange from linked list
ll.display()
ll.remove_by_value("figs")
ll.display()
ll.remove_by_value("banana")
ll.remove_by_value("mango")
ll.remove_by_value("apple")
ll.remove_by_value("grapes")
ll.display()

Stacks using linked list

A stack is a linear data structure that follows a specific order.

The order may be:

  • LIFO(Last In First Out)
  • FILO(First In Last Out)

Here, you can only retrieve whichever element you enter first at the end and not in between.

There are many ways to implement a stack data structure, but we are gonna do it using a linked list.

# the node class is used to create an element holder and the respective reference pointers.
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
# this is the main class that that is used to create queues data struture which contains many functions.
class Stack:
# this is automatically class when an instance of the class is called.
def __init__(self):
self.top = None
# the below function is used to append an value on the top of the stack.
def push(self, data):
if self.top is None:
self.top = Node(data, None)
return
self.top = Node(data, self.top)
# the below function is used to remove an value from the top of the stack.
def pop(self):
if self.top is None:
return
temp = self.top
if self.top is not None:
self.top = self.top.next
temp.next = None
return temp.data
# the below function returns the value on the top of the stack.
def peek(self):
return self.top.data
# this function simply clears the whole stack.
def clearstack(self):
self.top = None
# the below tells us if the stack is empty.
def emptystack(self):
if self.top is None:
return True
return False
# this below function is used print out the stacks.
def display(self):
itr = self.top
sstr = ' '
while itr:
sstr += str(itr.data) + '-->'
itr = itr.next
print(sstr)
if __name__ == "__main__":
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(40)
stack.peek()
stack.display()
stack.pop()
stack.push(30)
stack.display()
stack.clearstack()
stack.display()

Queues using linked list

A queue is also a linear structure that follows a specific order.

The order is:

  • First In First Out (FIFO)

The difference between stacks and queues is how they are removed. In a stack, we remove the item most recently added; in a queue, we remove the item least recently added.

There are many ways to implement a queue data structure, but we are going to do it using a linked list.

# the node class is used to create an element holder and the respective reference pointers.
class Node:
def __init__(self, data=None, next=None, prev=None):
self.data = data #creating a storage for assigning value
self.next = next #pointer to the next value
self.prev = prev #pointer to the already existing previous value.
# this is the main class that that is used to create queues data struture which contains many functions.
class Queue:
# this is automatically class when an instance of the class is called.
def __init__(self):
self.front = self.rear = None
# this below function is used to append a value at the end of the queue which is similar to a late comer joins at the end.
def enqueue(self, data):
if self.rear is None:
self.front = self.rear = Node(data, None)
return
self.rear.next = Node(data, None)
self.rear.next.prev = self.rear
self.rear = self.rear.next
# this below function is used remove a value from the start of the queue.
def dequeue(self):
if self.front is None:
raise Exception('empty queue')
temp = self.front.data
self.front = self.front.next
if self.front is None:
self.rear = None
return
self.front.prev = None
return temp
# this code is used to clear the whole queue
def clearqueue(self):
self.front = self.rear = None
# this is used to check idf the queue in empty or not.
def emptyqueue(self):
if self.front is None:
return True
return False
# this is used to print queues
def display(self):
itr = self.front
sstr = ' '
while itr:
sstr += str(itr.data) + '-->'
itr = itr.next
print(sstr)
if __name__ == "__main__":
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
queue.display()
queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.display()
queue.enqueue(40)
queue.enqueue(50)
queue.enqueue(60)
queue.display()
queue.clearqueue()
queue.display()

Free Resources