Data Structures
memory slot = 8bit
8 bit = 1byte
In 32 bits, we require 4 byte for each individual element;
in 64 bit, we require 8 bytes
logb(x) = y => bpower y = x
log (x) with base 2 is equals to 'y' and the condition is '2^y' is equal to 'x'.
for computer base is always 2
So what should be the value of log of 1?
To find the value of log (1), all you have to do is use this equation.
So we have '2^y' is equals to 1.
Since we already know the 'n' part, so this is equals to 1. Now we need to find the power of 2 and that should give us the value of 1.
So '2^0' is equals to 1, then here 'y' is equals to 0. That means the value of log (1) is equals to 0.
log(2) = 1
log(4) = 2
log(8) = 3
log(16) = 4
log(512) = 9
log(1024) = 10
log(1048576) 20
When we double the value of n, value of log increase by 1
So data structure are of two types, which is primitive data structure and non primitive.
Primitive, I think you already know, Integer, Float, Pointers, Char and lot more,
whereas non primitive can be divided into two parts, which is Linear data structure and Non Linear data structure.
These are sequential and these are random.
So linear data structure have Array, Stack, Queue, Link List, and there will be few other, non linear have Graph and Trees
Array
a variable as vooc = [ 1, 2 ,3]
as we are using 32 bit system, this will take 12 bytes of space, which is 12 memory slot; 4 slot per value
There are basically two types static and dynamic. If you are using C or C++, Java, then you might have noticed while initializing any type of array, you have to give its size. if you are talking about three elements, you have to specify their size while initializing, while declaring itself.
the second one is dynamic array. If you are using Python or JavaScript, then by default, you are using dynamic array, you don't have to provide any size, it is taken care by your system itself.
with static array, once we allocate memory slot, it will never change. Since we have already declared the size while initializing and they are fixed, we cannot just append them and add more elements, these are static, these are fixed in size and we cannot change them
Now, if I talk about dynamic while initializing, we don't have to specify any of their size, and we can append them and can add as many elements as we want. Since they are dynamic, there are several advantages that we are going to have with this array
static array - need continuous chunk of memory. for any new item added it shit to new address for continuous chunks
Dynamic array = allocate memory in logs value. so when we need 5 item with allocation 2^3 8 value store. for 9 value allocation 2^4=16
Linked list = 8 Bits (4 to store value , 4 to store next address) first is head and last is tail point to None
Double linked list = 12 bits (4 to store value, 4 to store last address, 4 to store next address)
STACK = LIFO last in first out. pop remove last item. peek/top give last item, push put new item on top (use array)
Queue = FIFO (deQueue - remove first, enqueue - pput new item in end, peek - first item view) (use linked List)
HEAP -
can be arranged in an Array
80
52 76
72 34 56 67
80 52 76 72 34 56 67
0 1 2 3 4 5 6 7 8
so child position left = 2i + 1 example 52 left child is 2* 1 + 1 = 3 (72)
right 2i + 2 2*1 +2 = 4 (34)
same way parent for new child will be 7/2 - 1 = 3 so 72 will be the parent for child on 7the position
all odd have position have left child and even have right child
Binary Search
def binarySearch(my_array, target):
left = 0
right = len(my_array) - 1
while left <= right:
middle = (left + right) // 2
middle_ele = my_array[middle]
if target == middle_ele:
return middle
elif target < middle_ele:
right = middle - 1
else:
left = middle + 1
return -1
print(binarySearch([1,5,10,12,25,30,32], 30))
Binary Search With Recurrsion
def binarySearchRecurrsion(my_array, target):
left = 0
right = len(my_array) - 1
result = helper(my_array, target, left, right)
return result
def helper(my_array, target, left, right):
if left <= right:
return -1
middle = (left + right) // 2
middle_ele = my_array[middle]
if target == middle_ele:
return middle
elif target < middle_ele:
right =
return helper(my_array, target, left, middle - 1)
else:
return helper(my_array, target, middle - 1, right)
return -1
print(binarySearchRecurrsion([1,5,10,12,25,30,32], 30))
def selectionSort(arr):
"""sort by looking for smallest item and put it in place
complexity is O(n^2)
"""
for i in range(len(arr)):
min_x = if
for item in range(i+1, len(arr)):
if arr[item] < arr[min_x]:
mn_x = item
arr[i], arr[min_x] = arr[min_x], arr[i]
arr = [20,12,10,15,2]
selectionSort(arr)
print(arr)
