DATA STRUCTURE WITH PYTHON
LAB MANUAL
SEACOM ENGINEERING COLLEGE
SUBJECT TEACHER- MR. SUBHANKAR ROY
EXPERIMENT NO1:- Implementation of data structure operations (insertion,
deletion, traversing and searching) in array. Linear search and binary search
Solve:-
Inserting an Element to an array using array module
With the array module, you can concatenate, or join, arrays using the + operator
and you can add elements to an array using the append(), extend(),
and insert() methods.
Program code:
import array
arr1 = [Link]('i', [1, 2, 3])
arr2 = [Link]('i', [4, 5, 6])
print("arr1 is:", arr1)
print("arr2 is:", arr2)
arr3 = arr1 + arr2
print("After arr3 = arr1 + arr2, arr3 is:", arr3)
Output:
arr1 is: array('i', [1, 2, 3])
arr2 is: array('i', [4, 5, 6])
After arr3 = arr1 + arr2, arr3 is: array('i', [1, 2, 3, 4, 5, 6])
The preceding example creates a new array that contains all the elements of the the
given arrays.
The following example demonstrates how to add to an array using
the append(), extend(), and insert() methods:
import array
arr1 = [Link]('i', [1, 2, 3])
arr2 = [Link]('i', [4, 5, 6])
print("arr1 is:", arr1)
print("arr2 is:", arr2)
[Link](4)
print("\nAfter [Link](4), arr1 is:", arr1)
[Link](arr2)
print("\nAfter [Link](arr2), arr1 is:", arr1)
[Link](0, 10)
print("\nAfter [Link](0, 10), arr1 is:", arr1)
Output:
arr1 is: array('i', [1, 2, 3])
arr2 is: array('i', [4, 5, 6])
After [Link](4), arr1 is: array('i', [1, 2, 3, 4])
After [Link](arr2), arr1 is: array('i', [1, 2, 3, 4, 4, 5, 6])
After [Link](0, 10), arr1 is: array('i', [10, 1, 2, 3, 4, 4, 5, 6])
Deletion an Element to an array using array module:
There are 4 methods for deleting from a list in Python:
remove() - This method removes a certain element from the list. In case of
multiple occurrences of that element, it removes the first occurrence.
pop() - This method removes the element from a certain index from the list.
If no argument is provided this method removes the last element from the
list.
del - del keyword can be used to delete a certain index of an list or the whole
list itself.
clear() - This method can be used to delete all the elements from the list.
Program Code:
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[Link](2)
print(lst)
[Link](0)
print(lst)
[Link]()
print(lst)
del lst[0]
print(lst)
del lst
lst = [1, 2, 3, 4]
print(lst)
[Link]()
print(lst)
EXPERIMENT NO2:- Implement of Stack, queue operation using array. Pop,
Push, Insertion, deletion, Implementation of Circular queue. Infix to postfix
expression evaluation.
Implementation of stack operations in data structure:
class Stack:
def __init__(self):
[Link] = []
def is_empty(self):
return len([Link]) == 0
def push(self, item):
[Link](item)
def pop(self):
if not self.is_empty():
return [Link]()
else:
print("Stack is empty. Cannot pop.")
return None
def peek(self):
if not self.is_empty():
return [Link][-1]
else:
print("Stack is empty. Cannot peek.")
return None
def size(self):
return len([Link])
stack = Stack()
[Link](1)
[Link](2)
[Link](3)
print("Stack:", [Link])
print("Peek:", [Link]())
print("Pop:", [Link]())
print("Stack:", [Link])
print("Is Empty?", stack.is_empty())
print("Stack Size:", [Link]())
Implementation of circular queue operations in data structure:
class CircularQueue:
def __init__(self, size):
[Link] = size
[Link] = [0] * size
[Link] = -1
[Link] = -1
def enqueue(self, item):
if [Link]():
[Link] = 0
[Link] = 0
[Link][[Link]] = item
else:
[Link] = ([Link] + 1) % [Link]
if [Link] == [Link]:
print("Queue is full. Cannot enqueue.")
[Link] = ([Link] - 1 + [Link]) % [Link]
else:
[Link][[Link]] = item
def dequeue(self):
item = -1 # Assuming -1 represents an empty value
if not [Link]():
item = [Link][[Link]]
if [Link] == [Link]:
[Link] = -1
[Link] = -1
else:
[Link] = ([Link] + 1) % [Link]
else:
print("Queue is empty. Cannot dequeue.")
return item
def peek(self):
if not [Link]():
return [Link][[Link]]
else:
print("Queue is empty. No peek value.")
return -1 # Assuming -1 represents an empty value
def isEmpty(self):
return [Link] == -1 and [Link] == -1
if __name__ == "__main__":
circularQueue = CircularQueue(5)
[Link](1)
[Link](2)
[Link](3)
# Should print 1
print("Peek:", [Link]())
# Should print 1
print("Dequeue:", [Link]())
# Should print 2
print("Peek after dequeue:", [Link]())
Implementation of evaluating Infix to Postfix expression in data
structure:
Function to return precedence of operators
def prec(c):
if c == '^':
return 3
elif c == '/' or c == '*':
return 2
elif c == '+' or c == '-':
return 1
else:
return -1
Function to perform infix to postfix conversion
def infixToPostfix(s):
st = []
result = ""
for i in range(len(s)):
c = s[i]
if (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z') or (c >= '0' and c <= '9'):
result += c
elif c == '(':
[Link]('(')
elif c == ')':
while st[-1] != '(':
result += [Link]()
[Link]()
else:
while st and (prec(c) < prec(st[-1]) or prec(c) == prec(st[-1])):
result += [Link]()
[Link](c)
while st:
result += [Link]()
print(result)
exp = "a+b*(c^d-e)^(f+g*h)-i"
infix To Postfix(exp)
EXPERIMENT NO3:- Implementation of linked lists: Single linked list, circular
linked list, double linked list, doubly circular linked list. Implementation of stack
and queue using linked list. Merging two linked list, Linked list representation of a
polynomial, polynomial addition, polynomial multiplication.
Implementation of single linked list in data structure:
Insertion of linked list
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head
return new_node
def insert_at_end(head, data):
new_node = Node(data)
if head is None:
return new_node
current = head
while [Link]:
current = [Link]
[Link] = new_node
return head
def traverse(head):
current = head
while current:
print([Link], end=" -> ")
current = [Link]
print("None")
head = None
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
insert_at_end(head, 4)
traverse(head)
Deletion of the Single Linked list
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head
return new_node
def delete_at_beginning(head):
if head is None:
print("Error: Singly linked list is empty")
return None
new_head = [Link]
del head
return new_head
def traverse(head):
current = head
while current:
print([Link], end=" -> ")
current = [Link]
print("None")
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
head = delete_at_beginning(head)
traverse(head)
Implementation of the circular linked list in Data Structure:
Insertion in Circular Linked List:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class LinkedList:
def __init__(self):
[Link] = None
def insert_at_beginning(self, data):
new_node = Node(data)
if not [Link]:
[Link] = new_node
new_node.next = [Link]
else:
new_node.next = [Link]
temp = [Link]
while [Link] != [Link]:
temp = [Link]
[Link] = new_node
[Link] = new_node
def display(self):
current = [Link]
while current:
print([Link], end=" -> ")
current = [Link]
print("None")
linked_list = LinkedList()
linked_list.insert_at_beginning(3)
linked_list.insert_at_beginning(2)
linked_list.insert_at_beginning(1)
print("Linked List after insertion at the beginning:")
linked_list.display()
Deletion in Circular Linked List:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class CircularLinkedList:
def __init__(self):
[Link] = None
def append(self, data):
new_node = Node(data)
if not [Link]:
new_node.next = new_node
[Link] = new_node
else:
current = [Link]
while [Link] != [Link]:
current = [Link]
[Link] = new_node
new_node.next = [Link]
def delete_at_beginning(self):
if not [Link]:
print("Circular Linked List is empty")
return
if [Link] == [Link]:
[Link] = None
return
current = [Link]
while [Link] != [Link]:
current = [Link]
[Link] = [Link]
[Link] = [Link]
def display(self):
if not [Link]:
print("Circular Linked List is empty")
return
current = [Link]
while True:
print([Link], end=" -> ")
current = [Link]
if current == [Link]:
break
print("", end="")
circular_list = CircularLinkedList()
circular_list.append(1)
circular_list.append(2)
circular_list.append(3)
print("Circular Linked List before deletion:")
circular_list.display()
print()
circular_list.delete_at_beginning()
print("Circular Linked List after deletion at the beginning:")
circular_list.display()
Implementation of double linked list in data structure:
Insertion of double linked list:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head
if head:
[Link] = new_node
return new_node
def display(head):
current = head
while current:
print([Link], end=" <-> ")
current = [Link]
print("None")
head = None
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
print("Doubly Linked List after insertion at the beginning:")
display(head)
Deletion of double linked list:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
def delete_at_beginning(head):
if head is None:
print("Doubly linked list is empty")
return None
if [Link] is None:
return None
new_head = [Link]
new_head.prev = None
del head
return new_head
def traverse(head):
current = head
while current:
# Print current node's data
print([Link], end=" <-> ")
# Move to the next node
current = [Link]
print("None")
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head
if head:
[Link] = new_node
return new_node
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
head = delete_at_beginning(head)
traverse(head)
Implementation of doubly Circular linked list in data structure:
Insertion of the Doubly circular linked list:
class Node:
def __init__(self, x):
[Link] = x
[Link] = None
[Link] = None
def insertAtBeginning(head, newData):
newNode = Node(newData)
if head is None:
[Link] = [Link] = newNode
head = newNode
else:
last = [Link]
[Link] = head
[Link] = last
[Link] = newNode
[Link] = newNode
head = newNode
return head
def printList(head):
if not head:
return
curr = head
while True:
print([Link], end=" ")
curr = [Link]
if curr == head:
break
print()
head = Node(10)
[Link] = Node(20)
[Link] = head
[Link] = Node(30)
[Link] = [Link]
[Link] = head
[Link] = [Link]
head = insertAtBeginning(head, 5)
printList(head)
Implementation of queue using linked list:
class Node:
def __init__(self, new_data):
[Link] = new_data
[Link] = None
class Queue:
def __init__(self):
[Link] = None
[Link] = None
def is_empty(self):
return [Link] is None and [Link] is None
def enqueue(self, new_data):
new_node = Node(new_data)
if [Link] is None:
[Link] = [Link] = new_node
return
[Link] = new_node
[Link] = new_node
def dequeue(self):
if self.is_empty():
print("Queue Underflow")
return
temp = [Link]
[Link] = [Link]
if [Link] is None:
[Link] = None
def get_front(self):
if self.is_empty():
print("Queue is empty")
return float('-inf')
return [Link]
def get_rear(self):
if self.is_empty():
print("Queue is empty")
return float('-inf')
return [Link]
if __name__ == "__main__":
q = Queue()
[Link](10)
[Link](20)
print("Queue Front:", q.get_front())
print("Queue Rear:", q.get_rear())
[Link]()
[Link]()
[Link](30)
[Link](40)
[Link](50)
[Link]()
print("Queue Front:", q.get_front())
print("Queue Rear:", q.get_rear())