1
#Program 1: Python code stack and its operations
class Stack:
def __init__(self):
self._items = []
# Push operation: add element to top
def push(self, item):
self._items.append(item)
# Pop operation: remove and return top element
def pop(self):
if self.is_empty():
raise IndexError("Pop from empty stack")
return self._items.pop()
# Peek operation: view top element without removing
def peek(self):
if self.is_empty():
raise IndexError("Peek from empty stack")
return self._items[-1]
# Check if stack is empty
def is_empty(self):
return len(self._items) == 0
# Return size of stack
def size(self):
return len(self._items)
def __repr__(self):
return f"Stack({self._items})"
stack = Stack()
[Link](10)
[Link](20)
[Link](30)
2
print(stack) # Stack([10, 20, 30])
print([Link]()) # 30
print([Link]()) # 30
print([Link]()) # 2
print(stack.is_empty())# False
Output: Stack([10, 20, 30])
30
30
2
False
#Program 2: Python Program about Queue and its operations
class Queue:
def __init__(self):
[Link] = []
def is_empty(self):
return len([Link]) == 0
def enqueue(self, item):
[Link](0, item) # Add at rear
def dequeue(self):
if not self.is_empty():
return [Link]() # Remove from front
return None
def peek(self):
if not self.is_empty():
return [Link][-1]
return None
def size(self):
return len([Link])
3
# Example usage
q = Queue()
[Link](10)
[Link](20)
print([Link]()) # 10
print([Link]()) # 20
print([Link]()) # 1
Output:
10
20
1
#Program 3: Singly Linked List and its operations
class Node:
def __init__(self, data):
[Link] = data # heterogeneous data
[Link] = None # pointer to next node
class SinglyLinkedList:
def __init__(self):
[Link] = None
# Insertion at the end
def insert(self, data):
new_node = Node(data)
if [Link] is None:
[Link] = new_node
return
temp = [Link]
while [Link]:
temp = [Link]
[Link] = new_node
# Deletion by value
4
def delete(self, key):
temp = [Link]
# If head node itself holds the key
if temp is not None and [Link] == key:
[Link] = [Link]
temp = None
return
# Search for the key
prev = None
while temp is not None and [Link] != key:
prev = temp
temp = [Link]
# If key not found
if temp is None:
print(f"{key} not found in list")
return
# Unlink the node
[Link] = [Link]
temp = None
# Traversal
def traverse(self):
temp = [Link]
while temp:
print(f"Data: {[Link]} (Type: {type([Link]).__name__})")
temp = [Link]
# Example usage
ll = SinglyLinkedList()
[Link](10) # integer
5
[Link]("Hello") # string
[Link](3.14) # float
[Link]([1, 2, 3]) # list
print("Traversal after insertion:")
[Link]()
[Link]("Hello")
print("\nTraversal after deletion:")
[Link]()
Output: Traversal after insertion:
Data: 10 (Type: int)
Data: Hello (Type: str)
Data: 3.14 (Type: float)
Data: [1, 2, 3] (Type: list)
Traversal after deletion:
Data: 10 (Type: int)
Data: 3.14 (Type: float)
Data: [1, 2, 3] (Type: list)
#Program 4: Doubly Limked list and its operations
class Node:
def __init__(self, data):
[Link] = data # heterogeneous data
[Link] = None # pointer to previous node
[Link] = None # pointer to next node
class DoublyLinkedList:
def __init__(self):
[Link] = None
[Link] = None
# Insert at the end
def insert_end(self, data):
new_node = Node(data)
6
if [Link] is None: # empty list
[Link] = [Link] = new_node
else:
[Link] = new_node
new_node.prev = [Link]
[Link] = new_node
# Insert at the beginning
def insert_begin(self, data):
new_node = Node(data)
if [Link] is None: # empty list
[Link] = [Link] = new_node
else:
new_node.next = [Link]
[Link] = new_node
[Link] = new_node
# Delete a node by value
def delete(self, data):
current = [Link]
while current:
if [Link] == data:
# If node is head
if [Link] is None:
[Link] = [Link]
if [Link]:
[Link] = None
# If node is tail
elif [Link] is None:
[Link] = [Link]
[Link] = None
else:
[Link] = [Link]
[Link] = [Link]
return True
7
current = [Link]
return False
# Forward traversal
def traverse_forward(self):
current = [Link]
while current:
print([Link], end=" <-> ")
current = [Link]
print("None")
# Backward traversal
def traverse_backward(self):
current = [Link]
while current:
print([Link], end=" <-> ")
current = [Link]
print("None")
# Example usage
dll = DoublyLinkedList()
dll.insert_end(10)
dll.insert_end("Hello")
dll.insert_begin(3.14)
dll.insert_end([1, 2, 3])
print("Forward Traversal:")
dll.traverse_forward()
print("Backward Traversal:")
dll.traverse_backward()
print("Deleting 'Hello'...")
[Link]("Hello")
8
print("Forward Traversal after deletion:")
dll.traverse_forward()
Output: Forward Traversal:
3.14 <-> 10 <-> Hello <-> [1, 2, 3] <-> None
Backward Traversal:
[1, 2, 3] <-> Hello <-> 10 <-> 3.14 <-> None
Deleting 'Hello'...
Forward Traversal after deletion:
3.14 <-> 10 <-> [1, 2, 3] <-> None
#Program 5: Quick sort
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0] # choose the first element as pivot
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
# Example usage
numbers = [34, 7, 23, 32, 5, 62]
sorted_numbers = quick_sort(numbers)
print("Sorted list:", sorted_numbers)
Output: Sorted list: [5, 7, 23, 32, 34, 62]
#Program 6: Merge Sort
def merge_sort(arr):
if len(arr) <= 1:
return arr
# Split array into two halves
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
# Merge the sorted halves
return merge(left_half, right_half)
9
def merge(left, right):
merged = []
i=j=0
# Compare elements from both halves
while i < len(left) and j < len(right):
if left[i] < right[j]:
[Link](left[i])
i += 1
else:
[Link](right[j])
j += 1
# Add remaining elements
[Link](left[i:])
[Link](right[j:])
return merged
# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
print("Original array:", arr)
print("Sorted array:", merge_sort(arr))
Output: Original array: [38, 27, 43, 3, 9, 82, 10]
Sorted array: [3, 9, 10, 27, 38, 43, 82]
#Program 7 Shell sort
def shell_sort(arr):
n = len(arr)
gap = n // 2 # Initial gap size
# Keep reducing the gap until it becomes 0
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j=i
# Perform a gapped insertion sort
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
10
arr[j] = temp
gap //= 2 # Reduce the gap size
return arr
# Example usage
data = [23, 12, 1, 8, 34, 54, 2, 3]
print("Original array:", data)
sorted_data = shell_sort(data)
print("Sorted array:", sorted_data)
Output: Original array: [23, 12, 1, 8, 34, 54, 2, 3]
Sorted array: [1, 2, 3, 8, 12, 23, 34, 54]