SYCS Data Structure NEP All Practical-1.docx

SYCS Data Structure NEP All Practical-1.docx

1. SYCS Data Structure Practicals (SEM III)
Practical 1a
Aim: python program to implement abstract data type
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
else:
return "Stack is empty"
def peek(self):
if not self.is_empty():
return self.items[-1]
else:
return "Stack is empty"
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# Example usage
s = Stack()
s.push(10)
s.push(20)
print("Top element:", s.peek()) # Output: Top element: 20
print("Stack size:", s.size()) # Output: Stack size: 2
print("Popped:", s.pop()) # Output: Popped: 20
print("Is empty?", s.is_empty()) # Output: Is empty? False

2. Prcatical 1b
Aim: Implement python program to create, update, delete using structures.
class Stack:
def __init__(self):
self.items = []
def push(self, item): # Create
self.items.append(item)
def pop(self): # Delete
if not self.is_empty():
return self.items.pop()
return "Stack is empty"
def update(self, index, value): # Update
if 0 <= index < len(self.items):
self.items[index] = value
else:
print("Invalid index")
def is_empty(self):
return len(self.items) == 0
def display(self):
print("Stack:", self.items)
# Example usage
s = Stack()
s.push(10)
s.push(20)
s.display() # Stack: [10, 20]

3. s.update(0, 99)
s.display() # Stack: [99, 20]
print(s.pop()) # 20
s.display() # Stack: [99]
Output

4. Practical 2a
Construct python program for dynamic singly linked list with basic operations.
# Node class for singly linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Singly Linked List class
class SinglyLinkedList:
def __init__(self):
self.head = None
# Insert at the end
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
# Display the list
def display(self):
current = self.head
while current:
print(current.data, end=" -> " if current.next else "")
current = current.next
print()
# Example usage
if __name__ == "__main__":
sll = SinglyLinkedList()
sll.append(10)
sll.append(20)
sll.append(30)

5. sll.display() # Output: 10 -> 20 -> 30
Practical 2b
Python program for playlist using single linked list
def __init__(self, title):
self.title = title
self.next = None
class Playlist:
def __init__(self):
self.head = None
def add(self, title):
n = Node(title)
if not self.head:
self.head = n
else:
curr = self.head
while curr.next:
curr = curr.next
curr.next = n
def remove(self, title):
curr, prev = self.head, None
while curr:
if curr.title == title:
if prev: prev.next = curr.next
else: self.head = curr.next
break

6. prev, curr = curr, curr.next
def show(self):
curr = self.head
while curr:
print(curr.title, end=" -> ")
curr = curr.next
print("None")
# Example usage
p = Playlist()
p.add("Song A")
p.add("Song B")
p.add("Song C")
p.show() # Song A -> Song B -> Song C -> None
p.remove("Song B")
p.show() # Song A -> Song C -> None

7. Practical 3a
Represent polynomials using linked lists.
class Node:
def __init__(self, coeff, exp):
self.coeff = coeff
self.exp = exp
self.next = None
class Polynomial:
def __init__(self):
self.head = None
def add_term(self, coeff, exp):
new_node = Node(coeff, exp)
if not self.head:
self.head = new_node
else:
curr = self.head
while curr.next:
curr = curr.next
curr.next = new_node
def display(self):
curr = self.head
while curr:
print(f"{curr.coeff}x^{curr.exp}", end=" ")
if curr.next:
print("+", end=" ")
curr = curr.next
print()
# Example usage
poly = Polynomial()
poly.add_term(3, 2) # 3x^2
poly.add_term(2, 1) # 2x^1
poly.add_term(5, 0) # 5x^0
print("Polynomial:")
poly.display() # Output: 3x^2 + 2x^1 + 5x^0

9. Practical 3b
Python program for polynomial addition and subtraction by merging
lists.
class Node:
def __init__(self, coeff, exp):
self.coeff = coeff
self.exp = exp
self.next = None
class Polynomial:
def __init__(self):
self.head = None
def add_term(self, coeff, exp):
new_node = Node(coeff, exp)
if not self.head:
self.head = new_node
else:
curr = self.head
while curr.next:
curr = curr.next
curr.next = new_node
def display(self):
curr = self.head
while curr:
print(f"{curr.coeff}x^{curr.exp}", end=" ")
if curr.next:
print("+", end=" ")
curr = curr.next
print()
# Example usage
poly = Polynomial()
poly.add_term(3, 2) # 3x^2
poly.add_term(2, 1) # 2x^1
poly.add_term(5, 0) # 5x^0
print("Polynomial:")
poly.display() # Output: 3x^2 + 2x^1 + 5x^0

11. Practical 4a
Create a short and simple Python program for doubly linked list
with forward and backward traversal.
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insert_end(self, data):
node = Node(data)
if not self.head:
self.head = self.tail = node
else:
node.prev = self.tail
self.tail.next = node
self.tail = node
def display_forward(self):
curr = self.head
while curr:
print(curr.data, end=" <-> " if curr.next else "")
curr = curr.next
print()
def display_backward(self):
curr = self.tail
while curr:
print(curr.data, end=" <-> " if curr.prev else "")
curr = curr.prev
print()
# Example usage
dll = DoublyLinkedList()
dll.insert_end(1)
dll.insert_end(2)
dll.insert_end(3)
dll.display_forward() # Output: 1 <-> 2 <-> 3
dll.display_backward() # Output: 3 <-> 2 <-> 1

12. Practical 4b
simple Python program for a singly linked list that supports insertion and deletion at the head, tail,
and a specific position:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
# Insert at head
def insert_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
# Insert at tail
def insert_tail(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
curr = self.head
while curr.next:
curr = curr.next

13. curr.next = new_node
# Delete at head
def delete_head(self):
if self.head:
self.head = self.head.next
# Delete at tail
def delete_tail(self):
if not self.head:
return
if not self.head.next:
self.head = None
return
curr = self.head
while curr.next.next:
curr = curr.next
curr.next = None
# Display the list
def display(self):
curr = self.head
while curr:
print(curr.data, end=" -> " if curr.next else "")
curr = curr.next
print()
# Example usage
sll = SinglyLinkedList()
sll.insert_head(10)
sll.insert_tail(20)
sll.insert_head(5)
sll.insert_tail(30)
sll.display() # Output: 5 -> 10 -> 20 -> 30
sll.delete_head()
sll.display() # Output: 10 -> 20 -> 30
sll.delete_tail()
sll.display() # Output: 10 -> 20

14. Practical 5a
Aim: program for push, pop, peek using arrays or linked lists.
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if self.stack:
return self.stack.pop()
return "Stack is empty"
def peek(self):
if self.stack:
return self.stack[-1]
return "Stack is empty"
# Example usage
s = Stack()
s.push(10)
s.push(20)
print(s.peek()) # Output: 20
print(s.pop()) # Output: 20

15. print(s.pop()) # Output: 10
print(s.pop()) # Output: Stack is empty
Practical 5b
Aim: Python program to Solve problems like delimiter matching
or undo mechanism.
def is_matched(expr):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for ch in expr:
if ch in pairs.values():
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
# Example usage
print(is_matched("{[()]}")) # True
print(is_matched("{[(])}")) # False
print(is_matched("a[b+{c*(u-r)}]")) # True
print(is_matched("a[b+{c*(u-r)}}]")) # False

16. Practical 5c
Aim: simple Python program to Convert expressions from prefix to
postfix and evaluate them.
def is_operator(c):
return c in '+-*/'
def prefix_to_postfix(prefix):
stack = []
# Process prefix from right to left
for ch in prefix[::-1]:
if ch.isalnum(): # Operand
stack.append(ch)
elif is_operator(ch):
op1 = stack.pop()
op2 = stack.pop()
stack.append(op1 + op2 + ch)
return stack[-1]

17. def evaluate_postfix(postfix):
stack = []
for ch in postfix:
if ch.isdigit():
stack.append(int(ch))
elif is_operator(ch):
b = stack.pop()
a = stack.pop()
if ch == '+': stack.append(a + b)
elif ch == '-': stack.append(a - b)
elif ch == '*': stack.append(a * b)
elif ch == '/': stack.append(a // b) # integer division
return stack[-1]
# Example usage
prefix_expr = "*+23-45" # equivalent to (2+3)*(4-5)
postfix_expr = prefix_to_postfix(prefix_expr)
print("Postfix Expression:", postfix_expr) # Output: 23+45-*
result = evaluate_postfix(postfix_expr)
print("Evaluation Result:", result) # Output: -5

18. Practical 6a
Python program to Develop linear and circular queues to
simulate task scheduling.
class LinearQueue:
def __init__(self):
self.q = []
def enqueue(self, task):
self.q.append(task)
def dequeue(self):
return self.q.pop(0) if self.q else "Queue Empty"
def display(self):
print("Linear Queue:", self.q)
# Example usage
lq = LinearQueue()
lq.enqueue('Task1')
lq.enqueue('Task2')
lq.enqueue('Task3')
lq.display()
print("Processing:", lq.dequeue())
lq.display()

19. Practical 6b
simple Python program to Perform enqueue and dequeuer
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item) # Add item to the end
def dequeue(self):
if self.is_empty():
return "Queue is empty"
return self.items.pop(0) # Remove item from the front
def is_empty(self):
return len(self.items) == 0
def display(self):
print("Queue:", self.items)
# Example usage
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
q.display() # Queue: [10, 20, 30]
print("Dequeued:", q.dequeue()) # Dequeued: 10
q.display() # Queue: [20, 30]

20. Practical 7a
Create a binary search tree (BST) from a dataset.
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(root, data):
if root is None:
return TreeNode(data)
if data < root.data:
root.left = insert(root.left, data)
elif data > root.data:
root.right = insert(root.right, data)
return root
def in_order_traversal(node):
if node:
in_order_traversal(node.left)
print(node.data, end=" ")
in_order_traversal(node.right)
# Example dataset
dataset = [13, 7, 15, 3, 8, 14, 19, 18]
# Build BST
root = None
for num in dataset:
root = insert(root, num)
print("In-order Traversal of BST:")
in_order_traversal(root) # Output: 3 7 8 13 14 15 18 19

22. Practical 7b
Perform and visualize in-order, pre-order, and post-order traversals.
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=' ')
inorder(root.right)
def preorder(root):
if root:
print(root.val, end=' ')
preorder(root.left)
preorder(root.right)
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(root.val, end=' ')
# Example tree construction:
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

23. root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print("In-order traversal:")
inorder(root) # Output: 4 2 5 1 6 3 7
print("\nPre-order traversal:")
preorder(root) # Output: 1 2 4 5 3 6 7
print("\nPost-order traversal:")
postorder(root) # Output: 4 5 2 6 7 3 1

24. Practical 8a
Program to calculate height of AVL tree
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def get_height(node):
if not node:
return 0
return node.height
# Example
a = Node(10)
b = Node(20)
a.right = b
a.height = 1 + max(get_height(a.left), get_height(a.right))
print("Height of node a:", a.height) # Output: 2
Output

25. Practical 8b
Program to calculate the balance factor of a node.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def get_height(node):
return node.height if node else 0
def get_balance(node):
if not node:

26. return 0
return get_height(node.left) - get_height(node.right)
# Example
a = Node(30)
a.left = Node(20)
a.right = Node(40)
a.height = 1 + max(get_height(a.left), get_height(a.right))
print("Balance factor of root:", get_balance(a)) # Output: 0

27. Practical 9a
simple Python program for Represent graphs using adjacency matrices and
lists.
def create_adjacency_matrix(vertices, edges):
n = len(vertices)
matrix = [[0]*n for _ in range(n)]
for u, v in edges:
i, j = vertices.index(u), vertices.index(v)
matrix[i][j] = 1
matrix[j][i] = 1 # For undirected graph
return matrix
# Example
vertices = ['A', 'B', 'C']
edges = [('A', 'B'), ('B', 'C')]
matrix = create_adjacency_matrix(vertices, edges)
print("Adjacency Matrix:")
for row in matrix:
print(row)

28. Practical 9b
Program for Adjacency matrix and list
def create_adjacency_matrix(vertices, edges):
n = len(vertices)
matrix = [[0]*n for _ in range(n)]
for u, v in edges:
i, j = vertices.index(u), vertices.index(v)
matrix[i][j] = 1
matrix[j][i] = 1 # For undirected graph
return matrix
# Example
vertices = ['A', 'B', 'C']
edges = [('A', 'B'), ('B', 'C')]
matrix = create_adjacency_matrix(vertices, edges)
print("Adjacency Matrix:")
for row in matrix:
print(row)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'D'],
'D': ['B', 'C', 'E'],
'E': ['B', 'D']
}

29. # Print adjacency list
for node in graph:
print(f"{node}: {graph[node]}")

30. Practical 10 a
Python program that demonstrates both a min-heap and a max-heap
import heapq
# Min-heap example
min_heap = []
for num in [10, 35, 19, 7, 21, 15, 6, 22, 9]:
heapq.heappush(min_heap, num)
print("Min-heap:", min_heap)
print("Pop min:", heapq.heappop(min_heap))
print("Min-heap after pop:", min_heap)
# Max-heap example (using negative values)
max_heap = []
for num in [10, 35, 19, 7, 21, 15, 6, 22, 9]:
heapq.heappush(max_heap, -num)
print("Max-heap:", [-n for n in max_heap])
print("Pop max:", -heapq.heappop(max_heap))
print("Max-heap after pop:", [-n for n in max_heap])

31. Practical 10b
simple Python program for a hash table using chaining
class HashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
idx = self._hash(key)
# Update value if key already exists
for pair in self.table[idx]:
if pair[0] == key:
pair[1] = value
return
self.table[idx].append([key, value])
def get(self, key):
idx = self._hash(key)
for pair in self.table[idx]:
if pair[0] == key:
return pair[1]
return None
def remove(self, key):

32. idx = self._hash(key)
for i, pair in enumerate(self.table[idx]):
if pair[0] == key:
del self.table[idx][i]
return
def display(self):
for i, bucket in enumerate(self.table):
print(f"{i}: {bucket}")
# Example usage
ht = HashTable(5)
ht.insert("apple", 10)
ht.insert("banana", 20)
ht.insert("grape", 30)
ht.display()
print(ht.get("banana")) # Output: 20
ht.remove("banana")
ht.display()