Data Structures in Python

Posted on May 4, 2024 in Computers

Factorial Calculation in Python
def recur_factorial(n):
      if n==1:
           return n
      else:
            return n*recur_factorial(n-1)
num=4
if num<0 :
    print(” sorry factorial does not exist for negative number”)
elif num == 0:
        print(” the factorial of 0 is 1″)
else:
        print (” the factorial of”,num ,recur_factorial(num))
Algorithm for Factorial Calculation
Step 1 : start
Step 2: take input from the user for finding the factorial
Step3: create a variable ‘factorial’ and assign the value 
Step 4: If (number < 0)
        Print cannot be calculated 
Elif (number ==1)
Print 1
Else :
      For I in range (1,number+1)
   Factorial *=1
Step 5 : Print factorial 
Step 6 : stop
Bracket Matching Implementation
open_list = [“[“, “{“, “(“]
close_list = [“]”, “}”, “)”]
def check(myStr):
  stack = []
  for i in myStr:
      if i in open_list:
        stack.append(i)
      elif i in close_list:
        pos = close_list.index(i)
        if (len(stack) > 0) and (open_list[pos] == stack[len(stack) – 1]):
            stack.pop()
        else:
            return “unbalanced”
  if len(stack) == 0:
      return “balanced”
  else:
      return “unbalanced”
String = “{[ ] { ( ) }}”
print(String, “=”, check(String))
String = “[ { } { } ) ( ]”
print(String, “=”, check(String))
String = “( ( ( )”
print(String, “=”, check(String))
Tower of Hanoi
def TowerOfHanoi (n,source,destination,auxilary):
    if n==1:
        print(“move disk 1 from source “, source,”to destination”, destination)
       return
   TowerOfHanoi(n-1, source, auxiliary, destination)
       print(“move disk”, n,”from source “,source, “to destination”, destination)
        n = 3
        TowerOfHanoi (n,’A’,’B’,’C’)
Doubly Linked List Implementation
# Initialise the Node
class Node:
    def __init__(self, data):
        self.item = data
        self.next = None
        self.prev = None
# Class for doubly Linked List
class doublyLinkedList:
    def __init__(self):
        self.start_node = None
    # Insert Element to Empty list
    def InsertToEmptyList(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
        else:
            print(“The list is empty”)
    # Insert element at the end
    def InsertToEnd(self, data):
        # Check if the list is empty
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
            return
        n = self.start_node
        # Iterate till the next reaches NULL
        while n.next is not None:
            n = n.next
        new_node = Node(data)
        n.next = new_node
        new_node.prev = n
    # Delete the elements from the start
    def DeleteAtStart(self):
        if self.start_node is None:
            print(“The Linked list is empty, no element to delete”)
            return 
        if self.start_node.next is None:
            self.start_node = None
            return
        self.start_node = self.start_node.next
        self.start_prev = None;
  # Delete the elements from the end
    def delete_at_end(self):
        # Check if the List is empty
        if self.start_node is None:
            print(“The Linked list is empty, no element to delete”)
            return 
        if self.start_node.next is None:
            self.start_node = None
            return
        n = self.start_node
        while n.next is not None:
            n = n.next
        n.prev.next = None
    # Traversing and Displaying each element of the list
    def Display(self):
        if self.start_node is None:
            print(“The list is empty”)
            return
        else:
            n = self.start_node
            while n is not None:
                print(“Element is: “, n.item)
                n = n.next
        print(“\n”)
# Create a new Doubly Linked List
NewDoublyLinkedList = doublyLinkedList()
# Insert the element to empty list
NewDoublyLinkedList.InsertToEmptyList(10)
# Insert the element at the end
NewDoublyLinkedList.InsertToEnd(20)
NewDoublyLinkedList.InsertToEnd(30)
NewDoublyLinkedList.InsertToEnd(40)
NewDoublyLinkedList.InsertToEnd(50)
NewDoublyLinkedList.InsertToEnd(60)
# Display Data
NewDoublyLinkedList.Display()
# Delete elements from start
NewDoublyLinkedList.DeleteAtStart()
# Delete elements from end
NewDoublyLinkedList.DeleteAtStart()
# Display Data
NewDoublyLinkedList.Display()
Queue Implementation
class Queue:
    def __init__(self):
        self.queue = []
    def enqueue (self,item):
        self.queue.append(item)
    def dequeue (self):
        if len (self.queue)<1:
            return None
        return self.queue.pop(0)
    def display(self):
        print(self.queue)
    def size (self):
        return len(self,queue)
q=Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.display()
q.dequeue()
print(“After removing an element”)
q.display()
Stack Implementation
def create_Stack():         
    Stack = []
    return Stack
def check_Empty(Stack):
    return len (Stack)==0
def push(Stack, item):
    Stack.append(item)
    print(“Pushed Item:”,item)
def pop(Stack):
    if(check_Empty(Stack)):
        return “Stack is Empty”
    return Stack.pop()
Stack = create_Stack()
push(Stack, str(1))
push(Stack, str(2))
push(Stack, str(3))
push(Stack, str(4))
print(“Popped Item”,pop(Stack))
print(“Stack after popping an element”, str(Stack))
Circular Doubly Linked List Implementation
# Python3 program to illustrate inserting
# a Node in a Circular Doubly Linked list
# in begging, end and middle
#start = None
# Structure of a Node
class Node:
 def __init__(self, data):
  self.data = data
  self.next = None
  self.prev = None
# Function to insert at the end
def insertEnd(value) :
 global start
 # If the list is empty, create a
 # single node circular and doubly list
 if (start == None) :
  new_node = Node(0)
  new_node.data = value
  new_node.next = new_node.prev = new_node
  start = new_node
  return
 # If list is not empty
 # Find last node */
 last = (start).prev
 # Create Node dynamically
 new_node = Node(0)
 new_node.data = value
 # Start is going to be next of new_node
 new_node.next = start
 # Make new node previous of start
 (start).prev = new_node
 # Make last previous of new node
 new_node.prev = last
 # Make new node next of old last
 last.next = new_node
# Function to insert Node at the beginning
 # of the List,
def insertBegin( value) :
 global start
 # Pointer points to last Node
 last = (start).prev
 new_node = Node(0)
 new_node.data = value # Inserting the data
 # setting up previous and
 # next of new node
 new_node.next = start
 new_node.prev = last
 # Update next and previous pointers
 # of start and last.
 last.next = (start).prev = new_node
 # Update start pointer
 start = new_node
# Function to insert node with value as value1.
# The new node is inserted after the node with
# with value2
def insertAfter(value1, value2) :
 global start
 new_node = Node(0)
 new_node.data = value1 # Inserting the data
 # Find node having value2 and
 # next node of it
 temp = start
 while (temp.data != value2) :
  temp = temp.next
 next = temp.next
 # insert new_node between temp and next.
 temp.next = new_node
 new_node.prev = temp
 new_node.next = next
 next.prev = new_node
def display() :
 global start
 temp = start
 print (“Traversal in forward direction:”)
 while (temp.next != start) :
  print (temp.data, end = ” “)
  temp = temp.next
 print (temp.data)
# Driver Code
#start = None
if __name__ == ‘__main__’:
    global start # Start with the empty list
    start = None
 # Insert 5. So linked list becomes 5.None
    insertEnd(5)
 # Insert 4 at the beginning. So linked
 # list becomes 4.5
    insertBegin(4)
 # Insert 7 at the end. So linked list
 # becomes 4.5.7
    insertEnd(7)
 # Insert 8 at the end. So linked list
 # becomes 4.5.7.8
    insertEnd(8)
 # Insert 6, after 5. So linked list
 # becomes 4.5.6.7.8
    insertAfter(6, 5)
    print (“Created circular doubly linked list is: “)
    display()
Singly Linked List Implementation
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
         self.head = None
         self.last_node = None
    def append(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next
  # Deleting a node
    def deleteNode(self, position):
        if self.head is None:
            return
        temp = self.head
        if position == 0:
            self.head = temp.next
            temp = None
            return
        # Find the key to be deleted
        for i in range(position – 1):
            temp = temp.next
            if temp is None:
                break
 # If the key is not present
        if temp is None:
            return
  if temp.next is None:
            return
        next = temp.next.next
        temp.next = None
        temp.next = next
    def display(self):
        current = self.head
        while current is not None:
            print(current.data)
            current = current.next
    def find_index(self, key):
        current = self.head
        index = 0
        while current:
            if current.data == key:
                return index
            current = current.next
  index = index + 1
        return -1
a_llist = LinkedList()
for data in [4, -3, 1, 0, 9, 11]:
    a_llist.append(data)
print(‘The linked list: ‘)
a_llist.display()
print()
print(“\nAfter deleting an element:”)
a_llist.deleteNode(9)
a_llist.display()
print()
key = int(input(‘What data item would you like to search for? ‘))
index = a_llist.find_index(key)
if index == -1:
    print(str(key) + ‘ was not found.’)
else:
print(str(key) + ‘ is found at index ‘ + str(index) + ‘.’)