PRACTICLES
NAME: Ayush Sharma
COURSE: B.A(Hons.) Economics
ROLL NO. : 23/32122
ANSWER 1 :
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class LinkedList:
def __init__(self):
[Link] = None
# a. Insert an element x at the beginning
def insert_at_beginning(self, x):
new_node = Node(x)
new_node.next = [Link]
[Link] = new_node
# b. Insert an element x at ith position
def insert_at_position(self, x, i):
if i < 0:
return
new_node = Node(x)
if i == 0:
new_node.next = [Link]
[Link] = new_node
return
current = [Link]
for _ in range(i - 1):
if current is None:
return
current = [Link]
if current is None:
return
new_node.next = [Link]
[Link] = new_node
# c. Remove an element from the beginning
def remove_from_beginning(self):
if [Link] is None:
return
[Link] = [Link]
# d. Remove an element from ith position
def remove_from_position(self, i):
if [Link] is None or i < 0:
return
if i == 0:
[Link] = [Link]
return
current = [Link]
for _ in range(i - 1):
if current is None:
return
current = [Link]
if current is None or [Link] is None:
return
[Link] = [Link]
# e. Search for an element x
def search(self, x):
current = [Link]
position = 0
while current:
if [Link] == x:
return position
current = [Link]
position += 1
return -1
# f. Concatenate two singly linked lists
def concatenate(self, other_list):
if [Link] is None:
[Link] = other_list.head
return
if other_list.head is None:
return
current = [Link]
while [Link]:
current = [Link]
[Link] = other_list.head
ANSWER 2:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
class DoublyLinkedList:
def __init__(self):
[Link] = None
# a. Insert an element x at the beginning
def insert_at_beginning(self, x):
new_node = Node(x)
if [Link]:
new_node.next = [Link]
[Link] = new_node
[Link] = new_node
# b. Insert an element x at ith position
def insert_at_position(self, x, i):
if i < 0:
return
new_node = Node(x)
if i == 0:
new_node.next = [Link]
if [Link]:
[Link] = new_node
[Link] = new_node
return
current = [Link]
for _ in range(i - 1):
if current is None:
return
current = [Link]
if current is None:
return
new_node.next = [Link]
new_node.prev = current
if [Link]:
[Link] = new_node
[Link] = new_node
# c. Insert an element x at the end
def insert_at_end(self, x):
new_node = Node(x)
if not [Link]:
[Link] = new_node
return
current = [Link]
while [Link]:
current = [Link]
[Link] = new_node
new_node.prev = current
# d. Remove an element from the beginning
def remove_from_beginning(self):
if not [Link]:
return
[Link] = [Link]
if [Link]:
[Link] = None
# e. Remove an element from ith position
def remove_from_position(self, i):
if not [Link] or i < 0:
return
if i == 0:
[Link] = [Link]
if [Link]:
[Link] = None
return
current = [Link]
for _ in range(i):
if current is None:
return
current = [Link]
if current is None:
return
[Link] = [Link]
if [Link]:
[Link] = [Link]
# f. Remove an element from the end
def remove_from_end(self):
if not [Link]:
return
if not [Link]:
[Link] = None
return
current = [Link]
while [Link]:
current = [Link]
[Link] = None
# g. Search for an element x
def search(self, x):
current = [Link]
position = 0
while current:
if [Link] == x:
return position
current = [Link]
position += 1
return -1
# h. Concatenate two doubly linked lists
def concatenate(self, other_list):
if not [Link]:
[Link] = other_list.head
return
if not other_list.head:
return
current = [Link]
while [Link]:
current = [Link]
[Link] = other_list.head
other_list.[Link] = current
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class CircularLinkedList:
def __init__(self):
[Link] = None
def is_empty(self):
return [Link] is None
def insert_at_front(self, data):
"""Inserts a new node with the given data at the front of the list."""
new_node = Node(data)
if self.is_empty():
[Link] = new_node
[Link] = [Link]
else:
temp = [Link]
while [Link] != [Link]:
temp = [Link]
[Link] = new_node
new_node.next = [Link]
[Link] = new_node
print(f"Inserted {data} at the front.")
def insert_after(self, new_data, after_data):
"""Inserts a new node with new_data after the first occurrence of after_data."""
if self.is_empty():
print(f"{after_data} not found. List is empty.")
return
current = [Link]
while True:
if [Link] == after_data:
new_node = Node(new_data)
new_node.next = [Link]
[Link] = new_node
print(f"Inserted {new_data} after {after_data}.")
return
current = [Link]
if current == [Link]:
break
print(f"{after_data} not found in the list.")
def insert_at_back(self, data):
new_node = Node(data)
if self.is_empty():
[Link] = new_node
[Link] = [Link]
else:
temp = [Link]
while [Link] != [Link]:
temp = [Link]
[Link] = new_node
new_node.next = [Link]
print(f"Inserted {data} at the back."
def remove_from_back(self):
"""Removes the last node from the list."""
if self.is_empty():
print("List is empty. Cannot remove from the back.")
return None
if [Link] == [Link]:
removed_data = [Link]
[Link] = None
print(f"Removed {removed_data} from the back (only element).")
return removed_data
current = [Link]
previous = None
while [Link] != [Link]
previous = current
current = [Link]
removed_data = [Link]
[Link] = [Link]
print(f"Removed {removed_data} from the back.")
return removed_data
def remove_from_front(self):
"""Removes the first node from the list."""
if self.is_empty():
print("List is empty. Cannot remove from the front.")
return None
removed_data = [Link]
if [Link] == [Link]:
[Link] = None
else:
temp = [Link]
while [Link] != [Link]:
temp = [Link]
[Link] = [Link]
[Link] = [Link]
print(f"Removed {removed_data} from the front.")
return removed_data
def remove_element(self, data):
"""Removes the first occurrence of the given data from the list."""
if self.is_empty():
print(f"{data} not found. List is empty.")
return
if [Link] == data:
if [Link] == [Link]:
[Link] = None
else:
temp = [Link]
while [Link] != [Link]:
temp = [Link]
[Link] = [Link]
[Link] = [Link]
print(f"Removed {data} from the list.")
return
current = [Link]
previous = None
while True:
previous = current
current = [Link]
if current == [Link]:
break
if [Link] == data:
[Link] = [Link]
print(f"Removed {data} from the list.")
return
print(f"{data} not found in the list.")
def search(self, data):
"""Searches for the given data in the list and returns its pointer (node)."""
if self.is_empty():
print(f"{data} not found. List is empty.")
return None
current = [Link]
while True:
if [Link] == data:
print(f"{data} found. Returning pointer to the node.")
return current
current = [Link]
if current == [Link]:
break
print(f"{data} not found in the list.")
return None
def display(self):
"""Displays the elements of the circular linked list."""
if self.is_empty():
print("List is empty.")
return
current = [Link]
elements = []
while True:
[Link]([Link])
current = [Link]
if current == [Link]:
break
print("Circular Linked List:", " -> ".join(map(str, elements)), "-> (head)")
Answer4
class Stack:
def __init__(self):
[Link] = []
def push(self, item):
[Link](item)
def pop(self):
if not self.is_empty():
return [Link]()
return None
def peek(self):
if not self.is_empty():
return [Link][-1]
return None
def is_empty(self):
return len([Link]) == 0
def size(self):
return len([Link])
ANSWER 5:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class StackLinkedList:
def __init__(self):
[Link] = None
self._size = 0
def push(self, item):
new_node = Node(item)
new_node.next = [Link]
[Link] = new_node
self._size += 1
def pop(self):
if self.is_empty():
return None
popped = [Link]
[Link] = [Link]
self._size -= 1
return popped
def peek(self):
if self.is_empty():
return None
return [Link]
def is_empty(self):
return [Link] is None
def size(self):
return self._size
ANSWER 6:
class Stack:
def __init__(self):
[Link] = []
def push(self, item):
[Link](item)
def pop(self):
return [Link]() if not self.is_empty() else None
def is_empty(self):
return len([Link]) == 0
def evaluate_postfix(expression):
stack = Stack()
for token in [Link]():
if [Link]():
[Link](int(token))
else:
b = [Link]()
a = [Link]()
if token == '+':
[Link](a + b)
elif token == '-':
[Link](a - b)
elif token == '*':
[Link](a * b)
elif token == '/':
[Link](a // b)
return [Link]()
def evaluate_prefix(expression):
stack = Stack()
tokens = [Link]()
for token in reversed(tokens):
if [Link]():
[Link](int(token))
else:
a = [Link]()
b = [Link]()
if token == '+':
[Link](a + b)
elif token == '-':
[Link](a - b)
elif token == '*':
[Link](a * b)
elif token == '/':
[Link](a // b)
return [Link]()
ANSWER 7 :
class CircularQueue:
def __init__(self, capacity):
[Link] = capacity
[Link] = [None] * capacity
[Link] = 0
[Link] = -1
[Link] = 0
def enqueue(self, item):
if self.is_full():
return False
[Link] = ([Link] + 1) % [Link]
[Link][[Link]] = item
[Link] += 1
return True
def dequeue(self):
if self.is_empty():
return None
item = [Link][[Link]]
[Link][[Link]] = None
[Link] = ([Link] + 1) % [Link]
[Link] -= 1
return item
def is_empty(self):
return [Link] == 0
def is_full(self):
return [Link] == [Link]
def display(self):
if self.is_empty():
print("Queue is empty")
return
idx = [Link]
for _ in range([Link]):
print([Link][idx], end=" ")
idx = (idx + 1) % [Link]
print()
ANSWER 8:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class CircularQueueLinkedList:
def __init__(self):
[Link] = None
def enqueue(self, item):
new_node = Node(item)
if [Link] is None:
[Link] = new_node
[Link] = [Link]
else:
new_node.next = [Link]
[Link] = new_node
[Link] = new_node
def dequeue(self):
if [Link] is None:
return None
if [Link] == [Link]:
item = [Link]
[Link] = None
return item
item = [Link]
[Link] = [Link]
return item
def display(self):
if [Link] is None:
print("Queue is empty")
return
current = [Link]
while True:
print([Link], end=" ")
current = [Link]
if current == [Link]:
break
print()
ANSWER 9:
class BSTNode:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
class BinarySearchTree:
def __init__(self):
[Link] = None
# a. Insert an element x
def insert(self, x):
if not [Link]:
[Link] = BSTNode(x)
else:
self._insert_recursive([Link], x)
def _insert_recursive(self, node, x):
if x < [Link]:
if [Link] is None:
[Link] = BSTNode(x)
else:
self._insert_recursive([Link], x)
else:
if [Link] is None:
[Link] = BSTNode(x)
else:
self._insert_recursive([Link], x)
# b. Delete an element x
def delete(self, x):
[Link] = self._delete_recursive([Link], x)
def _delete_recursive(self, node, x):
if node is None:
return None
if x < [Link]:
[Link] = self._delete_recursive([Link], x)
elif x > [Link]:
[Link] = self._delete_recursive([Link], x)
else:
if [Link] is None:
return [Link]
elif [Link] is None:
return [Link]
temp = self._min_value_node([Link])
[Link] = [Link]
[Link] = self._delete_recursive([Link], [Link])
return node
def _min_value_node(self, node):
current = node
while [Link]:
current = [Link]
return current
# c. Search for an element x, change its value to y, then place y at its appropriate position
def search_and_replace(self, x, y):
# First, delete x
[Link](x)
# Then, insert y
[Link](y)
# d. Display the elements in preorder, inorder, postorder traversal
def preorder(self):
self._preorder_recursive([Link])
print()
def _preorder_recursive(self, node):
if node:
print([Link], end=" ")
self._preorder_recursive([Link])
self._preorder_recursive([Link])
def inorder(self):
self._inorder_recursive([Link])
print()
def _inorder_recursive(self, node):
if node:
self._inorder_recursive([Link])
print([Link], end=" ")
self._inorder_recursive([Link])
def postorder(self):
self._postorder_recursive([Link])
print()
def _postorder_recursive(self, node):
if node:
self._postorder_recursive([Link])
self._postorder_recursive([Link])
print([Link], end=" ")
# e. Display the elements in level-by-level traversal
def level_order(self):
if not [Link]:
return
queue = [[Link]]
while queue:
node = [Link](0)
print([Link], end=" ")
if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])
print()
# f. Display the height of the BST.
def height(self):
return self._height_recursive([Link])
def _height_recursive(self, node):