1. Python program to and demonstrate basic data structure.
#List
list=["krishna", "Eshwar", "Ganesh"]
print(list)
print(list[2])
print(list[-1])
#tuples
tuple=(1,2,3,4,5)
print(tuple)
print(tuple[2])
#Sets
list=[1,2,3,4,4,4,4,5,5,5,6,6,6]
print(list)
s=set(list)
print(s)
#Dictionaries
dict={"deer":"animal"}
print(dict["deer"])
OUTPUT:-
['krishna', 'Eshwar', 'Ganesh']
Ganesh
Ganesh
(1, 2, 3, 4, 5)
[1, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6]
{1, 2, 3, 4, 5, 6}
Animal
2. Implement an ADT and compute space and time complexity.
class Stack:
def __init__(self):
self.stack = []
def push(self,item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop();
else:
return None
def peek(self):
if not self.is_empty():
return self.stack[-1]
else:
return None
def is_empty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)
#exmples
stack = Stack()
stack.push(10)
stack.push(20)
print(stack.pop())
print(stack.peek())
print(stack.is_empty())
print(stack.size())
OUTPUT:-
20
10
False
1
3. Implement bubble, selection, insertion sorting algorimthms.
#bubble_sort
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
return arr
# Example usage
numbers = [87, 89, 54, 80, 10, 25, 20]
print("Original array:", numbers)
sorted_arr = bubble_sort(numbers)
print("Sorted array:", sorted_arr)
OUTPUT:-
Original array: [87, 89, 54, 80, 10, 25, 20]
Sorted array: [10, 20, 25, 54, 80, 87, 89]
#Selection_sort
def selection_sort(arr):
n = len(arr)
for i in range(n-1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
print(f"Step {i+1}: {arr}")
return arr
# Examples
arr = [99, 87, 22, 3, 11]
print("Original Array:", arr)
sorted_arr = selection_sort(arr)
print("Sorted Array:", sorted_arr)
OUTPUT:-
Original Array: [99, 87, 22, 3, 11]
Step 1: [3, 87, 22, 99, 11]
Step 2: [3, 11, 22, 99, 87]
Step 3: [3, 11, 22, 99, 87]
Step 4: [3, 11, 22, 87, 99]
Sorted Array: [3, 11, 22, 87, 99]
#Insertion_sort
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j=i-1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# Example usage
array = [53, 64, 5, 18]
sorted_array = insertion_sort(array)
print("Sorted Array:", sorted_array)
OUTPUT:-
Sorted Array: [3, 11, 22, 87, 99]
Sorted Array: [5, 18, 53, 64]
4.Implement simply linked list(traversing the nodes, searching for a node,
prepending nodes, removing nodes) .
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def traverse(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
def search(self, key):
current = self.head
while current:
if current.data == key:
return True
current = current.next
return False
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def remove(self, key):
current = self.head
prev = None
while current and current.data != key:
prev = current
current = current.next
if current is None:
print("Key not found!")
return
if prev is None:
self.head = current.next
else:
prev.next = current.next
del current
if __name__ == "__main__":
sll = SinglyLinkedList()
sll.prepend(10)
sll.prepend(20)
sll.prepend(30)
print("Linked List:")
sll.traverse()
print("\nSearch for 20:", sll.search(20))
print("Search for 50:", sll.search(50))
print("\nRemoving 20...")
sll.remove(20)
sll.traverse()
OUTPUT:-
Linked List:
30 -> 20 -> 10 -> None
Search for 20: True
Search for 50: False
Removing 20...
30 -> 10 -> None
5.Implement linked list Iterators.
class Node:
def __init__(self,data):
self.data=data
self.next=None
class LinkedList:
def __init__(self):
self.head=None
def append(self,data):
new_node=Node(data)
if not self.head:
self.head=new_node
else:
current=self.head
while current.next:
current=current.next
current.next=new_node
def __iter__(self):
return LinkedListIterator(self.head)
class LinkedListIterator:
def __init__(self,node):
self.current=node
def __iter__(self):
return self
def __next__(self):
if not self.current:
raise StopIteration
data=self.current.data
self.current=self.current.next
return data
#example
ll=LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
print("Linked List elements:")
for value in ll:
print(value)
OUTPUT:-
Linked List elements:
1
2
3
6. Implement stack data structure.
class Stack:
def __init__(self):
self.stack = []
def is_empty(self):
return len(self.stack) == 0
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
else:
return "Stack is empty"
def peek(self):
if not self.is_empty():
return self.stack[-1]
else:
return "Stack is empty"
def size(self):
return len(self.stack)
def display(self):
return self.stack
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print("Top item:", stack.peek())
print("Stack size:", stack.size())
print("Stack contents:", stack.display())
stack.pop()
print("Stack after pop:", stack.display())
OUTPUT:-
Top item: 30
Stack size: 3
Stack contents: [10, 20, 30]
Stack after pop: [10, 20]
7. Implement an ADT with all its operations.
class StackADT:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Pop from empty stack")
return self.stack.pop()
def peek(self):
if self.is_empty():
raise IndexError("Peek from empty stack")
return self.stack[-1]
def is_empty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)
def __str__(self):
return "Stack: " + str(self.stack)
if __name__ == "__main__":
stack = StackADT()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack)
print(stack.pop())
print(stack.peek())
print(stack.size())
print(stack.is_empty())
OUTPUT:-
Stack: [10, 20, 30]
30
20
2
False
8. Implement Queue.
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
print(f"Enqueued: {item}")
def dequeue(self):
if self.is_empty():
print("Queue is empty!")
return None
item = self.items.pop(0)
print(f"Dequeued: {item}")
return item
def is_empty(self):
return len(self.items) == 0
def display(self):
if self.is_empty():
print("Queue is empty!")
else:
print("Queue contents:", self.items)
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
queue.display()
queue.dequeue()
queue.display()
OUTPUT:-
Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue contents: [10, 20, 30]
Dequeued: 10
Queue contents: [20, 30]
9.
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)
number = 5
print(f"Factorial of {number} is {factorial(number)}")
OUTPUT:-
Factorial of 5 is 120
10
def towers_of_hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
towers_of_hanoi(n - 1, source, auxiliary, target)
print(f"Move disk {n} from {source} to {target}")
towers_of_hanoi(n - 1, auxiliary, target, source)
n=3
towers_of_hanoi(n, 'A', 'C', 'B')
OUTPUT:-
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
