Data Structure using Python
### MAPS – based on Dictionaries
import collections
d1 = {“name”:“Sachin”,“city”:“Mumbai”,“age”:50}
d2 = {“sports”:“Hockey”,“team”:“India”,“Goals”:322}
output = collections.ChainMap(d1,d2)
print(output.maps)
print(“Keys = “,list(output.keys()))
print(“Values = “,list(output.values()))
print(“Items = “,list(output.items()))
# in operator
print(“Is city in the map? “,“city” in output)
print(“Value at city = “,output[“city”])
#update
output[“city”] = “Hyderabad”
print(output)
import collections
d1 = {“name”:“Sachin”,“city”:“Mumbai”,“age”:50}
d2 = {“sports”:“Hockey”,“team”:“India”,“Goals”:322}
output = collections.ChainMap(d1,d2)
print(output.maps)
print(“Keys = “,list(output.keys()))
print(“Values = “,list(output.values()))
print(“Items = “,list(output.items()))
# in operator
print(“Is city in the map? “,“city” in output)
print(“Value at city = “,output[“city”])
#update
output[“city”] = “Hyderabad”
print(output)
# LINKED LIST: sequence of data elements
## Properties: Traverse, Insert & Delete
## Insert: Begining, Middle, End
class Node:
def __init__(self,data=None):
self.value = data
self.nextnode = None
class ListPointer:
def __init__(self):
self.head = None
#function to traverse through the Linked List
def traverse(self):
header = self.head
val=[]
while header is not None:
#print(“Value from the Linked List:”,header.value)
val.append(header.value)
header = header.nextnode
return val
# Inserting a node to the beginning of the linked List
def Insert_Beginning(self,newdata):
NewNode = Node(newdata)
NewNode.nextnode = self.head
self.head = NewNode
#Inserting at the end
def Insert_End(self,newdata):
NewNode = Node(newdata) #nextnode is null
#check if there is existing node or not
if self.head is None:
self.head = NewNode
return
last = self.head
while last.nextnode is not None:
last = last.nextnode
last.nextnode = NewNode
#Inserting Between 2 Nodes
def Insert_Between(self, betweennode, newdata):
if betweennode is None:
print(“The between Node is not available!”)
return
NewNode = Node(newdata)
NewNode.nextnode = betweennode.nextnode
betweennode.nextnode = NewNode
#Remove a node
def Remove(self,value):
# check for 3 conditions – First, Inbetween and Last
return
if __name__==“__main__”:
list = ListPointer() # created header
list.head = Node(“January”) # first node with value January and pointing to null
n2 = Node(“February”) # second node with value February and pointing to null
list.head.nextnode = n2 #first node is now linked to second node
n3 = Node(“March”) #third node with value March and pointing to null
n2.nextnode = n3 #second node is now linked to third node
# traversing through the list
print(list.traverse())
# add at the beginning
list.Insert_Beginning(“December”)
# traversing through the list
print(list.traverse())
#Add April at the end
list.Insert_End(“April”)
print(list.traverse())
list.Insert_Between(n3,“November”)
print(list.traverse())
#remove
## Properties: Traverse, Insert & Delete
## Insert: Begining, Middle, End
class Node:
def __init__(self,data=None):
self.value = data
self.nextnode = None
class ListPointer:
def __init__(self):
self.head = None
#function to traverse through the Linked List
def traverse(self):
header = self.head
val=[]
while header is not None:
#print(“Value from the Linked List:”,header.value)
val.append(header.value)
header = header.nextnode
return val
# Inserting a node to the beginning of the linked List
def Insert_Beginning(self,newdata):
NewNode = Node(newdata)
NewNode.nextnode = self.head
self.head = NewNode
#Inserting at the end
def Insert_End(self,newdata):
NewNode = Node(newdata) #nextnode is null
#check if there is existing node or not
if self.head is None:
self.head = NewNode
return
last = self.head
while last.nextnode is not None:
last = last.nextnode
last.nextnode = NewNode
#Inserting Between 2 Nodes
def Insert_Between(self, betweennode, newdata):
if betweennode is None:
print(“The between Node is not available!”)
return
NewNode = Node(newdata)
NewNode.nextnode = betweennode.nextnode
betweennode.nextnode = NewNode
#Remove a node
def Remove(self,value):
# check for 3 conditions – First, Inbetween and Last
return
if __name__==“__main__”:
list = ListPointer() # created header
list.head = Node(“January”) # first node with value January and pointing to null
n2 = Node(“February”) # second node with value February and pointing to null
list.head.nextnode = n2 #first node is now linked to second node
n3 = Node(“March”) #third node with value March and pointing to null
n2.nextnode = n3 #second node is now linked to third node
# traversing through the list
print(list.traverse())
# add at the beginning
list.Insert_Beginning(“December”)
# traversing through the list
print(list.traverse())
#Add April at the end
list.Insert_End(“April”)
print(list.traverse())
list.Insert_Between(n3,“November”)
print(list.traverse())
#remove
# LINKED LIST: sequence of data elements
## Properties: Traverse, Insert & Delete
## Insert: Begining, Middle, End
class Node:
def __init__(self,data=None):
self.value = data
self.nextnode = None
class ListPointer:
def __init__(self):
self.head = None
#function to traverse through the Linked List
def traverse(self):
header = self.head
val=[]
while header is not None:
#print(“Value from the Linked List:”,header.value)
val.append(header.value)
header = header.nextnode
return val
# Inserting a node to the beginning of the linked List
def Insert_Beginning(self,newdata):
NewNode = Node(newdata)
NewNode.nextnode = self.head
self.head = NewNode
#Inserting at the end
def Insert_End(self,newdata):
NewNode = Node(newdata) #nextnode is null
#check if there is existing node or not
if self.head is None:
self.head = NewNode
return
last = self.head
while last.nextnode is not None:
last = last.nextnode
last.nextnode = NewNode
#Inserting Between 2 Nodes
def Insert_Between(self, betweennode, newdata):
if betweennode is None:
print(“The between Node is not available!”)
return
NewNode = Node(newdata)
NewNode.nextnode = betweennode.nextnode
betweennode.nextnode = NewNode
#Remove a node
def Remove(self,value):
# check for 3 conditions – First, Inbetween and Last
header = self.head
if header is None:
# Do nothing – linked list is blank
return
if header is not None:
if header.value == value: #first node in the list to be removed
self.head = header.nextnode
header = None
while header is not None:
if header.value == value:
break
previous = header #
header = header.nextnode
if header ==None: #you have reached last node and still value not matched
#simply it means no value matched
print(“Value not found in the linked list”)
return
previous.nextnode = header.nextnode
header = None
return
if __name__==“__main__”:
list = ListPointer() # created header
list.head = Node(“January”) # first node with value January and pointing to null
n2 = Node(“February”) # second node with value February and pointing to null
list.head.nextnode = n2 #first node is now linked to second node
n3 = Node(“March”) #third node with value March and pointing to null
n2.nextnode = n3 #second node is now linked to third node
# traversing through the list
print(list.traverse())
# add at the beginning
list.Insert_Beginning(“December”)
# traversing through the list
print(list.traverse())
#Add April at the end
list.Insert_End(“April”)
print(list.traverse())
list.Insert_Between(n3,“November”)
print(list.traverse())
#remove
list.Remove(‘December’) # first value
print(list.traverse())
list.Remove(“March1”)
print(list.traverse())
## Properties: Traverse, Insert & Delete
## Insert: Begining, Middle, End
class Node:
def __init__(self,data=None):
self.value = data
self.nextnode = None
class ListPointer:
def __init__(self):
self.head = None
#function to traverse through the Linked List
def traverse(self):
header = self.head
val=[]
while header is not None:
#print(“Value from the Linked List:”,header.value)
val.append(header.value)
header = header.nextnode
return val
# Inserting a node to the beginning of the linked List
def Insert_Beginning(self,newdata):
NewNode = Node(newdata)
NewNode.nextnode = self.head
self.head = NewNode
#Inserting at the end
def Insert_End(self,newdata):
NewNode = Node(newdata) #nextnode is null
#check if there is existing node or not
if self.head is None:
self.head = NewNode
return
last = self.head
while last.nextnode is not None:
last = last.nextnode
last.nextnode = NewNode
#Inserting Between 2 Nodes
def Insert_Between(self, betweennode, newdata):
if betweennode is None:
print(“The between Node is not available!”)
return
NewNode = Node(newdata)
NewNode.nextnode = betweennode.nextnode
betweennode.nextnode = NewNode
#Remove a node
def Remove(self,value):
# check for 3 conditions – First, Inbetween and Last
header = self.head
if header is None:
# Do nothing – linked list is blank
return
if header is not None:
if header.value == value: #first node in the list to be removed
self.head = header.nextnode
header = None
while header is not None:
if header.value == value:
break
previous = header #
header = header.nextnode
if header ==None: #you have reached last node and still value not matched
#simply it means no value matched
print(“Value not found in the linked list”)
return
previous.nextnode = header.nextnode
header = None
return
if __name__==“__main__”:
list = ListPointer() # created header
list.head = Node(“January”) # first node with value January and pointing to null
n2 = Node(“February”) # second node with value February and pointing to null
list.head.nextnode = n2 #first node is now linked to second node
n3 = Node(“March”) #third node with value March and pointing to null
n2.nextnode = n3 #second node is now linked to third node
# traversing through the list
print(list.traverse())
# add at the beginning
list.Insert_Beginning(“December”)
# traversing through the list
print(list.traverse())
#Add April at the end
list.Insert_End(“April”)
print(list.traverse())
list.Insert_Between(n3,“November”)
print(list.traverse())
#remove
list.Remove(‘December’) # first value
print(list.traverse())
list.Remove(“March1”)
print(list.traverse())
# Building Stack
# Push (last) and Pop (last)
# assignment: create a parent class for both Stack and Queue
## and implement display function
class Stack:
def __init__(self):
self.stack = []
def push(self, value):
#do not accept duplicate values
self.stack.append(value)
return
def pop(self):
# what is there is no element to remove – handle
self.stack.pop(-1)
return
def display(self):
#print(self.stack)
# handle empty
if len(self.stack) !=0:
return self.stack
class Queue:
def __init__(self):
self.queue = []
def add(self,value):
if value in self.queue:
print(“This value is already in Queue”)
return
self.queue.append(value)
def remove(self):
if len(self.queue)>0:
self.queue.pop(0)
else:
print(“Queue is empty!”)
def display(self):
if len(self.queue) !=0:
return self.queue
class DoubleLinkedList:
def __init__(self,data):
self.data = data
self.next = None
self.prev = None
def LRTraverse(self):
pass
def RLTravserse(self):
pass
if __name__ ==“__main__”:
import june2023 as st
mystack = st.Stack()
mystack.push(55)
print(mystack.display())
mystack.push(75)
print(mystack.display())
mystack.pop()
print(mystack.display())
myq = st.Queue()
myq.add(55)
print(myq.display())
myq.add(75)
print(myq.display())
myq.remove()
print(myq.display())
## DEQUEUE – Double ended queue
import collections
names = [‘Sachin’, ‘Virat’, ‘Dhoni’]
dq = collections.deque(names)
dq.pop()
print(dq)
dq.popleft()
print(dq)
dq.append()
# Push (last) and Pop (last)
# assignment: create a parent class for both Stack and Queue
## and implement display function
class Stack:
def __init__(self):
self.stack = []
def push(self, value):
#do not accept duplicate values
self.stack.append(value)
return
def pop(self):
# what is there is no element to remove – handle
self.stack.pop(-1)
return
def display(self):
#print(self.stack)
# handle empty
if len(self.stack) !=0:
return self.stack
class Queue:
def __init__(self):
self.queue = []
def add(self,value):
if value in self.queue:
print(“This value is already in Queue”)
return
self.queue.append(value)
def remove(self):
if len(self.queue)>0:
self.queue.pop(0)
else:
print(“Queue is empty!”)
def display(self):
if len(self.queue) !=0:
return self.queue
class DoubleLinkedList:
def __init__(self,data):
self.data = data
self.next = None
self.prev = None
def LRTraverse(self):
pass
def RLTravserse(self):
pass
if __name__ ==“__main__”:
import june2023 as st
mystack = st.Stack()
mystack.push(55)
print(mystack.display())
mystack.push(75)
print(mystack.display())
mystack.pop()
print(mystack.display())
myq = st.Queue()
myq.add(55)
print(myq.display())
myq.add(75)
print(myq.display())
myq.remove()
print(myq.display())
## DEQUEUE – Double ended queue
import collections
names = [‘Sachin’, ‘Virat’, ‘Dhoni’]
dq = collections.deque(names)
dq.pop()
print(dq)
dq.popleft()
print(dq)
dq.append()
#SORTING: BUBBLE, LINEAR, INSERTION, SHELL, SELECTION
list1 = [10,30,70,20,80,40,60,50]
for i in range(len(list1)-1):
for idx in range(0,len(list1)-1-i):
if list1[idx] > list1[idx+1]:
list1[idx],list1[idx+1] =list1[idx+1], list1[idx]
print(“Bubble Sorted List = “,list1)
list1 = [10,30,70,20,80,40,60,50]
for i in range(len(list1)-1):
for idx in range(i+1,len(list1)):
if list1[i] > list1[idx]:
list1[i],list1[idx] =list1[idx], list1[i]
print(“Linear Sorted List = “,list1)
list1 = [10,30,70,20,80,40,60,50]
def merge(left,right):
result = []
while len(left)!=0 and len(right)!=0:
if left[0] > right[0]:
result.append(right[0])
right.remove(right[0])
else:
result.append(left[0])
left.remove(left[0])
if len(left) ==0:
result+=right
else:
result+=left
return result
def divide(list1):
if len(list1)<2:
#print(“Merge Sort: “,list1)
return list1
else:
center = len(list1) //2
left_list = list1[:center]
right_list = list1[center:]
left_list = divide(left_list)
right_list = divide(right_list)
return list(merge(left_list,right_list))
print(“List 1 before Merge Sort: “,list1)
list1 = divide(list1)
print(“List 1 after Merge Sort: “,list1)
list1 = [10,30,70,20,80,40,60,50]
for i in range(len(list1)-1):
for idx in range(0,len(list1)-1-i):
if list1[idx] > list1[idx+1]:
list1[idx],list1[idx+1] =list1[idx+1], list1[idx]
print(“Bubble Sorted List = “,list1)
list1 = [10,30,70,20,80,40,60,50]
for i in range(len(list1)-1):
for idx in range(i+1,len(list1)):
if list1[i] > list1[idx]:
list1[i],list1[idx] =list1[idx], list1[i]
print(“Linear Sorted List = “,list1)
list1 = [10,30,70,20,80,40,60,50]
def merge(left,right):
result = []
while len(left)!=0 and len(right)!=0:
if left[0] > right[0]:
result.append(right[0])
right.remove(right[0])
else:
result.append(left[0])
left.remove(left[0])
if len(left) ==0:
result+=right
else:
result+=left
return result
def divide(list1):
if len(list1)<2:
#print(“Merge Sort: “,list1)
return list1
else:
center = len(list1) //2
left_list = list1[:center]
right_list = list1[center:]
left_list = divide(left_list)
right_list = divide(right_list)
return list(merge(left_list,right_list))
print(“List 1 before Merge Sort: “,list1)
list1 = divide(list1)
print(“List 1 after Merge Sort: “,list1)
list1 = [80,70,60,50,40,30,20,10]
#for k in range(len(list1)-1):
for i in range(1,len(list1)):
j = i-1 #represents sorted array
next = list1[i] # unsorted array
while list1[j] > next and j>=0:
list1[j+1] = list1[j]
j=j-1
list1[j+1] = next
print(“Insertion Sort: “,list1)
#Shell sort
list1 = [80,70,60,50,40,30,20,10]
gap = len(list1) // 2
while gap >0:
for i in range(gap,len(list1)):
value = list1[i]
j=i #tracker
while j>=gap and list1[j-gap] > value:
list1[j] = list1[j-gap]
j=j-gap
list1[j] = value
gap=gap//2
print(list1)
## Shell sort: o(n square) BEST O(nlongn) worst case
#for k in range(len(list1)-1):
for i in range(1,len(list1)):
j = i-1 #represents sorted array
next = list1[i] # unsorted array
while list1[j] > next and j>=0:
list1[j+1] = list1[j]
j=j-1
list1[j+1] = next
print(“Insertion Sort: “,list1)
#Shell sort
list1 = [80,70,60,50,40,30,20,10]
gap = len(list1) // 2
while gap >0:
for i in range(gap,len(list1)):
value = list1[i]
j=i #tracker
while j>=gap and list1[j-gap] > value:
list1[j] = list1[j-gap]
j=j-gap
list1[j] = value
gap=gap//2
print(list1)
## Shell sort: o(n square) BEST O(nlongn) worst case
# Search
l1 = [10,50,30,70,40,20]
num = 10
idx = 0
found = False
for i in range(len(l1)):
if num==l1[i]:
found=True
idx = i
break
if found:
print(f”{num} is in the list at {idx}“)
else:
print(f”{num} is not in the list”)
#
num = 10
idx = 0
found = False
while idx<len(l1) and found is False:
if num==l1[idx]:
found=True
else:
idx+=1
if found:
print(f”{num} is in the list at {idx}“)
else:
print(f”{num} is not in the list”)
# Binary Search: works on sorted list
l1 = [10,50,30,70,40,20]
l1.sort() #sort the list before use
print(l1)
num = 10
idx = 0
found = False
low,high = 0, len(l1)
while low<high and found is False:
mid = (low+high)//2
if l1[mid] == num:
idx=mid
found=True
elif l1[mid] > num:
high = mid-1
else:
low = mid+1
if found:
print(f”Binary Search: {num} is in the list at {idx}“)
else:
print(f”Binary Search: {num} is not in the list”)
## BINARY TREE
class Node:
def __init__(self,key):
self.value = key
self.left = None
self.right = None
#Preorder traversal
def pretraverse(self):
print(self.value, end=“, “)
if self.left:
self.left.pretraverse()
if self.right:
self.right.pretraverse()
def intraverse(self):
if self.left:
self.left.intraverse()
print(self.value, end=“, “)
if self.right:
self.right.intraverse()
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.pretraverse()
print(“\n In traverse:”)
root.intraverse()
l1 = [10,50,30,70,40,20]
num = 10
idx = 0
found = False
for i in range(len(l1)):
if num==l1[i]:
found=True
idx = i
break
if found:
print(f”{num} is in the list at {idx}“)
else:
print(f”{num} is not in the list”)
#
num = 10
idx = 0
found = False
while idx<len(l1) and found is False:
if num==l1[idx]:
found=True
else:
idx+=1
if found:
print(f”{num} is in the list at {idx}“)
else:
print(f”{num} is not in the list”)
# Binary Search: works on sorted list
l1 = [10,50,30,70,40,20]
l1.sort() #sort the list before use
print(l1)
num = 10
idx = 0
found = False
low,high = 0, len(l1)
while low<high and found is False:
mid = (low+high)//2
if l1[mid] == num:
idx=mid
found=True
elif l1[mid] > num:
high = mid-1
else:
low = mid+1
if found:
print(f”Binary Search: {num} is in the list at {idx}“)
else:
print(f”Binary Search: {num} is not in the list”)
## BINARY TREE
class Node:
def __init__(self,key):
self.value = key
self.left = None
self.right = None
#Preorder traversal
def pretraverse(self):
print(self.value, end=“, “)
if self.left:
self.left.pretraverse()
if self.right:
self.right.pretraverse()
def intraverse(self):
if self.left:
self.left.intraverse()
print(self.value, end=“, “)
if self.right:
self.right.intraverse()
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.pretraverse()
print(“\n In traverse:”)
root.intraverse()
# Quick sort: divide and conquer
## pick a pivot element:
# 1. first number is pivot
# 2. last number is pivot
# divide the list based on this pivot value:
# left list (numbers < pivot) and right list (numbers > pivot)
l1 = [90,80,70,60,50,40,30,20,10]
def QuickSortAlgo(l1, low,high):
if low < high:
pivot = l1[high]
##logic to partition the dataset into 2 parts
i=low-1
for j in range(low, high):
if l1[j] <= pivot:
i+=1
l1[i],l1[j] = l1[j],l1[i]
l1[i+1], l1[high] = l1[high], l1[i+1]
pivot = i+1
##
#Partioning the left sub-list
QuickSortAlgo(l1,low,pivot-1)
# Partioning the right sub-list
QuickSortAlgo(l1, pivot + 1, high)
size = len(l1)
QuickSortAlgo(l1, 0,size-1)
print(“Sorted list: \n“,l1)
def sum_n(n):
if n==0:
return 0
else:
return n + sum_n(n-1)
ans = sum_n(10)
print(ans)
# 10 + 9 + 8 + .. 0
def fibo(n):
if n <=1:
return n
else:
return fibo(n-2) + fibo(n-1)
# fibo(4)= fibo(2) + fibo(3) = 0 + 1 + 1 + 0 + 1 = 3
for i in range(15):
print(fibo(i))
## pick a pivot element:
# 1. first number is pivot
# 2. last number is pivot
# divide the list based on this pivot value:
# left list (numbers < pivot) and right list (numbers > pivot)
l1 = [90,80,70,60,50,40,30,20,10]
def QuickSortAlgo(l1, low,high):
if low < high:
pivot = l1[high]
##logic to partition the dataset into 2 parts
i=low-1
for j in range(low, high):
if l1[j] <= pivot:
i+=1
l1[i],l1[j] = l1[j],l1[i]
l1[i+1], l1[high] = l1[high], l1[i+1]
pivot = i+1
##
#Partioning the left sub-list
QuickSortAlgo(l1,low,pivot-1)
# Partioning the right sub-list
QuickSortAlgo(l1, pivot + 1, high)
size = len(l1)
QuickSortAlgo(l1, 0,size-1)
print(“Sorted list: \n“,l1)
def sum_n(n):
if n==0:
return 0
else:
return n + sum_n(n-1)
ans = sum_n(10)
print(ans)
# 10 + 9 + 8 + .. 0
def fibo(n):
if n <=1:
return n
else:
return fibo(n-2) + fibo(n-1)
# fibo(4)= fibo(2) + fibo(3) = 0 + 1 + 1 + 0 + 1 = 3
for i in range(15):
print(fibo(i))
def toh_rec(n_disk, source,inter, target):
if n_disk ==1:
print(f”Move disk 1 from Tower {source} to Tower {target}“)
return
toh_rec(n_disk-1, source,target, inter)
print(f”Move disk {n_disk} from Tower {source} to Tower {target}“)
toh_rec(n_disk – 1, inter, source, target)
disks = 3
toh_rec(disks, “Source”,“Inter”,“Target”)
## Backtracking
# CIRCULAR DOUBLY LINKED LIST
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class CircularDLL:
def __init__(self):
self.first = None
def getnode(self,index):
current = self.first
for i in range(index):
current = current.next
if current == self.first:
return None
return current
def insertafter(self, beforenode, newnode):
newnode.prev = beforenode
newnode.next = beforenode.next
newnode.next.prev = newnode
beforenode.next = newnode
def insertbefore(self,beforenode, node):
self.insertafter(beforenode.prev, node)
def insertbegin(self,node):
self.insertend(node)
self.first = node
def insertend(self,node):
if self.first is None:
self.first = node
node.next = node
node.prev = node
else:
self.insertafter(self.first.prev)
def remove(self):
pass
def display(self):
pass
#Main Menu
print(“Type the operation you want to perform: “)
print(“insert <data> after <index>”)
print(“insert <data> before <index>”)
print(“insert <data> at beginning”)
print(“insert <data> at end”)
print(“remove <index>”)
print(“display”)
print(“quit”)
cdll = CircularDLL()
while True:
print(“The values in the Circular Doubly Linked List are: “)
cdll.display()
ch=input(“What do you want to do?”)
ch = ch.lower().strip().split()
print(“CH = “,ch)
if ch[0]==“insert”:
value = int(ch[1])
newNode = Node(value)
if ch[2]==“after”:
data = cdll.getnode(int(ch[3]))
if data is None:
print(“Given index doesnt exist”)
else:
cdll.insertafter(data, newNode)
elif ch[2]==“before”:
cdll.insertbefore(newNode)
elif ch[2]==“at”:
if ch[3]==“beginning”:
cdll.insertbegin(newNode)
elif ch[3]==“end”:
cdll.insertend(newNode)
else:
print(“Error! Try again!”)
continue
else:
print(“Error! Try again!”)
continue
elif ch[0]==“remove”:
idx = int(ch[1])
idx_node = cdll.getnode(idx)
if idx_node is None:
print(“No such index, cant perform remove option.”)
continue
# if condition is false
cdll.remove()
elif ch[0]==“display”:
print(“The values in the Circular Doubly Linked List are: “)
cdll.display()
elif ch[0]==“quit”:
break
else:
print(“Invalid option, try again!”)
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class CircularDLL:
def __init__(self):
self.first = None
def getnode(self,index):
current = self.first
for i in range(index):
current = current.next
if current == self.first:
return None
return current
def insertafter(self, beforenode, newnode):
newnode.prev = beforenode
newnode.next = beforenode.next
newnode.next.prev = newnode
beforenode.next = newnode
def insertbefore(self,beforenode, node):
self.insertafter(beforenode.prev, node)
def insertbegin(self,node):
self.insertend(node)
self.first = node
def insertend(self,node):
if self.first is None:
self.first = node
node.next = node
node.prev = node
else:
self.insertafter(self.first.prev)
def remove(self):
pass
def display(self):
pass
#Main Menu
print(“Type the operation you want to perform: “)
print(“insert <data> after <index>”)
print(“insert <data> before <index>”)
print(“insert <data> at beginning”)
print(“insert <data> at end”)
print(“remove <index>”)
print(“display”)
print(“quit”)
cdll = CircularDLL()
while True:
print(“The values in the Circular Doubly Linked List are: “)
cdll.display()
ch=input(“What do you want to do?”)
ch = ch.lower().strip().split()
print(“CH = “,ch)
if ch[0]==“insert”:
value = int(ch[1])
newNode = Node(value)
if ch[2]==“after”:
data = cdll.getnode(int(ch[3]))
if data is None:
print(“Given index doesnt exist”)
else:
cdll.insertafter(data, newNode)
elif ch[2]==“before”:
cdll.insertbefore(newNode)
elif ch[2]==“at”:
if ch[3]==“beginning”:
cdll.insertbegin(newNode)
elif ch[3]==“end”:
cdll.insertend(newNode)
else:
print(“Error! Try again!”)
continue
else:
print(“Error! Try again!”)
continue
elif ch[0]==“remove”:
idx = int(ch[1])
idx_node = cdll.getnode(idx)
if idx_node is None:
print(“No such index, cant perform remove option.”)
continue
# if condition is false
cdll.remove()
elif ch[0]==“display”:
print(“The values in the Circular Doubly Linked List are: “)
cdll.display()
elif ch[0]==“quit”:
break
else:
print(“Invalid option, try again!”)
# CIRCULAR DOUBLY LINKED LIST
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class CircularDLL:
def __init__(self):
self.first = None
def getnode(self,index):
current = self.first
for i in range(index):
current = current.next
if current == self.first:
return None
return current
def insertafter(self, beforenode, newnode):
newnode.prev = beforenode
newnode.next = beforenode.next
newnode.next.prev = newnode
beforenode.next = newnode
def insertbefore(self,beforenode, node):
self.insertafter(beforenode.prev, node)
def insertbegin(self,node):
self.insertend(node)
self.first = node
def insertend(self,node):
if self.first is None:
self.first = node
node.next = node
node.prev = node
else:
self.insertafter(self.first.prev,node)
def remove(self, node):
if self.first.next == self.first:
self.first = None
else:
node.prev.next = node.next
node.next.prev = node.prev
if self.first == node:
self.first = node.next # node.prev
def display(self):
if self.first is None:
print(“NO VALUES”)
return
current = self.first
print(“\n“)
while True:
print(current.data, end=‘, ‘)
current = current.next
if current == self.first:
break
print(“\n“)
#Main Menu
print(“Type the operation you want to perform: “)
print(“insert <data> after <index>”)
print(“insert <data> before <index>”)
print(“insert <data> at beginning”)
print(“insert <data> at end”)
print(“remove <index>”)
print(“display”)
print(“quit”)
cdll = CircularDLL()
while True:
print(“The values in the Circular Doubly Linked List are: “)
cdll.display()
ch=input(“What do you want to do?”)
ch = ch.lower().strip().split()
print(“CH = “,ch)
if ch[0]==“insert”:
value = int(ch[1])
newNode = Node(value)
if ch[2]==“after”:
data = cdll.getnode(int(ch[3]))
if data is None:
print(“Given index doesnt exist”)
else:
cdll.insertafter(data, newNode)
elif ch[2]==“before”:
ref_node = cdll.getnode(int(ch[3]))
cdll.insertbefore(ref_node,newNode)
elif ch[2]==“at”:
if ch[3]==“beginning”:
cdll.insertbegin(newNode)
elif ch[3]==“end”:
cdll.insertend(newNode)
else:
print(“Error! Try again!”)
continue
else:
print(“Error! Try again!”)
continue
elif ch[0]==“remove”:
idx = int(ch[1])
idx_node = cdll.getnode(idx)
if idx_node is None:
print(“No such index, cant perform remove option.”)
continue
# if condition is false
cdll.remove(idx_node)
elif ch[0]==“display”:
print(“The values in the Circular Doubly Linked List are: “)
cdll.display()
elif ch[0]==“quit”:
break
else:
print(“Invalid option, try again!”)
## Assignment: Modify above code to create CircularQueue
## ## PRIORITY QUEUE ## ##
#Priority Queue
from queue import PriorityQueue
apq = PriorityQueue()
apq.put(50)
apq.put(30)
apq.put(40)
print(“Printing elements of Priority Queue:\n“)
while not apq.empty():
print(apq.get(), end=“, “)
print()
print(“Adding values with Priority:”)
apq = PriorityQueue()
apq.put((5, “Study”)) # combination of priority and values are added as tuple
apq.put((2, “Sleep”))
apq.put((9, “Eat”))
apq.put((4, “Play”))
print(“2. Printing elements of Priority Queue:\n“)
while not apq.empty():
print(apq.get(), end=“, “)
print()
### ### ### ###
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class CircularDLL:
def __init__(self):
self.first = None
def getnode(self,index):
current = self.first
for i in range(index):
current = current.next
if current == self.first:
return None
return current
def insertafter(self, beforenode, newnode):
newnode.prev = beforenode
newnode.next = beforenode.next
newnode.next.prev = newnode
beforenode.next = newnode
def insertbefore(self,beforenode, node):
self.insertafter(beforenode.prev, node)
def insertbegin(self,node):
self.insertend(node)
self.first = node
def insertend(self,node):
if self.first is None:
self.first = node
node.next = node
node.prev = node
else:
self.insertafter(self.first.prev,node)
def remove(self, node):
if self.first.next == self.first:
self.first = None
else:
node.prev.next = node.next
node.next.prev = node.prev
if self.first == node:
self.first = node.next # node.prev
def display(self):
if self.first is None:
print(“NO VALUES”)
return
current = self.first
print(“\n“)
while True:
print(current.data, end=‘, ‘)
current = current.next
if current == self.first:
break
print(“\n“)
#Main Menu
print(“Type the operation you want to perform: “)
print(“insert <data> after <index>”)
print(“insert <data> before <index>”)
print(“insert <data> at beginning”)
print(“insert <data> at end”)
print(“remove <index>”)
print(“display”)
print(“quit”)
cdll = CircularDLL()
while True:
print(“The values in the Circular Doubly Linked List are: “)
cdll.display()
ch=input(“What do you want to do?”)
ch = ch.lower().strip().split()
print(“CH = “,ch)
if ch[0]==“insert”:
value = int(ch[1])
newNode = Node(value)
if ch[2]==“after”:
data = cdll.getnode(int(ch[3]))
if data is None:
print(“Given index doesnt exist”)
else:
cdll.insertafter(data, newNode)
elif ch[2]==“before”:
ref_node = cdll.getnode(int(ch[3]))
cdll.insertbefore(ref_node,newNode)
elif ch[2]==“at”:
if ch[3]==“beginning”:
cdll.insertbegin(newNode)
elif ch[3]==“end”:
cdll.insertend(newNode)
else:
print(“Error! Try again!”)
continue
else:
print(“Error! Try again!”)
continue
elif ch[0]==“remove”:
idx = int(ch[1])
idx_node = cdll.getnode(idx)
if idx_node is None:
print(“No such index, cant perform remove option.”)
continue
# if condition is false
cdll.remove(idx_node)
elif ch[0]==“display”:
print(“The values in the Circular Doubly Linked List are: “)
cdll.display()
elif ch[0]==“quit”:
break
else:
print(“Invalid option, try again!”)
## Assignment: Modify above code to create CircularQueue
## ## PRIORITY QUEUE ## ##
#Priority Queue
from queue import PriorityQueue
apq = PriorityQueue()
apq.put(50)
apq.put(30)
apq.put(40)
print(“Printing elements of Priority Queue:\n“)
while not apq.empty():
print(apq.get(), end=“, “)
print()
print(“Adding values with Priority:”)
apq = PriorityQueue()
apq.put((5, “Study”)) # combination of priority and values are added as tuple
apq.put((2, “Sleep”))
apq.put((9, “Eat”))
apq.put((4, “Play”))
print(“2. Printing elements of Priority Queue:\n“)
while not apq.empty():
print(apq.get(), end=“, “)
print()
### ### ### ###
class BST:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def bst_insert(node,key):
if node is None:
return BST(key)
if node.value <key:
node.right = bst_insert(node.right, key)
if node.value >key:
node.left = bst_insert(node.left, key)
return node
def bst_search(node, key):
if node is None or node.value == key:
return root
if node.value < key:
return bst_search(node.right, key)
if node.value > key:
return bst_search(node.left, key)
# 50, 30, 10, 70, 90, 80, 15, 25, 35
if __name__ == “__main__”:
root = None
root = bst_insert(root,50)
bst_insert(root,30)
bst_insert(root, 10)
bst_insert(root, 70)
bst_insert(root, 90)
bst_insert(root, 80)
bst_insert(root, 15)
bst_insert(root, 25)
bst_insert(root, 35)
key = 70
isFound = bst_search(root,key)
if isFound is None:
print(“Value “,key,“not in the BST!”)
else:
print(“Value”,key,” is found in the BST!”)
key = 75
isFound = bst_search(root, key)
if isFound is None:
print(“Value”,key,” not in the BST!”)
else:
print(“Value”,key,“is found in the BST!”)
# insertion, deletion and displaying the tree
# left, node, right
