B.
TECH I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
DATA STRUCTURES LAB
For
B. Tech I Year II Semester
Department of Artificial Intelligence and Machine Learning
Malla Reddy Technical Campus
A Constituent Unit of
Malla Reddy Vishwavidyapeeth
( Deemed to be University )
Approved by UGC & AICTE, New Delhi
Malla Reddy Technical Campus DEPARTMENT OF AIML
1
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
LIST OF EXPERIMENTS:
1. Linked List Implementation
2. Stack ADT
3. Queue ADT
4. Priority Queue
5. Sorting and Searching
6. Tree Traversal
7. Tree Structure – Binary Tree
8. Binary Search Tree Structure
9. Graph Traversals (BFS & DFS)
10. Hash Table
Malla Reddy Technical Campus DEPARTMENT OF AIML
2
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
EXPERIMENT NO.1
LINKED LIST IMPLEMENTATION
OBJECTIVE:
To implement a Singly Linked List using Python classes and perform the following
operations:
• Insert at beginning
• Insert at end
• Insert at a position
• Delete a node
• Traverse the list
HARDWARE REQUIRED:
Personal Computer
SOFTWARE REQUIRED:
Python
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class LinkedList:
def __init__(self):
[Link] = None
# Insert at beginning
def insert_begin(self, data):
new_node = Node(data)
new_node.next = [Link]
[Link] = new_node
Malla Reddy Technical Campus DEPARTMENT OF AIML
3
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
# Insert at end
def insert_end(self, data):
new_node = Node(data)
if [Link] is None:
[Link] = new_node
return
temp = [Link]
while [Link]:
temp = [Link]
[Link] = new_node
# Insert at position (1-based index)
def insert_position(self, data, pos):
new_node = Node(data)
if pos == 1:
self.insert_begin(data)
return
temp = [Link]
for _ in range(pos - 2):
if temp is None:
print("Position out of range")
return
temp = [Link]
new_node.next = [Link]
[Link] = new_node
# Delete a node
def delete_node(self, key):
temp = [Link]
# If head is the node to delete
if temp is not None and [Link] == key:
[Link] = [Link]
return
Malla Reddy Technical Campus DEPARTMENT OF AIML
4
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
prev = None
while temp is not None and [Link] != key:
prev = temp
temp = [Link]
if temp is None:
print("Node not found")
return
[Link] = [Link]
# Display the list
def display(self):
temp = [Link]
while temp:
print([Link], end=" → ")
temp = [Link]
print("NULL")
# Main Program
ll = LinkedList()
ll.insert_begin(30)
ll.insert_end(40)
ll.insert_position(35, 2)
[Link]()
ll.delete_node(35)
[Link]()
OBSERVATIONS:
30 → 35 → 40 → NULL
30 → 40 → NULL
RESULT:
The program successfully demonstrates the creation and manipulation of a singly linked list.
Malla Reddy Technical Campus DEPARTMENT OF AIML
5
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
EXPERIMENT NO.2
STACK ADT (USING OOP IN PYTHON)
OBJECTIVE:
To implement a Stack Abstract Data Type (ADT) using Python classes and perform
operations:
• PUSH
• POP
• PEEK
• DISPLAY
HARDWARE REQUIRED:
Personal Computer
SOFTWARE REQUIRED:
Python
PROGRAM:
class Stack:
def __init__(self):
[Link] = []
# PUSH operation
def push(self, data):
[Link](data)
print(f"Pushed: {data}")
# POP operation
def pop(self):
if not [Link]:
print("Stack Underflow")
return
removed = [Link]()
print(f"Popped: {removed}")
# PEEK operation
def peek(self):
if not [Link]:
print("Stack is Empty")
return
print(f"Top element: {[Link][-1]}")
Malla Reddy Technical Campus DEPARTMENT OF AIML
6
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
# DISPLAY stack
def display(self):
if not [Link]:
print("Stack is Empty")
return
print("Stack (Top → Bottom): ", end="")
for item in reversed([Link]):
print(item, end=" ")
print()
# Main Program
s = Stack()
[Link](10)
[Link](20)
[Link](30)
[Link]()
[Link]()
[Link]()
[Link]()
OBSERVATIONS:
Pushed: 10
Pushed: 20
Pushed: 30
Stack (Top → Bottom): 30 20 10
Popped: 30
Top element: 20
Stack (Top → Bottom): 20 10
RESULT:
The Stack ADT was successfully implemented using Python OOP principles,
demonstrating push, pop, peek, and display operations.
Malla Reddy Technical Campus DEPARTMENT OF AIML
7
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
EXPERIMENT NO.3
QUEUE ADT (USING OOP IN PYTHON)
OBJECTIVE: To implement a Queue Abstract Data Type using Python classes and perform:
• ENQUEUE
• DEQUEUE
• FRONT element
• DISPLAY
HARDWARE REQUIRED:
Personal Computer
SOFTWARE REQUIRED:
Python
PROGRAM:
class Queue:
def __init__(self):
[Link] = []
# ENQUEUE operation
def enqueue(self, data):
[Link](data)
print(f"Enqueued: {data}")
# DEQUEUE operation
def dequeue(self):
if not [Link]:
print("Queue Underflow")
return
removed = [Link](0)
print(f"Dequeued: {removed}")
# FRONT element
def front(self):
if not [Link]:
print("Queue is Empty")
return
print(f"Front element: {[Link][0]}")
Malla Reddy Technical Campus DEPARTMENT OF AIML
8
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
# DISPLAY queue
def display(self):
if not [Link]:
print("Queue is Empty")
return
print("Queue (Front → Rear): ", end="")
for item in [Link]:
print(item, end=" ")
print()
# Main Program
q = Queue()
[Link](10)
[Link](20)
[Link](30)
[Link]()
[Link]()
[Link]()
[Link]()
OBSERVATIONS:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue (Front → Rear): 10 20 30
Dequeued: 10
Front element: 20
Queue (Front → Rear): 20 30
RESULT:
The Queue ADT was successfully implemented using Python OOP, demonstrating
enqueue, dequeue, front, and display operations.
Malla Reddy Technical Campus DEPARTMENT OF AIML
9
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
EXPERIMENT NO.4
PRIORITY QUEUE IMPLEMENTATION (USING OOP IN PYTHON)
OBJECTIVE: To implement a Priority Queue using Python classes, where each element has a
priority and deletion always removes the highest-priority (lowest value number) element.
Operations performed:
• INSERT with priority
• DELETE highest priority element
• DISPLAY queue
HARDWARE REQUIRED:
Personal Computer
SOFTWARE REQUIRED:
Python
PROGRAM:
class PriorityQueue:
def __init__(self):
[Link] = []
# Insert element with priority
def insert(self, data, priority):
[Link]((priority, data))
print(f"Inserted: {data} with Priority: {priority}")
# Delete element with highest priority (smallest number)
def delete(self):
if not [Link]:
print("Priority Queue Underflow")
return
# Find minimum priority tuple
highest = min([Link], key=lambda x: x[0])
[Link](highest)
print(f"Deleted Element: {highest[1]} (Priority: {highest[0]})")
# Display priority queue
def display(self):
if not [Link]:
print("Priority Queue is Empty")
return
Malla Reddy Technical Campus DEPARTMENT OF AIML
10
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
print("Priority Queue (Priority → Element):")
for p, d in sorted([Link]):
print(f"{p} → {d}")
# Main Program
pq = PriorityQueue()
[Link]("A", 3)
[Link]("B", 1)
[Link]("C", 2)
[Link]()
[Link]()
[Link]()
OBSERVATIONS:
Inserted: A with Priority: 3
Inserted: B with Priority: 1
Inserted: C with Priority: 2
Priority Queue (Priority → Element):
1→B
2→C
3→A
Deleted Element: B (Priority: 1)
Priority Queue (Priority → Element):
2→C
3→A
RESULT:
The Priority Queue was successfully implemented. Elements were inserted with
priorities, and deletion successfully removed the element with highest priority using
Python OOP.
Malla Reddy Technical Campus DEPARTMENT OF AIML
11
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
EXPERIMENT NO.5
SORTING AND SEARCHING (USING OOP IN PYTHON)
OBJECTIVE:
To implement sorting (Bubble Sort) and searching (Linear & Binary Search) using OOP in Python.
HARDWARE REQUIRED:
Personal Computer
SOFTWARE REQUIRED:
Python
PROGRAM:
Class SearchingSorting:
def __init__(self, arr):
[Link] = arr
# Bubble Sort
def bubble_sort(self):
n = len([Link])
for i in range(n):
for j in range(0, n - i - 1):
if [Link][j] > [Link][j + 1]:
[Link][j], [Link][j + 1] = [Link][j + 1], [Link][j]
print("Array after Bubble Sort:", [Link])
# Linear Search
def linear_search(self, key):
for i in range(len([Link])):
if [Link][i] == key:
print(f"Linear Search: {key} found at position {i+1}")
return
print("Element not found (Linear Search)")
# Binary Search
def binary_search(self, key):
low = 0
high = len([Link]) - 1
while low <= high:
mid = (low + high) // 2
if [Link][mid] == key:
print(f"Binary Search: {key} found at position {mid+1}")
return
elif [Link][mid] < key:
low = mid + 1
else:
high = mid - 1
print("Element not found (Binary Search)")
Malla Reddy Technical Campus DEPARTMENT OF AIML
12
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
# Main Program
data = [34, 12, 5, 66, 89, 1]
ss = SearchingSorting(data)
ss.bubble_sort()
ss.linear_search(66)
ss.binary_search(12)
OBSERVATIONS:
Array after Bubble Sort: [1, 5, 12, 34, 66, 89]
Linear Search: 66 found at position 5
Binary Search: 12 found at position 3
RESULT:
Sorting (Bubble Sort) and searching (Linear & Binary Search) were successfully
implemented using OOP in Python.
Malla Reddy Technical Campus DEPARTMENT OF AIML
13
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
EXPERIMENT NO.6
TREE TRAVERSALS (USING OOP IN PYTHON)
OBJECTIVE: To implement a Binary Tree and perform the following tree traversal operations:
• Inorder Traversal
• Preorder Traversal
• Postorder Traversal
HARDWARE REQUIRED:
Personal Computer
SOFTWARE REQUIRED:
Python
PROGRAM:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
class BinaryTree:
def __init__(self):
[Link] = None
# Insert nodes manually (Binary Tree, not BST)
def create_sample_tree(self):
[Link] = Node(1)
[Link] = Node(2)
[Link] = Node(3)
[Link] = Node(4)
[Link] = Node(5)
# Inorder Traversal (Left, Root, Right)
def inorder(self, node):
if node:
[Link]([Link])
print([Link], end=" ")
[Link]([Link])
Malla Reddy Technical Campus DEPARTMENT OF AIML
14
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
# Preorder Traversal (Root, Left, Right)
def preorder(self, node):
if node:
print([Link], end=" ")
[Link]([Link])
[Link]([Link])
# Postorder Traversal (Left, Right, Root)
def postorder(self, node):
if node:
[Link]([Link])
[Link]([Link])
print([Link], end=" ")
# Main Program
bt = BinaryTree()
bt.create_sample_tree()
print("Inorder Traversal: ", end="")
[Link]([Link])
print("\nPreorder Traversal: ", end="")
[Link]([Link])
print("\nPostorder Traversal: ", end="")
[Link]([Link])
OBSERVATIONS:
Inorder Traversal: 4 2 5 1 3
Preorder Traversal: 1 2 4 5 3
Postorder Traversal: 4 5 2 3 1
RESULT:
Tree traversals (Inorder, Preorder, and Postorder) were successfully implemented
using Python OOP.
Malla Reddy Technical Campus DEPARTMENT OF AIML
15
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
EXPERIMENT NO.7
TREE STRUCTURE – BINARY TREE CREATION
OBJECTIVE: To create and represent a Binary Tree structure using Python OOP.
HARDWARE REQUIRED:
Personal Computer
SOFTWARE REQUIRED:
Python
PROGRAM:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
class BinaryTreeStructure:
def __init__(self):
[Link] = None
# Manual Binary Tree Construction
def build_tree(self):
[Link] = Node("A")
[Link] = Node("B")
[Link] = Node("C")
[Link] = Node("D")
[Link] = Node("E")
[Link] = Node("F")
# Display Tree (Level Order)
def display(self):
if not [Link]:
return
queue = [[Link]]
print("Binary Tree Structure (Level Order):")
while queue:
node = [Link](0)
print([Link], end=" ")
if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])
Malla Reddy Technical Campus DEPARTMENT OF AIML
16
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
# Main Program
bt = BinaryTreeStructure()
bt.build_tree()
[Link]()
OBSERVATIONS:
RESULT:
The Binary Tree structure was successfully created and displayed using Python
classes.
Malla Reddy Technical Campus DEPARTMENT OF AIML
17
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
EXPERIMENT NO.8
BINARY SEARCH TREE (BST) IMPLEMENTATION (USING OOP IN PYTHON)
OBJECTIVE: To implement a Binary Search Tree using Python OOP, and perform
the following operations:
• Insert a node
• Search for a value
• Inorder Traversal (to display sorted order)
HARDWARE REQUIRED:
Personal Computer
SOFTWARE REQUIRED:
Python
PROGRAM:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
class BinarySearchTree:
def __init__(self):
[Link] = None
# Insert a node
def insert(self, node, data):
if node is None:
return Node(data)
if data < [Link]:
[Link] = [Link]([Link], data)
else:
[Link] = [Link]([Link], data)
return node
def insert_value(self, data):
[Link] = [Link]([Link], data)
Malla Reddy Technical Campus DEPARTMENT OF AIML
18
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
# Search for a value
def search(self, node, key):
if node is None:
return False
if [Link] == key:
return True
elif key < [Link]:
return [Link]([Link], key)
else:
return [Link]([Link], key)
# Inorder traversal (L, R, Root)
def inorder(self, node):
if node:
[Link]([Link])
print([Link], end=" ")
[Link]([Link])
# Main Program
bst = BinarySearchTree()
elements = [50, 30, 20, 40, 70, 60, 80]
for val in elements:
bst.insert_value(val)
print("Inorder Traversal (Sorted): ", end="")
[Link]([Link])
key = 60
print("\nSearching for", key, ":", "Found" if [Link]([Link], key) else "Not Found")
OBSERVATIONS:
RESULT:
A Binary Search Tree was successfully implemented using Python OOP.
Insertion, search, and inorder traversal operations were performed correctly.
Malla Reddy Technical Campus DEPARTMENT OF AIML
19
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
EXPERIMENT NO.9
GRAPH TRAVERSALS – BFS & DFS (USING OOP IN PYTHON)
OBJECTIVE: To represent a graph using Python OOP and perform:
• Breadth-First Search (BFS)
• Depth-First Search (DFS)
HARDWARE REQUIRED:
Personal Computer
SOFTWARE REQUIRED:
Python
PROGRAM:
from collections import deque
class Graph:
def __init__(self):
[Link] = {}
# Add edge
def add_edge(self, u, v):
if u not in [Link]:
[Link][u] = []
[Link][u].append(v)
# BFS Traversal
def bfs(self, start):
visited = set()
queue = deque([start])
print("BFS:", end=" ")
while queue:
node = [Link]()
if node not in visited:
print(node, end=" ")
[Link](node)
for neighbour in [Link](node, []):
[Link](neighbour)
# DFS Traversal
def dfs(self, start, visited=None):
if visited is None:
visited = set()
print(start, end=" ")
[Link](start)
Malla Reddy Technical Campus DEPARTMENT OF AIML
20
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
for neighbour in [Link](start, []):
if neighbour not in visited:
[Link](neighbour, visited)
# Main Program
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 5)
[Link](1)
print("\nDFS:", end=" ")
[Link](1)
OBSERVATIONS:
RESULT:
Graph representation and traversal operations BFS and DFS were successfully
implemented using Python OOP.
Malla Reddy Technical Campus DEPARTMENT OF AIML
21
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
EXPERIMENT NO.10
HASH TABLE IMPLEMENTATION (USING OOP IN PYTHON)
OBJECTIVE:
To implement a hash table using Python OOP with:
• Hash function
• Chaining (Linked List method)
• Insert and Search operations
HARDWARE REQUIRED:
Personal Computer
SOFTWARE REQUIRED:
Python
PROGRAM
class HashTable:
def __init__(self, size):
[Link] = size
[Link] = [[] for _ in range(size)]
# Hash function
def hash_function(self, key):
return key % [Link]
# Insert key
def insert(self, key):
index = self.hash_function(key)
[Link][index].append(key)
print(f"Inserted {key} at index {index}")
# Search key
def search(self, key):
index = self.hash_function(key)
if key in [Link][index]:
print(f"Key {key} found at index {index}")
else:
print("Key not found")
# Display hash table
def display(self):
print("Hash Table:")
for i, bucket in enumerate([Link]):
print(f"Index {i}: {bucket}")
Malla Reddy Technical Campus DEPARTMENT OF AIML
22
[Link] I YEAR II SEMESTER DATA STRUCTURES LAB MANUAL
# Main Program
ht = HashTable(10)
[Link](23)
[Link](43)
[Link](13)
[Link](33)
[Link]()
[Link](43)
OBSERVATIONS:
Inserted 23 at index 3
Inserted 43 at index 3
Inserted 13 at index 3
Inserted 33 at index 3
Hash Table:
Index 0: []
Index 1: []
Index 2: []
Index 3: [23, 43, 13, 33]
Index 4: []
Index 5: []
Index 6: []
Index 7: []
Index 8: []
Index 9: []
Key 43 found at index 3
RESULT:
A hash table was successfully implemented using OOP in Python with chaining for collision
resolution, and operations of insertion and search were demonstrated
Malla Reddy Technical Campus DEPARTMENT OF AIML
23