Data Structures Using Python
Some Data Structures Using Python. In Linked List the concept is same just the
difference is that we are not manually managing the memory from heap like in cpp
but it's an advantage of Python that we don't have to worry about the memory
management and also that is a problem in Cpp and C as that many times leads to
memory leaks and also Cpp and C are vulnerable to bufferOverflow attacks due to
this.
''' Queues Using Arrays-Date- 5th November 2022 '''
class queue():
def __init__(self,size):
self.size=size
self.arr=[0]*self.size
self.f=-1
self.r=-1
def isFull(self):
if(self.r==self.size-1):
return True
else:
return False
def isEmpty(self):
if(self.f==self.r):
return True
else:
return False
def enqueue(self,data):
if(self.isFull()):
print("Queue is Full!")
return
self.r+=1
self.arr[self.r]=data
def dequeue(self):
if(self.isEmpty()):
print("Queue is Empty!")
return
self.f+=1
def __str__(self):
if(self.isEmpty()):
return "Queue is Empty"
ls=[]
print(self.arr)
print(f"self.f is {self.f}")
for i in range(self.f+1,self.r+1):
ls.append(str(self.arr[i]))
return " ".join(ls)
def main():
q1=queue(5)
q1.enqueue(1)
q1.enqueue(2)
print(q1)
if __name__=="__main__":
main()
''' A simple Tree- Date- 5th November 2022'''
ls=[]
class node():
def __init__(self,data):
self.data=data
self.left=None
self.right=None
class tree():
def __init__(self,node):
self.root=node
def __str__(self):
global ls
def preOrderIn(root):
if(root is not None):
ls.append(str(root.data))
preOrderIn(root.left)
preOrderIn(root.right)
preOrderIn(self.root)
return " ".join(ls)
def preOrder(self,root):
# The base condition is root as None
if(root is not None):
print(root.data,end=" ")
self.preOrder(root.left)
self.preOrder(root.right)
def inOrder(self,root):
if root is not None:
self.inOrder(root.left)
print(root.data,end=" ")
self.inOrder(root.right)
def postOrder(self,root):
if root is not None:
self.postOrder(root.left)
self.postOrder(root.right)
print(root.data,end=" ")
''' Traversal Algos '''
def preOrder(root):
if(root is not None):
print(root.data,end=" ")
preOrder(root.left)
preOrder(root.right)
def inOrder(root):
if root is not None:
inOrder(root.left)
print(root.data,end=" ")
inOrder(root.right)
def postOrder(root):
if root is not None:
postOrder(root.left)
postOrder(root.right)
print(root.data,end=" ")
def main():
n1=node(12)
n2=node(23)
n3=node(40)
n4=node(50)
n5=node(100)
n6=node(123)
n7=node(7)
'''
12
/ \
23 40
/ \ / \
123 100 7 50
'''
n1.left=n2
n1.right=n3
n2.left=n6
n2.right=n5
n3.left=n7
n3.right=n4
# Making a new Tree(t1)
t1=tree(n1)
t1.preOrder(n1)
print()
t1.inOrder(n1)
print()
t1.postOrder(n1)
print()
print(t1)
# print("\110\145\154\154\157")
if __name__=="__main__":
main()
''' Linked Lists in Python-Date- 4th November 2022 '''
class node():
def __init__(self,data):
self.data=data
self.next_node=None
self.size=1
class linked_list():
def __init__(self,head_node):
self.head_node=head_node
self.size=head_node.size
def __str__(self):
temp=self.head_node
ls=[]
while(temp is not None):
ls.append(str(temp.data))
temp=temp.next_node
return " ".join(ls)
def insert_begin(self,value):
self.size+=1
new_node=node(value)
# Make new_node point to head_node, that's it
new_node.next_node=self.head_node
# new_node is now the head_node of the linked list
self.head_node=new_node
def insert_end(self,value):
self.size+=1
# A temporary node for traversal in the linked list, pointing to the head_node
temp=self.head_node
new_node=node(value)
# Traversing to the end node of the linked list
while(temp.next_node is not None):
temp=temp.next_node
# Now we are at the end node of the ll
temp.next_node=new_node
def insert_pos(self,pos,value):
''' pos is based on 1-based indexing: 1st elem will be 0th elem(acc. to 0 based indexing) '''
if(pos==0):
self.insert_begin(value)
return
self.size+=1
itr=1
new_node=node(value)
temp=self.head_node
for _ in range(pos-1):
temp=temp.next_node
# New_node will point to the next node of temp
new_node.next_node=temp.next_node
# Now we have to insert in the next position of the temp pointer
temp.next_node=new_node
def print_list(self):
temp=self.head_node
while(temp is not None):
print(temp.data,end=" ")
temp=temp.next_node
print()
def del_end(self):
self.size-=1
temp=self.head_node
while(temp.next_node.next_node is not None):
temp=temp.next_node
print(f"{temp.next_node.data} deleted from the end of the linked list!")
# Orphaning the last node, it is in the memory but no more in the linked list
temp.next_node=None
def del_front(self):
self.size-=1
print(f"{self.head_node.data} removed from the linked list!")
# Making the new head_node to remove the first node
self.head_node=self.head_node.next_node
print("Is this printed?")
def print_ll(a):
''' Optional Function to print a linked list '''
"""
a: head_node of any linked list
"""
temp=a
while(temp is not None):
print(temp.data,end=" ")
temp=temp.next_node
print()
def main():
a=node(32)
l1=linked_list(a)
l1.insert_end(44)
l1.insert_end(56)
l1.insert_end(100)
l1.del_end()
l1.del_front()
l1.insert_pos(1,50)
# Printing a list using the dunder str method
print(l1)
print(l1.size)
# Manually inserting a new_node in the linked list, at the first position
b=node(100)
b.next_node=l1.head_node
l1.head_node=b
print(l1)
# If we manually insert a node in the linked list, then the size will be wrong
print(l1.size)
if __name__=="__main__":
main()
Comments
Post a Comment