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 = array.array('i', [1, 2, 3])
arr2 = array.array('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 = array.array('i', [1, 2, 3])
arr2 = array.array('i', [4, 5, 6])
print("arr1 is:", arr1)
print("arr2 is:", arr2)
arr1.append(4)
print("\nAfter arr1.append(4), arr1 is:", arr1)
arr1.extend(arr2)
print("\nAfter arr1.extend(arr2), arr1 is:", arr1)
arr1.insert(0, 10)
print("\nAfter arr1.insert(0, 10), arr1 is:", arr1)
Output:
arr1 is: array('i', [1, 2, 3])
arr2 is: array('i', [4, 5, 6])
After arr1.append(4), arr1 is: array('i', [1, 2, 3, 4])
After arr1.extend(arr2), arr1 is: array('i', [1, 2, 3, 4, 4, 5, 6])
After arr1.insert(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]
lst.remove(2)
print(lst)
lst.pop(0)
print(lst)
lst.pop()
print(lst)
del lst[0]
print(lst)
del lst
lst = [1, 2, 3, 4]
print(lst)
lst.clear()
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):
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:
print("Stack is empty. Cannot pop.")
return None
def peek(self):
if not self.is_empty():
return self.stack[-1]
else:
print("Stack is empty. Cannot peek.")
return None
def size(self):
return len(self.stack)
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print("Stack:", stack.stack)
print("Peek:", stack.peek())
print("Pop:", stack.pop())
print("Stack:", stack.stack)
print("Is Empty?", stack.is_empty())
print("Stack Size:", stack.size())
Implementation of circular queue operations in data structure:
class CircularQueue:
def __init__(self, size):
self.maxSize = size
self.queueArray = [0] * size
self.front = -1
self.rear = -1
def enqueue(self, item):
if self.isEmpty():
self.front = 0
self.rear = 0
self.queueArray[self.rear] = item
else:
self.rear = (self.rear + 1) % self.maxSize
if self.rear == self.front:
print("Queue is full. Cannot enqueue.")
self.rear = (self.rear - 1 + self.maxSize) % self.maxSize
else:
self.queueArray[self.rear] = item
def dequeue(self):
item = -1 # Assuming -1 represents an empty value
if not self.isEmpty():
item = self.queueArray[self.front]
if self.front == self.rear:
self.front = -1
self.rear = -1
else:
self.front = (self.front + 1) % self.maxSize
else:
print("Queue is empty. Cannot dequeue.")
return item
def peek(self):
if not self.isEmpty():
return self.queueArray[self.front]
else:
print("Queue is empty. No peek value.")
return -1 # Assuming -1 represents an empty value
def isEmpty(self):
return self.front == -1 and self.rear == -1
if __name__ == "__main__":
circularQueue = CircularQueue(5)
circularQueue.enqueue(1)
circularQueue.enqueue(2)
circularQueue.enqueue(3)
# Should print 1
print("Peek:", circularQueue.peek())
# Should print 1
print("Dequeue:", circularQueue.dequeue())
# Should print 2
print("Peek after dequeue:", circularQueue.peek())
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 == '(':
st.append('(')
elif c == ')':
while st[-1] != '(':
result += st.pop()
st.pop()
else:
while st and (prec(c) < prec(st[-1]) or prec(c) == prec(st[-1])):
result += st.pop()
st.append(c)
while st:
result += st.pop()
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):
self.data = data
self.next = 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 current.next:
current = current.next
current.next = new_node
return head
def traverse(head):
current = head
while current:
print(current.data, end=" -> ")
current = current.next
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):
self.data = data
self.next = 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 = head.next
del head
return new_head
def traverse(head):
current = head
while current:
print(current.data, end=" -> ")
current = current.next
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):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
new_node.next = self.head
else:
new_node.next = self.head
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = new_node
self.head = new_node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
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):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
new_node.next = new_node
self.head = new_node
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
def delete_at_beginning(self):
if not self.head:
print("Circular Linked List is empty")
return
if self.head.next == self.head:
self.head = None
return
current = self.head
while current.next != self.head:
current = current.next
current.next = self.head.next
self.head = self.head.next
def display(self):
if not self.head:
print("Circular Linked List is empty")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
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):
self.data = data
self.next = None
self.prev = None
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head
if head:
head.prev = new_node
return new_node
def display(head):
current = head
while current:
print(current.data, end=" <-> ")
current = current.next
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):
self.data = data
self.next = None
self.prev = None
def delete_at_beginning(head):
if head is None:
print("Doubly linked list is empty")
return None
if head.next is None:
return None
new_head = head.next
new_head.prev = None
del head
return new_head
def traverse(head):
current = head
while current:
# Print current node's data
print(current.data, end=" <-> ")
# Move to the next node
current = current.next
print("None")
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head
if head:
head.prev = 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):
self.data = x
self.next = None
self.prev = None
def insertAtBeginning(head, newData):
newNode = Node(newData)
if head is None:
newNode.next = newNode.prev = newNode
head = newNode
else:
last = head.prev
newNode.next = head
newNode.prev = last
head.prev = newNode
last.next = newNode
head = newNode
return head
def printList(head):
if not head:
return
curr = head
while True:
print(curr.data, end=" ")
curr = curr.next
if curr == head:
break
print()
head = Node(10)
head.next = Node(20)
head.next.prev = head
head.next.next = Node(30)
head.next.next.prev = head.next
head.next.next.next = head
head.prev = head.next.next
head = insertAtBeginning(head, 5)
printList(head)
Implementation of queue using linked list:
class Node:
def __init__(self, new_data):
self.data = new_data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
def is_empty(self):
return self.front is None and self.rear is None
def enqueue(self, new_data):
new_node = Node(new_data)
if self.rear is None:
self.front = self.rear = new_node
return
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.is_empty():
print("Queue Underflow")
return
temp = self.front
self.front = self.front.next
if self.front is None:
self.rear = None
def get_front(self):
if self.is_empty():
print("Queue is empty")
return float('-inf')
return self.front.data
def get_rear(self):
if self.is_empty():
print("Queue is empty")
return float('-inf')
return self.rear.data
if __name__ == "__main__":
q = Queue()
q.enqueue(10)
q.enqueue(20)
print("Queue Front:", q.get_front())
print("Queue Rear:", q.get_rear())
q.dequeue()
q.dequeue()
q.enqueue(30)
q.enqueue(40)
q.enqueue(50)
q.dequeue()
print("Queue Front:", q.get_front())
print("Queue Rear:", q.get_rear())
