1.
Write a complete menu driven program to implement the basic operations of a
Singly Linked List.
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class SinglyLinkedList:
def __init__(self):
[Link] = None
def add_node_at_the_end(self, data):
new_node = Node(data)
if not [Link]:
[Link] = new_node
return
last_node = [Link]
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def add_node_at_the_begin(self, data):
new_node = Node(data)
new_node.next = [Link]
[Link] = new_node
def insert_at_position(self, position, data):
if position < 0:
print("Invalid position.")
return
if position == 0:
self.add_node_at_the_begin(data)
return
new_node = Node(data)
current_node = [Link]
for _ in range(position-1):
if not current_node:
break
current_node = current_node.next
if not current_node:
print("Position is greater than the length of the list.")
return
new_node.next = current_node.next
current_node.next = new_node
def delete_from_beginning(self):
if not [Link]:
print("List is empty. Nothing to delete.")
return
[Link] = [Link]
def delete_from_end(self):
if not [Link]:
print("List is empty. Nothing to delete.")
return
if not [Link]:
[Link] = None
return
second_last = [Link]
while second_last.[Link]:
second_last = second_last.next
second_last.next = None
def delete_at_position(self, position):
if position < 0:
print("Invalid position.")
return
if position == 0:
self.delete_from_beginning()
return
current_node = [Link]
prev_node = None
for _ in range(position):
if not current_node:
print("Position is greater than the length of the list.")
return
prev_node = current_node
current_node = current_node.next
if not current_node:
print("Position is greater than the length of the list.")
return
prev_node.next = current_node.next
def traverse(self):
current_node = [Link]
while current_node:
yield current_node.data
current_node = current_node.next
def sort(self):
elements = list([Link]())
[Link]()
[Link] = None
for element in elements:
self.add_node_at_the_end(element)
def reverse(self):
prev = None
current = [Link]
while current:
next_node = [Link]
[Link] = prev
prev = current
current = next_node
[Link] = prev
def display(self):
current_node = [Link]
while current_node:
print(current_node.data, end=" ")
current_node = current_node.next
print()
linked_list = SinglyLinkedList()
while True:
print("\n1. Add a Node in the Linked List.")
print("2. Delete a Node from the Linked List.")
print("3. Traverse the Nodes of the Linked List.")
print("4. Sort the Linked List.")
print("5. Reverse the Linked List.")
print("6. Exit")
choice = int(input("Enter your choice: "))
if choice == 1:
print("\n1. Add a Node at the beginning of the Linked List.")
print("2. Add a Node at the end of the Linked List.")
print("3. Add a Node at any position in the Linked List.")
ch = int(input("Enter your choice: "))
if ch == 1:
data = int(input("Enter data to add at the beginning of the Linked
List: "))
linked_list.add_node_at_the_begin(data)
linked_list.display()
elif ch == 2:
data = int(input("Enter data to add at the end of the Linked List: "))
linked_list.add_node_at_the_end(data)
linked_list.display()
elif ch == 3:
data = int(input("Enter data to add in the Linked List: "))
pos = int(input("Enter the position to add a Node in the Linked List:
"))
linked_list.insert_at_position(pos,data)
linked_list.display()
elif choice == 2:
print("\n1. Delete a Node from the beginning of the Linked List.")
print("2. Delete a Node from the end of the Linked List.")
print("3. Delete a Node from any position in the Linked List.")
ch = int(input("Enter your choice: "))
if ch == 1:
linked_list.delete_from_beginning()
linked_list.display()
elif ch == 2:
linked_list.delete_from_end()
linked_list.display()
elif ch == 3:
pos = int(input("Enter the position of the Node to delete from the
Linked List: "))
linked_list.delete_at_position(pos)
linked_list.display()
elif choice == 3:
linked_list.traverse()
linked_list.display()
elif choice == 4:
linked_list.sort()
linked_list.display()
elif choice == 5:
linked_list.reverse()
linked_list.display()
elif choice == 6:
break
else:
print("Invalid choice. Please try again.")
2. Write a Python program to implement the basic operations of Stack. Write the
corresponding algorithm.
class Stack:
def __init__(self):
[Link] = []
def push(self, item):
[Link](item)
def pop(self):
if not self.is_empty():
return [Link]()
else:
raise IndexError("Pop not possible ! Stack is empty !!!")
def peek(self):
if not self.is_empty():
return [Link][-1]
else:
raise IndexError("Peek not possible ! Stack is empty !!!")
def is_empty(self):
return len([Link]) == 0
stack = Stack()
while True:
print("\n1. Push an element in the Stack.")
print("2. Pop from the Stack.")
print("3. Peek an element from the Stack.")
print("4. Check whether the stack is empty or not.")
print("5. Exit")
choice = int(input("Enter your choice: "))
if choice == 1:
data = int(input("Enter an element to insert in the Stack : "))
[Link](data)
print([Link])
elif choice == 2:
[Link]()
print("Stack after pop : ", [Link])
elif choice == 3:
print([Link]())
elif choice == 4:
print(stack.is_empty())
elif choice == 5:
break
else:
print("Invalid choice. Please try again.")
3. Write a Python program which takes a postfix expression as argument and evaluate
it using Stack. Write the corresponding algorithm.
class Stack:
def __init__(self):
[Link] = []
def push(self, item):
[Link](item)
def pop(self):
if not self.is_empty():
return [Link]()
else:
raise IndexError("pop from empty stack")
def peek(self):
if not self.is_empty():
return [Link][-1]
else:
raise IndexError("peek from empty stack")
def is_empty(self):
return len([Link]) == 0
def evaluate_postfix(expression):
stack = Stack()
operators = set(['+', '-', '*', '/'])
for token in [Link]():
if token not in operators:
[Link](float(token))
else:
operand2 = [Link]()
operand1 = [Link]()
result = perform_operation(token, operand1, operand2)
[Link](result)
return [Link]()
def perform_operation(operator, operand1, operand2):
if operator == '+':
return operand1 + operand2
elif operator == '-':
return operand1 - operand2
elif operator == '*':
return operand1 * operand2
elif operator == '/':
return operand1 / operand2
postfix_expr = input("Enter the expression : ")
print("Postfix Expression:", postfix_expr)
print("Result:", evaluate_postfix(postfix_expr))
4. Write a Python program to convert an infix expression into postfix expression.
def infix_to_postfix(expression):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
stack = []
postfix = []
for char in expression:
if [Link]():
[Link](char)
elif char == '(':
[Link](char)
elif char == ')':
while stack and stack[-1] != '(':
[Link]([Link]())
[Link]()
else:
while stack and [Link](stack[-1], 0) >= [Link](char,
0):
[Link]([Link]())
[Link](char)
while stack:
[Link]([Link]())
return ''.join(postfix)
infix_expr = input("Enter an infix expression: ")
postfix_expr = infix_to_postfix(infix_expr)
print("Infix Expression:", infix_expr)
print("Postfix Expression:", postfix_expr)
5. Write a Python program to evaluate a postfix expression.
def evaluate_postfix(expression):
stack = []
for char in expression:
if [Link]():
[Link](int(char))
else:
operand2 = [Link]()
operand1 = [Link]()
if char == '+':
[Link](operand1 + operand2)
elif char == '-':
[Link](operand1 - operand2)
elif char == '*':
[Link](operand1 * operand2)
elif char == '/':
[Link](operand1 / operand2)
elif char == '^':
[Link](operand1 ** operand2)
return [Link]()
postfix_expr = input("Enter a postfix expression: ")
result = evaluate_postfix(postfix_expr)
print("Postfix Expression:", postfix_expr)
print("Result:", result)
6. Write a program to create a linked list to contain the vowels ‘a’, ‘e’, ‘i’,
‘o’, ‘u’ in the data field of the nodes.
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class LinkedList:
def __init__(self):
[Link] = None
def insert_at_end(self, data):
new_node = Node(data)
if [Link] is None:
[Link] = new_node
return
current = [Link]
while [Link]:
current = [Link]
[Link] = new_node
def display(self):
current = [Link]
while current:
print([Link], end=" ")
current = [Link]
print()
vowels = ['a', 'e', 'i', 'o', 'u']
ll = LinkedList()
for vowel in vowels:
ll.insert_at_end(vowel)
print("Linked List with vowels:")
[Link]()
7. Write a program to delete the first node that contains an integer data item of a
single linked list.
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class LinkedList:
def __init__(self):
[Link] = None
def insert_at_end(self, data):
new_node = Node(data)
if [Link] is None:
[Link] = new_node
return
current = [Link]
while [Link]:
current = [Link]
[Link] = new_node
def delete_first_integer_node(self):
if [Link] is None:
return
if isinstance([Link], int):
[Link] = [Link]
return
current = [Link]
while [Link]:
if isinstance([Link], int):
[Link] = [Link]
return
current = [Link]
def display(self):
current = [Link]
while current:
print([Link], end=" ")
current = [Link]
print()
ll = LinkedList()
ll.insert_at_end('a')
ll.insert_at_end('e')
ll.insert_at_end(1)
ll.insert_at_end('i')
ll.insert_at_end('o')
ll.insert_at_end(2)
ll.insert_at_end('u')
print("Original Linked List:")
[Link]()
ll.delete_first_integer_node()
print("Linked List after deleting the first integer data node:")
[Link]()
8. Write a Python program that implements stack as a linked list.
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class Stack:
def __init__(self):
[Link] = None
def push(self, data):
new_node = Node(data)
new_node.next = [Link]
[Link] = new_node
def pop(self):
if self.is_empty():
raise IndexError("pop from empty stack")
popped = [Link]
[Link] = [Link]
[Link] = None
return [Link]
def peek(self):
if self.is_empty():
raise IndexError("peek from empty stack")
return [Link]
def is_empty(self):
return [Link] is None
def __str__(self):
current = [Link]
stack_str = ""
while current:
stack_str += str([Link]) + " "
current = [Link]
return stack_str.strip()
stack = Stack()
[Link](10)
[Link](20)
[Link](30)
print("Stack:", stack)
print("Peek:", [Link]())
print("Pop:", [Link]())
print("Stack after pop:", stack)
9. Write a Python program that implements queue as a linked list.
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class Queue:
def __init__(self):
[Link] = None
[Link] = None
def enqueue(self, data):
new_node = Node(data)
if self.is_empty():
[Link] = new_node
else:
[Link] = new_node
[Link] = new_node
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue from empty queue")
dequeued = [Link]
[Link] = [Link]
if [Link] is None:
[Link] = None
[Link] = None
return [Link]
def peek(self):
if self.is_empty():
raise IndexError("peek from empty queue")
return [Link]
def is_empty(self):
return [Link] is None
def __str__(self):
current = [Link]
queue_str = ""
while current:
queue_str += str([Link]) + " "
current = [Link]
return queue_str.strip()
queue = Queue()
[Link](100)
[Link](200)
[Link](300)
print("Queue:", queue)
print("Peek:", [Link]())
print("Dequeue:", [Link]())
print("Queue after dequeue:", queue)
10. Write a Python program that implements circular queue as a linked list.
CODE :
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class CircularQueue:
def __init__(self, capacity):
[Link] = capacity
[Link] = 0
[Link] = None
[Link] = None
def enqueue(self, data):
if self.is_full():
raise IndexError("enqueue to full queue")
new_node = Node(data)
if self.is_empty():
[Link] = new_node
else:
[Link] = new_node
[Link] = new_node
[Link] = [Link]
[Link] += 1
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue from empty queue")
dequeued = [Link]
if [Link] == 1:
[Link] = None
[Link] = None
else:
[Link] = [Link]
[Link] = [Link]
[Link] = None
[Link] -= 1
return [Link]
def is_empty(self):
return [Link] == 0
def is_full(self):
return [Link] == [Link]
def __str__(self):
if self.is_empty():
return "Empty queue"
current = [Link]
queue_str = ""
while [Link] != [Link]:
queue_str += str([Link]) + " "
current = [Link]
queue_str += str([Link]) + " "
return queue_str.strip()
queue = CircularQueue(5)
[Link](1)
[Link](2)
[Link](3)
[Link](4)
[Link](5)
print("Queue:", queue)
print("Dequeue:", [Link]())
print("Queue after dequeue:", queue)
[Link](6)
print("Queue after enqueue:", queue)
11. Write a Python program that implements deque using a linked list.
CODE :
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
class Deque:
def __init__(self):
[Link] = None
[Link] = None
def is_empty(self):
return [Link] is None
def add_front(self, data):
new_node = Node(data)
if self.is_empty():
[Link] = new_node
[Link] = new_node
else:
new_node.next = [Link]
[Link] = new_node
[Link] = new_node
def add_rear(self, data):
new_node = Node(data)
if self.is_empty():
[Link] = new_node
[Link] = new_node
else:
[Link] = new_node
new_node.prev = [Link]
[Link] = new_node
def remove_front(self):
if self.is_empty():
raise IndexError("remove_front from empty deque")
removed = [Link]
if [Link] == [Link]:
[Link] = None
[Link] = None
else:
[Link] = [Link]
[Link] = None
[Link] = None
return [Link]
def remove_rear(self):
if self.is_empty():
raise IndexError("remove_rear from empty deque")
removed = [Link]
if [Link] == [Link]:
[Link] = None
[Link] = None
else:
[Link] = [Link]
[Link] = None
[Link] = None
return [Link]
def peek_front(self):
if self.is_empty():
raise IndexError("peek_front from empty deque")
return [Link]
def peek_rear(self):
if self.is_empty():
raise IndexError("peek_rear from empty deque")
return [Link]
def __str__(self):
if self.is_empty():
return "Empty deque"
current = [Link]
deque_str = ""
while current:
deque_str += str([Link]) + " "
current = [Link]
return deque_str.strip()
deque = Deque()
deque.add_front(1)
deque.add_front(2)
deque.add_rear(3)
print("Deque:", deque)
print("Peek front:", deque.peek_front())
print("Peek rear:", deque.peek_rear())
print("Remove front:", deque.remove_front())
print("Deque after remove front:", deque)
print("Remove rear:", deque.remove_rear())
print("Deque after remove rear:", deque)
12. Write a Python program that implements a priority queue using a linked list.
class Node:
def __init__(self, data, priority):
[Link] = data
[Link] = priority
[Link] = None
class PriorityQueue:
def __init__(self):
[Link] = None
def is_empty(self):
return [Link] is None
def enqueue(self, data, priority):
new_node = Node(data, priority)
if self.is_empty() or priority > [Link]:
new_node.next = [Link]
[Link] = new_node
else:
current = [Link]
while [Link] and priority <= [Link]:
current = [Link]
new_node.next = [Link]
[Link] = new_node
def dequeue(self):
if self.is_empty():
raise IndexError("dequeue from empty priority queue")
dequeued = [Link]
[Link] = [Link]
[Link] = None
return [Link]
def peek(self):
if self.is_empty():
raise IndexError("peek from empty priority queue")
return [Link]
def __str__(self):
if self.is_empty():
return "Empty priority queue"
current = [Link]
queue_str = ""
while current:
queue_str += f"{[Link]}:{[Link]} "
current = [Link]
return queue_str.strip()
priority_queue = PriorityQueue()
priority_queue.enqueue("Task1", 2)
priority_queue.enqueue("Task2", 1)
priority_queue.enqueue("Task3", 3)
print("Priority Queue:", priority_queue)
print("Peek:", priority_queue.peek())
print("Dequeue:", priority_queue.dequeue())
print("Priority Queue after dequeue:", priority_queue)
