#Singly linked list
Code
'''class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next=next
class LinkedList:
def __init__(self):
self.head = None
def insert(self, data):
newNode = Node(data)
if (self.head):
current = self.head
while (current.next):
current = current.next
current.next = newNode
else:
self.head = newNode
def searchlist(self, value):
position = 0
found = 0
if self.head is None:
print("The linked list does not exist")
else:
temp_node = self.head
while temp_node is not None:
position = position + 1
if temp_node.data == value:
print("the required value was found at position:" + str(position))
found = 1
temp_node = temp_node.next
if found == 0:
print("the required value does not exist in the list")
def printLL(self):
current = self.head
while (current):
print(current.data)
current = current.next
def atBeg(self,value):
new_node = Node(value)
new_node.next = self.head
self.head = new_node
def delEnd(self):
if (self.head == None):
return
elif (self.head.next == None):
self.head = None
return
else:
temp_node = self.head
while ((temp_node.next).next is not None):
temp_node = temp_node.next
print('deleted item = ', (temp_node.next).data)
temp_node.next = None
return
LL = LinkedList()
LL.insert(9)
LL.insert(98)
LL.insert("welcome")
LL.insert(23)
print("contents of list:")
LL.printLL()
LL.searchlist(98)
LL.atBeg(5)
print("Contest of list:")
LL.printLL()
LL.delEnd()
LL.delEnd()
print("Contest of list:")
LL.printLL()
Output
contents of list:
9
98
welcome
23
the required value does not exist in the list
the required value was found at position:2
Contest of list:
5
9
98
welcome
23
deleted item = 23
deleted item = welcome
Contest of list:
5
9
98
#linked list iterators
Code
class Node:
def __init__(self,data=None,next=None):
self.data=data
self.next=next
class LinkedList:
def __init__(self):
self.head = None
def insert(self,data):
newNode = Node(data)
if(self.head):
current =self.head
while(current.next):
current=current.next
current.next=newNode
else:
self.head=newNode
def iterate_item(self):
current_item=self.head
while current_item:
val=current_item.data
current_item=current_item.next
yield val
LL=LinkedList( )
LL.insert(9)
LL.insert(98)
LL.insert("welcome")
LL.insert(23)
LL.insert(5)
print("list:")
for val in LL.iterate_item():
print(val)
Output
list:
9
98
welcome
23
5
#Stack data structure
Code
def push():
n=int(input("enter the number:"))
if len(stack)==0:
stack.append(n)
else:
stack.insert(0,n)
print(n,"is inserted")
def pop():
if len(stack)==0:
print("stack is empty:")
else:
print(stack[0],"is deleted:")
del stack[0]
def display():
if len(stack)==0:
print("stack is empty:")
else:
print("elemnet of stack one:")
for ele in stack:
print(ele)
stack=list()
while(1):
print("enter 1 for push,2 for pop,3 for display,4 for exit")
str=input()
if str=="1":
print("push")
push()
elif str=="2":
pop()
elif str=="3":
display()
elif str=='4':
exit()
else:
print("invalid input")
break
Output
enter 1 for push,2 for pop,3 for display,4 for exit
1
push
enter the number:1
enter 1 for push,2 for pop,3 for display,4 for exit
1
push
enter the number:2
2 is inserted
enter 1 for push,2 for pop,3 for display,4 for exit
1
push
enter the number:3
3 is inserted
enter 1 for push,2 for pop,3 for display,4 for exit
3
element of stack one:
3
2
1
enter 1 for push,2 for pop,3 for display,4 for exit
2
3 is deleted:
enter 1 for push,2 for pop,3 for display,4 for exit
4
#Implement bracket matching using stack.
Code
open_list=['[','{','(']
close_list=[']','}',')']
def checkParanthesis(myStr):
stack=[]
for i in myStr:
if i in open_list:
stack.append(i)
elif i in close_list:
pos =close_list.index(i)
if((len(stack)>0)and(open_list[pos]==stack[len(stack-1)])):
stack.pop()
else:
return "Unbalanced"
if len(stack)==0:
return "Balanced"
else:
return "Unbalanced"
string="{[]{()}}"
print(string,"-",checkParanthesis(string))
string="[{}{})(]"
print(string,"-",checkParanthesis(string))
string="((()))"
print(string,"-",checkParanthesis(string))
Output
{[ ]{()}} - Unbalanced
[{}{})( ] - Unbalanced
((())) - Unbalanced
#Program to demonstrate recursive operations (factorial/ Fibonacci)
Code
def fib(n):
if n < 0 or int (n)!=n:
return "Not defined"
elif n==0 or n==1:
return n
else:
return fib(n-1)+fib(n-2)
n=int(input("enter the number:\n"))
print("fibonnaci series:",end="")
for i in range (0,n):
print(fib(i),end="")
Output
enter the number:
5
fibonnaci series:01123
#Tower of Hanoi
Code
def tower_of_hanoi(disks,source,auxiliary,target):
if (disks==1):
print("move disk 1 from rod{}to rod {}.".format(source,target))
return
tower_of_hanoi(disks-1,source,target,auxiliary)
print("move disk{}from rod {}to rod {}.".format(disks,source, target))
disks=int(input("enter the number of disks:"))
tower_of_hanoi(disks,'A','B','C')
Output
enter the number of disks:5
move disk 1 from rodAto rod C.
move disk2from rod Ato rod B.
move disk3from rod Ato rod C.
move disk4from rod Ato rod B.
move disk5from rod Ato rod C.
#Implement queue
Code
def enqueue():
n=int(input("enter the number"))
queue.append(n)
print()
def dequeue():
if len(queue)==0:
print("queue is empty")
print()
else:
print(queue[0],"is the element to be deleted")
del queue[0]
print()
def display():
if len (queue)==0:
print("queue is empty")
else:
print("elements of the queue are:")
for ele in queue:
print(ele,end="")
print("front of the queue is:",queue[0])
print()
queue=list()
while(1):
print("1 to queue,2 to dequeue,3 to display,other to exit")
str=input()
if str=='1':
print("enqueue")
enqueue()
elif str=='2':
print("dequeue")
dequeue()
elif str=='3':
print("display")
display()
else:
print("exit")
break
Output
1 to queue,2 to dequeue,3 to display,other to exit
1
enqueue:
enter the number:13
1 to queue,2 to dequeue,3 to display,other to exit
1
enqueue:
enter the number:14
1 to queue,2 to dequeue,3 to display,other to exit
1
enqueue:
enter the number:45
1 to queue,2 to dequeue,3 to display,other to exit
3
display:
elements of the queue are:
131445front of the queue is: 13
1 to queue,2 to dequeue,3 to display,other to exit
4
Exit
#Implement priority queue
Code
class PriorityQueue:
def __init__(self):
self.queue=[]
def __str__(self):
return ''.join([str(i)for i in self.queue])
def isEmpty(self):
return len(self.queue)==0
def insert(self,data):
self.queue.append(data)
def delete(self):
try:
max_val=0
for i in range (len(self.queue)):
if self.queue[i]>self.queue[max_val]:
max_val=i
item=self.queue[max_val]
return item
except IndexError:
print()
exit()
qu=PriorityQueue()
qu.insert(12)
qu.insert(10)
qu.insert(11)
qu.insert(9)
qu.insert(8)
print("pq:",qu)
while not qu.isEmpty():
print(qu.delete())
break
Output
pq: 12101198
12
#Breadth first search
Code
from collections import defaultdict, deque
def bfs(graph, start):
d= set( )
queue = deque([start])
d.add(start)
while queue:
i = queue.popleft()
print(i, end=' ')
for x in graph[i]:
if x not in d:
d.add(x)
queue.append(x)
# Example graph represented as an adjacency list
graph = defaultdict(list)
graph[0] = [1, 2]
graph[1] = [2]
graph[2] = [0, 3]
graph[3] = [3]
print("BFS Traversal:")
bfs(graph, 2)
Output
BFS Traversal:
2031
Code
def dfs(h, start, d=None):
if d is None:
d = set()
d.add(start)
print(start, end=' ')
for x in h[start]:
if x not in d:
dfs(h, x, d)
h={
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("DFS Traversal:")
dfs(h, 'A')
Output
DFS Traversal:
ABDEFC
