Why DSA used in all Langues used to write efficent Program I By usinG Basix Data Stucture Algorithm Is an way to solve program and Get Get Desire Outcome from a prgram we write Optimized Program In Computer can write any Kinde of Progam
Data Structure is a Key Componenet Progarmming used to writte OS and Software
Most Of Them are Insipre from Real World we can Handell Multiple Data requestes and Data Handeleing In Optimixed Way
Two main Types PRIMATIVE NON PRIMITIVE types
PRIMATIVE
Can Hold single Value in the int cahr , bool,
NoN PRIMATIVE
are of Two types
LINEAR
NON LINEAR STRCUTURE
LINEAR DATA STRUCTURE
they include IN LInear way and One element is connect to another element in a way
ARRAY
SATCK
QUEUE
LINKED LIST
NON LINEAR DATA STRUCTURE
THey are connected with more than ONE elements are randomaly arrange
TREE
GRAPHS
STATIC
: AT compile time size ia allocated , Max size is fixed
DYNAMIC DATA STRUCTURE
: at run time sixe is allocated sixe is flexible
common opertions
SEARCHING
SORTING
INSERTION
UPDATION
DELETION
ALGORITHMS
STEPS TO GET REQUIRED OUTPUT
it should have wel defined outputs and Valued Output
should be terminated after completion
Must Have few steps and Directions
alogoritms sholud be writen in Human LANGUAGE AND cAAN bE CODEDE in desire Language to implete it we can use and Programming Language
C is mother of all Lamguages and OS compiler are written in It can understand How sysytems Arcitecture workes
Foundational for All Languages
Low level for writting Compillers and Engine writtng
Faster than all
best fro performance
CONCEPT OF TIME COMPLEXITY AND BIG O NOTATION tO CALCULATE HO EFFICENT A ALGORITHM IS
O(n) mean to measure complexity of a algorithm n : means how much operation an algorithm takes to complete the steps
O(n) means it depend upon the number n means if n increase the complexity also incease depend upon on the size
O(n2) it is worst case very slow mean if n=10 it will take 100 operation to calculate the Task
O(1) : is best case means constant time
supose we have an array each indivisual is the same size in array we take that sixe and Multiply with the index of the element ans we get the required data
One of good example of O(1) is a hash Table In whic we pass Data with key value and to get Data we pass Key to function and get Output They are very efficenty for inserting Data and reteriving Data It have fixed Time . Now we wil Take an example on an Array we have an array with integer have memeoru address and of 4 bytes if we want to get an element we will pass the memory sixe of Item and then mutiply with the Number of item in array and we get the address of item we wanted
O(log n) : it is also Good worst case O(n!) is the most worst case O(2) : it is also the worst case
LineAR algorithm it take entire list lenght : it is worst case seniro
Binaary search Algorithm : it will always starts from the middle . we have to make array in sorted array . we check out the Data if is less the the them more towared the Other side we cut down the Data and Hera come the concept of log(n) :
Worst alogorithm : Like a nested Loop, for every element we have to check all elemsnt in an array . where we have to place in array , It will have O(n2) .
O(n!) :
n is the Input size
we can say by increaseing of n by One Number add computation Grow Alots .
like 3!=6 and 4!=24.
we don,t have enought compution power to calculate .
BASIC OF OBJECT ORINTATION LANGUAGE
Classes and Objct : Data structure Store data. Class is a Blue Print that define Varibles and The Methods to all Common to that Object of a certin Kind class is a user defined descripltion what a certin Object will look Like we can define Varibles and function in It
we can also say it is lika container in whicj we have define Methods and Varibles
Methods : are functions do processing
Inheritence : core concept of Object orintation Programming . It is a mechanism wher we can to derive a class from another class for a hieraracy of classes that sgare a set of attributes of classes that share a set of attributes and methods
Inheritance is the procedure in which one class inherits the attributes and methods of another class
Polmorphism : Means have many forms . In simple world we can define it as a abaality of a message to be displayed in more than one form . Or we can also say that use of a single symbol to represent mutiple different types Describle something occure in several differnt forms
Encapsulation : it refer to the building that data with the methods that operates on that Data > It is used to hide the Value of a State of a Structred Data object inside a class , Prevent unathorized parties diret access to them The general idea of this mechanism is simple. For example, you have an attribute that is not visible from the outside of an object. You bundle it with methods that provide read or write access. Encapsulation allows you to hide specific information and control access to the internal state of the object.
Setting and Getting are the Important examples of it
ARRAY And LINK LIST :
to store large data and perform differn opertions on it
TWO MAIN TYPES OF ARRAY :
STATIC ARRAY :
Static arrays have their size or length determined when the array is created and/or allocated. For this reason, they may also be referred to as fixed-length arrays or fixed arrays.
in a computer Memeory all Data is store in sequentaly so
DYNAMIC ARRAY :
Dynamic arrays are those arrays which are allocated memory at the run time with the help of heap.Thus Dynamic array can change its size during run time.
LINK LIST : a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.
WE CAN ALSO SAY THAT it is series of data structure which are connected nodes .
each node store Data and address of next node .
It have head and Tail .
start and end at end we have Null .
there ane Differnt Types Single , Double , Circule ,
Two amin parts Data Item and Adddres of next node that can be any wher in memory
The power of a linked list comes from the ability to break the chain and rejoin i
creat a new structur and allocate memory to it
add dat value as 4
Point it next structe node contain 2 as the Data Value .
doin somthing Like this inan aray we have to shift tyhe Poisition of all element
explainHow Pointers Works .
explaun TRESS and GRAPHS
Time complexity :
SEARCH : O(n);
INSERT : O(1);
DELETION: O(1);
SPACE COMPLEXITY ;
O(n);
Featurs :
Dunamic Memory Allocation,
implementing StacK and Queue,
Hash Table and Graphs ,
commmom exmaple od Link List is Our Browswer History that we go to New Link and Go baxck Is Saved