<repo_name>kartiktanksali/Data-Structures<file_sep>/LinkedList(Singly).py
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 29 22:20:37 2019

@author: kartiktanksali
"""

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        
class LinkedList:
    def __init__(self):
        self.head = None
        
            
    def push(self,data):
        new_node = Node(data)
        if self.head==None:
            self.head=new_node
        else:
            new_node.next = self.head
            self.head = new_node
        print("Element Pushed")
        
    def append(self,data):
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
            print("Element Appended")
        temp = self.head
        while(temp.next):
            temp = temp.next
        temp.next = new_node
        print("Element appended")
    
    def deleteFront(self):
        if self.head == None:
            print("No elements present to delete")
        else:
            temp = self.head.next
            self.head = temp
            print("Element deleted")
        
    def insert(self,pos,val):
        new_node = Node(val)
        temp = self.head
        prev = self.head
        for i in range(pos):
            prev = temp
            temp = temp.next
        prev.next = new_node
        new_node.next = temp
        print("Element inserted")
        
    def delete(self,key):
        if self.head==None:
            print("No elements to delete")
            return
        elif self.head.data == key:
            self.head = self.head.next
            return
        temp = self.head
        prev = self.head
        while(temp is not None):
            if temp.data==key:
                prev.next = temp.next
                print("Element Deleted")
                return
            else:
                prev = temp
                temp = temp.next
        print("Key not found")
        
        
        
    def deletePos(self,pos):
        if pos == 1:
            self.head = self.head.next
            print("Element Deleted")
            return
        temp = self.head
        prev = self.head
        for i in range(pos-1):
            prev = temp
            temp = temp.next
            
        prev.next = temp.next
        print("Element Deleted")
        
        
    def findLength(self):
        count=0
        if self.head==None:
            return 0
        if self.head.next==None:
            return 1
        
        temp = self.head
        while(temp):
            temp = temp.next
            count+=1
        return count
    
    def checkElement(self,key):
        if self.head==None:
            print("No element present to search")
        elif self.head==key:
            print("Element Found")
        else:
            temp = self.head
            while(temp):
                if temp.data==key:
                    print("Element Found")
                    return
                else:
                    temp = temp.next
            print("Element not Found")
        
    def PrintList(self):
        if self.head==None:
            print("No Linked List present to print")
        else:
            temp = self.head
            while(temp):
                print(temp.data)
                temp = temp.next
        
    def deleteList(self):
        if self.head==None:
            print("List if already null")
        else:
            temp = self.head
            self.head=None
            while(temp):
                prev = temp
                temp = temp.next
                del prev.data
            print("List Deleted")
            
    
    
        

if __name__ == "__main__":
    
    ch=0
    llist = LinkedList()
    while(ch<11):
        print("1) Push an element(Insert at front")
        print("2) Append an element(Insert at Rear")
        print("3) Delete an element from the front")
        print("4) Insert at a position")
        print("5) Delete a key")
        print("6) Delete at a position")
        print("7) Length of the List")
        print("8) Check for a element")
        print("9) Print the List")
        print("10) Delete the LinkedList")
        print("Enter your choice: ")
        ch = int(input())
    
        
        
        if ch==1:
            ele = int(input("Enter the element to be pushed: "))
            llist.push(ele)
        elif ch==2:
            ele = int(input("Enter the element to be appended: "))
            llist.append(ele)
        elif ch==3:
            llist.deleteFront()
        elif ch==4:
            ele = int(input("Enter the element to be inserted: "))
            pos = int(input("Enter the position to be inserted: "))
            llist.insert(pos,ele)
        elif ch==5:
            ele = int(input("Enter the element to be deleted: "))
            llist.delete(ele)
        elif ch==6:
            pos = int(input("Enter the position from the element should be deleted: "))
            llist.deletePos(pos)
        elif ch==7:
            res = llist.findLength()
            print("The length of the list: ",res)
        elif ch==8:
            ele = int(input("Enter an element to be searched: "))
            llist.checkElement(ele)
        elif ch==9:
            llist.PrintList()
        elif ch==10:
            llist.deleteList()
       
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    <file_sep>/CircularLinkedList.py
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 31 10:07:23 2019

@author: kartiktanksali
"""

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        
    def push(self,data):
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
            self.tail.next = self.head
        else:
            new_node.next = self.head
            self.head = new_node
            self.tail.next = new_node
    
    def append(self,data):
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
            self.tail.next = self.head
        else:
            self.tail.next = new_node
            self.tail = new_node
            self.tail.next = self.head
    
    def deleteFront(self):
        if self.head == None:
            print("No elements present to delete")
        elif self.head == self.tail:
            self.head = None
            print("Element deleted and also the linked list is empty")
        else:
            self.head = self.head.next
            self.tail.next = self.head
            print("Element Deleted")
    
    def deleteRear(self):
        if self.head == None:
            print("No elements present to delete")
        elif self.head == self.tail:
            self.head = None
            print("Element deleted and also the linked is empty")
        else:
            temp = self.head
            while(temp.next!=self.tail):
                temp = temp.next
            
            temp.next = self.head
            self.tail = temp
            self.tail.next = self.head
            print("Element Deleted")
       
    def insertPos(self,pos,data):
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
            self.tail.next = self.head
        else:
            temp = self.head
            for _ in range(pos):
                temp = temp.next
            
            if temp == self.tail:
                self.append(data)
            else:
                new_node.next = temp.next
                temp.next = new_node
                print("Element inserted")

                
            
    def printList(self):
        if self.head==None:
            print("No elements present to print")
        else:
            temp = self.head
            while(temp):
                print(temp.data)
                if temp.next==self.head:
                    return
                temp = temp.next
                
                
                
        
    
if __name__ == "__main__":
    
    llist = LinkedList()
    
    ch=0
    
    while(ch<7):
        print("1) Push an element")
        print("2) Append an element")
        print("3) Delete an element in the front")
        print("4) Delete an element from the rear")
        print("5) Insert at a position")
        print("6) Print list")
        
        ch = int(input("Enter your choice: "))
        print()
        
        if ch==1:
            ele = int(input("Enter the element you want to push: "))
            llist.push(ele)
        elif ch==2:
            ele = int(input("Enter the element you want to append: "))
            llist.append(ele)
        elif ch==3:
            llist.deleteFront()
        elif ch==4:
            llist.deleteRear()
        elif ch==5:
            ele = int(input("Enter the element to be inserted: "))
            pos = int(input("Enter the position: "))
            llist.insertPos(pos,ele)
        elif ch==6:
            llist.printList()
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            <file_sep>/Dynamic_Stack_Demonstration.py
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 16:01:11 2019

@author: kartiktanksali
"""

#Demonstration of implmenting a dynamic stack
#Note: The list in pyhton are dynamic in their memory allocation, therefore this is a demonstration.


max_size=5
lst = [" "]*max_size
ch=0
top=-1


def push():
    global top
    global lst
    global max_size
    if top!=max_size-1:
        max_size = max_size*2
        lst.append(" "*max_size)
    element = int(input("Enter the element to be entered: "))
    top+=1
    lst[top]=element
    return f"{element} Pushed"
        

def pop():
    global top
    global lst
    if top!=-1:
        element = lst[top]
        top-=1
        return f"{element} popped"
    

def tops():
    global top
    global lst
    if top!=-1:
        return lst[top]
    else:
        return "No element present in the stack"
    
def display():
    global top
    global lst
    if top!=-1:
        for i in range(top+1):
            print(lst[i],end=" ")
    else:
        print("Stack is now empty")
        

while(ch<5):
    print("\n 1)Push \n 2)Pop \n 3)Top \n 4)Display \n 5)Exit \n")
    ch = int(input("Enter your choice: "))
    
    if ch==1:
        res = push()
        print(res)
        display()
    elif ch==2:
        res = pop()
        print(res)
        display()
    elif ch==3:
        res = tops()
        print(res)
    elif ch==4:
        display()
        <file_sep>/BinarySearchTree.py
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Apr 16 22:24:56 2019

@author: kartiktanksali
"""
count = 0
INT_MAX = 4294967296
INT_MIN = -4294967296

class Node:
    
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        

        
class Tree:
    
    def __init__(self):
        self.root = None
        

    
    def getRoot(self):
        return self.root
    
    
    
    def insertNode(self,root,node):
        if root == None:
            self.root = node
        else:
            if node.data <= root.data:
                if root.left == None:
                    root.left = node
                    print("Node Inserted")
                else:
                    self.insertNode(root.left,node)
            elif node.data > root.data:
                if root.right == None:
                    root.right = node
                    print("Node Inserted")
                else:
                    self.insertNode(root.right,node)
                    
                    
    def minimum(self,root):
        if root == None:
            print("No tree present")
        else:
            temp = root
            while(temp.left != None):
                temp = temp.left
        
        print("Minimum Value is ",temp.data)
        return temp
    
    
    def maximum(self,root):
        if root == None:
            print("No tree present")
            return 0
        else:
            temp = root
            while(temp.right!=None):
                temp = temp.right
        print("Maximum Value is ",temp.data)
        return temp
        
        
    def deleteNode(self,root,data):
        if root == None:
            print("No elements to delete")
            return root
                
        if data < root.data:
            root.left = self.deleteNode(root.left,data)
        elif data > root.data:
            root.right = self.deleteNode(root.right,data)
        elif data == root.data:
            if root.left is None:
                temp = root.right
                root = None
                return temp
            elif root.right is None:
                temp = root.left
                root = None
                return temp
            
            temp = self.minimum(root.right)
            
            root.data = temp.data
            
            root.right = self.deleteNode(root.right,temp.data)
            
        return root
        
    
    
    def getCount(self,root):
        if root == None:
            return 0
        else:
            return self.getCount(root.left) + self.getCount(root.right) + 1
        
    def getHeight(self,root):
        if root == None:
            return -1
        else:
            return max(self.getHeight(root.left),self.getHeight(root.right)) + 1
                    
            
    def search(self,root,data):
        if root is None or root.data == data:
            return root
        else:
            if data <= root.data:
                return self.search(root.left,data)
            elif data > root.data:
                return self.search(root.right,data)
            
    def breadthFirstSearch(self,root):
        if root == None:
            return 
        else:
            queue = []
            queue.append(root)
            while(len(queue)>0):
                current = queue[0]
                print(current.data)
                if current.left != None:
                    queue.append(current.left)
                if current.right != None:
                    queue.append(current.right)
                queue.pop(0)
                            
            
    def inorder(self,root):
        if root:
            self.inorder(root.left)
            print(root.data)
            self.inorder(root.right)
            
            
    def isBST(self,root):
        return (self.isBSTUtil(root,INT_MIN,INT_MAX))
    
    
    def isBSTUtil(self,root,mini,maxi):
        if root == None:
            return True
        
        if root.data < mini or root.data > maxi:
            return False
        
        return (self.isBSTUtil(root.left,mini,root.data) and self.isBSTUtil(root.right,node.data,maxi))
        
                
            
            
tree = Tree()

ch=0

while(ch<10):
    print("\n 1) Insert Node")
    print("2) Search Node")
    print("3) Find Minimum Value")
    print("4) Find Maximum Value")
    print("5) Number of Nodes")
    print("6) Delete Node")
    print("7) Find height of the tree")
    print("8) BFS - Traversal")
    print("9) InOrder Traversal")
    
    
    ch = int(input("Enter your choice: "))
    if ch==1:
        ele = int(input("Enter the element to be inserted in tree: "))
        root = tree.getRoot()
        node = Node(ele)
        tree.insertNode(root,node)
    elif ch==2:
        ele = int(input("Enter the element to be searched: "))
        root = tree.getRoot()
        res = tree.search(root,ele)
        if res:
            print("Element present")
        else:
            print("Element not present")
    elif ch==3:
        root = tree.getRoot()
        tree.minimum(root)
    elif ch==4:
        root = tree.getRoot()
        tree.maximum(root)
    elif ch==5:
        root = tree.getRoot()
        res = tree.getCount(root)
        print("Number of nodes present in tree: ",res)
    elif ch==6:
        ele = int(input("Enter the element to be deleted: "))
        root = tree.getRoot()
        tree.deleteNode(root,ele)
    elif ch==7:
        root = tree.getRoot()
        res = tree.getHeight(root)
        print("The height of the tree is: ",res)
    elif ch==8:
        root = tree.getRoot()
        tree.breadthFirstSearch(root)
    elif ch==9:
        root = tree.getRoot()
        tree.inorder(root)


<file_sep>/DoublyLinkedList.py
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Apr  1 11:33:31 2019

@author: kartiktanksali
"""

class Node:
   def __init__(self,data):
        self.data = data
        self.next = None
        self.prev = None
        
        
class LinkedList:
   def __init__(self):
        self.head = None

   def push(self,data):
       new_node = Node(data)
       if self.head == None:
           self.head = new_node
           print("Element Pushed")
       else:
           new_node.next = self.head
           self.head.prev = new_node
           self.head = new_node
           print("Element Pushed")
           
   def append(self,data):
       new_node = Node(data)
       if self.head == None:
           self.head = new_node
           print("Element Appended")
       else:
           temp = self.head
           while(temp.next!=None):
               temp = temp.next
           temp.next = new_node
           new_node.prev = temp
           print("Element Appended")
               
   def deleteFront(self):
        if self.head == None:
            print("No element to delete")
        else:
            self.head = self.head.next
            print("Element Deleted")
        
   def deleteRear(self):
       if self.head==None:
           print("No element to delete")
       else:
           temp = self.head
           while(temp.next!=None):
               temp = temp.next
               
           if temp.prev == None:
               self.head = None
           else:
               temp.prev.next = None
               
        
           print("Element Deleted")
     
   def insertPos(self,pos,data):
       new_node = Node(data)
       if self.head == None:
           self.head = new_node
           print("Element Inserted")
       else:
           temp = self.head
           for i in range(1,pos):
               temp = temp.next
           if temp.next==None:
               temp.next = new_node
               new_node.prev = temp
           else:
               next_node = temp.next
               temp.next = new_node
               next_node.prev = new_node
               new_node.next = next_node
               new_node.prev = next_node
                
               print("Element inserted")
    
   def printList(self):
       temp = llist.head
       
       while(temp):
           print(temp.data)
           temp = temp.next
       


if __name__=="__main__":       
    llist = LinkedList()
    
    ch=0
    
    while(ch<7):
        print("1) Push an element")
        print("2) Append an element")
        print("3) Delete an element in the front")
        print("4) Delete an element from the rear")
        print("5) Insert at a position")
        print("6) Print list")
        
        ch = int(input("Enter your choice: "))
        print()
        
        if ch==1:
            ele = int(input("Enter the element you want to push: "))
            llist.push(ele)
        elif ch==2:
            ele = int(input("Enter the element you want to append: "))
            llist.append(ele)
        elif ch==3:
            llist.deleteFront()
        elif ch==4:
            llist.deleteRear()
        elif ch==5:
            ele = int(input("Enter the element to be inserted: "))
            pos = int(input("Enter the position: "))
            llist.insertPos(pos,ele)
        elif ch==6:
            llist.printList()
        