Linked Lists, Queue & Stack in Python

Today I am going to show Creating Linked list, Queue and Stack  data structure using python .

In my previous post I show how to implement Priority Queue using Python.

Linked List

Like in the game Treasure hunt, you find the first clue, use the information from that and find the second clue and the message there leads you to the third.

Similarly, Linked Lists is a series of connected “nodes” that contains the “address” of the next node and Store any given data.

Implementing the above logic in python code

	# A simple Python program on linked list
	# Node class
	class Node:
	# Function to initialise the node object
	def __init__(self, data):
	self.data = data # Assign data
	self.next = None # Initialize next as null
	# Linked List class contains a Node object
	class LinkedList:
	# Function to initialize head
	def __init__(self):
	self.head = None
	# This function prints contents of linked list
	# starting from head
	def printList(self):
	temp = self.head
	while (temp):
	print(temp.data),
	temp = temp.next
	# Code execution starts here
	if __name__=='__main__':
	# Start with the empty list
	llist = LinkedList()
	llist.head = Node(1)
	second = Node(2)
	third = Node(3)
	llist.head.next = second; # Link first node with second
	second.next = third; # Link second node with the third node
	llist.printList()

view raw LinkedListNode.py hosted with ❤ by GitHub

Queue
Queue is an open-ended data structure. One end is always used to insert data (enqueue) and the other is used to eliminate data (dequeue). 
This adapts FIFO (First In First Out) methodology i.e the item stored first is used first
We can use container module collections in python to initialize a queue by giving the size.

• Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition – Time Complexity : O(1)
• Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition – Time Complexity : O(1)
• Front: Get the front item from queue – Time Complexity : O(1)
• Rear: Get the last item from queue – Time Complexity : O(1)

Stack
A stack is an ordered list in which, insertion and deletion can be performed only at one end that is called top. 
Stacks are sometimes called as Last-In-First-Out (LIFO) lists i.e. the element which is inserted first in the stack, will be deleted last from the stack.

• empty() – Returns whether the stack is empty – Time Complexity : O(1)
• size() – Returns the size of the stack – Time Complexity : O(1)
• top() – Returns a reference to the top most element of the stack – Time Complexity : O(1)
• push(g) – Adds the element ‘g’ at the top of the stack – Time Complexity : O(1)
• pop() – Deletes the top most element of the stack – Time Complexity : O(1)

	class Stack:
	def __init__(self):
	self.items = []
	def isEmpty(self):
	return self.items == []
	def push(self, item):
	self.items.append(item)
	def pop(self):
	return self.items.pop()
	def size(self):
	return len(self.items)
	stacks = Stack()
	stacks.push("April")
	stacks.push("May")
	stacks.push("June")
	print(stacks.items)
	print(stacks.pop())

view raw StackExample.py hosted with ❤ by GitHub

Thanks
Saurabh Sharma
Happy Coding !!!