Skip to content

Latest commit

 

History

History
295 lines (248 loc) · 6.91 KB

README.md

File metadata and controls

295 lines (248 loc) · 6.91 KB
Raw

// DSA with python //

doing this course on dsa with python, so thought of making notes and posting them basically so i dont forget :P

Lists []

  • mutable
  • indexing can be done
  • not homogenous[not same data structure possible]
  • allow duplicates
  • eg hello=[10,'string',0.3]
  • methods for insertion
    • hello.append([10,38]) //takes an object
    • hello.insert(index,value)
    • hello.extend(91,22) //takes an iterable
  • methods for removing
    • hello.pop() //pop the last element
    • hello.clear() //will clear up all elements
    • hello.remove('bye') //remove the element that given
  • other useful methods
    • hello.sort() //will sort the string
    • hello.count(10) //will return the no. of happenings of 10
    • hello.index(10) //find index of 10

Tuple ()

  • immutabe(means cannot just change the data but can add more if wanted)
  • can indexing
  • allow duplicates
  • collection of python objects
  • eg tup=(1,2,3,'string')
  • methods for appending
    • use + operator tup=(10,20,30) tup=tup+(40,50,60)
  • methods for slicing
    • use colon : for slice tup[1:3]
    • the first index in [first:second] will come but second index will not
  • methods for deletion
    • use del del tup
  • other methods
    • len(tup) for length
    • lst=tuple([11,22,33]) will convert it to a tuple
    • tup.count(22) will count the no. of instances of 22 in tuple

Sets {}

  • no duplicates allowed
  • no indexing
  • whole set is mutable
  • order of printing will be random
  • 2 ways of making sets
    • eg days={92,74,204,67}
    • eg times=set([12,34,56,77])
  • for accessing elements
    • for element in days:
    • print(element)
  • methods for adding
    • times.add(10) will add 10
  • methods for removing
    • times.discard(5) will remove 5
  • methods for union
    • pipe | will do the uniontimes | timer
  • method for intersection
    • ampersand & will do the intersection times & timer
  • method for comparing
    • times <= timer will return a boolean value

Dictionaries { A : 10,}

  • mutable
  • key-value pairs
  • 2 ways of making dictionary
    • eg book={1:'intro',2:'blogs',3:'content',4:'end'}
    • eg okay=dict([(0,2),(1,4)]) here output would be {0:2,1:4}
  • accessing book[2] here 2 is the key not the index
  • methods for changing and adding key-value pairs
    • book[1]='titles'
    • book[5]='sign'
  • methods for deleting
    • book.pop(2) will pop element at 2 key
    • book.clear() will remove all elements of the dictionary
  • other methods
    • book.keys() will give out all the keys
    • book.values() will give out all the values
    • book.items() will give the items like [(1,'intro'),(2,'blogs')]

2-d arrays [[2,4],[5,6]]

  • stores in 2 dimensions
  • uses a list basically
  • eg array=[[1,3,5],[6,7,9],[8,4,7]]
  • eg of inputing can be: 
    size=int(input())
arr=[]

for x in range(size):
  arr.append([
    int(y) for y in input().split()
  ])

print(arr)
  • eg for traversing the 2-d array
arr = [[1,3,5],[6,9,2],[6,8,3]]
for i in arr:
  for j in i:
    print(j,end=" ")
  print()
  • eg deletion can be done by del(arr[i][j])
  • array slicing eg arr[1:3] #index 1 to 2
  • array length eg len(arr) #no. of rows

// OOPS in python

  • Object oriented programming
  • because somehow procedural way isn't cool
  • uses classes which have functions
  • class has init method
  • eg of class made
class Employee:
  def __init__(self,name='harry'):
    self.name = name
  def display(self):
    print("name of employee is", self.name)

first = Employee()
first.display()

// Time Complexity

  • describes the amount of computer time to take to run an algorithm
  • uses Big O notation basically
  • O(1) means for any input time taken is same fastest
  • O(log n) means for n input then time is log n faster
  • O(n) time increasing steadily as input size increasing normal
  • O(n^2) time increasing very rapidly for input slow

Stacks

  • uses lifo [ Last in, first out ]
  • push for adding data
  • pop for removing the top element
  • peek for getting value of top element
  • for array implimentation time complexity is O(1)
  • eg
# stack nowww

def create_stack():
  stack=[]
  return stack

def push(stack,item):
  stack.append(item)
  print("pushed "+item)

def check_empty():
  return len(stack)==0

def pop(stack):
  if(check_empty(stack)):
    return "Stack is empty"
  else:
    return stack.pop()

stack=create_stack()
push(stack,str(6))
push(stack,str(5))
pop(stack)
print(stack)

Queue

  • based on fifo [ first in, first out ]
  • enqueue for entering elements
  • dqueue for deletion of elements
  • time complexity is O(1)
  • eg
class Queue:
  def __init__(self):
    self.queue=[]
    print("Queue is created 🎉")
    
  def enqueue(self,item):
    self.queue.append(item)

  def dqueue(self):
    if(len(self.queue)<1):
      return None
    return self.queue.pop(0)
    
  def display(self):
    print(self.queue)

tom = Queue()
tom.enqueue(5)
tom.enqueue(6)
tom.enqueue(8)
tom.enqueue(9)
tom.display()
tom.dqueue()
tom.display()

linked list

  • includes a series of connected nodes
  • each node stores data and address of other node
  • address of first node is HEAD
  • next address of last node is NULL
  • most efficient data structure
  • search for searching
  • insert for insertion
  • deletion for deletion
  • time complexity
    • searching O(n)
    • insertion O(1)
    • deletion O(1)
  • eg
class Node:
  def __init__(self,data=None,next=None):
    self.data=data
    self.next=next

class LL():
  def __init__(self):
    self.head=None
    print("linked list created, lol")

  def printlist(self):
    temp=self.head
    while(temp):
      print(temp.data)
      temp=temp.next

  def push(self, new_data):
    new_node = Node(new_data)
    new_node.next=self.head
    self.head=new_node
  
  def insertAfter(self,prev_node, new_data):
    if prev_node is None:
      print "The given previous node must be in linked list"
      return
    new_node = Node(new_data)

    new_node.next = prev_node.next
    prev_node.next = new_node


  def append(self,new_data):
    last=self.head
    if self.head is None:
      self.head=new_node
      return
      
    while(last):
      last=last.next
    last
    new_node=Node(new_data)
    last.next=new_node
  
  def delNode(self, pos):
    cur_node= self.head
    prev=None
    count=0
    while cur_node and count != pos:
      prev=cur_node
      cur_node=cur_node.next
      count += 1

    if cur_node is None:
      return
    prev.next = cur_node.next
    cur_node = None
    

cat = LL()
cat.push(4)
cat.push(5)
cat.push(6)
cat.printlist()