***LinkedList***
class Node:
def __init__(self,data=None):
[Link]=data
[Link]=None
class Linkedlist:
def __init__(self):
[Link]=None
def insert_at_beginning(self,data):
new_node=Node(data)
if [Link]==None:
[Link]=new_node
print("node is inserted at begining if no node is present initially")
else:
new_node.next=[Link]
[Link]=new_node
print("node is inserted at the begining if already an initial node exists")
def insertion_at_end(self,data):
new_node=Node(data)
cur=[Link]
while [Link]!=None:
cur=[Link]
[Link]=new_node
def insert_after_node(self,key,value):
cur=[Link]
while cur!=None:
if([Link]==key):
break
cur=[Link]
if cur is None:
return [Link]
new_node=Node(value)
new_node.next=[Link]
[Link]=new_node
return [Link]
def insertion_at_position(self,pos,value,size):
if pos<1 or pos>size+1:
print("insertion is not possible")
return [Link]
else:
new_node=Node(value)
if pos==1:
[Link]=new_node.next
[Link]=new_node
else:
cur=[Link]
for _ in range(1,pos-1):
cur=[Link]
new_node.next=[Link]
[Link]=new_node
size+=1
return [Link]
def insert_at_end(self,data):
new_node=Node(data)
cur=[Link]
while cur!=None:
cur=[Link]
[Link]=new_node
def find_length(self):
count=0
cur=[Link]
while cur!=None:
cur=[Link]
count+=1
print(count)
def search(self,key):
cur=[Link]
while cur!=None:
if [Link]==key:
return True
cur=[Link]
return False
def del_at_first(self):
if [Link] is None:
return None
[Link]=[Link]
def del_at_specific(self,position):
temp=[Link]
prev=None
if temp is None:
return [Link]
if position==1:
[Link]=[Link]
return [Link]
for i in range(1,position):
prev=temp
temp=[Link]
if temp is None:
return [Link]
if temp is not None:
[Link]=[Link]
return [Link]
def del_at_end(self):
if not [Link]:
return None
if not [Link]:
return None
second_last=[Link]
while second_last.[Link]:
second_last=second_last.next
second_last.next=None
return [Link]
def reverse(self):
cur=[Link]
prev=None
while cur!=None:
next_node=[Link]
[Link]=prev
prev=cur
cur=next_node
[Link]=prev
def display(self):
elems=[]
cur_node=[Link]
while cur_node!=None:
[Link](cur_node.data)
cur_node=cur_node.next
print(elems)
l=Linkedlist()
l.insert_at_beginning(2)
l.insert_at_beginning(1)
l.insertion_at_end(4)
l.insert_after_node(2,3)
l.insertion_at_position(3,5,4)
l.insertion_at_end(6)
[Link]()
l.find_length()
print([Link](5))
new_head=l.del_at_first()
print(new_head)
[Link]()
l.del_at_specific(3)
[Link]()
l.del_at_end()
[Link]()
[Link]()
[Link]()
Output:
node is inserted at begining if no node is present initially
node is inserted at the begining if already an initial node exists
[1, 2, 5, 3, 4, 6]
6
True
None
[2, 5, 3, 4, 6]
[2, 5, 4, 6]
[2, 5, 4]
[4, 5, 2]
** Process exited - Return Code: 0 **
Press Enter to exit terminal
DoubleLinkedlist:
class Node:
def __init__(self,data):
[Link]=data
[Link]=None
[Link]=None
class DoubleLinked:
def __init__(self):
[Link]=None
def insert_at_beginning(self,data):
new_node=Node(data)
new_node.next=[Link]
if [Link] is not None:
[Link]=new_node
[Link]=new_node
return [Link]
def insert_at_end(self,data):
new_node=Node(data)
if [Link] is None:
[Link]=new_node
else:
cur=[Link]
while [Link] is not None:
cur=[Link]
[Link]=new_node
new_node.prev=cur
return [Link]
def insert_at_pos(self,pos,data):
new_node=Node(data)
count=0
cur=[Link]
while [Link]!=None:
if(count==pos):
new_node.prev=cur
new_node.next=[Link]
[Link]=new_node
[Link]=new_node
return head
count=count+1
cur=[Link]
if [Link]==None and count==pos:
[Link]=new_node
new_node.prev=cur
return [Link]
def display(self):#forward_traversal
elems=[]
cur=[Link]
while cur!=None:
[Link]([Link])
cur=[Link]
return elems
def backward(self):
elems=[]
cur=[Link]
while cur!=None and [Link]!=None:
cur=[Link]
while cur!=None:
[Link]([Link])
cur=[Link]
return elems
def length(self):
count=0
cur=[Link]
while cur!=None:
count+=1
cur=[Link]
return count
def del_beginning(self):
if not [Link]:
return
[Link]=[Link]
if [Link] is not None:
[Link]=None
return [Link]
def del_at_end(self):
if not [Link]:
return
if [Link] is None:
return None
cur=[Link]
while [Link]!=None:
cur=[Link]
[Link]=None
return [Link]
def del_at_specific(self,pos):
if not [Link]:
return
cur=[Link]
for i in range(1,pos):
if cur==None:
break
cur=[Link]
if cur is None:
return [Link]
if [Link] is not None:
[Link]=[Link]
if [Link] is not None:
[Link]=[Link]
if [Link] == cur:
[Link]=[Link]
cur=None
return [Link]
def search_ele(self,val):
cur=[Link]
while cur!=None:
if [Link]==val:
return True
cur=[Link]
return False
dl=DoubleLinked()
dl.insert_at_beginning(1)
print([Link]())
dl.insert_at_end(2)
dl.insert_at_end(3)
dl.insert_at_end(4)
dl.insert_at_end(5)
print([Link]())
dl.insert_at_pos(4,6)
print([Link]())
print([Link]())
print([Link]())
dl.del_beginning()
print([Link]())
dl.del_at_end()
print([Link]())
dl.del_at_specific(2)
print([Link]())
print(dl.search_ele(6))
[1]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6]
[6, 5, 4, 3, 2, 1]
6
[2, 3, 4, 5, 6]
[2, 3, 4, 5]
[2, 4, 5]
False
** Process exited - Return Code: 0 **
Press Enter to exit terminal
***Stack***
class Stack:
def __init__(self):
[Link]=[]
def is_empty(self):
return len([Link])==0
def push(self,data):
[Link](data)
def pop(self):
if self.is_empty():
raise IndexError("stack is empty we cannot pop")
return [Link]()
def peek(self):
if self.is_empty():
raise IndexError("stack is empty")
return [Link][-1]
def size(self):
return len([Link])
def __str__(self):
return str([Link])
# Example usage
stack = Stack()
[Link](1)
[Link](2)
[Link](3)
print("Stack:", stack)
print("Pop:", [Link]())
print("Peek:", [Link]())
print("Size:", [Link]())
print("Is empty:", stack.is_empty())
***stack implementation using linkedlist**
#implementing stack using linkedlist:
class Node:
def __init__(self,data):
[Link]=data
[Link]=None
class Stack:
def __init__(self):
[Link]=None
def is_empty(self):
return [Link] is None
def push(self,data):
new_node=Node(data)
if not new_node:
print("\n stack overflow")
return
new_node.next=[Link]
[Link]=new_node
def pop(self):
if self.is_empty():
print("\n stack underflow")
else:
temp=[Link]
[Link]=[Link]
del temp
def peek(self):
if not self.is_empty():
return [Link]
else:
print("\n stack is empty")
return float('-inf')
st=Stack()
[Link](1)
[Link](2)
[Link](3)
[Link](4)
print("top element is",[Link]())
[Link]()
print("top element is",[Link]())
**Queue data structure**:
class Queue:
def __init__(self):
[Link]=[]
def is_empty(self):
return len([Link])==0
def enqueue(self,data):
[Link](data)
def dequeue(self):
if self.is_empty():
raise IndexError("queue is empty")
return [Link](0)
def length(self):
return len([Link])
def peek(self):
if self.is_empty():
raise IndexError("Queue is empty")
return [Link][0]
def __str__(self):
return str([Link])
qe=Queue()
[Link](1)
[Link](2)
[Link](3)
[Link](4)
[Link](5)
print("queue :", qe)
print("Dequeue : ",[Link]())
print("length : ", [Link]())
print("peek : ", [Link]())
print("queue :", qe)
***Queue using Linkedlist***
class Node:
def __init__(self,data):
[Link]=data
[Link]=None
class Queue:
def __init__(self):
[Link]=None
[Link]=None
def is_empty(self):
return [Link] is None and [Link] is None
def enqueue(self,data):
new_node=Node(data)
if [Link] is None:
[Link]=[Link]=new_node
return
[Link]=new_node
[Link]=new_node
def dequeue(self):
if self.is_empty():
print("\n Queue is empty")
return
temp=[Link]
[Link]=[Link]
if [Link] is None:
[Link]=None
def get_front(self):
if self.is_empty():
print("\n Queue is empty")
return float('-inf')
return [Link]
def get_rear(self):
if self.is_empty():
print("\n queue is empty")
return float('-inf')
return [Link]
q = Queue()
# Enqueue elements into the queue
[Link](10)
[Link](20)
# Display the front and rear elements of the queue
print("Queue Front:", q.get_front())
print("Queue Rear:", q.get_rear())
# Dequeue elements from the queue
[Link]()
[Link]()
# Enqueue more elements into the queue
[Link](30)
[Link](40)
[Link](50)
# Dequeue an element from the queue
[Link]()
# Display the front and rear elements of the queue
print("Queue Front:", q.get_front())
print("Queue Rear:", q.get_rear())
**Tree Implementation**
# Tree traversal in Python
class Node:
def __init__(self, item):
[Link] = None
[Link] = None
[Link] = item
def inorder(root):
if root:
# Traverse left
inorder([Link])
# Traverse root
print(str([Link]) + "->", end='')
# Traverse right
inorder([Link])
def postorder(root):
if root:
# Traverse left
postorder([Link])
# Traverse right
postorder([Link])
# Traverse root
print(str([Link]) + "->", end='')
def preorder(root):
if root:
# Traverse root
print(str([Link]) + "->", end='')
# Traverse left
preorder([Link])
# Traverse right
preorder([Link])
root = Node(1)
[Link] = Node(2)
[Link] = Node(3)
[Link] = Node(4)
[Link] = Node(5)
print("Inorder traversal ")
inorder(root)
print("\nPreorder traversal ")
preorder(root)
print("\nPostorder traversal ")
postorder(root)
**Binary Search Tree Implementation**
class TreeNode:
def __init__(self,data):
[Link]=data
[Link]=None
[Link]=None
class BinarySearchTree:
def __init__(self):
[Link]=None
def insert(self,data):
if [Link] is None:
[Link]=TreeNode(data)
return
self._insert([Link],data)
def _insert(self,node,data):
if data < [Link]:
if [Link] is None:
[Link]=TreeNode(data)
else:
self._insert([Link],data)
else:
if [Link] is None:
[Link]=TreeNode(data)
else:
self._insert([Link],data)
def inorder(self):
nodes=[]
self._inorder([Link],nodes)
return nodes
def _inorder(self,node,nodes):
if node is not None:
self._inorder([Link],nodes)
[Link]([Link])
self._inorder([Link],nodes)
def preorder(self):
nodes=[]
self._preorder([Link],nodes)
return nodes
def _preorder(self,node,nodes):
if node is not None:
[Link]([Link])
self._preorder([Link],nodes)
self._preorder([Link],nodes)
def postorder(self):
nodes=[]
self._postorder([Link],nodes)
return nodes
def _postorder(self,node,nodes):
if node is not None:
self._postorder([Link],nodes)
self._postorder([Link],nodes)
[Link]([Link])
def find(self,data):
return self._find([Link],data)
def _find(self,node,data):
if node is None:
return False
if data==[Link]:
return True
elif data<[Link]:
return self._find([Link],data)
else:
return self._find([Link],data)
bst=BinarySearchTree()
bst = BinarySearchTree()
[Link](10)
[Link](5)
[Link](20)
[Link](3)
[Link](7)
[Link](15)
[Link](30)
print("Inorder traversal:", [Link]())
print("Preorder Traversal:",[Link]())
print("Postorder Traversal:",[Link]())
print("Element is present:",[Link](15))
*** DFS Tree Traversal***
# Python3 program to for tree traversals
# A class that represents an individual node in a
# Binary Tree
class Node:
def __init__(self, key):
[Link] = None
[Link] = None
[Link] = key
# A function to do inorder tree traversal
def printInorder(root):
if root:
# First recur on left child
printInorder([Link])
# then print the data of node
print([Link]),
# now recur on right child
printInorder([Link])
# A function to do postorder tree traversal
def printPostorder(root):
if root:
# First recur on left child
printPostorder([Link])
# the recur on right child
printPostorder([Link])
# now print the data of node
print([Link]),
# A function to do preorder tree traversal
def printPreorder(root):
if root:
# First print the data of node
print([Link]),
# Then recur on left child
printPreorder([Link])
# Finally recur on right child
printPreorder([Link])
# Driver code
root = Node(1)
[Link] = Node(2)
[Link] = Node(3)
[Link] = Node(4)
[Link] = Node(5)
print "Preorder traversal of binary tree is"
printPreorder(root)
print "\nInorder traversal of binary tree is"
printInorder(root)
print "\nPostorder traversal of binary tree is"
printPostorder(root)
