Data Structures and Algorithms using Java

what are data structures the reason we are talking about this is because if you look at the internet everyone says if you want to get into this company or that company they will ask you a question Based on data structures and algorithms so first of all why such a hype and what exactly data structures are so before we get into data structures let's talk about data see the entire software industry is based on data when you do a course on it which we call Information Technology it's not about technology it's about information because we work with information so data is everything so it doesn't matter what technology you learn you basically learn or you work on it so that you can work with data example think about programming languages why do we use programming languages to process the data why do we use database to store the data why do we use AI to generate data or to understand data right I mean just to bring it down everything is data now then question arise what is data structures now if you talk about any programming language we have something called primitive data types if you want to store a number we store that in integer if you want to store a a text you store that in a string if you want to store a character you store that in a character of course depending upon different languages the term or the way you store it changes but ultimately you have some types to it where you store the data but what if you have bunch of data and if you want to store them it's not just about storing data anyone can do that it's about how do you store data efficiently and you can also save some memory the thing is if you simply Dum the data you are expanding the memory and if you want to search something from the data will be difficult and that's why storing that data efficiently is very important and that's where data structures comes into picture so data structure is a way to organize and store data efficiently okay so when you say efficiently it means two things first in terms of performance and also in terms of the memory now what about performance now think about this if you if you talk about any software application which we use it can be a normal calculator or it can be an application like Amazon website or any application which we use a banking application as well now what we do in that application is we use some features using which you can compute something you can process something example on calculator you calculate on the banking website you transfer money so what you're doing is you are basically building an application which will do some processing and the way you build an application is through algorithms now what are algorithms set of instructions let's say if I want to uh add two numbers it's very simple you what you do is you say take two values from the user then perform the operation and give the value back to the user now those are the steps right those are instructions now what I have mentioned the instructions those are called pseudo code because we're not actually typing a code here we're not being specific to a language let's say C C++ Java python jav JavaScript what we are simply saying is these are the steps you have to follow and that's your algorithm right but yes when you want to make it work you have to convert that into a code which will run on the computer right that's your actual software code and you can use any language doesn't matter right but the pseudo code will remain same now when it comes to processing of data for any task it's important for us to make it fast and also save memory now most of the companies are focusing on this concept of data data structures is because they want to give a good experience to the user of course right if I'm using some application I want it to be fast now you will say okay to to make the system faster you can increase the CPU speed you can increase the amount of ram you can do that but what if with the same amount of memory same amount of CPU power you can still make it more faster right and that can be done with the help of data structures now if you know how do you store that data efficient ently l in a proper structure and by doing that you can make your application faster because in data structures we have different type of data structures example let's say if you have bunch of data you can store that in an array but apart from array we have other types as well we have Set uh we have link list so when to use what it's not that this is best or that is best it's it's all about when to use what and to understand when to use what you have to first understand what those things are right how do you decide that this time you have to use at this time you have to use set and that's where understanding these concepts are very important now these are not the only options we have we have tree we have graph when to use them so when you understand those Concepts then we can think about okay for this situation we will use this and this is why companies are preferring candidates who knows DSA it will help them in multiple ways first it helps them to reduce the cost is because every computation see U I know you you might be thinking uh most of the application which we use are free right think about in Instagram now when we use Instagram of course we are not paying for it but then companies are paying for it right so the meta is paying for for you to use Instagram so because those computations will be happening somewhere maybe meta is using some cloud service let's say Amazon in this case So Meta is basically paying to Amazon for every computation which you do okay of course they earn from ads but then they are paying for it so what they will do is they will try to optimize it they will say okay if one query takes let's say $1 or maybe half a dollar can we just reduce it more can we just make it 10 cents so that's the thing they are trying to do and the way you can do that is by making sure you use a proper algorithm with a proper data structure so why companies are doing it to reduce reduce the cost second to give a better customer experience so that it will run faster and if I search something it should be faster for me as well so as a customer next when companies want to hire people they have so many candidates right how will they filter those candidates now data structures algorithm becomes one of the way to filter the candidates because if you know data structures that means you have worked a lot on that particular language and you understand how how a particular system works on the other hand data structures are not the only thing you need to know if you want to be a good developer if you want to get hired there are multiple things needed example you need to have a good hold on a particular language a particular technology you should have worked on few projects understanding the entire ecosystem not just one language working with databases working with networking but then DSA becomes one of the important thing there so just to summarize what are data structures so data structures is basically a way to organize and store your data in the efficient way and there are multiple data structures option available there and you will understand that in the upcoming sessions we're going to talk about in the upcoming videos you will we will talk about what are the types of data structures we have how to use them when to use what and what are the algorithms available there so I hope you got some idea getting data structures so of course entire series is important to understand that properly welcome back aliens my name is ready and in this video we'll talk about a DT which is abstract data type now before we move towards ADT let's talk about data here of course in the previous video when we talked about what are data structures we have talked about data and we also mentioned that in the software industry everything is about data so whatever you do you doing it for data right now with this data basically you get data from the user you process data you also give the output to the user or maybe you want to store this data in the database for the permanent storage but the thing is it's all about data and whenever we use any language doesn't matter which language you use what you do is you store that data in your code somewhere and to store that data we use something called a variable now imagine variable as a box and you are keeping your data inside that box the problem is every box need to have a type of course there are languages which are dynamically typed language where you don't actually mention the type of the variable but in general this box will have a type so that means if you want to store the data you need a box which is your variable and this variable also needs a type to it or this box needs a type to it now example let's say if you want to store a number so we can use something called an integer or if you have any other point values you can also use float or double now it depends on the languages how they work but in most of the languages we have something in common we have integer for the normal numbers we have a float for the point values and what if you want to store a text that's why we have string and in few languages we don't have all these types we have limited types and in other languages we have many but that doesn't matter right in general we'll be having a variable and a type to it now all these type are called data types and they are system defined data types or you can also call them as primitive types is because it's there in the language itself you can directly use them but sometime you want to use some complex data type and we can create that with the help of some other Concepts example let's say if you want to represent a human or if you want to represent a phone now I love phone so I'll be using that example so if we talk about this phone here now this phone will have a name to it right so it will have a name it will have a brand of course name is model number then brand then the configuration the amount of CPU Ram all this are your data right so if you want to represent any physical thing in the virtual world we use objects there right now in some languages which are objected programming we do that with the help of objects example in C we use something called structures so we can define a structure name let's say phone and inside that you can specify what are the properties there in the same way in the object uned languages we use something called class in this class you create different variables with primitive type and then the block box itself or the class itself is your complex data type or you can say user defined data type user defined because system is not giving you we are defining our own type right so that's about data and data types but let's say if you want to store a bunch of data how will you work with that and when it comes to data structure how will you store this data in a proper way see what happens is when you talk about primitive types as well every type will have a way to store data of course that's why creating them right so example if you are creating a variable called num now let's say this num is of type integer and then you are storing a value to it now with this variable numb you can perform operations as well now what are the operations you can do with integer you can add two values you can subtract two values you can divide multiply so you can perform those operations on the number but let's say you have a string there now with string of course you will not be adding to string that doesn't make sense right why you will add two names let's say nav and K you will get a new name okay a lot of parents are doing that for for their kids but that's not the idea here right we can't add string we cannot subtract strings but yes with string you can do something else maybe you want to see the size of a string maybe you want to concatenate two strings maybe you want to cut two strings so string are different operations in the same way if you are creating your own type this will have data of course but also you have to you have to mention the operations which you're going to perform so we have two things right we have data and we have operations now let's say in data structures you want to store of data as we mentioned and you want to store so there's a concept of array so if you have multiple data instead of showing them in multiple variables let's say you have five numbers uh 2 6 12 21 and so on now if you have all these values you basically store that in five different variables or you can create a single array and you can store all the values there the advantage would be you have just have to use one variable name there so instead of saying a b c d e you can simply say nums you can use any any variable doesn't matter so what's important is you can use array here now when we use array we are not basically using a primitive type here we are creating our own type here own data type which is an array now in this array basically you should be also able to perform some operation example let's say what if you want to read some value you want to uh fetch a particular element you want to search the array maybe you want to add a element maybe you want to delete a element so this operation should be possible on thatp so in the concept way when you have a type where you can perform some operation we call them as abstract is because the implementation for array changes from language to language and we don't just have array right so let's say if you want to store a bunch of values we can use list we can use set Q now when you talk about a q here let's say now inside Q we have I mean we have one more option for that which is tack they follow different concepts so let's say if you want to add element in the queue which follows last in first out which means you have to insert from the end and you will get it from the first of course you can reverse it you can insert from the start and you can take it from the end the thing is you have you will insert from one end and you will remove from the other end so that is first in first out in stack it is reverse you do last in first out example let's say U to an example let's say for queue we can say a queue which you follow right example if you want to buy a coffee from a cafe shop of course there's a queue there you have to stand in a queue and then when your number comes you will get the uh coffee so basically the first person who went first we'll be getting the coffee first right in terms of Stack it is different so when you keep multiple books the first book which you can take out is a last book which you have kept there right is the last in first out that is your stack now we have different way of implementing in different languages the concept remains same right so when you have a concept and the associated operations to it and of course with data which we call them as abstract data type we also have map but we'll talk about those things later at this point point to remember is we can create our own types and which is a concept and if you want to have data inside that and also you want to specify what operations you can perform that is your abstract data type of course in the subscri videosos we'll talk about how do you create them how do you work with them and it will be fun in this video let's talk about arrays so let's say you have bunch of values let's say five values now instead of storing them in five different variables we can store that in in one particular sequence right or one variable you can say now in this array you can store fire value so let's say we have this array here and then this will have a name to it now of course this data will be stored in a memory right and every memory will have something called a memory location so let's say we are storing this data in at a location 101 now what happens is every time you store a normal variable let's say A Primitive type let's say int and depend upon how much sizes Tak so every type will have have a different size to it depending upon a language but let's say we have two bytes now inside your memory let's say if you create a normal variable which is int a equal to 5 now this particular a variable will take some space in the memory of course let's say two bytes and it will also have an address to it right so every time you in your programming language you say hey I want a value for a the program will jump to the m location by searching for the address and it will get the value but the problem is when it comes to array we have multiple values right right and we only have one address now that's tricky of course each element here will take the same size if you say int take two bytes the complete array will take 10 bytes is because every element will take two bytes how will you allocate memory now that's an issue so what you do is the array will have a memory but that will that is only pointing to the first location right so if you say the the memory for this is one1 the first element is 101 what about the second element now that's where we have to use something called a index value values so let's say the first element is look is at one1 so it will have a index value which is zero the second element is one then two then three then four right now for five values the index value starts from zero and ends at four now why zero is because we start we have a memory allocated right one Z1 which represent to the first element so we don't have to give one to it so what you do is the next element is + one that's why 1 2 3 and then you can just get it right so one 1 let's say if you want to get the third element you have to say plus two that's how you do it so you got the values you got the index and you also got a memory address to it now with this array as we already talked about ad which is abstract data type we should be able to perform some operations now what operation you can perform on this array now we can perform something called a read operation so what is read so let's say you want to get the value of a index number three now what what you do in this case is you say okay my array name is nums and then for this nums I want the value at index index three so in different languages we have different representation for this but let's say this is common one so nums bracket of three now what your computer will do is it will directly jump to the memory address it's very simple for for that right so you will say one 1 plus 3 you will get the value so that's how you do it now reading is very easy and computer takes way less time to jump to that particular area is because the computer knows the memory right because you you are mentioning the index value reading is good it's fast also what about searching now this is tricky because when you're searching you're not searching for an index you are basically searching for a value now so let's say from this are I want to search what is 17 now in this case your computer has no idea where 17 is because computer only knows about the memory address of course the values are there but computer has no idea in which location we have that value and do we even have that value so what a computer will do is it will start from the first location so basically you have to write a code to search from the first location you have to check is the first one 17 if yes yes good we can exit no then have to jump to the next location is it matching if yes good if not next matching yes no next so basically you have to search each element right and let's say the element is at the end you are searching you are basically tracking to all the different locations so this is time consuming right what if you have a array of let's say, values to to move between this values it will take some time what about inserting now this will beit tricky is because see if you want to insert a element what do you think will it will it take a lot of time see if you want to insert the element at the end that's very simple you can get the size of the array because we also have to have that option of getting a size of the array right so let's say you have five values you you will simply jump to the sixth location which is index five and then you will say Okay I want to add a value here let's say the value value is 21 and you can add the value it's it's very fast but what if you want to add a value in between so let's say you want want to add that value at the second location so after the first you want to add the new value now what you will do is you don't have a space there right you can't simply create a new space you can create space at the end so what you do is you basically have to move all the elements and you it's not like you can simply move the elements what you do is create a new block so move the second last element now to the last block then again you have to move every element one by one then you can add your value to the second location so if you are inserting at the end that's fine but if you're inserting in between that will take a lot of time and that depends upon the number of elements after the position which which you're adding what about deleting see deleting from the from the end is always welcome is because you're not affecting your array in total but what if you want to delete a particular element from between now you can't simply delete from the between right you have delete the end block but how will you move so again when you to when you want to delete this just replace all the values right so that's that's true tricky so it will take a lot of time depend upon how many elements you have after that index value now while we are talking about all this thing array was simple right we can perform the operations the important thing here is time taken for each operation and it's not about CPU time if you're thinking uh my computer is super fast it will be happening very fast there see in the world we have different computers and different computer have different CPU power different Ram Power different configuration and that's why let's not calculate a speed of speed of a code or the algorithm by the actual runtime important is the number of steps it takes example let's say if you want to insert the element at the end that's good if you want to insert the element in between that will take a lot of steps is because you want to move the elements right now in the upcoming videos we we going to also talk about time complexity which is a very important concept something called Big Big O notation but yeah we'll talk about that in detail later I know you're excited to hear that but important thing is when you write a code think about the number of steps your code takes because that defines your time complexity and if you say my algorithm is good it should be time efficient okay so for the same particular operation you can write two different codes example on the screen if you want to print let's say 10 numbers from 1 to 10 and maybe you just want to print the even numbers we have two options there which one is good of course you'll let me know in the comment sections but the code which is notating between all the values is good right so that's how you define how your algorithm is good now we can also expand the ARR example let's say if you have a sorted array so let's say you have an array and this is sorted by default so every time you insert the element it gets sorted by by default you don't have to mention where you want to insert this example let's say you have bunch of values here all are sorted and now you want to insert element which is 11 now if you want to insert 11 there where it will get inserted of course it will search for the location let's say we have a number nine it will get inserted after 9 now the question is how do your code knows where is n so you have to basically search you have to match is it greater than is it greater than is it greater than and then you have to insert so that will take a lot of time but what if you're inserting in between you have to shift all the elements so that's about the array and a basic introduction of time complexity we'll discuss that in detail later in this video we'll talk about time complexity see a thing is in the previous video we have talked about algorithms right now the thing is if you want to build an application basically we are trying to solve a problem right and every problem will have multiple Solutions so the steps which we write to solve that problem that's what we call algorithm example let's say if you want to cook something you follow some steps right now those steps are your algorithm example if I want to record a video we do multiple things we prepare the content we set up this camera mic and then we start recording then we edit the video so there are multiple things involved in the same way if you want to solve any problem we have to follow some steps which we call algorithms and the thing is for one particular problem we don't have one solution we have multiple Solutions and we have to pick the best one now question arise how will you choose the best one so when you say best one what exactly it means so let's say when I run this application I want my application to use less memory or maybe I want when I run this application I want it should take less time or maybe both and that's why we have this term called algorithm analysis so basically you have to analyze your algorithm so that you can make it more efficient right of course as a developer first focus is first the product should work and then you think about optimizing it but when you say optimizing you have to you can optimize in two ways one think about the space complexity and second is the time complexity space complexity simply means can we use an algorithm which will take less memory and time complexity means it will it should take less time but there's one more problem here and the problem is how will you calculate the time or how do you specify the exact time because every machine will have a different output right so if you are testing the algorithm in your machine it might might give you different time and then the moment you test this in your office machine it will give you a different time so that's not the best thing to calculate the number of seconds it takes but what you can do is there's a way you can calculate with the help of steps but before we go there let's focus on two algorithms here and then this will make much more sense so the algorithm which we're talking about now is the searching an element in a sorted array so in the previous video we have talked about array and then we have also talked about the sorted array so in sorted array by by default all the elements will be sorted right now what I want to do is I want to search a particular element from this array now there are multiple ways of doing it let's talk about the two so basically we have an option of linear search binary search or many more but let's focus on this two so what exactly linear search and Bunny search is let's talk about that so what is linear search so let's say you have an array with you okay so this is your array and in this you have multiple values so let's say I'm going with few values here let's say five values and then I'm going to write let's say 5 7 9 12 17 so we got this five values here right and then I want to search a particular element now this is sorted AR because you can see all the elements are sorted we got 5 7 9 12 17 and I want to search a particular element let's say I want to search 12 okay I want to search this element so maybe there is a target value which I want to search in this case the target value is 12 so I want to search 12 right and then this is an array so what we do in thead search is you go one by one so what you do is in fact we have talked about this in the previous video as well so we'll make it bit faster so what you do is whatever your target value is you will compare that with the first element if it is matching grade otherwise you will move to the next element otherwise you will move to the next element otherwise you will move to the next element and I mean of course at this point we don't have to go to the next element so here we basically got the value and once you got the value you can return the value right now there's a problem here the problem is what if the element is not there in the array so of course you have have to reach till the end okay what could be the best way scenario here so let's say you are searching for element let's say element is five and now we know element five at the start itself so when you have the element at the start it will take only one step but what if you have element at the end so it will take the steps depend upon the length of the array so let's say if you have five values it will take five steps when you have 10 values it will take 10 steps when you have 1 million values okay that's huge let's talk about thousand so let's say when you have have 1,000 values it will take 1,000 steps that's tricky right now the problem is not it is taking 1,000 step the problem is as your size increases it is also increasing the number of steps to search okay that's one parameter you have to remember so that's a theory right now let's understand that with the help of a pseudo code here so you can see I'm writing a pseudo code why pseudo code why not some programming language uh syntax here is because we wanted to make it generic so that you can doesn't matter in which language you work work maybe C C++ Java JavaScript python maybe cobal your choice this could Iman right now this can be function procedure doesn't matter so what I'm doing is doing here is we have a procedure right it can be a function and the name of the function here is the linear search okay now we are accepting a list of items now this is your array the name of the array is a okay and then you are also passing a Target what you're searching so in this case we were searching for 12 but doesn't matter so you have an array with multiple values it can be one value 10 values thousand values doesn't matter and then you're also passing a Target what you want to search now you will go inside this and then for the first thing you will do is you will want to find the length of the array because of course you should know right till when you have to search so you got a length which is stored in the n and then we are going to basically going from zero to n minus one because we when you start with zero you have to end with one less right so if you have 10 values you you will go till 0 to 9 so you will go from the first value to the last value and then you will search if the target which you are searching is equal to the current element where you searching so when you're searching for the first element that's the first element here Target is matching if yes you're good you can simply return the value but what if you're not match it's not matching it will go for the next situation next value is it matching yes good return what if it's not matching next value so BAS basically you have to search each value till you're not finding it so that's basically a pseudo code here and what if there's no element example you have an you have five values and you're searching for a value which is not there you can return minus one by specifying hey the value is not there this is simple linear search the code is small but then the time complexity which is the amount of time it takes is huge okay now let's go for the second approach which is your binary search now what happens in binary search sees it's very simple basically it's not that simple but let's say so what you do is you have a array again a sorted array and let's say we have multiple values here I'm not sure how many lines I'm going to draw so let's count it later so let's say we got five here again 6 8 9 11 13 17 okay so I maybe I love odd numbers so doesn't matter what values you have there uh so we got uh 1 2 3 4 5 6 7 so we got seven values right now what you do is in ban search now since this is sorted if you're searching for a particular element let's say I'm searching for eight here okay and we know eight is here we know it but computer has no idea where it is so how how it is going to search now in linear search what we were doing is we were jumping basically from value to Value searching checking this checking this and then goes on so now why why this call this binary is because you divide your array into two parts that's the binary is now how you do it so basically what you do is you give a starting point and then you give a ending point and of course every element here will have a index value so in total here we got uh seven values right which goes from 0 to six now what you do is you first divide your array into two parts and to do that we have to find a mid value okay so even before you divide you find a mid value so how do you find a mid value so mid value is equal to the starting position plus ending position divide by two okay now this is 6 / 2 which is three okay so your your mid now is three and this is your mid okay now basically you check with the mid okay so you always check with the mid is the value which you searching for which is here is it matching with the mid value which is nine no it's not matching but is it less than or greater than if the value which are searching for is less than the value which you got as a mid value then the values after the M mid value is of no importance right so this values here has no importance you can directly skip them so you you can divide your are into two parts so you got the first section here which is 5 6 8 9 and then you got the second section here which is 11 13 17 so what you can do is you can basically skip this part or maybe I will just do that with a color now we can skip this part we don't need this value the value which you want to focus on is 5 6 8 9 so what you do now is you make your mid as the end okay because we have shifted to the left part of the array now when of of course when you shift to the right part of part part of the array in case then you shift your starting value now here you got S and E again and then what you do is you again check your ending you you will find your new new MID value so again s + e / 2 now s is 0 0 + 3 is 3 by 2 which is 1 uh of course you can say 1.5 but let's say this is 1 equal to 1 we can apply a float function to get the nearest integer okay so we got one here right so what you do is you check so this is your made again you check is it matching with the value no it's not matching so 8 is not matching with six then what you do then you again divide your array into two parts but then which which one you have to skip now now now we know that the mid is six so we have to jump to the next value I mean we have to look at the right side value so six is less than eight right so I have to look at the right side so now what we're going to do is let's we have divided into two parts right so now we can skip this part and focus on the right side now so your starting position has been moved here now now this is your s and you got e so again you will find a new MID which is s + e / 2 which is 1 + 3 is 4 4 / 2 is equal to two so your mid now is 8 now is it matching yes okay and that's how you got the value now if you might be thinking we have done so many steps right not exactly basically at the start itself we have removed half of the and which is very important right so let's say if you have at size of 1,000 at the start of the first operation you have removed 500 values for the next operation when you do it you remove 250 values so the number of operation which are doing with B search is less right and that's how you know that this is better than the linear search of course in linear search if the value which you're searching for is the first value it's very fast right it will take a lot of time for binary search but in general binary search works faster but how do you do that so with this Theory let's talk about the Practical implementation here so let's look at the uh code here very fast because we have already done the theory here so what you do is you basically write a function let's say binary search and then you passed a list of values right and then you also pass a Target same thing we have done in the linear search and here then you go with the left and right so basically we have mentioned the start and the end here in this we are taking left and right left starts with zero as we mentioned the starting start start with zero ending ends at the last value okay we have done that and then you run a loop till you find the value of course then what you do is you check the mid value so this is a mid value we have done that mid is the the starting point ending point divid by two and then you check is the miror matching with the target if yes you're done you can simply return the value otherwise we have to do something more then you check if the value which you got which is mid value and the target if the mid value is less than the Target in this case you will focus on the right hand side okay so basically you have to shift to right hand side so your left your starting point will shift and we have discussed that here right your starting point will shift and then what if the mid value is greater than the target value in that case you will shift to the right the left position okay so that's what we have doing here and then every time you do that you run the loop again you find a new MID value and that's what we have done multiple times right we found the mid value three times in the same way you're you're doing you're going to do here and then at the end you will get a value if it is not get if if this not there you will simply return minus one as we have done before so basically by doing this what we doing is we we have seen two algorithms right now we have to find the time complexity now what exactly time complexity is it's not about number of seconds it takes to run your code it's all about this so time complicity simply means the measure of how the running time of an algorithm increases with the size of input data so basically let's say when you are testing a particular algorithm you're testing for let's say 10 values or 20 values but what if the values goes up what if you have thousand values how will it will affect your time will it increase the time in linear section let's say if it takes 5 seconds for 10 values will it take 10 seconds for 20 values or will it take more or will it take less okay or let's say you have 1 million records will it take 1 million seconds that's the question we have to answer okay now how will you do that and that's where we have something called Big O notation now what happens in Big O notation is we use this particular concept to understand your time complexity of your algorithm if someone says hey your algorithm is not fast enough you have to first find the Big O notation of it uh so why Big O is because it is represented with the help of O the big o in bracket you mention the order of n or something so basically it is also called order of or Big O notation and anything will do so how do you represent that you represent that with something like this so we have o off and then the value which is one will keep changing so there are multiple things here you can say we have O big O of log n we got Big O of n we got Big O of n log n we say Big O of n² which is quadratic time we got 2 to n and we got n factorial okay so we got all this notation but how do you find this okay now this is tricky so of course in this particular video is not you will not understand everything but let's start with the basic now let's talk about the linear search now if you go back to linear search what we were doing there now in linear search when you have five values you take five steps when you have 10 values you take 10 steps you when you have H 100 values you take 100 steps right but let's say that is for searching right what about read if you want to read a particular element from the linear search or from the array it's very easy right you specify the index value let's say the index value is 0 1 2 3 4 and then you specify hey I want the value at index two so let's say you say nums which is the name of the array and when you say two basically what you get is nine it's very fast so it doesn't matter what is a size of your array it can be 1 million records the time taken to get a particular particular element with the help of index value is constant right because computer knows where that memory is so in that case I can say the Big O the time complexity for this is one because it is constant okay now see it's not about one step if you're thinking just because Ive mentioned that it is only one step it can be three steps as well so let's say if you are reading a particular element and maybe behind the scene it takes three steps doesn't matter it's constant right it can be one one step three step 10 steps it should be constant if it is constant you can say o of one but what if you are searching element so if you have an array size of let's say 10 it takes 10 steps now you'll be saying hey you know what if your element is at the start itself of course it will take one step but we have to go for the worst case scenario here the worst case is what if the element is at the end what if the element is not even there it will take 10 steps and that's why we can say the order the Big O notation here will be n what is n here the number of elements in the array as it increases the time also increases the time complexity I'm not talking about the actual seconds okay so that's your linear search now coming back to the ban search what could be the Big O notation for ban search see the thing is as the number increases it will not directly increase the number of steps reason for that is let's say we have we have seven values how many T steps it takes let's say three steps because we have to find the mid value three times right what if the size increases to double so let's say from Seven we got 14 so what do you think how many steps will increase what if I say only one reason being even if you have let's say 14 values here let's say we have so many values at the start itself it will be half right you will get seven values after one step and then you basically incre increased one more step to find the meter so that means when your value increases it will also Al increase the number of steps taken but not exactly n because in the linear search if your number of values increases by 10 it will increase 10 steps here as the number of value increases it will not increase the steps in the same sequence so what we can say is we can say it is something between constant it's not exactly constant but it is between the O of one and O of n so it is between this two and what comes between this two is O of log n now what is log n basically so log n basically means we have a base two here by default okay so number of steps it takes so what exactly this n here so let's say we have eight values here so when you say log two of 8 it will give the value which is three okay now why it is three is because uh log of 8 is simply means it will take two multiply itself three times to get eight okay so as the number increases let's say now instead of eight values we got 16 values it will give you four because it will take two to multiply itself four times to get 16 right uh so it will give you four that means as your number of value increases from 8 to 16 it will only increase one step right and that's why the binary search is log n so your linear search is O of N and your binary search is O of log n so which will take less time the log of n okay and you can see the graph here as well so this is elements the number of number of elements you have in the array and this is the number of operation it takes okay so number of steps so if your algorithm is following the constant time it means it's here it doesn't matter how many values you increase it will be constant time log n is similar to it's almost same as constant not exactly same as constant but it will take less time so you can see log n is mentioned here it's there the the wave is there you can't see it it's there uh so what if you go with Big O of n so as your value increases your time also increases right but there can be some worse scenarios as well there can be some other algorithms which you implement which might take n log of n which is worse than o of n there might be some algorithm which will take o of n² which is worse than the o n log n so basically if you want to build an algorithm try to make sure that you are here if you are here you're good okay if you are here it's okay if you are here try to make it better if you are here that's the worst scenario that means you're building an application which is not scalable the moment you have five users on your server your server says I'm good the moment you have 1,000 users it will struggle okay so make sure that you when you whichever algorithm you write you follow this of course in the upcoming videos we'll work on some more algorithms we will see which one matches there but you got the idea right so the time complexity simply means this definition the measure of how the runtime of the algorithm increases with the size of the input data and to represent that we use Big O notation in this video we'll talk about the Practical implementation of linear search and binary search to understand the time complexity which we can represent with the help of Big O notation now basically we'll write two examples here in fact we will also do binary search in two ways just to understand how thing works and then how will you find the amount of time it takes not in seconds of course but the number of steps right so we have discussed about Big O notation which is the Big O of one big O of n Big O of log n right but we also have multiple options but then at this point let's focus only on two with the help of two algorithms linear search which is Big O of N and B search which is Big O of log n okay so what I will do is I will write this code in Java and of course we'll not be doing very complex stuff in Java if you know any other language you can follow this so I'm using an IDE and again you can use any IDE I'm using intell idea so in this I have a project I will simply create a file here and we'll name this file as demo so we got a file called demo. Java and this is where basically we'll also have our main method so if you are coming from different languages you know we also have main there so we have a main now let's start with the actual work imagine this as just a template for to run the code we'll write our code here now what we want to achieve now basically we will be having a list of elements and we want to search a element out of it okay now the size can be anything it can be five it can be 10 it can be 20 100 doesn't matter initially we'll go for less number of values and then we'll also see how do you work with thousands of values and how do you find element and then how much steps it takes to search a particular element there so what are we do is first of all I will create a simple array here and we'll say this array name as nums so let's say we got an array and then I will also specify the initial values to it and since we are going for a sorted array of course when you talk about the lineal search we don't have to specify a sorted array it can be applicable on any kind of array but when it comes to the B search you need to pass a sorted element array or the list you can say so here I will simply ass some values let's say we got five values here and then I'm I just want to keep it simple with those values of course you can have any value doesn't matter I'm just trying to keep it simple or maybe if you want I can say 7 9 11 13 that's my love for odd numbers okay and I want to search a value so whatever value I want to search we can also specify here now we can use any variable name but we have already used Target as a variable right when we were discussing the Theory so we'll say Target equal to and we'll mention the target let's say I want to search a element which is 11 okay so this is what I want to search from this particular list we can do this with multiple algorithms we can use linear search binary search or whatever you think about but let's go for linear search initially and then we'll look at the binary search now how do we do that so what we can do is we can say I want to get the result okay uh I want to find this 11 in this list and give me the index number I don't want anything else just the index number where it belongs to okay so who will give me that so what I can do is I can assign this St to someone else let's say linear search now this is another method which will give the value to us so I don't want to populate everything in this particular main main will simply say Hey you know I got this two things I got the list I got the target value you tell me which Index this value belongs to or if you don't have this value in the list also let me know so linear search will say Okay um accepted the challenge it will accept two things for first nums and Target why you have to pass nums of course linear search will say I will search but tell me where to search and Target will say this is a value you want to search now the thing is we don't have this method yet so what I will do is I will just use my IDE to generate okay so I will say more actions create this method and you can see we got this method I don't want this to be private I want this to be public and that's it what you're doing is you are calling Under the method at this point since we are returning a value what we can say we can say return minus one okay nothing fancy I just want this to work and that's why I'm rning minus one okay and what if you get the result of course uh if there's no if this value is not there in the list it will return minus one otherwise we can return the index value so whatever value you get you can simply print here and you can say element found at index and then you can specify the index value here so let me just give a space so I can specify the result here so whatever index is there there okay and let's run this code just to see I just want to make sure that everything is working let me just run this code and you can see we got the answer and also I want to move this to right hand side okay so it looks good so you can see the output says element found at index minus one that's weird it's just that we are ring minus one that's why it's printing minus one what we should be doing is we should be checking if the result is not equal to 1 or not equal to minus one so this statement it should print only when the result is not minus one in case it is minus one that means the element was not there so I can simply print element not found okay and now if on this code it will print element not found because we are not even searching right but we'll search now so how do you search it's very simple so what you can do is you can use a simple Loop here okay nothing fancy again simple Loop and and in this you're going to iterate so we have seen the linear search right so if remember the theory we have talked about this uh so basically we'll search from the first element right so we are going to start from five and then we'll look for is it matching is it matching is it matching of course the values are different but we'll basically search for each element in the same way in linear search if you want to move you have to use a loop so it will start from zero and will go till the nums of length so basically if you if the value number of values you have five you have to reach four okay so that's why we have saying less than and then i++ that's your for Loop right so in this for Loop you don't have to do much you simply have to check so whatever element you got the recent the current element which you're focusing on so in the list we have five values if you're focusing on five we'll check if five which is a first element is it matching with the target if it is matching with the target our job is done we can simply return the index the current index so let's say if you're searching for five and then you got five return zero your job is done that's what you're doing here okay and that's it okay it should work that's what we expecting linear search is so simple if you run this code it says the element found at index 3 that's right so this is 0 1 2 3 and our job is done okay uh what if you are searching for let's say five in this case it will print at index zero and that's what we got so this is working but what if you're searching for something let's say 77 which is not there in the list if you run this code it will say element not found so linear search is working right now we can do the same thing with the help of binary search now let's see how binary search works so what I will do is I will just write a code here which is public in fact I will just copy paste the code not a copy pasting but reusing the code I can simply copy this code and paste it here now if you're coming from java and if you're getting confused why I'm getting a starting method why not non- starting methods is because I don't want to deal with objects here okay just want to keep it simple so we got a static method and a binary search the thing is only method name will change the parameter will remain same in binary search also you pass a list and you pass a Target the algorithm will change of course it will return minus one that's not that is not something which is changing but what we will do inside this now if you go to the board here what we have done is if you have a list of values if you can see we have a list of values here now initially you have to specify the starting point and then you have to specify the ending point as well right so starting and ending you have to specify in this example we'll say left and right okay because that's how that makes much more sense right left and right starting point is left ending point is right and then you will find a mid every time you find a mid if it is matching that's great otherwise you have to uh basically skip the number of elements which is in the other section okay so how do we do that here so what I can simply do here is in fact I will just for my reference I will also have those values here so I will say 5 7 9 11 and 13 okay and the value let's say which I'm searching for this time let's have the value so let's say I'm searching for 11 okay so what I will do is if you when you're searching for 11 first of all you have to specify the starting point so I will say left in fact left int left is equal to now left is a starting point right which is zero then int right which is the ending point which could be four but then why to hardcode it what you can do is you can say nums do length minus one nums do length will give you five you have to say minus one which will give you four so now we got the starting point ending point and then Our Journey Begins right so what are we going to do here so we'll use a y Loop here now inside this while loop what I'm going to do is I'm going to check if my left is less than equal to right we'll check if left is less than right because that's what we want right left should be on the left hand side which is the which is smaller values and then here what we'll do is we'll find the mid okay that's the journey we are going to start so mid is basically your starting point right which is left plus right and we want this to be in the bracket so that we can divide so left plus right divid by two okay that's how you find the mid right now once you got your mid you can basically check if the nums of mid is it matching with Target if it is matching that's great we can simply return the index which is mid of course right mid is representing a index here if it is not matching then we have to change the value of left or right depending upon what you got in the mid so what we'll do is we'll say if else if now how do you check so we can check if nums of mid is less than the target so let me take this up as well yeah so if nums of mid is less than Target so let's say when you talk about this elements and then we are searching for 11 right the mid which we got is nine if the nine is less than the 11 we have to shift our left right so this left left which was representing five will shift here now I mean not even nine we don't have to even consider nine right so what we can do is we can say left will shift to Mid + 1 okay so basically now we have two values 11 and 13 which we are going to focus in the next iteration but what if you're searching for something else which is on in this side let's say we were searching for seven in this case we have to shift our right so right is mid minus one so basically let's say if you're searching for seven here we got a mid as 9 what you will do is you will say Okay so the value is less than the mid so we have to we have to skip this two the focus will be only on five and seven that's what we have done here if you're searching for seven okay I think uh this looks cool we our job is done let's verify if things are working out the only thing if we do is instead of searching for a linear search this time we'll go for a banner search let's run it works you can see it says found index at three and what if you you are searching for let's say 17 which is not there run it says not found let's search for five and it says it works you can say index zero so that means you can use linear search or B search both works but what if you want to really see how many steps it is getting so what I will do is let me just say this is result two which is B search and let me also say Result One of course I'm not going to use both the things I'm just I just want to call both the methods okay I'm just going to use result one because if linear search is able to find it fin search will also able to find it okay let's print result one here so I just want to call both the methods that's reason I'm I'm using result two but result two we are not using it anywhere else okay so let's do this with both the algorithms and you can see both will print the same thing or we're not printing the second part okay doesn't matter both will give the same result but what I'm really concerned about is the number of steps so what I'm going to do here is let's calculate the number of steps it takes so I will say for linear search steps is equal to zero initially and every time the loop iterates okay I will simply say steps number of steps taken so steps plus plus and then I'm going to print just so just before return I'm going to print steps taken by linear colon and I will print steps the same thing I want to print here as well what if there's no element found so this will not never be executed right okay we have to put this into a curly brackets cool so we are printing the steps here the same thing I think we should do for bunny search as well so here I will say int steps is equal to zero and every time you iterate in this Loop you will say steps Plus+ and then basically here you will print the same statement so I will just copy this so we'll print before returning the value but here we'll say binary and we also print this before returning just to cover all the cases okay let's see what it does run this code and you can see for five elements linear search is searching in one okay reason being we are searching for five right I think we searching for five let's search for 11 okay in some cases linear search works well run and you can see the linear search takes four steps the binary search Takes Two Steps that's crazy run again of course you will get the same output but what if the values are higher let's say I have more values here let me add 10 me add one two three so now we have more values right I don't know how many values we have but let's say if I run this code the linear search takes eight steps B search takes three steps okay but what if you have thousand values now how do you check thousand values now that will be tricky so what I'm going to do is let's add some R the values here let me create a array of size th000 I don't want to specify my own values let's say 1,000 and the value which I searching for is let's say 500 okay it's somewhere between maybe I will say 900 let's see what happens so I have a value which is 1 to th000 I'm searching for I mean I have th000 values in the array and I'm searching for 900 but by default the value will be zero okay uh example if you search this it will say not found but look at the number of steps linear search takes th000 binary takes 10 and what if you have more values here run linear search takes 10,000 ban takes 4 and look at the size example let's say if the size is 8 and by default all the values on the array is zero so anyway it is sorted by default and you can see if I run this code uh which says eight for linear four for binary but the moment I double the values look at the steps taken by binary is only one extra linear all is double if I double the value again 32 so every time you double the value B search will take only one extra step and that's why we say it's a biger notation for this is log n okay so in this case the binary search works better than the linear search now the same code you can write with the help of binary search as well example instead of using a loop here I can simply commment the entire section and we can replace this with a recursive function the only thing is in recursive that the changes we will be doing is in recursive you're going to call the same function again again by changing the values let's say you have this big uh array and then you done your first search you find you found the mid now the moment you found this section let's say this part or this part whichever is matching you will remove the other half and again you will run the same B search on this list and then again you will break it down into two parts you will remove one and you will run the B search on the other one so in B search basically if you want to make it recursive you have to pass two more things which is int left and okay not in in left you have to specify the left and right so I will say zero and nums do length minus one so basically you have to specify the start and the end and every time you call binary you will simply accept those two things you you will say left and right so that you don't have to specify them here in fact you know instead of removing it maybe you want to refer this later I'll just come in this section now since this is a recursive you don't need a loop here right what you can do is you can check if the same step left is less than equal to right if this is a scenario what you will do is of course you have to find the mid I will just copy this code this is where you finding mid and after finding the mid you can basically also uh check the same logic this is a logic you're going to use the changes is we we going to change in the else part I mean the eils part let me uncommon the entire section the changes you're going to do let let's not print the steps now we know know the steps right how many steps it takes but I'm just trying to convert that into a recursive function so it will you will return mid here there's no problem with this the changes happens in the elsf so in the else if instead of doing this we are going to basically call the binary search Once Again by passing the same nums and then you will change the target value now so you will pass Target value so you have to pass nums and Target value then you have to pass the left value now what is left so in this case we have to change the left right left will become mid + 1 and right will remain same right will remain right but here again we have to make the changes else part instead of this left will remain left and right becomes mid minus one so basically what you're doing is you are changing the values like this if you have this list of values you break it down to two parts again after checking and then you're change you're again calling the same B search with a new values okay that's what we're doing here so let me remove the extra cly brackets just to make the code look good or short basically and that's it this is your B search let's see if this works let's re restart I mean rerun and it says not found because yeah of course it's not found because we don't have that value but yeah this is a code for the uh binary search with the help of recursive now there's one more thing uh you can try with different examples what you can do is you can take a array of thousand values and add random values so in Java we have this random class you can add the values and see how much time it takes in this video we'll talk about the Sorting techniques now basically we have talked about the Big O notation right and now we know that if you want to judge the algorithm which you are writing you have to make sure that you are using an algorithm which is efficient in terms of time and space as well we are focusing more on the time complexity where as your data increases it should not increase your time exponentially so we have seen different levels of uh time complexity and we want to be into that lower Zone not on the upper zone right now when when it comes to understanding different algorithms we have to go for some inbu algorithms right or some old algorithm which normally we use so sorting so we have talked about searching sorting is one of the way you can learn more about algorithms and how do you make it more efficient also in the real world we do use sorting a lot so let's say when you when you say you want to search something on the internet or maybe you want you want to buy something on the Amazon you do that uh sort by Price sort by reviews right so you do that multiple times so sorting is majorly used so there are a lot of different sorting techniques available so we'll try to understand them not everything or not every algorithm but let's try to understand few of them now if you talk about these algorithms some algorithms are easy or simple to understand but they are not time efficient and then there are some algorithms which are good in terms of time so they are time efficient but they're not simple to understand okay uh so we have to do a trade-off here now which is the best one that depends if you have less number of elements and if you're learning for the education purpose or to understand how sorting works then we can talk about those algorithms like bubble sort selection sort and then there are some algorithms which are bit difficult and they are very efficient when you have huge amount of data now what Al I'm talking about so when you talk about sorting there are different options available so we have Bubble sort selection sort interesting sort merge sort quick sort counting sort uh re hip sort bucket sort and there are multiple sorting techniques the famous One are bubble sort quick sort selection sort insertion and then M sort if I'm not repeted that multiple times so let's start with the first one which is bubble sort now bubble sort is not efficient but it is simple to understand so that gives us a starting point when we talk about bubble sort why do we use it so let's say if you want to sort different elements ments so let's say we have this list in front of you the numbers are 8 6 9 2 4 5 now if you want to basically sort them how will you do it now of course we don't have a magical way where you can find hey this is the first one this is the second one so what you do is you basically try to use some algorithm like bubble sort to sort it in this what you do is you basically create a bubble now what exactly this bubble is take one element put that into bubble and shift it to the end okay now that sounds weird right so let's let's step by step now when you have this value let's say you have six value in front of you you can put them in an array like this and then you have provided the index values now if you want to do this sorting on this of course we want a ascending sorting here so basically we want to at the start then four uh then five then six then 8 and then n that's a sequence we want but how will you get it so what you do is you compare two values at a time so let's say if you put six people in front of you and you want to sort them according to the their height so what you do of course you will compare two people at a time right that's how you sort and then you will try to swap them so how it exactly it works so let's say we have these two values here 8 and six and then what you do is you want to make sure that the biggest element from this particular array in the first iteration goes to the end okay so the way you do that is first you compare the first two values now these are the first two values when you're comparing it if the first value is greater than the second value you basically need to swap okay swapping is very important here so you have to first compare the first two values if the first value is greater than second value then you have to swap and then you basically shift your pointer to the next two values okay done we are done with the six now let's go for the next two the next two is8 and N if the first value is greater than the second value you have to swap in this case they are not they are so the first value is less than the second value so what you do is you simply say skip because there's no swapping needed then you go for the next two values the first first value is greater than second value so of course we have to swap and then again you shift your values next two values again you will compare the first value is greater than second swap then again you will compare the next two value the first value is greater than second swap so basically after the first situation you got the biggest value at the end but is it sorted unfortunately not you need to do this operation one more time actually not one more time multiple times till you get this sorted now this also depends upon this size of your elements or array now in this case the first five values are still unsorted the last one is done so we don't have to touch the last element so in the first iteration if you're going for six times the second iteration you can go for five times the third iteration you can go for four times so let's see how that works now after the first iteration we got the nine value at the end now what you do is again you repeat the same steps compare the first two values is it required to swap in this case no we can skip it next two Valu is the first value greater than second value yes swap it then again you go for this next two values is 8 greater than four yes swap it is then again next two values 8 greater than five yes swap it now in this case what happened is after the two iterations you got the two biggest values which is 8 and N at the end now we know that those two values are sorted but what about other values those are not sorted so let's sort them again you have to repeat the same steps so you have to say 62 which is 6 is greater than two again we have to swap it 6 and four greater than 6 is greater than four swap it 6 and five again swap it so now after this iteration you got three values 6 8 9 which is sorted but what about the values they're still unsorted I mean we know they're sorted now but your algorithm has no idea if they're sorted okay now this is tricky because your algorithm goes from start to end okay it will not check for do the other values are sorted or not so it will keep doing that so it will compare uh the first two values not swap not needed next two values swap not needed done we have also confirm five still there's a confusion for two and four your algorithm has no idea those two are already sorted but still it will try to sort them it will compare the two values they are compared swapping not needed so by doing that four is confirmed and since you only have one element now that itself is sorted and by doing this you got the entire sorted at so yes even if you it is sorted it will still check we are reducing One Step which is swapping but still you are checking and that's why bubble sort is not an efficient algorithm and the problem is the time complexity for this is O of n² because you have to use two Loops one for the iterations and the inner loop for each iteration you have to compare the values so that's your n² not a good way of of sorting the elements now think about six elements so that's good six squar is not a big number it is actually but what about if you have a very big array or very big list let's say 20 values 30 values imagine the number of steps it will take so not an efficient algorithm but easy to understand now it's time to convert this into a code okay now let's try to implement the concept of bubble sort in the code so we are going to use Java as a language so if if you want to sort of course you have to store the Valu somewhere first so what I will do is I will create an array of integers and let me just name this as nums and then I will assign some values of course I can go for this new array and then assign the value one by one or we can give them the static values so here let's say we go with values 6 comma 5 comma 2 comma 8 comma 9 comma 4 I don't remember the sequence in the previous video which we talked about the theory but let's go with this values and I want to sort them okay okay so what I will do is even before sorting let me print all the values the way you can print the values of an array in Java is you of course you can use a normal Loop or we can use enhanced for Loop so let me just use enhanced for Loop here so I will say for INT num in nums and then we can print the values right so I'm printing num here so I will say this is before sorting and then I will I will do the same thing I will execute the same code but after sorting here so let's say this is after sorting okay now if I run this code of course you will get the same value two times so if I and one more thing I will not be I want to print this on the same line because Ellen will print on a new line I don't want it and maybe after every printing I want to give some space as well to differentiate the values and let me do that here as well so that it will it will print on the same line with spaces right click here and say run and you can see uh we got before sorting after sorting I think uh this should be printed on a new line so what I can do is just before this I'll say out and run okay so this is before sorting and this is after sorting at this point is not getting sorted of course right we have not written any logic here now this is where in between you have to write the logic for sorting now in bubble sort what you do is you compare the values two Val at a time and then you swap so you compare these two values if the first one is greater than second one just Swap and then likewise you will do for all the elements now for sure if you want to move to the ation now we have to do two Loops here the nested Loop basically the outer loop is responsible for the number of iterations or the number of passes and the inner loop is actually responsible for swapping so what I mean by that is I need a first variable I which start from zero and where are we going to end it so of course I can end it at less than six so you can say six or you can say nums do length Okay so basically we can use the added length you know the better way would be to store this value somewhere so I can say size nums do length so I'm just storing that value in a variable called size it will be easier to work with so I will simply say size and then I will say i++ so it will go from uh start to end so this is only for passing right we have to do this multiple times you have seen that in the animations but now let's do the inner loop which will do the actual swapping so here I will say int J is equal to Zer because going to start from zero the real question is where are we going to end it at this point I will say size and let's see what happens if you do do with size okay so both the loop the outer loop and the inner loop are starting from zero and ending at size the size of the array and now we have to basically compare two values now how will you compare two values uh and how do we even swap them so we will check if the first value now how do you know the first value so nums of six or nums of Z basically six is nums of Z so nums of zero compared with nums of one that's how you compare again you can compare nums of one with nums of two then nums of two with nums of three then nums of three with nums of four that means the current number when you say 0 1 2 it is represented by J so I can say nums of J but this will be compared with the next value and how do I know the next value which is your nums of J + 1 as simple as that so we are comparing two values now how we are comparing them which operator we are going to use here so we are going to use greater than if the first value is greater than the second value then you have to swap simple technique right now how do you swap there are different ways of which you can swap the values uh I'm going to use a traditional way let me use a temp variable uh in fact you can also declare a temp temp variable here so I can say int you know it's better to have all the variables on top so I will say int temp equal to0 initially and then using the third variable I can can simply swap them so I can say temp is equal to nums of J and then nums of J is equal to nums of J + 1 and then nums of J + 1 is equal to time so basically what we doing is with these three lines we are just swapping them nothing complex just swapping the two values okay and that's what we have done here so every time you find this the first value greater than the second value just swap them and you do this multiple times because we are keeping this in a loop and that's it the Sorting is done uh since it will be happening multiple times it will make sure that you keep the values at the end the bigger value at the end after each iteration so if you run this okay we got an error it says out of bound now there's one problem here don't you think when we are going for J + 1 what about the last value so we need to make sure that we don't go to the last value so it should end minus one right uh because when you're comparing the last two values the value for J will be here and this will be J + 1 so we have to make sure that your J ends before the last value that was the eror and run and you can see sorting done and you got the sorted values this this is how basically you sort them again we have seen this explanation in theory how things are working out but here we just try to sort it with the help of this logic now there's one problem here uh every time you do this in the animation if you remember every after every pass we don't have to go for all the values because the last value is sorted in the next pass two values are sorted in the next pass three values are sorted so we don't have to sort them again or even check them again so here J should be not going to size minus one in fact it should go size - i - 1 is because after every iteration so let's say we have the first iteration where I is zero it will go till the second second last value because we saying minus one in the second iteration where the I value will be one it will go till the second last position or third last position because the last value is sorted you don't have to check that again it will not affect the output but it will affect the speed because we are saving some time by not checking the same sorted value again and again okay that's how you basically you do it in fact if you want what we can also do is we can print this in every iteration so I can just copy this and after every iteration of the outer loop we can print the values and see what is happening there right so in fact I will also print a new line here so that it will come on new line let's run this so this this is what basically is happening initially you have this value and then this is where the Sorting starts if you can see after the first iteration the biggest value nine just went till the end then after the next for the next iteration the biggest value which is uh eight is at the end our second biggest value third iteration we got three value sorted fourth iteration we got four value sorted fifth iteration we got four value sorted or five value sorted and last iteration we got all the value sorted so that's how basically it does of course here too we got at the start itself we don't have to sort them again but that's Alm works right how will you even check if the array is sorted even before you compare all the values so that's the thing about the bubble sort where you compare the values swap them and done in this video we'll talk about selection sort so basically we'll talk about the theory in this and then in the next video we'll talk about the Practical of it the thing is when you talk about sorting we have different techniques available in the previous video we have talked about bubble sort and it was working right but also the amount of time it takes basically the time complexity of the bubble sort is n squ now that's not the main issue of course that's a main issue but then in this video we are not going to solve that quadratic uh time complexity but at least we can reduce the number of steps now in bubble sort we are going from start to end multiple times that's not the big issue the big issue is swapping because every time in the Inner Loop we were doing this swapping multiple times and it consumes a lot of time and memory so what if we can reduce that and that's where selection sort comes into picture now what we do in selection sort is we don't actually swap every time when you compare to values but what you do is from the entire array or the Leist you find the minimum or the maximum value depend upon how you want to implement it so let's say we got we are going for the minimum value so what you do is from the entire array you find the minimum value and then you make sure that the minimum value stays at the start now once that is done now that is your sorted part so from the entire list you create two sections the sorted section and the unsorted section so once you find two that goes into this sorted section which is at the start and then you scan more values now let's say when you scan you find hey we have three which is the minimum value in the unsorted array then what you do is you pick up that three and replace it with the second location now what happens to the value of the second location now that will be swapped where the value of three was so what you're doing here is you are swapping by selecting the minimum value So when you say selecting that's your selection sort now what it does is you're not basically swapping value inside the inner loop you are doing that in the outer loop which means the number of swapping in a code will reduce now to understand this mode Let's look an example so let's say we have six values here which is 65 2 8 37 and we want to sort them so how we you do it first of all going from all the values now of course as I mentioned before you can go for the minimum value or you can go for the maximum value so let's go for maximum value okay so ultimately you will get the same output but the way you do do the code will be different so let's say we are going for a maximum value now from all this Valu we have to find the maximum value now of course at the start we don't have any idea which value is a maximum so let's say you make six as the maximum value because at this point we don't know right so let's assume that six is the biggest value from the from all these values and then you start comparing six with all the other values so you will compare six with five if six is still bigger no issue go with the next value is six is still bigger no issue go with the next value now at this point we are comparing six with 8 and we know now 8 is the biggest value so now what you do is you change your variable or your you change your biggest value from six to eight and then you start comparing eight with the other remaining value which is three and seven so you compare with three eight is still the B biggest you compare it with seven seven eight is still the biggest now once you go through all the values now you know the eight is the biggest value so what you do is you make sure that 8 goes at the end now if you're doing this with for the minimum value what you do is you take the value two which is a minimum value and you put that at the start but since we are going for a different approach where you're finding the biggest value you will make sure that eight goes at the end now when you move eight to the end what happens to seven now seven will say okay I don't have a place so eight will say don't worry I will come to your place you come to my place that is swapping of the values but if you remember we are not doing it in every iteration of the inner loop we are doing that in the outer loop so once you complete one pass that's where you do the swapping so only once for the entire iteration okay now by doing this we have made sure that you have the biggest value at the end and you got a sorted at the end which is the eight and then the first five values are still unsorted so what you do is you repeat the steps again start with six now we'll say Okay six is the biggest value let's say assume that and then you start comparing six with five if it is a biggest six is still bigger no need to change the value of biggest value then you compare it with two no need to change but then when when seven comes to picture seven says hey you know I'm the big I'm bigger than you so six says okay you're the biggest value so now the current value will be seven the biggest value is seven now again we have to compare seven with three now seven is still the biggest so we have to make sure that after all the situation we move seven at the place of three and that's what we going to do now by doing the second iteration so we have completed the second iteration in which you got two values seven and8 at the end and the first four values are same so again you do the same thing next iteration so you have to do this till the till you complete all the Sorting so you again go with six and say Hey you know I'm the biggest now let's compare six with five so still the biggest compare it with two still the biggest compared with three still the biggest now once you complete that unsorted iteration you will make sure that you move your six to the location of three because that's where the six should be so it will swap with three and then the last three values 6 7 8 are sorted the first three values are not sorted so again if You observe what we are doing is we are making sure that you got two different sections of sorted values and unsorted values now goes for the first three values so three let's assume three is the biggest and then compare it with five now we know that five is the biggest of all or at least bigger than three and then you compare you you make the bigger value as five now three is gone then you compare five with two still five is biggest and now we know that five need to go at the location of two so you have to swap it now comes the first two values again the same thing you will keep doing this till you reach to the end of your array and you move to three and since we only have one value don't need to sort it that's already sorted and by doing this you basically basically got a sorted array now again compared to the bubble sort we are still going from start to end you have a outer loop you have a inner loop but we are doing swapping only once in every big iteration or in every pass so that's the advantage of using selection sort over the bubble sort about the overall the time complexity is still o of n² but at least it is better than the bubble sort in terms of swapping now it's time to implement selection sort in Java so in the previous video we have talked about the bubble sort right and this is how it works now one thing to remember in the Inner Loop can you see this Loop in this Loop we are basically doing the swapping so it increases the time as well so in selection what you do is you basically Swap this of course you do that swapping but outside the inner loop somewhere here so it reduces the number of swap you're doing how will you do it so what I will do is I will just remove the entire code from here because this is the bubble sort I don't need this and what we have here is we have the array which is which has six elements we got a size variable where we are storing the length of an array and then we also have a temp variable for swapping then we are printing the array before sorting then and we are printing the array after sorting okay so if you run this you will get the values before sorting after sorting but at this point they are same is because the main logic of sorting is missing here so let's write the logic for selection sort here the thing is in the theory we have said that we'll go for the maximum value the biggest value to swap or we'll put the biggest value at the end let's say in the Practical let's try to implement with the smallest value and we'll we have seen both the approach then so what we're going to do is we'll look at the entire array and then we'll find the smallest value which is two of course you have to iterate between all the values and then once you got the smallest value you will swap this six with two because two should be the first value and that's how we can start and for doing that we have to use use two Loops the outer loop and inner loop we'll start outer loop with zero and then we'll say I less than uh size right okay so we'll say I ++ but also we can make it more efficient by saying that size minus one is because if you remember when we were doing the sorting and once once you got all the values sorted except the first value or the last value you don't basically sort the one value right so you can reduce the number of equations you go for so we can say size minus one and we'll see if that works or not and if it works then we are happy we'll also go for the inner loop now for the inner loop we'll go for J equal to now where do we going to start J so basically if you're putting the starting the biggest value or the smallest value at the start what it means is after for every iteration the inner loop we we can skip the first value right so for the for the second iteration we can skip the first value for the third itation we can skip the first two values because they are sorted right so we have two sections right sorted array and unsorted array so here we can start with J equal to I yeah in fact when your I value is zero J should start from zero so we can say J equal to I and J less than size and j++ so basically we have to end we have to go to the end okay so that's the for we have now what you do inside this so we have to find the minimum value to start with we can take Min value variable here so I can say int Min is equal to zero in fact we want the minan index not the minan value because we have to work with the index right and we'll say the index is by default minus one and here to start with we'll start with me uh index equal to I and then what you do you basically check if the array which is nums of mean index now we want this to be smallest value right so I assume that this is the smallest but what if this is not the smallest compared to the value which we are considering the value which is considering here is nums of J so example if this six is the smallest which we are thinking in fact you know we should be saying I + 1 the reason being when you are saying that six is the minimum value we are assuming that and then we are comparing with five now you will get five when you say J starts with i + 1 because in the first iteration the value of I will be zero and this five is one right so we'll compare this two values okay if six is smaller than five then everything works but what if six is greater than five in that case we have to swap now okay we don't have to swap we basically have to change the minan index to J because the new index you will get is J so the new index here is one okay uh so that's the main main index so what we are doing by doing this is after the entire iteration you will get the minimum value from this array okay so that means after this iteration you will you will know that two is the minimum value now once you know the minimum value what you do is you swap two with six is that simple how do you swap two and six how do you know we have to swap six because I is referring to six and the mid index is referring to two so we can simply swap them so we can use a temp variable here and we can put nums of uh Min index and we can say nums of Min index is equal to nums of I and nums of I is equal to 10 so basically we just have to swap them so what we are doing is in the Inner Loop we are just finding the minimum value and then once you find it you simply swap it with the Min value which you're considering which is the first value and as the I value goes up first you will compare with this then you compare with the five and you compare then you make two as a minimum after of course after the swiping and I what what I will do is I will also print this values after each iteration so I can just copy this and paste it here and we also print a new line to get it on the new line so now if you run this let's see what happens so you can see if this is okay uh I will after printing this also I will just say new line or maybe I will just skip this new line before the for Loop printing okay let's run and you can see this is before swapping and then and this is after swapping so let's compare the value is it properly sorted uh yes 2 4 5 6 8 9 those are the values we have and then see the steps in the first situation before swapping uh so this is the first situation what you do is you know that two is a minimum value so you swap six with two and that's done then in the second iteration you find the minimum value so the minimum value from this is four so you swap four with five and that is done here then you consider six then you say you find the minimum value from this which is five you will swap five with six so in this you'll say uh six is the minimum so you will swap it with eight comparing this two this is eight and nine so you will swap eight with nine and in last value you don't have to even sort it because it's always sorted and that's what we are doing here and that's why we say it's size minus one we don't even sort here in fact if you don't put this minus one what will happen is if you run this code you will get one more iteration and there's no change there it doesn't matter how many values you have you're not going to have any change in the large iteration so you simply save it by saying minus one here so that's how we use selection sort basically find the minimum value and swipe it with the location where it should be so we have talked about different sorting techniques we have talked about bubble sort and selection sort in this video we'll talk about insertion sort so what you do in this technique is basically you take the elements and then you put the elements at the right position that is your insertion so you have to put at the right location now in this you don't normally do swapping yes we do swapping but we don't use word swapping what you use is something called shifting okay so example if you playing uh if you're playing cards so if you if you have a random cards on your table so basically in this example we not going to use cards we are going to use this uh characters I I found these characters in my uh in my drawer I think I got it for my kids's birthday but it doesn't matter so I got this and we'll try to sort this values here so let's say if you randomly get these values and if you want to sort them uh what you do is you pick up the value and then you you know imagine these are cards playing cards so what you do is you take the first value you take the second value and then you keep it like this I don't know if how many of you play cards I used to love them not for money uh but I used to love them then you take a next card and then you put it before this then you take a card then you know that this card goes between a and o you put it here so this is called insertion but how exactly you're going to do that that will see with the example on this table and with this with this cards so now let's sort this values now this these are not values but characters so let's try so what we have here is we'll start with the first location as you can see on the screen we have different values here and I'll pull this down a bit so that we can have some place to keep this so the first value is O now I'm assuming the the O goes here the first location because it's always sorted and then you take the next value which is e let's say now we know that e comes before o so what we have to do is this need to go at the start so you have to move this to the next location so that you will have some space for e now the point to remember here is it's all about shifting okay so we don't use a word swapping here you'll understand that in sometime why don't we say swapping uh let's go for the next one which is s now we know that s is greater than so we'll compare s with all the values so we'll compare s with e okay it goes after that it goes after o so s goes here okay I'm not promoting any camera model here but that's the sequence then you go for the next one which is D now d goes at the start so what you do is you basically have to move all the elements right so if you compare with s here D is less than S so you compare so you have to shift s you have to make some space for D then you take o and you move o here so that you can make some space for D then you compare D with E and you have to make some space of course you have to swap you have to move this you will make some space for D and D goes here right so now it is in sequence then what about the last value which is a now a we all know we have to I mean of course it goes at the start but we have to compare from start or last so this goes here which is s if it is less than that we'll shift this to make space for a but then we have to also check with o this also have to shift with we check with e this also have to check shift We compare with d this also has to shift and then a goes at the start by doing this what you're doing is you're basically inserting value at their location so this is how you do the insertion sort now let's say this was randomly we were picking values right but what if you have things already in the array so what we'll do is we'll keep it here we'll keep this here we'll keep this here this goes here and let's say this goes here in fact I will also move this okay I'm not trying to make any city name but let's say we have this sequence we have these five values and now you want to sort them so what you do is you don't start from the first value you start with the second value and then because we assuming that the first value is already sorted okay so what you do in this technique is basically you divide your list or array into two segments the sorted and unsorted at this point all are unsorted so this is unsorted array but when you start you have to assume that your s is already sorted then you start with E then you see hey do do we have e at the right position the way you do that is you compare e with s and this and you say Hey you know e is not at the right position so you will take e out uh in programming you what you do is you save the value of e in the temporary location okay so exactly you're not moving e you're just making a copy of it maybe there will be a copy of e here as well but you have extra copy with you saved in a temporary variable so let's say this is a temporary space then you move your s here so that you can make space for e and that's sorted now now if you see this two it looks sorted now what you do is you check E before do we have any value so of course we don't have any value before E now that is sorted then you go for the next value so we started here in the next iteration you basically start with o now o will compare with the previous value which is s now is it the right position no so we have to copy o in the temporary variable and move your s so that you can make some space for o and O of course you can move o here you have to also check if o really goes here you have to compare o with the previous value which is e and we know that o is greater than e so you can keep o here so that's how you basically sorted the third element then you go for the next element which is D so what you do is you compare D with s here and then you know that D is smaller than s or S is greater than D so what you do is you have to move so you take into temporary variable move s here of course you don't move D directly there you have to compare D with the other other elements which is O is it smaller than that yes we have to move this here we have to make space for d right again the before that also we have one more element which is e so you move e here it's all about shifting values and then your D goes here and if you compare uh it it looks sorted right compared to the other other values so it looks sorted but then we have to complete one more iteration so you take a you compare a with s now a here is compared with s so again we have to shift so what you do is you take a as the temporary location then you move your s you will check a with o again you have to move O then you check a with e again you have to move e so remember you have to only move when you know that a will not be at the right position and then you compare a with d again D has to move so that you can make some space with for a so this is how basically you do this sorting technique now question arise how will you do in programming so what you need is you need two Loops one for the number of passes you are doing right moving from different element and you need a inner loop which will responsible to find the key and uh shift the values and also you need a temporary variable so that you can store it somewhere so you have to you need a key which will go into a temporary variable on something now how do we do this that's Implement in the code so let's try to implement insertion sort using Java now basically even before we Implement that before we write the code let's write the algorithm on the board and then we'll try to convert that into code so what we'll do is first of all let's create some let's get some values okay so we also need a array so let's say I will name this as array itself ARR and then it will have some values so let's let me create a array here and we'll take few values let's say we got uh five values of course you can go for more values here and then let me just say this values are three 6 2 1 5 okay so we got this five values now I want some variables as well so as I mentioned before we don't swap here right we do shifting of the values so of course to achieve that we need Inner Loop and the outer loop so let's say we got the outer loop which will will go for for Loop so let's say we have a for Loop here and then we have to take a variable which is I for the outer loop counter and then inside this we are going to have a while loop which will have let's say some some condition of course you can also go for four and four but then when you talk about insertion using Y Loop inside makes much more sense because we want to B we want to run this based on the condition not on the number of equations okay so this is your outer loop let's finish it here this is your inner loop let's finish it here and let's write the code there now we need two VAR as I mentioned of course in the while loop we are not going to create a variable we are going to use one variable but let's also go for J so we need a i variable let me just write I here we need a j variable and we need a key as well so that you can store this value somewhere so at one point you will compare and you will save it now from where we are going to start this now if you want to understand what what we going to do is it's very simple so initially you will take your six as a key so when you write this variable we'll say key is initially six okay now how you're going to get six so let's say we take a variable I here and then we'll keep the J here okay so we're not going to start I from the first one we're going to start I from the second one and then J will be the first value now I will represent the outer loop and J will change in the inner loop as well okay so that's why we are going for I and J we could have gone for different variable name but we got used to I and J for the Outer Loop and inner loop okay so now uh what you're going to do so the idea is very simple once you got a key which is six in this case now how you got six maybe we can do something like this we'll say a r r of I whatever I represents we'll save that in the variable K or key and then we're going to start J by saying J is equal to i - 1 so I is starting from 1 so J is i - one that means the value for J initially will be zero and I is one now what you're going to do with this it's very simple you will simply compare the value of J which is this the first value so we'll compare J with the key if this value is greater than the key then you will do the shifting part at this point we don't need that right because the value of J where the J represents is less than the key then you don't have to do any shifting part so this is already sorted okay but let's go for the next situation now when you say next situation it's very simple what you simply do is so you shift your value of I here and you shift your value of J here because we know that the three and six if you compare this two they are sorted let's go for the next one now in this what you will do is you will check again you will change certain things right if you can see this will change because now a r r of I is not six a r r of I is basically 2 okay so key is two now what about the value of I even I is changed I is now two so index is two so let me also write index so that it will make much more sense right so that those are the index value so I value is two now what about J so J is IUS 1 so J will start from 1 that's done and now you will apply a condition so what basically condition we are checking for so of course if you write the code here so I is initially starting with one we're not starting with zero and then we'll go till I less than n if the Val if the length of this array is n and then we'll say I ++ okay and then we'll assign the value okay we let's not write the actual code let's write some dummy code so let's say we got a key variable the value for key is basically a RR which is the array of I and that's what we are doing here that's one thing next we also need J variable so we'll say J is equal to i - 1 okay that's how we going to start now what you're going to compare in the while loop so in the while loop it's very simple you will check for the a RR so a RR of J let me just say complete this here so this if this is greater than the key because the shifting part will come only when whatever is represented by J is greater than the key so if you can see the key is two here and in this case yes it is greater so six is greater than two so what you do is you basically perform some operation now what operation I'm going to perform so basically first of all I will take this key somewhere of course we are do that key two in the key variable and then you do the shifting shifting of what so you will first compare this two with six and now we know that we have to shift six so you will shift six here then that's one done right can you put two here we can actually we can put two here but the problem is we also know that we have to compare two with the previous value which is three in this case so you will not shift two there but we'll shift three here but then to shift three here what we have to also do is we have to first shift our J here on the first location that means we are also going to perform J minus minus right so what I'm saying is the first option you're going to perform is Shifting the values right so how do you shift you simply take the next value so initially J was here right so this value six is going here so that means what we can do is we can say a r r of J + 1 which is in this case 2 is a r r of J by doing this what you're doing is you're shifting so the J initially was here which is one so index of J was 1 or the value of J was 1 then you're saying J of two I mean J becomes two then what we are saying is we are saying J + 1 which is two so the value of six which was here will move here that's what we are doing on this line that's a shifting point and then you will say jusus so you can say jusus or you can say J minus one even both works so this is the entire logic you have right but this Loop will repeat right now when it will repeat look at the condition here the condition is whatever J so we are shifting J backwards right J is now here so we'll check if a r out of J is greater than key in this case yes you can see the key is to a r of J is three so it is greater so will shift so how do you shift basically you do the same operation which is there inside the Y Loop Loop so if you compare this operation this is what it is doing the shifting part right and then we know that of course if you can see here we have one more step you will do J minus one which means your J basically moves one here because when you reduce the value of J it become it became zero right and then again you're doing it so it will become J J becomes minus one so we have to stop it here once the J becomes less than zero we have to stop but don't you think we have to also add that condition in the while loop so we'll do that we'll say and J should be greater than equal to Z okay this is one condition we have to add if this is false if J is not less than or equal to Z then you will do the last last step the last step is very simple you move your two here and the way you can do that is by saying a r r of J + 1 because J became minus one we don't want minus one we want zero is equal to K is equal to key so basically this is where the value goes first now by doing this we were able to sort the first three values now what next of of course you will increment the value of I so when you say increment that means the value of the I variable goes here and again for the next situation J goes IUS one right because of this basically for the outer loop the I value is incrementing but the J value is just before I and again you you do the same things what are the same things you first check if the key okay we have to update the key as well now how do you update the key now the key value is a r of I which is in this case should be one so the new key is one and j i is what I is 3 and J is 2 okay new key value is 1 you will compare if the a r r of J this is the condition we checking now if a r of J which is in this case is six is greater than the key in this case yes you perform this operation what is the operation it's very simple let's skip this value somewhere you start shifting six here six goes there and then your J comes back J comes here right because of this step here right and then you you again check if a rror of J is greater than key yes 3 is greater than 1 again you will shift three here then you shift J here then again you shift two here then you shift J here and then now J becomes minus one Let's Stop the Loop and shift one here you can do the same thing for five let's do that quickly so what you will do is you will shift the value of I here which means certain things are going to change now this I becomes four uh this J becomes three the key value now is five right again you do the same things uh you keep your J here because J is just IUS one then you compare if the a r r of J which is six in this case is great than the key yes let's do the shifting now how do we do that let's move that here and then we have to shift six here J goes here now again you check is the a AR of J is greater than key no it's not there so you will just simply come out of the loop and then you will keep five here and if you can see it's all sorted so this is the logic let's implement this logic in the code now so you have the logic in your in front of you what you will do is you you got the same values in fact we can go with the values which we have so let's say okay I now I just re return the values let's go for this values and let's see if this works instead of array we are going for nums that perfectly works I don't want a Time variable so we can remove this portion here this is basically the olda code which we had for selection sort if I'm not wrong and this is the before sorting elements this logic is going to change for sure okay so let's try the logic it's very simple you create a array so let's say this array is a RR is equal to let's have some default values to it let's say 5 6 2 3 1 this time we're going for only five values and this is an array okay what next now basically as we have WR in the board let's take a for Loop now the for Loop is going to start with i i is equal to 1 and we can do that quickly now it will finish at n but we don't know what n is so we can say add. length and we can say I ++ right that's one done and now okay let me just remove some space in between okay now what are the extra variables we need basically we need two variables right we need key the value for key will be a r r of I which we have done earlier and then we also need J and we know J is J minus one now this this is what happens when you know the algorithm on the on the board right I have a I have a board with me so okay those are the things we need okay not J minus one it should be IUS one and then you do a while loop because this is where you do the iteration we have to make sure that J is greater than zero that's one thing and we need to also check if a r r of J is greater than key in that case you will execute the while loop so you will do certain things here now what you are going to do inside this while loop so basically you have to do the shifting right if it goes inside you will say AR of J + 1 is is equal to a r r of J right and also you have to reduce the value of J so you will say J we can even say J minus minus syntactically that works and for the outer loop you will assign the value for key for that particular empty location and the empty location is defined by J itself so J + 1 is equal to key and I think we are done so the code is so short uh let me check if that works what I will do is I will just print the values here so I will take a for Loop and I will say int num from array and let's print the values let's print num I don't want the new line I would just want a space here and let's see if that works right click run and boom you can see we got the output and the values are sorted it doesn't matter what type of values you add here let's say 8 4 and run you can see this is sorted yeah so that's your insertion sort in this video let's talk about another sorting algorithm which is called a quick sort so the thing is when we talk about sorting algorithms the idea here is to explore different algorithm and we'll see how efficient it is now when we talked about the other algorithms which we talked about till now bubble sort selection sort they have a Big O notation of n² which we don't want right we want to make it faster or efficient now in that case we have to explore some other algorithms and one of them is quick sort now in the best case the quick sort goes for n log n which is much better compared to the n n squ but in the worst case also it goes for n Square so in the worst case yes it is almost there but uh on average it is n log n or you can say the best case so at least we are happy in the best case and in the average case now let's see what is quick sort so actually it uses multiple things so let's talk about that first the first thing is divide and conquer so basically till this point when we talked about bubble sort or selection sort we were doing the algorithm on the entire collection so let's say if you have a a list of values which is six values so what you do is you perform the operation of bubble sort and all the Sorting techniques which we have done before applied on the entire list but what quick sort says let's do divide and conquer which simply means divide your problem into multiple things and solve the problem or sub problems individually so what you're doing is you're dividing it you're solving it and at the end you will combine it so that's your divide and conquer so in this case if you have six values let's divide the values into multiple sub problems and then sort it and then combine it so that is your divide and conquer next it it uses something called a recursion of course you can also use recursion in the other other algorithms but here it works with recursion now basically what is recursion so when you call the same function by itself so example let's say the function name or the method name is show and if you're calling show inside show that's your recursion right and next we have to understand the concept of of pivot now basically pivot is something called a central point of a problem okay so let's say you have this entire list here or the array now you have to find a pivot and then based on that you will perform the operation of course it will make much more sense when we start but remember we have to work with the pivot so those are the things you have to remember divide conquer recursion and pivot there's one more thing which is the tree now basically when you say you are dividing your entire list into subsections or sub problems what you're doing is you are creating a tree structure okay so once we start with the diagrams it will make it will make much more sense but these are the things we have to remember so let's see how your quick sort works and then we'll try to convert that into algorithm and then we'll see how to write a code for it now B the basic idea here is let's say you have a list of values so we are discussing about quick sort uh so let's say we have a list of values so let's go for six values here and I will say this is 5 this is 3 6 1 4 4 and two so let's say we have the six values I'm not sure will it really make sense to use this example but let's get started now with this six values what you normally do is you do divide and conquer here so the basic idea is break the entire list into sub problems okay something like this maybe can we can create uh two two different arrays here we'll be having three uh I mean 5 3 six here you can have 1 4 2 and then you can again divide this maybe you can have 1 and 4 here and divide this into two here also we can have five and then we can have another array which is three and six so we got this two arrays from the big array and then you create the shorter format of it so at the end what you're doing is you're creating the small chunks now this is what your tree structure is so we have divide we talked about divide so we are dividing it we'll sort the array and then we'll combine it and then since we are performing the Sorting on each section in sub problem that is your recursion but is it the real thing no so basically we talked about the idea but how do you divide the array randomly I just divided the array but that's not the main idea but we have to divide but not this way so how we are going to divide this that's the question let's remove this and let's go with the values here the idea is you want to divide for sure you will divide this into two parts but you need to find a point from where you will divide this and that point is basically your pivot now how do you find a pivot now basically the reason we get this parti or pivot to do the partitions of the array right now should we pick up one now that depends so even before you divide you have to do one more thing so I'm saying pivot but then that pivot should be a point which is at the right position let me repeat the pivot is a point in this array which is at the right location now if you see this after this sorting what the values you will get so you will get values like let's say I will just write in sh of format now so you will get 1 2 3 4 5 6 this is the output I want okay I just went for the sequence of numbers here but this is the output so this is the output which we want from this input which which we have the bigger array here or the big size which I mentioned okay so if you talk about the value one here so one should be at the first position two should be at the second position three on the third position fourth fourth position fifth fifth and sixth right so they should be at that position position now since we had taken those values and that's why it might be confusing but you got the point right doesn't matter what your values you have it should be in the ascending order so the first value the smallest value should be first and then Leist goes on okay now we have to make sure that at least you you find one point from here or one value which is at the right position example if I say uh let let me take four now four is it at the right position the answer is no four should be here right so instead of one it should be before then we can say four as at the right position now if you want to understand this with an example so let's say you in a classroom and then you have multiple students there okay and then you want to sort them based on their height there's one way as a trainer I can be there and I can say okay you go there you go there and that's what we have done in the bubble sort right I was controlling it but what if student can sort themsel so they can compare each other and they say okay I should be here or I should be here and they they will move now one way is one person can sort them but then we don't want it so what we want is what if the students themselves can get into the right position that that will solve the problem right okay but how we are going to do here how they will reach to a right position now what you do is initially we don't know the position right so you can take any value normally we can uh we can find the pivot so for the first iteration we what we are trying to do is we want to make sure at least one value is at the right position so that we can divide the array now which value should we take technically if you take the the average value or if you take the middle value example if you if you go from 1 to six the mid value is three or four right so if I can take three as my Pivot it will be much easier for me to divide the array so what will happen is if I take three as my Pivot then three should be coming here right so three this is the right position for three right but it's not if you start with the are this is not at the right position but if you get to the right position we can divide into two parts right okay so that's the main idea how will you get that there so normally what you do is if you can find a good pivot and that's very difficult to find because how do you know the mid value since we know the values here I can find the mid value but as a program or as a software they don't they don't have any idea what are those values are so what we do is we randomly pick the pivot maybe you can pick up the pivot let's say one in between somewhere anywhere if you want so you can pick up this one you can pick up the six or you can pick up the first value or you can pick up the last value or what you can do is you can you can just add all these values and divide by six whatever value you will get so try to find the average of it that's what we we can do but again that's a lengthy process normally which I have seen is they go for the big the last value not the biggest value last value because we don't have any idea what's the biggest value is so we'll go for the last value okay so this is this becomes your pivot that means we need multiple variables here now what variables we need so I will just write variables here so the first variable we need is a pivot variable so we'll say Pi okay and then uh you need few more variables you need a variable I for the positioning again we'll discuss what this positioning is uh then we'll need a j which will track which will go through each element and we have done that in the Sorting right so when when you jump from each value that will be done by J and then of course we also need array here so let's say this is a r r this is your array okay and let's have the index value so we say this is 0 1 2 3 4 5 those are the index values we have apart from this we also need a low and a high variable okay so we'll say l and H so let's say this is L and this is H now normally we can say h is the last value or we can say it's a length minus one so we can say that so we have a low and we have a high so low starts from the first and H is the last value now how do you perform the operation it's very simple first you find the pavit now we know that we are going for pivot which is two in this case so what you will do is let's take this two as the pivot so I will say this is p so this is referencing this is uh referring this to so Pi variable at this point is referring to so I will say this is two in this case and then we need two variables so let's take variable I now by default the value for I will be the lowest value minus one so let's say the I value is here at this point you know what I will do let me just remove this portion at this point because let's keep this state clean so we need a i variable and then we need a j variable able so J will be here to start with so I will be here at the minus one position J will be here at the zeroth position and then what you do is you basically run a loop where of course the I will also increment but the main Loop here we want is for J okay uh so we'll take a for Loop for J okay so let me write the code here so what we want is of course the rough code so I will say for J will be starting with low okay that's what we are doing here and then J should go till n but then we are not using n variable right we are using variable high so let's say J less than high and j++ now what you are going to do in this inside this Loop so basically you will first make sure that you get the PT value right so you will I mean of course you have a PT value here which is two and then you also got I I is still minus one now inside this Loop what you will do is you will check if the a r r which is in this case we have an array if a of J if it is less than the pivot so pivot we have a variable here if it is less than pivot you will perform some operation now if you compare the values here do you think the a r r of J which is five in this case uh is it less than the pivot because pivot value is two no it is not less than pivot so we'll not do anything but we have to find a value Which is less than two right so if the value of five is less than two you will perform some operation since it is not true we are not going to perform any operation here so basically you're going to shift your J here okay now while we are doing it of course we are running a loop right so J starts with low and then we have to increment so J goes there it will compare itself with the pivot is it small no so again you will shift your J then you compare 6 with two then is it smaller no then you shift your J here then you check is it smaller yes what if it is smaller then what you will do in this case if it is smaller you perform some operation first thing you do is you increment the value of I basically what you're doing is you are shifting your I here okay that's done next we have to make sure that you swap the value of I and J okay so whatever value you have with I and J you basically swap them so what I'm saying is take this value here move this value five here and move this one here okay now how do we do that of course we have used it before so we can use a temp variable or maybe at this point I will simply say Swap and then we'll write the logic later so I want to swap basically the value of a r r of I with a r r of J okay so we need to do the swapping that's it this are the thing we are doing inside the if condition now once that is done of course you have to move your J again because we are in a loop so J will go here now again you will compare if the four is less than two no and that's it J will move here because if it is not less then we not doing any operation then your J goes to the last value because your J ends at high right so J reaches here and of course the pi and J is same then you don't you don't have to I mean of course it is false the condition this condition will be false which is a r r of J is not less than P so in this case it will not swap but what happens after that even if you complete the entire Loop do you think two is at the right position no two should be here right so this three need to go there so what you do is you perform one more operation after the loop so after the loop you what you will do is you will basically swap the a RR of I + 1 with the a RR of high okay now this is the operation you have to perform now what will be happening here so what is the value of I value of I is z which is index you're picking the next value which is three so you have to swap this three with this two because that's what your ARR of high is so you will move here and you will move this side now by doing this we made sure that the pit value which which you choosed is at the right position can you confirm is it the right position yes it's at right position now what you do is you divide I mean if you if you observe the array if you look at the pi which is p here now if you see the left hand side of it this is always lower than two and this value is always greater than the two so yes two is the right position now what's the next step the next step is very simple you divide this array based on the P value so what you do is you create another array here and in this you'll be having only one value which is coming from here right in fact we can also draw an arrow there so this is coming here two will remain there itself we can write two here we don't have to work with two because it's already sorted and then you take this particular section into another array not another array but let's say logical partition we are doing here so we'll get another array here so we are doing divide and conquer so here you're going to have 6 5 4 3 three If You observe they're not sorted but at least we got the partition right now what you do is you again perform the same operation which we have done here in the first example now you help me should we start with this yes we can start but don't you think we only have one value and whenever you have one value it is already sorted let's work with this so what you do is you again take the same thing so you take the low you take the high and then you of course you again have this P all this values here so all these variables are still EX it because you are going to apply quick sort again on this particular values so let's get started let's take pivot which pivot we have choosing of course we are choosing always the last value so this is your Pi I pivit then you got I here you got J here then what you do is you start running your algorithm which is first you compare the value of J which is six in this case is six smaller than three look at the algorithm which we have done is six smaller then the pay it the answer is no so you will simply so you will simply move your J here again check is it uh small no shift is it small no is it then again goes here is it small no then what you do is you have not you have not done any swapping but at the end we got one more logic right so once you complete this for Loop you will do something with this which is swapping the I + one so I is at minus one so you have to basically swap the six with the array of high which is three so this goes here and this goes here now if you look at the pivit this is sorted right so now what you do is you write three here which is your PT value and then you divide your array into two parts but since the pivot was the first value what you will do is you will get the new array now from this which is 5 4 6 and then you start performing operation here now what op operation the same operation which we have done again you will apply quick sort so this is L this is H so Pi is referring six here and then you start so you got I here you got J then you start comparing is the first value the value of J is it smaller than the PT yes now when you say yes what you will simply do is you will increment the value of I first if you look at the code that's that's what the logic we have and then you swap the value of I and J a now in this case I and J are deferring to the same value so spping doesn't make sense of course they will get the same value then you increment the value of J J goes here check is 4 less than 6 yes in that case you will move I here and then you will swap the value of I and J again it remains same so nothing to do here then you shift your J here of course the array of J is not less than P because there they the same value then this Loops end the for Loop ends then you perform this operation which is a r r which is + one this will be replaced by high and that remains same right so there's no swapping I know it's all depend upon the value type of values you're getting so at this point there's no swapping happened so this remain as it is six but then you will get a new array here which only has five and four and then you start applying the same operation let's get started in fact I will just write this bit up so that I will have some space and this is coming from this particular section then what you do is you will take the same value you say and if You observe we doing recursion right the same steps we are repeating multiple times so LH we got Pi I here we got the variable I referring to minus one position or in fact notus one position it is one less than the low so in this case the low is this position right now what is this position this is in fact we should have maintained the index value right so this is zero this is 1 this is 2 3 4 5 then we got three here which is this one this is 3 4 5 what we got here is 3 4 so these are the index values for them okay so we got I referring to the index value two and J is here then what you do is you simply compare the same steps we have which we have done so the array of J is it less than four no so all this operation this spping is not needed you will simply move your J here again do we need to swap of course not because the array of J is not less than pivot so it will remain same but then you will perform the last operation which is this one what it says it says Swap this value with the high value so this will be swapped so five goes here this goes here and this goes here now if You observe we divided and we conquered so if you merge this in fact we're not merging physically we are merging logically right because nowhere we have we were breaking the array but if you see if you try to merge logically what you will get so you will get this one first which is one goes here then two goes here then by sequence three goes here then by sequence this 4 five goes here and then this six goes at the end so if I want to write this this will go here so let me write one then this goes here that's two then three goes here that's three then if you can see in the binary tree we always goes from the left to right so if you see the left because six is there on the right hand side you will say four and five and at the end you will get six now this is sorted so after all this explanation this is how basically you sort them now this logic which we have written here is actually a part of a partition method so this is a partition method so the entire thing goes there but we also need to return the pivot value right so which is the pivot value so we return I + 1 because that's what the pivit is but this particular function will be called by whom so we have a concept of quick sort here so quick sort is going to call this partition how that we're going to see in the code itself so you got the idea basically you divide sort each values and you will get the output now this will make much more sense when you start coding and I hope it will get clear so what I will do is I will just remove the entire part here we got this array and we are going to perform the operation now of course you can write the entire logic here but then remember quick sort goes for recursion So when you say recursion you have to create a function or a method which will get called so what I will do is I will create a function here and let's call them so we'll say a quick sort as a function name or the method name which will take three parameters now what are the three parameters the first one is the array itself on which you want to perform the operation next is the starting point and the ending point of each section example if you start it will be the entire array but remember when we have to break it down so that is your each section okay so we have to specify the low and then you have to specify the the high now in this case what is low so low is zero and the high is basically the array do length minus one right that's the value you have to send now basically we don't have this function so we can just right click here and say okay I want the IDE to create this method for me may just using some inbu methods okay let's create our own so what I will do here is I will create a method called public I don't want to get the object I will say static void quick sort and it will take this three values so first it will take a int array in fact one of the syntax of array you can write it on this side because it will make much more sense you got array and then you got int low then you got int high so these are the variables you need and then you can start perform the operation so basically from the main you're calling quick sort only once but quick sort will be calling itself okay but based on what now basically I want quick sort to call itself only till when your low is less than high we don't want it right so that's what it makes sense right low should be low high should be high and and if it is true then keep calling the quick sort so I will I will keep calling the quick sort but the question is what values I have to pass now think about this if you have one big array and then you are saying that we'll be breaking this into two parts so don't you think you have to call quick sort two times for two different arrays that's right so I have to call two times but the question is what are the values for sure the first variable will be array because that's what we are sending right we have to sort the array the question is what will be the low what will be the high because when you divide your array into two parts what should be the starting point of the second array and the ending point of the second array that's what you have to mention but how will you know the starting point it is easy actually here the starting is always low for the first array and the ending is always high for the second array okay even that is solved the problem is with the ending of the first array and the starting of the second array that's what we need to find now how do you find this for this we have to run a partition okay so this is the logic which we have to refer to so what I will do is I will just reduce the I size so that I can see those those values I mean this logic so this is what we have to implement in the partition so basically to get this value the pivot value what you will do is you will say int pi equal to and you will create a method called Partition in which you will pass three values the same three values array low and high so basically in the logic I have not mentioned it but we want this value as well okay so we need to create this method so what I will do is I will just go back here more actions create a method okay so we got the method let's perform operation on this method we can make it private because we're not going to use partition outside this class so private works but what should be the logic here and we have to return something remember we have to return the pi value okay so we can write the same logic which we have return here and once you get this Pi you can basically pass the pi and we don't want to include the pi so we can say Pi minus one and here we have to pass Pi + 1 because every partition when you create you don't consider the PI right Pi stays there you create two parts and then those are your or two partitions but we have to find this Pi that's the main task and for that we have to write this logic which is mentioned here so we need some variables the first one is temporary pivot variable and we have to assume pivot for the first time so the pivot here is always high so that's the algorithm we are using but we can pick up the starting value or randomly any pick any value that works so let's say we got pivot high and then we also need one more variable which is I remember we have to use this I which will return so I is basically your low minus one remember if the if the array starts with zero the I will be at minus one next we need a loop so we can get the entire loop from here or maybe we can type so we can say for INT J is equal to Zer in fact not zero right it should be always low because when you create different partitions not every partition will start with zero but they will start with low so J less than equal to high and j++ I'm just referring to my algorithm which I mention here and then the logic we have to write is if a r r of J if it is less than pivot then you start doing some operation what operation first you increment the value of I and then you swap but how will you swap we don't have a swap function actually we can create one but instead of that what we can also do is we can write the logic so I can say int temp is equal to AR r r of I then a r r of I will be replaced by a r r of J and then a RR of J will be replaced by the temp okay that's the values we have to swap and that's it this will run and you will do the partitioning part but once you complete the for loop again we have to swap the value of I + one with high so we can actually use the same logic here or same statements so I'm not copy pasting I'm just reusing the code sounds better right so here we can say this will be replaced by I + 1 and I +1 will replaced by high and this high is going to replace by temp so iing done and at the end we need to return I + 1 because that's what is referring to the pivot okay uh looks like a right logic we just converted that into here so by doing the partition we are saying replace one in fact once you get this algorithm also try the same thing which I've done on the board okay then it will make much more sense okay I hope this will work what do you think let's run and let's see run and yes looks like sorted 1 two 3 four five 68 let's change some values let's say this is 81 this is 62 and this is 1 one let's try with this values and let's see if they sorted so 2 3 4 5 62 81111 so it works so this this is your quick sort now why we are saying this is n log of n is because we only have one Loop here which is for Loop plus we are doing the partitions of it right so they can run parallely yeah so this is n log n but in the worst case it can go for n square but better than the other sorting techniques so yeah that's it from quick sort we have written the code in Java in this video we'll talk about merge sort now basically let's talk about the theory first and then we'll focus on the implementation now when we talk about sorting techniques we have worked with multiple sorting technique and when we talked about the quick sort we which was going for the time complexity of n log n now we have one more there which is called a merge sort which also has a Time complexity of n log n now both quick sort and merge sort follows a technique called divide and conquer so basically what you do is you break down the problem into sub problems and apply the algorithm on those particular sub problems and once you get the solution for each sub problem then you combine the solutions or subsolutions to get a Final Solution that's what we are going to do here which is divide and conquer okay so how we are going to do this now basically it is actually easier to understand so if you can be with me it will make much more sense so what we're going to do is we'll take a array initially okay so let's say I'm taking a list of values here so let's say we are going for six values here and what are these six values so let's say I have a value which is 8 5 9 1 6 7 let's say so we got this values here and and then I want to sort them so what you do is you you will apply a merge sort now basically here as I mentioned before you will do two things you will in fact three things first you will divide this problem into sub problems and then you will conquer them and then you will simply merge them now since it is called a merge sort the important step here is merging so when I say important I'm also I'm also saying it is complex part the easier part is to break down this into small parts merging will be timec consuming so let's understand this so when you have this values here what you will do is first of all you will break down into two parts now the question is how will you break it down in different sorting algorithm we have a different way of breaking the entire list in fact in quick sort we use a pivot but here let's make it very simple we use something called a median now what is a median or maybe a midpoint so here what we can do is as we know that in if you talk about this particular array here the mid is here right we can see and we can tell that but how and algorithm will know that this is a mid and that's why we will do some calculation now what kind of calculation it's very easy so what we can do is let's say this is your left and this is your right so what we will do is we'll simply use index values so this the index values for this is 0 1 2 3 4 5 so that depends upon the values you have and then if you want to find a median so basically L represents the first index value and R represents the last index value so you have to find the median and the formula for median is very simple so what you will simply do is you will say median is equal to left + right divide by two that's how you get the median right now in this case the median is what is l l is zero R is five and this ID by 2 is equal to 5 by 2 now since in different languages we get different outputs so let's say this is two in this case uh because in most of the languages we go for the floor value so we got two here now two is your median so this is your median so whatever is there on this side will go into a different array and whatever is there in this side will go into different array so when I say array I'm talking about the least so what we can do is we can divide into two parts and then we can create a different section so we got a section here which has three values we got a section here which get three values and then the values will be 8 5 9 here and 1 16 7 here okay and again the dop is not done again you have to divide into two parts now how we going to do that it's very simple the same steps which you have followed again you will take L and R here L and R here let's find the median of the first point here or the first array now how do you get the median again you will say m is equal to l + r / 2 so now we can do it quickly so what is l in this case so if you go with the index value index value is 0 1 2 in this case and 3 4 5 now if you talk about the first array the L is 0 R is 2 so you will say 0 + 2 is 2 and 2/ 2 is 1 so M for this is 1 so m is z now if you want to calculate for the next array or the next values so again the same value so what is l l is three R is five so 3 + 5 is 8 8 / 2 is 4 so four is here so median is here of course when you look at the values you will find the median just by looking at it but let's talk about the algorithm and we don't have a limited set of values what if you have 500 values you will not simply search for the median right so that's how we can get the median again you will divide into two parts so we can divide something like this you will get two sections here for this and two sections for this we can say the first section will have two values which is 8 and five the second section will have a value which is nine here the first section since we only have one value here nine we got nine but let's say here we got one and six and here we got seven so basically that's how you divide again the job is not done so you have to go till the end and so what you're going to do again you will divide the first one so can we divide the second one the nine we don't we don't need to divide this part right because when you get one value you can you cannot divide that so let's divide the first part here so if you divide this you will get again two values which is 8 and five and again you will divide this you will get two values which is one and six so that's how you can divide and at the end you will get the individual values now still we can persist the index value because we are not physically dividing them we are just virtually dividing it right so index value for this is 0 1 2 3 4 5 the index number remains same and if you compare with the actual list we got the index value and the values are same right so to this point we have not done any sorting part we just did The Divide part and now it's time for the conquer now when you say conquer it simply means that you need to sort this value so whatever value you got at the end sort them but if You observe they are already sorted because each element if you compare if you say eight this list is sorted when you have only one value It Is by default sorted okay so sorting is done so conquering is done basically the next step is actually is to merge them and the actual fund starts here now when you when you say merge what it means so basically what you do is you start with the first two values and then you merge them now merging is important so when you say we are merging 8 and five of course you will get a list and you can again say eight and five but no this is not how you will merge it so the way you will merge it is this so you will take these two values and merge them into another block you will get two values but when you are merging it you will compare these two values so which is less here so if five is less you will put five here and then you'll put eight here because that's the only remaining element then you you think about merging so you will you will merge this two now when you merging this two of course you will get three values right so you will take it take three values here and this is coming from here so this two values and this one value now how will you merge now since we have two different list or two different values here or two different AR we can say when you want to merge that's where the actual algorithm starts because when you when you're merging two values you can simply compare smaller or get greater but now we have three values in first we have two in second we have only one so what you do here is you basically compare these values before adding them so what should be the first value now we know that the previous array is sorted right and then in fact both the values are sorted both the arrays are sorted when you combine them what you can do is you can compare the first two values only the first two values not eight only five and nine so which is smaller five so you will put five here now since five is done you can simply say okay I'm done with five now let me focus on eight and N so which is smaller eight and then the only thing remaining here is nine so we will put nine here now that's done now let's combine this three which is 1 6 and 7 now first you have to com combine this two so you will get another box here which is 1 and six so we will compare so it is 1 and six because they are sorted so now we will combine the next part you will get three values here now when you get three values what we are doing is we are basically combining this section and this section same steps you will compare the first two values so one compared with seven so one will come here this is done then compare six and seven six will come here this is done then seven will come here okay and then now the major work starts we have to combine this two now when you're combining this two you will get a bigger array of six elements so 1 two 3 4 five six so we got six box now what you will do is you you have you got two arrays and we know that those two arrays are actually sorted when you combine them again you will start with the first two values so when I say first two values let's let's compare five 5 and one so what you will do is you will compare okay five and one which will come here so it is one so this is done then you compare six and five because five is still remaining right so five and six is five then 8 and six which is six so five done six done then eight and seven so which is seven so seven done then eight again now we don't have anything comp to compare from the next array so you can simply take these two values as it is here this is merge sort okay so you get the sorted value I hope yeah you got the sorted value so this is how basically the merge sort works that's how you basically divide and you combine but if you want to do this in programming how will you do it and we'll keep this as a reference so we can divide we can write the section here so we can compare with this now if you want to write an algorithm for this first of all uh you will get an array of course now in this array you will have some values and we can take the same values which we have here right so let's say we have an array which some values here the same values which we have and then the next step is you basically need to create a function let's say merge sort and this is where you will do this sorting part so when I say merge sort the first thing you will do is you will say divide now when you say divide you have to pass two three things first you have to pass the array then you have to pass the L value R value right and then if You observe we are dividing again you're dividing again you're dividing so don't you think this is a concept of recursion when you do do the same thing multiple times so we have to do recursion here so basically here we have to pass three values right so you will pass an array you will pass the left value and right value for each array now as this will be called multiple times in recursion every time you have to pass the array the left and the right remember one thing we are not dividing the array physically we are dividing it logically so even if you divide this array ultimately the values will remain same okay now when I say divide what it means the first thing you will do is you have to find find the median or the mid value so I can say mid but then since this okay so let's find mid here so we got mid is equal to we know the formula r l + r / 2 now once we got the median what we're going to do is once you got the median you will break down into two parts and you will apply the merge sort in each section so what I'm saying is when I'm pass when I'm calling this for the first time I'm passing the entire array with the L value as zero and R value as five which is the last index but again I'm going to call the merge sort by passing different values so I'm going to pass AR RR next I need to pass the first array uh index value so the first array here starts from 0 to two which is the median so starting is L ending is median or M middle value or mid value we can say again I will call merge sort for this second array again I have to pass ARR but this time you have to pass if you look at the values we have to pass three three and five now where do we have three we don't have three anywhere so we can say mid + 1 so mid is two so mid + 1 is three and the ending is right okay so that's how you call the merge sort we have to remember one one more thing after doing merge sort which will break it we have to merge them as well so when you say merge you have to pass four things here first the are the left value the mid value and you have to also pass the right value again we'll see the logic later but this is the merge you have to pass but if you call the function by itself you can you can see merge is calling itself but don't you think there should be a limit when it should end so of course there should be a condition as well when your left is less than right then only you do this otherwise stop okay this is your merge sort so by doing this what you will get is you will get the values divided but where is the concept of merge we are calling merge but we have not defined the merge function yet now this is where things gets complicated not exactly comp but it's a lengthy process so what we need to do is when you say merge of course you have to pass all these values here now in this merge what we are going to do now basically the first thing here is you need to create two arrays I will not write the logic exact logic here but let me just draw something what we need is we we basically need two arrays here when you say merge at one time you need two arrays example so when we are combining this two we got one array so at one point you need two arrays to combine so that you will get one big array same goes here when you got two arrays here here we need to combine them to get a big array so that means every time I call merge I need two arrays we'll call them let's say left array and right array okay so we got two arrays here the next thing we need to do is we need to copy the elements of the left array and the right array this is empty at this point so we need to copy these values from the actual array okay now so we need to write a for Loop which will copy data from the array so basically it will copy data from the array and put them in this list okay so maybe I just I will just write copy values again we'll see the actual logic in the code itself okay next thing we have to do is once we have done with the copying part you will simply use these two arrays to combine to get a bigger array now how will you do this so of course there should be partition here there should be some values so what we will do is let's compare let's work with the last values here so we got the last value as 5 8 9 and 1 6 7 so the logic of combining this is you will need multiple variables here you need a variable I you need a variable J now why we need this two variables one to represents this particular array and one to represent this particular array to it trate then we also need a k which will use which will be used for the big array which you're going to create so out of from these three values or three three values you're going to create an array of six right so K will be handling this part now every time you copy one element so let's say when you compare five and one and you know that you're going to copy one here so basically the J value will shift here right because this is done the same thing goes here so once you got one next time you will get five here then you have to increment this here so I goes here and of course every time you copy element in the bigger array you will increment the value of K that's a logic okay so this is how you are going to complete the merge sort now how exactly you have to write thee code that we'll see in the Practical video so I hope merge sort makes sense where you basically break down the entire array into small chunks and then you combine them to get the sorted values so now let's implement this logic with the help of java now the thing is first we need a array right so let's create an array here so I will say int a RR and this will have certain values so let's have some values here we'll say 3 5 1 4 6 2 so we got this values here and and let's apply the Sorting techniques on this so before sorting I will print some values I'll say for in n in Array and let's print this values so I will say print n but I will also make sure that I will put a space I will not print on new line and once it is done I'll print on print a new line and then after sorting also so I will set this I will just write it here after sorting so here let's let's do the same thing and let's say after sorting it should print some value but at this point if you run this code let's run this and you can see in the output they both are unsorted so because that's why we have to do some sorting here right so let's apply the Sorting logic so what I will do is I will simply call a merge sort method which will basically accept three values the ARR the L now L here is zero and then you have to also pass the array do length minus one basically you have to pass the R value as well remember we have to pass three variables now since we don't have this method I will simply say more action create this method and you can see we got this method here and let me just put this method not here but on top now this is where the actual logic is going to happen so you can see we got two variables this should be L and this should be R so left and right okay now as for the logic if you can see in our logic we have already mentioned this logic so basically what we have to do is we have to first check if the L value is less than R then only you do certain things and what are things you have to do basically you have to find the middle value so I will say in mid is equal to l + r / 2 and then you have to call M sort two times again I'm just going with the logic which I written in the code or in the board here so you have to pass ARR and then you have to pass the L and then you have to pass mid that's how you create two different arrays so mid + one and R okay and then you will simply say merge of course right after doing the Sorting after breaking it down you have to also merge but while doing merge you have to pass three values ARR uh you have to pass the left mid and right you have to pass the three values so this is the only logic you have to write inside merge sort method but then we have to also complete merging because dividing is very easy this is how basically you are dividing the values the difficult part is merging them so let's Implement merge here so I will just go back here more actions uh create a method merge yes so I got a method at this point there are private method is because I'm going to call from the same class but depending upon your requirement you can just change them and now the actual logic goes here the merge okay now as I mentioned you need to create two arrays here right so if you can see the logic we need two arrays let's name this as lrr which is the left array and this will be an array but the question is what will be size of it because when I create this areay I have to mention the size I don't know what is the size here now based on when it is getting called it will be different size but the question is how we are going to know the size and that's why this l m all this thing comes or l r comes into picture so let's use that and let's get the size so if you want the size of the first array the first section basically you can simply say mid minus L because for the first array it starts with L if you can see here it starts with L and ends with mid so if you say mid minus L you will get the length right but the problem is since this is zero indexing we have to also add plus one because mid is not representing the size of the array it represents the index value so you have to say plus one then you will get the second AR length with the help of R minus met so we just put some space here so that it will be much more visible okay so you can see we got this two values and this is the size you have to mention here the first array will be of size N1 the second array will be of size N2 that's done the next step is actually to copy the values if you can see we are mentioning the copy values here right in the in the notes now how do you copy value we can use a for Loop and let's use two different variables I will say X and Y this time x is equal to zero and depend on the size of the array so for the first array the size is N1 and x++ not used to using X and Y inside a for Loop but let's try so how do you copy so a r r this values which is X now how will you get the values so from a r r from the main array we have to start from the left so you have to say left plus X that's how you get the values so whatever value of the L is example if you look at here uh for the first array the index is 012 but let's say if you're merging the second array this one the index value is 3 4 5 right so whatever value of L is which is the left which is three in this case it is 3 + x that's how you will copy and thenone so this is for the first one let's do the same thing but your different Valu so I will just copy this for the second array okay we can also use x here no problem we can say N2 and this will go into the right array but the question is what will be the value here now any guess so when you say on the right hand side it is your mid + 1 because we are not considering the mid value for the next example if if you go up the mid here was two but we started with three so you have to say 2 + 1 mid + 1 so that you will get three okay so we copied what the next step and now the actual work starts of merging and already mentioned we need two variables one is I equal to zero uh we also need J for the second array so first array will be counted with I and second array will be handling will be handled by J but we also need one more counter which will represents the main array right and this value will start with L because you have to start from the left hand side now once we get these three values let's start merging them so we have to do multiple times right when you say merge you have to take value from here example when we were doing this we would compare the first two values compare the next two values that's how we were doing right so when to end this if your I value is less than N1 and not this and and J value is less than N2 we'll we'll continue till this point if they are not true then we'll have to stop because that means we have to we have actually reach reach the end but now question arise how will you merge and that's where you have to start comparing values now when you say compare what it means compare five and 1 so basically the first element of this array and the first element of this array let's compare them how will you do that so let simply check if the L array of I because that's what is representing the L array which is the I variable if it is less than and we can also say equal to what if they're equal then we have to compare this with the r array of J if the left one is smaller in this case the R1 is smaller not the left one but let's say if the left left one is smaller in that case you will put that into the main array so array K is equal to l array not length L array of I now since we have used so let's say this was a smaller value and once we have used this we have to cancel this right I mean this is done so we can shift our pointer to the next next element how do you shift your not the pointer but the reference you will simply say I plus plus here in this case but what if it is not same or not is what if it is not true in that case you will go to else part you will do the same thing but not with the left array you will this time you will do with the right array and then the J variable and you will say j++ and every time you run this Loop because see after one of this Loop basically you will get the first value of the array right main array you will simply say k++ because you have to also increment this so once I is done because K is here once I is done you have to move K here okay and that's why you're doing k++ and that's it this is your merge sort let's see if that works let's refresh this or this rerun and we got an error something went wrong you can see everything was going well but this four is not at the right place we got one there because sometime what may happen is when you copying two arrays what if the values are left in one of the array example if you look at our example when we were copying this remember when when we were completing the entire task these two element were remaining from the first array which goes at the end so that thing is not covered yet so what you do is for the remaining elements of the particular array you will again run a while loop here so you will say if I is still not equal or still not less than N1 you will simply copy the remaining elements whatever is left because after this loop at least one array will be ended okay so we have to work for the second of the remaining element of one of the AR maybe left hand side or right hand side first we're trying to understand left hand side let's see what happens on the left hand side simply copy all the values so you will say AR of K is equal to we have to copy from the left array and let's use I here now every time you do this you you will increment both the elements I and K both so this is for the left hand side left out left out values the same thing should be done for the right hand side so this time I will say J is less than N2 in that case you will copy but not from the right left hand side you will do it from the right hand side the variable is J and the increment you'll do for j++ okay and let's run this and you can see now it is sorted and now it doesn't matter what values you have let's say let's take the values which we have returned on the board which was 8 what was the value 85 91 6 7 and if you run this you can see we got sorted values let's add some more values here just to remove the confusion with different values let's say 111 this is 57 and now let's see 6 7 8 9 57 75111 so this is your merge sort so the steps basically you have to first do the breakdown of you have to break the array down into small chunks and then you have to also merge them the only thing you have to remember is when we were drawing this we were going in two sections right something like this we were saying okay we will create two different section and then first section will break into two parts and second section will break into two parts no that's not how it is working If You observe what it will will do is it will break down the entire section into two parts yes but then first only you will get the first part then you you're not going to the second part okay you're not looking at here you this is not there yet you're still into the first part then this will divide into a section you will get this 85 then you're dividing into two sections which you will get 85 and then you will merge them then you will start break breaking down the second part which is nine okay nine was still not there then once this is also merge once you get this it will start working on the next part then it will work on this it will work on this this merge and merge I mean sorry break down then you get seven then you merge this two and then once you have merged then it will go for the next tool so it's not exactly breaking down the entire section equally it's basically going from left to right so yeah that's how things are working out and this is your merge sort with the help of java code and I hope this makes sense let me know in the comment section and this video we'll talk about link list in the last video we have talked about arrays and what are the drawbacks in Array now one of the drawback which we have seen is once you define the size of an array you cannot expand it or you can you cannot even shrink it but in case of Link list we can do that now in link list what we can do is we can create a collection of elements and every element will be linked with each other okay so let's let's make it simple now so what I will do is let's take an example here I will take four values let's say I want I want to take values like 12 the next value is let's say six and then we have 8 and then we have three so I want to store this four values so I want to say 12 6 8 and 3 I want to store it as a collection not individual because if you want to work with individual values you could have created three four variables and you can assign those values but if you want to keep it as one collection in normal way we can create an array but the only problem is you cannot expand it so in link list what we do is we use a concept of a data and a reference now what it means now first of all to store these values I will not go for any any continuous memory what I will do is I I will create this four four boxes so the first box is will have a value 12 the second box maybe anywhere so you have a sequential memory right you can have your data anywhere but just to make it simple you know just to represent in a format I'm doing in s way so we have one more value here which is six and then let me just draw one more here which is eight and the last one which is three so we have we have these four values we have 12 6 8 and three now what I want to do is I want to say this is a collection but then it is possible that they are not in a continuous location there might be some elements in between so let's say we have 12 here after that we have some element here maybe a b uh then you'll be having some some more more than maybe five to six elements in between maybe 15 20 elements in between so they're not continuous right so when I say I have these elements they're not in sequence example if I want to say hey I want to fetch the third value how can you mention third value because you you don't have any sequence if you want to make them in sequence what you have to do is first of all you have to make the first element as a head so you have to make this as a head so once you have made this head that means this is a first element so that is simple but how about the second element how do how do you link the first one and the second one now to make it work we will call each element here as nodes so the elements which we are using here are node so this is a node this is also a node the eight is also a node and three is also a node and of course all these are elements so node value is 12 node value is six node value is 8 and node value is three you can call them as value you can call them as info now how do you link this 12 and six the way you link is by creating one more memory here or one more box now this node will have two things the first one is the info so this 12 here is info and the next one will be the address of the next node now every node will have an address of course right so let's say the address for this node is 512 that's the address for this node the address for this node is let's say 326 the address for this node is let's say one1 and the address for this node is let's say 202 so we have all this address here now in this box this will have the address of the next node so in our example six is our next node right if you want to have eight as a next node you can write the address of eight here but in this case six is our next not as you can see the sequence here I want to maintain the sequence you can say 3 2 6 so this is the address of the next node that means we have a line between this so we have a line between the first node and the second node so this node one this is node two node three and node four now as you guessed it right in six you'll be having the address of three address of 8 which is 101 so this is 101 here and this one will have 2 02 so we have a reference so this is a link and even this is a link and that's called quite simple right but the problem is what about the last element now of course we don't have any element after that even that even there we'll be having an address but then address of what so it will be null now since we don't have anything after that it is null so we have the first node here which is 12 this is the first node second node third node and fourth node and fourth node will be null because we don't have anything after that this is how we create a link list so we have a list of values and they all are linked and that's why they say linked because they all are linked and the least because they this it's a least so once we have all these values assigned this is a Leist now in if you remember in the start of the session we we said this is expandable so when I say it is expandable how do I start the first one I mean how do I add the element anywhere so maybe I will start by adding the element at the end maybe I want to add the element here after three so let's say in the list we have one more value here let's say seven and how do we add seven at the end here so what you can do is as this this very simple step just create a node here whatever node you want and the the value for this node will be seven so this is the value right what about the address now this is as this is the last one you can simply put here null so you can say this is null because this is the last one but then we have mentioned three as null right but then now three is not the last element the last element is seven so after three also we have seven and the Seven will also have an address uh let's say the address for this one is uh 1 2 six this is the address if you want to link this you have to mention after three we have seven so what you do is you have to change this value so now you cannot have null here now you have to make it 1 2 6 after three we have seven right so I have to mention the address here and then we can we can give an arrow so this is the seven is the last element here after three we have seven that's how you can simply add the value it's that simple uh can we add the value at this start yeah it's quite possible uh the only thing you have to do is again create a node so we got a next node here and let's say the value for so after before 12 as well I want to assign a value like five I want to have a value five here so what you can do is you can make the value five here and how do I refer so now there there's one more change you cannot refer the 12 as the head element now so 12 is no more the head element now the head element is five and of course this will have an address so let's say five is at address uh 306 that's the address now what you will do is in five after five the element is 12 right so we have to mention the address of 12 here which is 1 512 so five went so after five we have 12 so that means we have an arrow so five is the first element now because that is head and then after that we have 12 after that we have six after that we have eight so that's how we can add the value at the start now can we add at the the value at in the somewhere in middle and the answer is yes it's quite possible what you can do is you can create one more box here let me make a box and that box will have a value so what I want to add so between 6 and 8 I want to add let's say nine so I want to add nine between 6 and 8 so you can create a nine you can have a nine value here and then it will have its own address let's say 56 I hope that add not C here so we have 506 here and know if you can observe I'm giving random values or random addresses because all these values will be stored somewhere else you you don't even know right they're not in sequence I mean you will know about the address but then they're not in sequence so if you don't have this links it will you cannot fetch them in sequence okay so now in nine so we have to mention nine comes before 8 so nine will have an address of8 which is 1 0 1 so now line is linking to 8 that means we have to remove I mean we have of course remove this link but then if you remove this link what should I put here so six so inside six will be not so the address will not be of eight now it will be of of nine so we have to say 56 and we have to give an arrow so of course we are not using this Arrow anymore so after six we have nine after 9 we have eight so that's how you can add values in between so it's that comfortable because we don't we are not consuming data in a continuous location so we can create as many notes as possible provided you have enough memory in your system it will create number of noes and all these notes will be connected with a link list now this typ of Link list which we have created here is called as a singly link list because it is single link list uh that means we we also have a dou link list or double link list yes we also have a double link list we'll see that in the in the in the one of the videos in future but now this is a single link list so this is better than arrays right so before we have talked about arrays and now we are talking about link list so now you tell me which is better is it array or link list now of of course both have their advantage and drawback but what is the advantage so the advantage of using link list is it is expandable you can increase the size of the list you can reduce the size of the list right so you can say the advantage here is expandable but the problem in link list is it is slow so when I say drawbacks uh it is slow in in when when you compare with array because in Array it works with index numbers now since everything is stored in a sequence it works with index numbers and you can fetch the value randomly so the benefit of array is you can fetch the value randomly right so that's the positivity of it so let's say this is Arrow positive value and the so linklist drawback is it's slow we have to also mention the drawback of added right in fact we have talked about in the in the previous video it's not expandable so yes link is slow because if you want to fetch a particular value let's say if you want to fetch eight you cannot directly go to eight you have to go from five so first you have to go to uh five then you can so you can go first you have to go to five then you have to go to 12 so they have to you have to follow that sequence and then you can reach to eight in fact we also have a concept of big Big O notation again we have not discussed that yet so we'll say Big O notation would be uh big big o n so if you want to search for the value you have to say Big O N again we'll talk about it later remember that link list to for search it uses big o n so it is timeconsuming compared to link compared to AR in in terms of searching but in but if you want to fetch if you want to insert value in between link this is the best one now this can be implemented using any language which you like you can implement this with C you can Implement that with C++ you can Implement with Java or maybe python in this video we'll see the implementation of Link list in the earlier videos we have talked about why do we need link list and what is link list so let's try to implement that with the help of java language and you can Implement that concept with any language which you love in this video we'll focus on Java we have two SE on this screen we have on the left hand side we have Eclipse IDE again you can use any ID which you prefer you can use intellig you can use net beans I'm I will be using Eclipse here on the right hand side I have a paint so that if if I want to show you anything any diagrammatical representation of that whatever we are doing you can see on the right hand side so what exactly we need so just to make a quick recap what we have learned till now is when you talk about link list we have representation like this we have noes now these are our nodes right so let's create a first node here so this is our first node and let's say I want to store values like 5 uh 12 6 9 I don't know why I love these numbers and let's say we have eight so I want to store these five values that's it nothing fancy just five values in a link list so in link list what we do is we create individual nodes so all these things are called as nodes right so this is a node and then we'll create another node so this node will have a value which is five and then we'll be having another node here which is let's say value 12 and this this node will have some address and we'll be having one more node here let's say six so this is six uh we have one more node here which is nine again I'm doing it purposefully creating the objects anywhere and then let's say we have eight here so we have all these nodes here so this node which is of five will will be linked with 12 we we have to find a way to link this two nodes and then we have to find a way to link this two nodes and then and this Noe and this Noe this is what we are going to do so once we can link this node in future if you want to add some new elements you can do that very easy easily every node will have two things a value so this is your value and this is your address now this is an address of the next node now in C programming we can use pointers but in Java what we do is we create a reference of the next object Java is all about objects right so of course this node is also object so this is the first object so you can say this is the first object this is the second object so the first object will have a reference of the second object the second object will have a reference of the third object now again we don't number them but then every object will have a reference of some other object the last object here will have nothing it will have null right so we don't have any other object after that so we'll be having null maybe after some time we'll add one more node the reference of that node will be assigned here so let's try to implement this so what are things we need here so let's see what are things we need in Java Java perspective so of course we need we need to create objects right so before getting the object we need to we need to use a class so the first class we need is a node class because a node class will have two things a node class will have a data and a node class will have the next node so data will be of type int again you can have any data you want you can have a string data you can have any object maybe alien object maybe accounts object maybe a laptop object your your wish and then the next node will be of type node itself because this will refer to the next node a node class so this is a class which has two things we have a data and a node then what other class we need we need a link list class right because link list class will have certain features because when you talk about link list it has certain methods example we are going to look at insert so we look at insert now insert will add data at the end so let's say if I specify data as five it will add that at the end of the at the list what if you want to add in between so you will say insert and you will say insert at I want to specify the position let's say I want to specify position three and or the index the value three and the value is let's say 12 so I want to add 12 at the location three uh maybe I want to add element at the end so I will say insert or maybe at the start we already done with the Ed end right so we'll say insert start so I want to insert at start so you can say I want to insert uh the start which is 18 so it will add at the start so this will add at the end this will add at in between and this will at the start you maybe want to delete the data as well so you can also use a delete method and delete you have to specify the index let's specify the index as two so it will delete the element at index value to these are the opertions I want to perform uh in my class and then to run this of course we need a class which has a main method so we'll have a main method in which you will be doing all these operations so you'll be having a main and then a main will have all the execution it will have a link list object and then using that link list object we can perform all these operations and then oh we also want a show method right so show method will display all the elements so if you want to display all the elements you can do that so this is where this is what you'll be doing here so in total we need three classes here so this is the first class we want to work with the second class we want to work with and the third class so let's create these three classes in our Java code so let's do that so I will say right click and let me create a Java class here I will say this class name as node because the first thing which we are going to do is node now this node will have two things as we have discussed the first thing it will have is the index value I guess the font is not visible let me just do that so now I would say this node will have the first thing which is the uh int data and as I mentioned you can use any data you want you can go for in float uh double alien type data any any complex type if you want and the next thing is the node itself so the node object which is next so this node is a reference so this next is a reference for the next node quite simple right so we have public class node and we have these two things nothing fancy here we got just two things you can make it more efficient you can write you can make it this private private Ables and you can use geta sets but then just to keep it simple I'm doing a I'm doing this code the next thing we need is uh a class which is called as link list but what if okay let's create a main class first I will say the main class and the main class name will be rner again you can have any name doesn't matter we have Runner class which has a main method now what if or maybe I don't want to create my own list I want to use the inbu feature so in fact in collection API you do have a link list as a class so you can say link list I will say list equal to uh New Link list in fact you can use the internal one as well or you can simply use this class and you can say least dot we have a add method so using add you can uh specify Which object you want to add maybe I want to say I want to add five so this is same as the thing which we are going to do we are going to use insert yeah and then we'll be having list. add you can specify the index value where you want to add let's say I want to add the index at four and you can add the element as let's say 12 so the same thing which we are doing here maybe index value three which we're talking about and then you can also delete element so you can say least. delete okay we have remove so we have remove we can specify the index value the method which I'm going to use is delete and then do we have a show method we don't have a show method here but we have size okay we have we are missing size there we'll be doing that later and okay we don't have the show method here but then we have iterator using which you can fetch all the values in fact you can print the entire list list as it is that will work this is how you work with list but then I don't want to use the internal implementation I want to go for my own implementation so of course we need a class so I would say the class name is link list itself again don't get confused with the name which we are using and which is provided by Java I'm going for the same name but since they're different package uh we can have our own class names now this class need to have certain methods right even before creating a method here what I'm going to do is every list will have one thing and that one thing is uh okay so how do you know that this is a first node now if you remember we use a concept of a head node so the first node will be referred as head node and where do we Define it so in the list itself I can say I have a node which is which I will call as head node so this will refer to the first node okay that's it so we got that node there let's implement the functions first of all this code is difficult to understand in the first go what I would say is watch the entire video and and then uh try it by yourself so maybe you'll be watching this video two to three times so make sure that you also practice this that's where you will get this concept okay so let's let's start with the first method so the first method we want to go for is insert so let's do that so I would say public void insert that's the first me I want to go for and this will accept a integer value I would say integer data itself so this is what I'm I'm expecting from the user now this data I want to assign to a node so whenever you call a insert what we have to do is we have to First create a node so what I will do is I will just clear this up so let's use this area here on this side so what we are going to do is every time you say insert you will be creating a new node so let's get a node here and this node will have a value which is which is whatever value you're passing so what we are going to do here is let's create a new node and then the way you create a new node is by saying node and let's name that node as node itself and we'll say new node this is how you create object right so so we got a node there the moment you say node node equal to new node this is what you will be getting in your memory the next thing we have to mention is two values of it so will say node. data the data which is coming from the user so whatever user is passing let's say if a user pass Five the node will get the value five just to make it more realistic what I will do is I will also create the object of list uh the link list here in the main so I would say link list uh link list I would name this as list itself equal to New Link list and in this link list I I have only one method right which is which is insert this insert will take a value let's say let's say I'm passing five so this method will call five will it will pass Five and that five will be assigned to a node which means this node here it will be having a value which is five that's simple right and by default the value of this one will be null so we got our first node but then it is possible that this is our first node because what we are expecting is when you say insert it will add the data at the end so if you already have a list with you it will simply add data at the end but what if you don't have a data itself I mean you don't have a list itself this is your first node in that scenario you have to check because if if if this is your first node then the head would head would be null right because by default the value for this head is null so if your if it is your first object this is the first object we are inserting so head is null so we'll verify if the head is equal to equal to null in this case I would say the node itself is a head so we'll say head equal to node so the first node itself is a header but what if that that is not a scenario what if you do this is not your first node we already have some nodes there in that case you will go for the else part so the first case we are checking is what if your head is null so then when you say head is null it means you don't have any nodes in the list so whatever node you are adding is a first node in that case we got the node by default the next value is null in fact you can if you want to make it more readable you can you can assign that to null even even if it don't do that that's fine because by default the value for the object is null but then this looks more readable right so you can do that so if it is a first object that's become your head but what if this is not the first object in that case you will create a node and you will make it as head okay now why I'm doing this it's because let's imagine you already have a list so let's say if you have multiple nodes here uh we got we got six and in fact let's go back to the original uh original diagram now you can see if I'm adding a node in between or somewhere here so let's say I'm adding a new node which is which is let's say okay the the value which I'm passing here is not let's say not five it is it is let's say 18 I'm passing 18 now so we got a new node and of course this is not the first node which which we are adding so head is pointing to five so in this case what it will do is it will create it will assign the value here which is 18 right we got 18 value here but then this is getting added at the end right but that means after eight what we have to do is we have to first check which is the last element how do I know which is the last element and that's where you have to start with the first location so from the first location you will you will travel from first location to the last location now that is tricky right how do we travel is it that easy um no it's not that easy but just try to understand so from the first one we'll go to head first and using head we'll jump to the next node so from the second node you will jump to the third node from the second third node you can jump to the fourth node and then fifth node and then but how do we stop where do we stop so we have to stop the moment you get null as the next value okay now this is this looks simple so to Traverse we have to use you have to use a node right a temporary node which will hold the data and that is let's say n here so we'll say while n do next since we have to Traverse between different nodes so we'll use a while loop so we will travel till you got a null value the moment you get a null value the value will stop so how do we travel so what we are doing is we are saying n. next equal to null so we have a temporary we have a temporary node here let's let's imagine I'm doing that node I'm creating that node here this is temporary node and I will call this node as n now this node will first refer to the Head node so it will refer to the Head node and then head node will check do we have a null value here no we don't have a null value we have the address of the second uh node in this case a reference of second node so it is not null okay so then we have to jump from here to here now how do we jump so to jump what we will do is we will change earlier this was referring to this node right now we have to refer to this node now how will you get this node it's very easy you will say n is equal to n. nextt so now you are jumping between nodes so if it is not null let's jump to Second node if this is not null let's jump to third node and using Y lo you can do that now this will stop the moment to get null at the end now once you got the null what you will do is once you got this null here you have to change this value you have to change from null here so you this is no not null anymore so this will refer to the new node which we have created now how will you do that so to do that we have to say n. next is equal to the new node which you have created that means the value of this node because the current n value is referring to the this this node right again this is the tricky part in in Java you have to you have to work with objects so imagine when the loop gets over so at this location when the loop gets over you are here at this node yeah you have you here this node now you have what you do is you have to just change this null to the next node whichever you have so the next this is a new node right so this is a node in in our case so the value of node will be assigned to the current node do next which is this value so this will be replaced by the node reference so you don't have a null anymore and this is null by default now if you can see the code here we have a null value here right okay this looks cool now this is how you insert value can be verify now even if you can verify we don't have a way to print all the values right so I will I will insert the data and I I will also try to print it now how do we print it we can use a show method to print all the values so I will say public void show to print all the values and how do I print the values so we will use some methods to we will use some statements to print here now how do we print the values so same steps you have to travel from between all these nodes now how will you travel between all these nodes is you have to say node n again you can say node uh node node equal to head so initially you have to start with head and then we'll be using a while loop we have to travel right so when you want to travel you will use a while loop so you will say n do uh node. next is not equal to null this is how you travel and then so while traveling you will print the data of the node so you will say system.out.print and you will print the data of the node so you will say node. data that's it this is what you are going to do and every time you print it you just have to shift to the next node and the way you can shift to next node is by saying node equal to node. next this is how you shift now see this Loop the same Loop so same file Loop the only thing is which the only thing which you're doing here is we are printing it that's it okay I hope this will work but let's try so what I will do is I will insert not one value I will insert three to four values so I will say least do insert and I will insert 45 as well and I will say least do insert I would say 12 okay let's add three values and at the end I will say least. show I hope this will work now so let's run this code right click and say run as Java application and we got oh we got the output but with one mistake you are getting 18 and 45 that's perfect we are not getting 12 so what's wrong is it not getting added or is it not getting printed uh I think it's not getting printed it's because you are are traversing till null right the moment you get null you are stopping it in this case we only have three nodes so in this case we only have three nodes let me just draw that here so we got the first node as uh 18 the second node as 45 and the third node as 12 so you got this three nodes right so this note is referring to this note that means this is not null value so this is not null even this is not null but this okay this is referring to this object right so this is null so this here is null so it will stop as soon as you get null oh okay that's weird that means we are not printing this one but we are reaching to this point right so when you say it will print data it will not print data which has a object which is null in that case let's let's do it manually so I say system do print in and here I will say no dot node. data so for the last element you have to PR Print It Outside The Loop because it will not getting printed in the loop itself now let's run the loop run the code and you can see we got those three beautiful values so just just to make a quick recap what we have done done we have created two methods here one is insert and one is show in insert what we are doing is we are creating a node because that's what we do every time you say insert it will create a new node and that node will have a value which is so whatever data you are passing will be assigned to that node now if you want me to go for a quick run through of this uh we can use a debugger so what we will do is we'll use a debugger here and let's apply a break point this is where I want to apply a break and then I will run this in debug mode I will say run as okay where's the debug mode it's here and let's jump to the locations so we'll say F5 and F5 will take to the next thing so what we are doing is the moment you got a link list uh so I will just draw it here so the moment you got a link list it will create the first element So when you say insert so insert what is it is doing is it is saying it will create a new node for you so here it will create a new node okay we got the node there and then we are saying uh okay it will go to note class it will take those two values and then it will assign the data so data is 18 can you see that it's 18 and we got 18 yeah and the ID for this is 22 so let me write 22 somewhere so we got 22 so the value is 18 and the value ID is 22 and then it is saying null so the next one is null here and then uh it is saying if it is null uh is the head element null yes by default is null so head is null here right Head is by default null in this case this becomes your head so head is head will point to this location now and then it will go it will not go to L spot because if got executed it will jump back to the second value which is 45 so in this case it will try to insert 45 so the same step it will get a node for you if I jump into this uh you can see it is getting a new node and with those two beautiful values which is data and next it is assign data which is 45 so we got 45 here and then the next value is so this is null now when you say null it will jump to the next location is it is it head null no head is not null right because head is point inting to the first node here so if will not get executed it will execute the else part and that's that's working now it will drive us between the elements right so first it will jump to head and check if so it will Traverse the first element itself is null so it will directly jump to the location here and you will say the N the this this dot next so this value will be replaced by the reference of the next element which is 20 uh okay what is the ID for this the ID for this this not is 23 so this will refer 23 now and then it will jump back to the insert the third block and will we have a we got the object here with the value 12 the same steps will happen now it will again go back it will create the object assign the data 12 and then this will be null so the text will be null here and then it will jump to next it will jump to head is it so head is null no it is pointing to the 18th location so it will not execute the if if block it will execute the else Block in else block it will Traverse from the head block to the end block uh so is is the first block is null you can say uh no it's not null so it will execute it will say jump to the next location so now n is referring here now is it null yes it is null you can see that is null so the moment you get null it will execute it will say the N do next next is this one so this will be replaced by the ID 24 so this the ID for this object is 24 this will 24 here and then you got a link it's that simple the end of the code and then when the moment you say show what we are doing in show is we are jumping from one location another location so while so it will start with the head location and it will check is it null no it's not null so let's print the value so it will print the value of it which is uh which is 18 so we got 18 there you can see the output console window here we got 18 and then when you say next uh you can see it is printing the next node now so it is referring to the node 23 is it yeah so now 23 and then it will print the value data of that which is 45 and now it so the moment I go back you can see the node ID is 24 now it is referring to 24 and it will print the data which is 12 so this is the beauty of Link list now you can add values anywhere again this is a lengthy video so what I will do is the remaining part we'll see in the next video where we'll talk about the other methods which we have discussed we'll talk talk about insert at insert uh at start delete and show so the next one will faster because we have seen the difficult part so I hope you understood something about link list again you may want to rewatch this video again so let me know in the comment section if you it was helpful so now let's see how do we add element at the start so we have seen how to insert the element at the end now we'll see how to add the element at the start so what we're going to do here is let's create another method and we'll name this method as public uh void insert insert and then we'll say insert at start okay so we just have to pass a value there so I would say the value would be in data that's the value we we are going to pass now let's try to add the value now how do we add the value so if you think about this same thing which we have drawn before let me just take it take you there now if you remember this image now I want to add a element at the start so I would say a new element and this element will go at the start so let's say the element is maybe 25 so I want to add 25 and this will go at the start now now when you say start it simply means that you just need to change your head location from the current current object to a new object so this is the uh new head location and the value or the address for this one would be the earlier first element which is 18 so the ID is 22 so I want this 22 to be here so that it will refer to this element now so now the new element is at the start so the head will become the new element and it will have the address of the previous first element so let's see how do we Implement that so same steps we have to get a node so I can you know I can simply copy paste the code now uh what I can do is I can say okay the same thing will this this thing will remain same so I will copy and paste it here again we cannot say copy paste I can say code reuse so I would say paste here and once I got the value the only thing you have to do now is the node so we have to say head node is equal to node the current node okay so when you say uh when you say you have to say head equal to node so the the current node will become the head but even before doing that I just need to verif I just need to mention that the next node for this so this so the current node next node should be the first node and it is there in the head right so head is the first node initially so I would say before assign the node to head you will say node do next I want to say head so whatever value was having with the head will be the next for this one so let's say this node is maybe uh let's name it as n6 so this node will have an address of this node initially this node was head so we can simply say node. next is equal to head is that simple let's verify it is working just to verify that what I'm going to do is let's go back to Runner after printing after adding 12 let's say insert at start I will say insert at start and the element I want to insert is 25 so now 25 becomes the first element let's run this code and you can see we got 25 the start so this is simple now we can add the element as start itself at start what we are doing is we're creating a node and just saying that the node next element would be the the previous head node and now head will be changed to the node so head will be pointing to the first the node which you have created just now that is how you insert at start the next method we are going to do is insert at any location so I would say insert at and then we have to specify two things the first thing you have to mention is the index value and then you spe specify the actual data now when you specify index value uh maybe I want to insert a data here so I would say list do insert and I would say insert at at position two now index number normally starts with zero and we'll say data is let's say 55 so I want to add 55 at location two so when I say location two it is zero it is zero location so this is my zero object now and this is the first this is the second one and this is third one so when I say I want to insert this 50 5 at okay I want to add 55 object at index 2 which means here so we got a new object and this will be 55 and this will have some address so this object the second first object will refer to the new object and the new object will refer to this one so now this becomes three and this becomes four in fact we don't have to number that but then this is how you push you have to push this one to the next location so what you will do is you will just mention this node will change to this address this and the new node which you have created will be will refer to the next object okay now how do we do that and we are why are we getting why we getting error there so I will go back to my link list I guess I've not saved it now how do we mention that so to achieve that what we'll do is we'll say node node equal to new node again the same steps in fact we could have copied it so we say paste yeah so this thing is for sure there with every insert now in this case we have to Traverse right because we have specified the index value we have to Traverse from that location to the to the to the index value and to travel we have to again start with the node the head node so I will say n equal to head so remember whenever you want to Traverse you have to always say n node I mean node n equal to head now how do we Traverse now since we know the index value so whenever you know the value it's always better to start with a loop so with that Trace what we have to go to this point so if your index value is two you have to reach till one so if index value is two you have to reach till one because in one you have to make the changes right so if i s x value two you have to make the changes here I guess this thing is not properly visible let me just rewrite again as I'm very bad with writing and writing so just let me just do that once again so I got the first object here so we got the first object which is 18 and which is referring to the next object which is 45 which is referring to the next object let's say this is uh 12 and uh oh we before that we got 25 right because 25 is the first element now so 25 referring to 18 18 referring to 45 45 referring to this one now when I say you want to count when I say index value two it means this is zero I have to start with zero this is 1 and this is two and this is three now when you say two that means you have to get a new node here somewhere here and let's say the value is 55 so you have to reach till this node first in this node you have to change the location from here to from this Arrow to this arrow and from here you have to refer this one so first you have to reach till this point now since the index value is two you have to reach till one how do we reach till one is by saying let me just go back there so we'll use a for Loop and in here I would say in IAL to 0 and I would say I less than equal to index minus one and I would say I ++ in fact not minus one but say index now every time you Traverse you have to say n equal to n do next that's how you Traverse right okay now there's one change when you say next that means we have to say minus one because we have to reach here this node by referring next because next itself is going for the next node so you have to say minus one you have to come come one back once you reach to this point you just have to you just need to change the address right you have to change the address of this node with the new node but even before doing that I will change the address of this node to the this node so this node the new node which you have created that is node so this in this current situation this is node and this is n i want to have the value of node next to the this value now to achieve that what we will do here is we'll say node. next is equal to n. nextt so n is this one so whatever value so whatever value is there here will go into this node right because this value is nothing but the pointer or the reference to the next node okay we have done that now we have to update this value so this this node so the 18th node now will have the address of this node and to do that we simply say n. next is equal to node and by doing this our job is done let's verify so I would say insert at two let me just run this code and you can see we got 55 at two so 25 18 and 55 is that simple awesome right so this is how you add the element in between but there's only one twist what if I add at zero location because for zero location is bit different right so if run this code now uh you can see it is adding at the first location so it is not working so for zero we have to put a special condition here so we will check if the index value is equal equal to Zer what we will do is we'll simply call because see when you say zero it means you want to you want to add a start right so you simply call that method start by passing this data so in case if index is zero that means your intention is to start from the first location so you have to say insert at insert at start so this is how you add the element at any location which you want so I hope you got the idea how to add at start and how to add at any location so till this point we have seen how to insert data into list how to insert data at the start of the list and then how to insert at specific index so if you can see we have a value which is 18 45 12 and 25 and then we are also adding five or 55 at the start so if onun this code we should be having five elements right but then I made a mistake so I this code you can see I made one mistake I'm getting this 55 two times so what went wrong if you can see the code here we are saying when when you insert at the start and in if the index value is zero then you need to execute this code that means we not we should not be executing the other code as well right I mean this thing is is need to be skipped and we are not doing that and that's why you can see we are inserting 55 two times so this code here should go into the else part which we missed in the last video I will just put uh else block here and after putting that else block I will just go back to my Runner and if I run this code now you can see we got 55 only one so yes that was one mistake in the last video uh so I just made some correction here so there should be an lse here it's working now you can see we got 55 so just to draw here whatever we have done till now uh so let's start with the first one so what we are doing is with this line of code will create your first box here and let me just write a box which is 18 and let's give an address which is 501 that's my first address let's let's have one more so when you say 45 we got a second box so when you add this list you will get 45 here and the value is 45 now let's say this is 502 so of course this 18 here will have an address of 502 so it will link to this box and then when we are saying add 12 so we got one more box here which is 12 and let's say this has some address with let's say 503 so for 45 here we'll have 503 now so we got this link here we got one more which is uh 25 but 25 will go at start so we got a new box here which is 25 initially we were having a head which was referring to 18 at this at the start of location but now that head is not referring here the head is referring to this new box 25 because we are saying start at the start so this will have its own address like 495 this is the address can go anywhere it's not just uh when you when you say it will add a start it will have this value it can have any value maybe 5.95 maybe 6.95 or 795 it doesn't matter now here it will have 5 0 1 so this will refer to the next element so the sequence is 25 18 45 and 12 and of course 12 will have null and then we have saying insert at zero location so we are adding one more element which is 55 5 so we got 55 which is going at and let's say 55 has its own address uh we'll say this is 702 55 will have 495 because the head value and then this will refer here now head will not be referring to the 25 head will refer to this new location so that's how you insert value in between or at the end so we have seen all those stuff the next thing which is remaining now is delete right so how do I perform delete operation so let's say I want to delete this 18 here so I want to delete this 18 with index number 012 so I want to delete this index value two now how we do that so when you want to delete this index value two so what we normally do is we just so the only thing we have to do is just change this address that's it the only thing we have to change is change this address so here instead of having 501 we can we need to change this to 502 our job will be done right so when you say this is 502 it will refer to the next node and we not be using this node anymore so this is gone okay now how do we execute that that so let's go back to our link list and let's add one more method which is delete so before show here I would say delete public vo delete and this will take a index value so I would say index int index now technically the name should be delete at right so it should be delete at because we are specifying the index value okay now we have a special scenario here what if you want to delete the first index so if you want to Del this one which is the first index here now in that case you just need to change one thing you need to change your head location with this one that's the only thing you do right and how do we achieve that so we say if my index value is equal to zero in that case I will change my head location so the head location will change to the next node and what is next node it is referred with the head node do next so I would say head. next so head will become head. next and that's it this is what you do when you want to delete the first element is that simple but what if it's not a first element so we'll go for lse part again and here we have toy Travers remember we whenever you want to Traverse you have to do something if you want to Travers remember this we were using a for Loop or a while loop we'll go for for Loop because we're using index value right so remember this this code here the same thing from here to here everything remains same we have to Travers to that location so let's go there I will say copy and we can just use reuse the code here so we are traversing right so from so from the head node we are traversing to that location now once you reach to that location so now when you pass a value two here so the index value when is two so this Loop will run only once right because the index value is two so 2 - 1 is 1 and we are going till I less than one which is zero itself so this Loop will R rate only once that means the current n value which representing after the loop would be this n so this one will be your n so n is one now I want this value which is 502 because so that if I know this 502 you can assign that value in this box and the way you do that is by using this node in some temporary variable so I will say that there's N1 so when I say N1 now I'm representing this object and when I say n I'm representing this object or this node so I would say first of all I want to assign N1 is equal to n. next that's how you get you will get this reference so if you want to if you want to use this object here you have to if you want to make it N1 you have to say n. next because n do next is N1 right oh but we don't have N1 anymore so we'll say n node n i mean node N1 is equal to null so that we can refer that so we have to declare that object first now once I got n and N1 the only thing which you have to do now is the n object so when I say n. next so the N do next need to be replaced by N1 do next and it's very simple now you can simply say n do next is equal to n 1. next okay and then once you got the value you can simply say system.out.print and you can print the value if you want uh you so just want just want to verify if everything is working properly you can delete the element which you want to delete so I will say I want to delete N1 because that's what we're doing we want to delete N1 right so we'll say N1 and let's print the value of N1 which is N1 dot data so we'll know at least which one is getting deleted now how to verify this let's go back to our runner and let's delete a value after some time so say least. delete I want to delete the element at index number two which is 18 in this case let's run this code and you can see after running we don't have 18 anymore in the list yeah this is getting printed in the delete method itself if I don't print something here even it will not print 18 there so yes with the we can delete the value just by using delete method so we have delete at it will you it will be used to delete the value of the particular index so that is awesome uh this is how you delete the element the only thing we did here is we just changed the reference right so this n so this element address is changed by the new one which is 50 502 not 501 in this case and that's it this is how you break the links okay there's one problem this object is still there it is deleted from the list but it's still there if you want to nullify it you can do that you can simply say N1 equal to null so that it will be eligible for garbage collection right so if I run this code now you can see we we have removed 18 and it is not there in the uh memory as well it is eligible for garbage collection so that's how you can uh delete this uh data and in this video we'll talk about stack now what stack means now stack is basically an ADT in data structures and as you know ADT stands for abstract data type so when you talk about abstract data type we only focus on the features it provides but not the implementation now in stack it provides you multiple features when I say features we have a list of features like we can add element and normally when you want to add element we use a term called as push you can you can delete the element using pop so you can do that with the help of pop or you can you cannot say delete but you can take out the element from the from the stack and then you can also look for the elements you can find an element the first element and then then you can do that with the help of peak again we'll understand this in detail later so we can apply a push operation we can say pop and we can say Peak stack it supports a feature called as LE 4 which is last in first out which simply means whatever element you have inserted last you can access that first so Leo stands for last in first out so whatever element you have added last you can access that first to explain this we will be having a stack here so the F last element you have inserted is the first you can take out and in stack you have only one entry point so you have only one entry and exit point that means this is the only entry and this is the only exit so this one will remain closed you can apply a lock here so this one will remains closed the only place where you can ENT you can enter the values is from one point from here and you can take it out so whatever element you have inserted last you can access that first but do we use this on real world and the answer is yes example let's say if you are working on a task so let's say if you're working on a project it's a very big project maybe that project is let's say a and that project will maybe will take uh 6 days so it will take 6 days to complete this project and suddenly the old project or the old old version which is already deployed on the server it is giving you an error now you let's say you got a bug now at that point what do you think will you complete the entire a project and then you will think about the bug or you will try to fix the bug first and of course right a bug is something which a user is facing nowadays so of course you have to fix the fix the bug first and then you have to think about the earlier task so in this scenario you will try to fix this bug that means you are keeping your job a aside and you're focusing on B now so you started working on on B and you thought okay in next 3 to 4 hours I will complete this B uh I will I will fix this bug so you're keeping this task a aside and you're working on B now and certainly that this is your lunch time now so you are going for a lunch so let's say this is 1:00 p.m. and then you want to have your lunch you're going for the lunch now so let's say that is Task C so task C is your lunch time and now you are having your lunch so while you're having your lunch of course you will not be working on be the same time because when you're having a lunch you should do only one thing at a time you should have your LUN lunch so when you're working on you're doing your lunch you will not be working on B that means you have kept B aside now once you complete your lunch what do you think which is the first task you will resume A or B it's B right because this is the last task you have left so when you say B this is what you left last so last in first out so this this is what you will resume and once you complete B then you will resume with your a that is last in first out so the last task which you are working is the first thing you will you will resume now do we use this in some other concept yes example if you have a stack of books so whenever you have a stack of books what you do is the first book so you will keep the first book here then second book then third book and then fourth book so once you keep all this book once once above other the first book you going to access is the last book you have kept here right so this is how your so let's say if you have if you have kept one more book here then this is the last book you can access first or this is the first this is the book you can access first what about virtual world so in virtu world as well you know when you talk about recent applications so in Windows we say alt tab so when you say alt tab it will show all the applications which you are working with so when I say all tab here you can see this is the first applic this is the last access application so you can see that first which is paint uh then I got this recording software which I have opened second last and then I was working on a notepad that's the third that's the third in the list and before that I have opened my my computer and before that I went to Google or Chrome room so this is the this is the stack right so the last axis element is coming at first here so yes we use stack a lot of time in in real world and in virtual world as well so let's try to understand how do we work with elements so let's say I want to store this four elements here we got five we got eight we got three and we got two so I want to insert this values in a in a stack so what we do is we create a stack here and again if you want to insert the value we will we will use push so using push you can insert the value using pop you can get the value the last value and using find if you don't want to delete the value from this stag you just want to see the value you can use Peak question is how do we implement this in fact you'll be seeing the implementation later but then there are multiple ways of implementing this we have the array way so you can Implement that with the help of array in fact in Array as well we can go for fixed length array then we can go for dynamic length array or then we can also go for link list so we have different implementation so we can go with the array implementation using fixed or dynamic length we can go for link list but doesn't matter what you go for let's say if you talk about array so let's say if I create an array of four elements here right so we got an array of four elements and this is index value zero index value one index value two index value three now how will you insert the value so this is the only entry point and this is the only exit point right so if you want to enter the values you'll be using a method called as push or a function called as push in this push you will pass the value so whatever value I want to pass let's say if I say I I will represent 5 or 8 or three or two whatever you pass so once you pass a value here that value will be assigned to zero so let's say we got five here then when you say eight8 will be assigned here now once you inserted this two value or maybe let let's say add three as well so we got three here now which is the last element you can access so if you have entered three this is the last element you can access but how do you know which is the last element so you can simply use a variable called as top now top will have the uh top will have a index value of the isent element so index two we have element three this is the top element and when you insert two now it will the two will go here simple right now how about if I say pop so when you say push everything go in this tag where you say 5 8 3 2 so the value will go down and then when you say pop it will remove the first element because when you say you have inserted two this is where you're represent representing your top right this is the topmost element so this is the element which will remove first so when you say pop it will remove it will remove this two and let's say after that if you're inserting 12 so let's say after that you after saying pop you you inserting 12 so 12 will come here because that's the last element you can access so again that will be go back to two yeah when you delete this element two before uh it will go back to three okay the the top variable will go back to the index number two which is three in this case so this is how you you push and you pop so the last element which is added is the first thing you can you have an access So when you say pop it will delete the element it will give you the element and to delete the element from the stack but what if you don't want to delete the element you can simply use find and use to use find we normally use a function name as Peak So when you say Peak at this point it will give you 12 pretty cool right now let's say once you have inserted all these values in the in the stack and the stack is full right because the size of the stack was four uh we can make it Dynamic we can use Link list but let's say if I'm using a fixed length array so if you're using a fixed length array here and if you have incre if you have crossed the limit of your stack which is four in the this case if I try to add one more element so so at the end here if I try to add an element which is one now the moment you say one if you if you try to add one it will give you an error and that error is Overflow error because you are trying to overflow this tag that's one one one case so if you try to push the value and if if your size is full it will give you overflow error what if you try to delete the element if you try to pop and your your stack is empty let's say if you don't have any element here so if a stack is empty and if you try to f petch value at this point it will give you another error so if your stag is empty and you're trying to pop it will give you error which is underflow error so underflow is when you when you don't have the value and try to pop the valents from it so that's how you have a overflow and underflow concept those are errors basically and there's one more thing here with this push pop and Peak we can use some other methods as well or functions as well example we can get the size of the size of the stack using size method you can also check if the stack is empty with the help of e empty function so again you can Implement whatever methods you want but these are the basic ones for stack and in this video we'll talk about the stack implementation using Java now when you say a stack basically stack is a class inside Java so if I simply say control space it belongs to a package java.util so you can use all the features of a stack here but then why to use a inbu class when you can create your own so I don't want to use the stack class which is inbu I want to create my own class so what I will do I will right click click here on the package I would say new and I want to create my own class and that class name is called a stack so I have my own class here and here I will create object of Stack I would say stack nums equal to new stack now in this stack object or the nums object I want to perform certain operations so when I say uh nums do push I want to push the element I can specify any value here if I say 15 so the first element should be 15 and then again I can push multiple elements and then I I maybe want to pop element which is taking out the element from the stack or maybe I want to fetch element so when I say stack basically it has certain features right as we discuss in the theory session we can use push uh we can use pop on we can use pip so we'll be using we'll be working on these methods so let's start with the first one which is push so if you can see in our stack we don't have any method yet so let's create certain methods so the first method is push now to implement push what I will do is I will say public wide push push now since we are adding the value we are not expecting any value so let's say push data so we have to send a data and it will add data there so now you can see if I go back now you can push the element and there's no error but then what you will do with the push to make it work first of all we need to create an array right so we have to create an array and we have to also specify the size of the array so let's say if I say we have an array here and initially we'll take an array of five elements so that if you can work on five elements you can work with any number of elements so let's say if I have the first one then the second one then the third one and fourth and fifth so we have these five elements here index number will be 0 1 2 3 and four now if you want to add the first element as we are doing it here we are passing 15 right so that 15 will go to the uh go to element zero so somewhere here we'll be having that value which is 15 but then we don't have array yet so even before you push the element you need to create that array so let's do that I would say int and we'll say stack equal to or stack it's an array basically so we'll say stack equal to new int and the size of int is five you can make it Dynamic you can you can take the input from the user what array size you want but time let's specify by by ourself so we are we have created the array and now we can push the element but question arise where so we'll say okay you have when you say push you will assign the value to the address location zero okay so that makes sense we can simply say zero right so we can say stack of Z and you can assign the value whatever whatever data is coming it's so easy you can that value which is 15 will be assigned to the index value zero it is that simple but here's a Twist The Twist is what if I if I want to add one more element so if I say nums so if I push another element here we'll say let's I want to pass maybe eight now we we are passing two elements right we got we got 15 and we got8 now what will happen is the moment you pass 8 here the 8 will be the value8 will be assigned to zero again with the zero location that's not what we want because if you if you if you run this code the value of 15 will will be replaced by eight we don't want that I want to assign value to one that means we need to count it we have to use we need to use a variable which will count the number and maybe I will use a variable here which is called as top and the initial value of top would be let's say zero we can simply specify top here right so instead of using zero we can say top okay now when the first element getting inserted so when you insert 15 that 15 will be inserted here at this at the top location zero right so we got 15 here now if I send eight oh eight is ALS the the value of top is still zero that means after doing this thing we have to you have to Simply say plus plus so every time you push an element you just need to increment the value of top so that when you pass eight now 8 will be assigned to index value one because when you pass eight the value of top at that point is eight so yeah so that is how you push the element in the in the stack okay now next point would be how will you fetch the element maybe I want to pop the element or even before let let's push all the element and let's say I want to print it I want to print this stag so after pushing two or three values let me just push one more we have a stack of size five in that let's say we have only three values let's say this is 15 8 and 10 I want to print the entire stack so I will say num. show so it should show the entire stack but the problem is we don't have show method in the stack so let's let's go there and say Hey I want a show method here which will print the entire stack now question arise how do you print the entire stack it's very simple actually you can take a loop enhance for Loop here and you can say int n colon tag that's an array and you can print each value and you can print that value with a space so I will say n and then I will print a space so that you know when you print all the value they should be separated with a with a space sounds cool let's go back and what do you think will it work let's try so I will right click here and we'll say run as Java application and it worked can you see that we got 15 8 and 10 and we got 0 0 so yes it is working so stack is working when you say push but how about pop I want to remove the elements now uh is it simple let's try so when I say pop I will simply say public now pop will also fetch the value so it will it will remove the value from the stack and it will also fetch the value so I would say int pop and this will not take any parameter now how will you fetch the value now temporary we can say int data is equal to okay first of all let's declare that how do you fetch a data it's simple right we can say data equal to the data is coming from stack now the the property of Stack is if you have three elements as we defined here we have three elements right we have 15 8 and 10 now when you pop what do you think which element you will be getting and by default the value of four and three is zero because that's how array Works in Java the point here is when I say pop which value I will get so it is done with the help of top so we have a top variable here and whatever value we have for top you will be fetching that value because you will always get last in first out so the last element which you have added is 10 so the top referring to 10 now this location so it will give you 10 and the way you do that is by simply saying you will say stack and you will say top now you will get that data quite simple right okay now there we have to do one more thing now once you say you are removing this 10 we will making it zero so I will remove I will make this element as zero and how do we do that it's very simple let's go back here and say stack of top is equal to zero so we are making it zero so that again you can make it zero you can make it negative value for whatever you want and then at the end we can say return daa I hope it will work now so let's run this code and you can see we got oh we have not we are not saying pop so we'll say nums do popop now it will delete the last data run and you can oh not working what's wrong what went wrong here okay so we are saying top top oh okay so we have to do one more thing see as you can see here when I say push the Top Value so when I say push first time the Top Value become one second time Top Value becomes two third time top top value becomes three that means it referring to this value we need to do minus minus we have to decrement the top before using it so we'll say top minus minus is it let's try so I will oh I'm not even printing pop value so whatever pop value I'm getting I should be printing it right so I would say system.out.print I hope this will work but on this code oh it worked now it worked you can see that we are removing the value of 10 from this tag and you got zero here cool right so that's how you use push and pop now what else we can do we can also Implement Peak here and how do we do that so Peak is very simple Peak is almost same as Pop the only thing is in Peak you you don't delete the element so I will paste it here and I will say this is Peak okay you will not do minus minus because if you do minus minus it will it will decrement the value but while you're fetching you will be fetching the minus one of it so we'll say minus one and you will not delete the element that's what you'll be doing that's it that's Peak for you after adding the after adding value eight I will Peak I would say nums do Peak if I run this code now you can see we got eight so the last value which I have inserted is eight here here and then I'm pushing 10 then I'm popping 10 and you can see that's why the in this tag we don't have 10 simple this is how you use push Peak and pop what else we can do here now we can Implement some certain other methods as well example you can get a size of the stack you can get uh you can you can make this Dynamic instead of saying five whatever size defined by the user or way Dynamic which is every time you add the element even if the initial size is five you can you can change it so you can you can increase the size on the go we have talked about three methods we have talked about push pop and peak in fact we have also used one more function which is uh show which will print all the elements of the stack now with this we need two more methods the first one is size now size will give you the size of the stack and we also need a methol as is empty now is empty will be useful to check if the stack is empty now why do we need that that we'll see in in some time but then let's Implement these two methods first now to implement this let's go back here and I would say in fact after this peak just implement the method which is size so how will get the size of this tack so I will say public int the method name would be size and here let's return top because top will give the size right okay we we have a top variable there so when I return top will what what do you think will it work let's try so I would say go back and run inside run so let me just not pop any element here so you can see we are pushing three elements and and then at the end I want to print the size of this stack I would say num. size now it should print the size for you let's run this code and okay it is printing three here but you know you should also print the message I would say size is and I would say sizes this one let's run this code and you can see it says size three that's right we we we have three elements let me just add one more and I would say the value is let's say seven and if I run this code it should say size is four oh that's working you can see that it is working and after that if I if I remove any element let me just say pop I would say nums do pop of course it will print seven the pop value but what's the size size becomes three so it it works right when you push the element it will increase the size when you pop the element it will decrease the size that makes sense uh let I want to implement one more which is is empty so I would say public now is empty is a method which returns a bullin value so whenever you whenever the method starts with EAS it always returns a buen value I would say is empty so let's return uh if the top is or less than equal to zero then we have to say it is empty right so if this not zero which is more than zero it's not empty right so let's go back to Runner and let's we have to check if it is empty so I will check it here after everything so I will say I would say empty status I want to check if it is empty we'll say true or false and the moment you do so we have we have to say num start is empty right and of course it is not empty so it should print false and you can see we got false if I do the same thing before pushing any value and if I run this code now you can see it says true and maybe if I push one element here and after that if I if I pop and again if I print is empty it will it will say true right because it is empty so that's how we can implement this two methods but what's the use of this implementing these two methods do we have any advantage and the answer is yes so what I will do is um let me just do some experiment and let me remove all the extra stuff from here I don't want to Peak I just want to push multiple elements and I don't want to do any of this stuff let's let's keep it simple say I'm I'm only pushing elements and then while I'm pushing I will push four elements and if I run this code so yes we got four elements what if I try to push five elements will it work let's try I would say 17 and if I run this code and yes it does work what if I try to push one more and let's say the value is maybe 77 in this case if I run this code you can see we got an exception which is array index out of bounds exception it's full right because the Stag is full that means whenever your stack is full you should not be adding the value you should print the message to the user hey this stag is full how will you do that how will you check if the if the Stag is full and the way you do that so every time you say push so before pushing you need to check is it full how do you check if it is full the stack value is five right the maximum size is five so I would say if top if this is equal to equal to four that means your stack is full right so if it is four I would say stack is full so I would say system.out.print stack is full and this part will be executed in else part okay let's go back here and after every push I will try to print show so that we'll know what is happening so I would say nums do show and let's run this code now and you can see oh at this point it is saying stack of Stack is full oh my bad okay I I guess I'm missing one more thing here after printing this stuffff I just want to print a new line so that every output I will get a new line okay so you can see it is it is saying stack is full here itself because I just made a mistake it should not be four it should be more than four why more than four is because every time you say push you can see we are incrementing the value here so it is not four it is five let's go back there and let's run this code and you can see that after this point it says stack is full so it will not allow to push the element after this point so that you can save yourself from the exceptions right so that's how you can check if it is full now what I will do is I will try to pop so I'm pushing all these elements and after pushing this if I try to pop the elements and I would say system.out.print and I would say uh nums do popop it will print it will pop all the elements and not all it will it will pop only one at one point so I will run this code you can see at the end you got only one element which is 17 that's great in fact I will not add all this element I just want to add three elements so that we can save our job so I'm adding only three elements now and if I say pop of course you will get the last element which is 10 right this is the last element which you have entered I would say pop two more times and you can see it will try to pop all the elements so if I say print the size I would say num. size it will print zero because we don't have any element right so you can see we got zero what if if your stag is empty now and if you try to pop now if you try to pop it will give you exception right because you don't have that value before that so you don't have any value in minus one so that means you need to stop it before going before popping the element how do you check so we'll say if so we have to do this only when if your if your stag is empty then you will not do all this things you will simply print a message which is tag is empty otherwise we'll say else and you got the point right so if I say Tab and if I on this code now okay I hope it will work there's an there's a problem here or data we have to ins something I would say data is by default zero that's a local variable right so before returning it we have to assign some value and let's run this code now and it worked you can see that it says tag is empty so it will not give you exception so we have to handle we have to take care of all this element as well right so that's it I hope you uh you understood what we have done so we have implemented two things one is size and second is is empty method so using these two methods we can per we can check if the stack is full or the stack is empty before performing any operation we have seen how do we Implement stack using a fixed size array so if you can you can see this example here we have a stack class in which I'm creating a stack array or basically an INT array of size five and then we were able to push element we were able to pop element then we were able to Peak and then we were checking the size of the array and then is it is empty and then we were able to print all the values and then using this we can perform the operation the only problem here is we have a stack and that's perfect we have a stack here and this stack does have a value which is you know 15 uh 8 and 10 but the problem is the size of this array is only five which means the maximum maximum element you can go here is five elements what if you want to go beyond that what if you want to have a stack which is which is expandable and that's where we have a concept of dynamic size array but then how we you implement Dynamic size array so what we are what we want here is the moment you say uh you have five elements let's say if you entered two more elements here here let's say three and six and after that if you try to add one more element which is seven and of course we don't have the AR size of size six so I want to create a new array so it should create an array of maybe um a new array using in which you'll be having all this values now when you say a new array so what should be the size of that array so I'm expecting the size of that array would be so let's say the current array is of size five the next array should be of size 10 technically we'll go with the power of two initially we'll have array of size two if you want to add more elements we'll make it four if you add more elements we'll go for eight if you add more elements we'll go for 16 this is what I'm planning for but then how will you increase the size every time so it's very simple the current array is so let's say if you have a current array and let's name that array as stack so that's your array we will create a new array with a name so let's say if I create a new aray with a name as new stack now this new stack will be having a size of 4 four but the problem is we got the new array what about the values in it so whatever value you have in this tag will be copied in the new ARR that's what we want to implement that's it if you can do that our job will be done so every time you increase you you go beyond the limit you have to Simply expand your array and okay there's one more thing what if you have a array size let's say 16 yeah so as you add more elements you'll be having an AR size of 16 and let's say you have 16 values and then you are saying pop pop pop for maybe 15 or 10 12 times in this case let's say if you have only three elements now so in total we have three elements and the size of this array is 16 that means you are wasting some memory right or we want to have a feature where you can shrink the size so we want an array when you say AR is dynamic you want it to be expandable and you want it to be shrinkable so we want to implement these two features and if we can if it is possible for us to implement these two features that is what your Dynamic size stack would be so let's get started so what I'm going to do here is first of all I want to copy the exact code because we will reuse the code here and I will simply copy this code I will say contr a copy and let's create a new class and I we call this class as Dynamic stack or it's a d stack you know that will that will look like a dynamic stack we are making a dynamic tack here so let's say d stack and we click on finish and in this tag class I want to have all those features I will just simply paste it here and if I go back up there might be some issues I have repeated the package and the class name is this this tag okay now the first thing we need is you know we cannot simply create an array of size five I want to create a variable with uh with a variable name as capacity capacity and then let's see the capacity of this is two initially we'll have a capacity of two and then we'll go beyond that normally we can go for a capacity of four or eight that will make more sense because normally when you say you have a stack of course you'll be having more elements but just to make it interesting you know just to show you how it expand and Shrink we start with q and then here when you create this array I want to say this is two again you can we can write capacity here right so you're creating an array of that size initially the array which you have is of size two okay that makes sense now of course we will be having a method which is size we have the element which is is empty so everything will remain same now what will change is the way you push so when I say I want to push the element and I can I don't want to print a message which is stack of full we don't have any option there now if you if you even if your stack is full you want to expand the size that means this code will happen for sure you will be able to add the element the only thing is maybe if your stag is full so you need to expand the size and then how will you expand the size so I will simply call a a function or a method here called as expand but when when I want to call a method which is expand so only when your stack is full but how do we know if this stag is full okay that's a good question right so if the size of the of the stack which is say size is okay if I say size is equal to equal to the capacity then that means your your stack is full in that scenario you will expand that's it nothing much in that scenario you will expand and anyway you have to do this task but question arise what you will do in expand what exactly happens in expand okay let's think about it what will happen in expand so in expand what we have to do is we have to create a new array that's the main idea right so let's say I want to get a method called as expand which will be this method here again you can make it public or private doesn't matter uh in this case I'm I'm keeping it private because I don't want to access this expand function from anywhere else I just want to use the expand only from the current class so I will use expand and then the first step would be I want to get the current length and the way you do that is by saying int length is equal to size So when you say size method it will give you the current length Okay that's simple now we have to create a new stack and as we Define in the diagram here we will simply create a new stack right this is the new stack we have so the way you do that is by saying I would say I want to get a new stack I would say int new stack and then I will give a bracket equal to new okay now the size of this tag would be doubled right so if if the current size is two the next size would be four right so I would say int and then I will simply say capacity whatever value of the capacity we have I will simply say capacity into two our job will be done so we got new stack and then we are saying it to two that makes sense the next thing we have is okay so we got the new array now we have to copy the element from the current array to the new array now how do we do that so we can run a loop here we can use normal for Loop the best way would be to use inblue classes again it's your choice okay you can use normal for Loop but since I'm lazy I'll be using some in classes I would say system I would say there's a method called as AR a copy so thankfully we got this method AR a copy this AR a copy takes five parameters the first parameter is from where you want to copy so I want to copy pro copy from the stack array which starts with index value zero again I want to copy the entire add right so I will start with zero and then it will it will get copied to the new stack and it would be zero and then how how many elements you want to copy I want to copy all the elements I would say simply say length once you have copied everything so in new stack we have all the new values but then unfortunately ultimately we are working with stag array itself right so even if you expand the new stack everywhere we are using the stack reference so of course we have to replace the stack reference with the new stack reference so that everywhere else I'll be using the stack reference which is representing new stack here okay so once we have done with the stack and now if you can observe we have also increased the capacity so I would say capacity is equal to the current capacity into two so I would say I would simply say into equal two so whatever capacity you have here it will we just trying to double it that's it it's so simple and now let's go back to Runner now instead of having the object of Stack let's say object of D stack so that we will not get the exception and I will not say pop this time I will only focus on push and every time I push the element I would say show just to get the output I say copy paste paste so you can see I'm entering five elements the size of the array which we have here is only two right but still we are trying to print five let's run this code let's say it is working and it works you see that it works so initially we were having two elements no problem we added new element but then the moment you added 10 can you see that it is the capacity is not three it is it is four in this scenario we have added four elements and now the moment you add one more element which is 10 again we got the element of size eight so that's how it is expanding cool right in fact you can print the you can print the value using size and you will get the exact size whatever or the capacity if you want to print so that's how we are expanding it so simple that's why you say it's a dynamic array the next point would be how do we pop the elements because I want to also want to pop elements right so I would say pop is working but then every time you say Pop I want to decrement I want to shrink okay first of all I will not say is empty do you want to check is empty yeah that sounds good is empty is is a good checking but every time I remove the element I want to shrink so I would say shrink now shrink may not work every time but then whenever your size goes okay when do you want to shrink that's a good question so let's say if you have an array of eight or maybe you have an array of 16 the size is the size of this array 16 but the elements you have let's say eight at this point I don't want to shrink but the moment elements goes or less than four so let's say if the if the number of elements is 1 2 3 or four in this scenario I want to shrink it and I want to make it half half of 16 which is eight so even if I have four elements I want to make keep it eight let's see if I go beyond that if I if I if I go below that if I say I have one element then I have to make it two right of course before going for one it will become four and then you it will become two so the idea here is if the number of elements goes be below 3x4 we will make it half so size of your add becomes half that's what we're going to do here in string so let's Implement shring method so I would say click and create a method called a shrink now inside this shrink method I want to perform those operation and how do we do that now first of all we want to know know the length because that's very important so I would say length equal to size and then once we got the size here or once we got the length now how do you how do you shrink it how first of all how do you know that your array is is the number of elements in the array is less than 3x4 now there are multiple ways of doing this formulas we can use shift left shift aray I mean left shift arrows you can do some mathematical calculations you know I'm since since I'm lazy I'll be using the simplest one which I love so I would say uh length is less than I would say Capac because this so the operation which I'm doing now will give you half so I would say divide by two it will give you half and again if I say divide by two it will give you the 1/4 in this scenario what I want to do is I want to reduce the capacity by half so I would say capacity is equal to capacity IDE by two but then it's not just reducing the capacity it's also about creating a new array that's important right so what I will do is I will create a new array which is I would say new stack again and and the question is what should be the size of this array and you guess it right it will be the new new capacitor right if you if if your earlier array was of size eight the new AR would be of size four so this is where you're doing it you're dividing by two again if you're thinking we will be getting a point value don't worry uh this is a part of two capacity will always give you part of two because we're expanding in that way so it will not create an issue for you now once you got the new array the same thing we can actually copy paste you know uh okay I cannot say copy paste should be saying code reuse that will make more sense go back here and paste and you can see we are creting a new add we are copying the elements and then we are saying stack equal to new stack I hope it will work let's go back to Runner and then at this point the size of your stack is eight after that I'm saying pop so I would say I don't I'm I don't want any value I would simply say ns. pop it should remove the element and then I will say nums do show so that I will see the elements and and look at the size it has removed the element let me just remove one more and in fact two more just let's go beyond three or Beyond two it will go let's go to two and the moment you have a size two can you see that the the array is getting shrinked and if I go one more time see the size see the add size it is getting shrinked so that's what that's how you you make it Dynamic and in this video we'll talk about Q now we have talked about link list we have talked about stat and now it's time for Q now Q is almost same as stack the difference would be in stack we use a concept of leao which is last in first out and in Q we use a concept of fif which is first in first out which means whichever element arrived first will be the first one to go out so it is first in first out now in real world whenever you want to take a movie ticket you join a queue right so whoever arrived first will get the first ticket in a queue what we do is we have let's say we can implement this with a different concept we will be implementing this with an array uh so you can do that with the help of array or you can do that with the help of Link list in this example we'll look at how do we Implement that with the help of array in fact in Array itself we can go with the flat array or we can go with the circular array but we'll see the difference now let's have the array of size four where you can have four elements in this array you'll be having two end the end from where you will insert the value and the end from where you will take out the value so this is your insert so this is where you will insert the element and this is where you will take out the element and that's why whichever element reaches first in the queue will be the first one to go out now let's say if I insert a value five so the five will be coming from here it will go in this area so the five will be saved here the moment you insert a new value let's say two it will go here let's say if I insert seven it will go here and let's say if I insert three it will go here so this is how you add the elements now if you want to delete the element so this is the first element which which go out so five is the first element which go out and then all this element which is 2 7 and three they will shift on left hand side so two will come here seven will go on the place of two and three will go on the place of seven and then you can add one more element at the end that's what we expecting from Q so in Q basically we have two end one is from where you insert the value and from where you can take out the value so you can call this this area or this thing called as front and this is the real end from where you're inserting the value now in Q we can perform certain operations so you can insert the values and you can remove the values the way we did with stack we in stack we use a concept of pop or push so push would be inserting values and the same way in Q we use a different term so that term is NQ so NQ is like inserting or in stack you can say push if you want to remove the element we use a word called as DQ so we have a concept of NQ so so you can represent insertion with the help of NQ and you can remove the element with the help of DQ now of course NQ will take a element from you so you have to pass a data and then in DQ don't pass the value but it will return your value so let's say if you say DQ and your front is five so it will give you five but let's say after after that also you are saying DQ it will give you two now with this two methods we can Implement some more methods as well example we can Implement a method of size which will give you the size of the Q uh we can Implement is empty if to check if it is empty these are two methods we can also Implement in this we can also Implement Peak the way we did in stack you can get the value which is going to be removed it will not remove the value but it will it will show you which is the value which which is going to removed now how do we implement this so first step would be we need to create a array so we have to create an array of we'll go for array of size five I love this number five so I will go for the array of size five and then I will try to add the element M now how many variables we need here so basically when we talk about this implementation maybe we need a front variable which will have the index number of the front because every time so initially when you don't have the value in this in the que so example if I create another que here and if I say the Q is of size five so we got a size of five so whenever you don't have any element of course the front and rear both will be not be refering here but then the moment you add a value front and rear both will refer to this value so this is your front and this is your rear but the moment you add more values let's say if you have entered five and then two the rear will be pointing at this point in fact the re rear we have to shift to this point when you insert two so that you can add three so rear will shift here so every time you add a value you will say re Plus+ and every time you delete the value you have to say front Plus+ So when you say delete you have to say front Plus+ and whenever you insert you will say rear plus we'll see the implementation and then you will understand understand what I'm talking about so I will go back here in the que and so you can see I have two classes one we have is Runner class another we have is a q class I will go to q and let's try to implement those methods the first method we have to implement is NQ oh before that we need to create some certain variables the first thing would be I want to create a q itself so I would say q and the size of this Q would be let's say uh five initially or this is not what you do it so you say new int and you the size five you can make it Dynamic your choice but initially I will go with the static one or fixed one so that it will be easier for you to understand and then we need three variables we'll say size one of the variable uh then I need a variable which is front which will refer to the front element and then I will need a rear element which will or rear variable which will refer to the rear element once you got these four variables and of course the value for the size would be zero front would be zero rare will be zero and then I will create the method so the method name is public void NQ this is my method which will take a int data and then I will try to insert a value here now how do we add the data into a NQ so for that I will go back to my this point and let me just make this an empty empty Q okay so you can see that we got a empty Q here so the name of this Q is Q itself and now I want to insert a value so let's say if I'm inserting a value which is five so in this que at the index value zero I want to insert five now if you want to insert the value we use variable which is rear and by default rear has the value which is zero in fact front will be also referring to the first element as at this point so we'll say front is also zero index number zero index number one index number two three and four now front and rear both will refer to the same element here at the end now the moment you add five so at the rear point you have to insert five now how do we achieve that so in the code itself you will say Q of rear is equal to whatever data you are passing so the data I'm passing is data itself now once you have added the value you need to do one thing after adding the value five you just need to shift your rear to the next location which is here and how do we do that how do we shift our rear it's very easy you simply say rear Plus+ so you will say rear is equal to rear + one or you can say Plus+ that's fine and then once you have added the value or incremented the value now I also want to increase the size of it right so now the size is size Plus+ because we are not in fact we can write size equal to size + one just to maintain the same sequence so you have rear equal to rear plus one and size equal to size plus one so every time you add the value the size will increment it's that simple time me let's work with NQ and then later we'll work with DQ I want to see the element as well so let me say I want to create a show method which will print the elements so we we also need one more method here which is show so I would say show method as well and show is respons possible to print all the elements and in this show if I want to print elements it will print all the elements in the from the queue uh but how do we do that so what I will do is I will say for loop I will start with zero initially and then I would say okay till what point we have to go I have I have to go till size right and then Plus+ because the size of the array maybe so you have inserted three values so the size would be three so you have to go till I less than three and every time you go there you just need to print the elements and the way you can print the element is by saying the value Q of I and then you will also print a space after that and here I want to print the elements I would say system.out.print I would say elements elements colon so that you know it will give you a good format of printing I don't want to a print in there that's it it will work now so we got NQ we got show now how do we verify so let's go to Runner and in this Runner let me create object of Q I would say q q is equal to New Q I got the object which is q and in this Q I will add the element I would say uh enq I want to enq the first element which is let's say five as we have done here now after inserting five I will just simply say q. show I want to see how many elements are there and if you onun this code you can see we got five we got only one element that's perfect let me just add one more element here and that would be two in this case I would say two here and when you say two if I run this code you can see we got five and two so every time you insert the value it will it will get added in the queue but question arise how will you remove the element and what happens when you go beyond the size let's say if I inserted uh seven values what will happen and of course if you insert seven values or six values it will give you a very famous error or the exception which is array index outter bound exception till this point we have only inserted the values now how do we remove the values and how do we avoid the exceptions so let's try to delete the values and how do we do that it's very simple just go back here and we just need to implement one simple method which is DQ so I would say public uh it will return the Valu so I would say DQ and it will take it will not take any parameter now how do we remove the elements it is simple right so just go there so when I say I have inserted two values so we got five and two and let me just insert some more values you know I will just try just to explain this in a better way I would say I want to insert some more values so in this least in this Q we got 7 and three right so we got this values I want to say DQ now so the moment you say DQ what should happen is it will remove five from the from the from the Q so it will remove this five now when you say removing the value maybe you will not remove the value the only thing we have to do is we just need to move our front from this point to this point so we just need to move our front right that's that's enough so I would say hey front just go to two here okay that should work I mean we just have to increment our front so what will do is when you say DQ first of all I want to return return a value so I would say int data is equal to which value the first value and how do we get the first value is by asking hey front give me your value so front will have front will be index number zero so it will give you the first element which is five that simple and then every time you fetch the value of we have to return the data as well so we return the value here but it's not just about returning value we have to move the front to the next location so how do we shift we say front equal to front + one is that simple and once you do that we also need to reduce the size of it so we'll say size minus minus uh we can say size equal to size minus one just to keep the uh same syntax yeah so we'll say size equal to size minus one so here we are saying size plus one here we are saying size minus one that's it it's so simple let's go back here now you can see we have inserted five values and before calling show in fact if I call show at this point you can see it will print all those four values but if I say DQ so if I if before saying show if I say DQ and if run this code you can see we got 5 2 and 7 oh we got a problem here we are not able to remove the last element we have removed the front as well so this is some problem with the front the problem is you are starting from zero and you are ending at size right that's perfect but then you cannot simply say I here you have to say front plus I because we are shifting the front as well right so you you don't want to start from zero you have to start from front and now if IUN this code uh you can see this is what we expecting right we got 2 7 and three we are removing the element which is five it's so simple now if I try to do this one more time if I said DQ and you are guessing it right we were getting only seven and three so if if you onun this code you can you can see we got seven and three so this is how you NQ and this is how you DQ now after deqing it what we are thinking is we only have two elements right so in an array we have only two elements but that's not the case let me prove it let me just add two more elements at the end now of course it should work right because in total when you say DQ in total you have two elements and I can insert two more elements there I can say I want to insert N9 I want to insert one so this should get added right but the moment I run this code we got an error which is array index out of bound exception why because even if you are deqing it you are not removing the elements you are just shifting the pointers in total you have four values there in fact after this four values you adding two more elements just to prove my point once again I will go back to this show and at the end when I say show at the end after printing the values I want want to print the array as it is and the way you do that is we can use enhanced for Loop or we can use normal for loop as well I can say q and then I will print the element of n with a space there now if I run this code you can see oh we got the exception uh let me just let me just not do that here let's say comment and let's run this and you can see we are getting oh okay I just forgot one more thing we just need to put a new line in between so that we'll get a difference and if I this code now you can see you can see it is working at this point because you are entering only four values and the size of the array is five so you're inserting four values you're trying to remove those two values so in total you have two values which we are getting but in Array we still have four elements and that's why if you try to enq two more elements there which means you are crossing the index value which is four five so index value last would be four right but the moment you try to add more elements it will give you error and as you can see we got error at this point you cannot go beyond that point in fact the exact error would be at here because 9 will be inserted because we have space for that not this value the problem is arising because of this real value because if you cross the fifth value which is this one index value this point is four and after that the value for rear becomes five and we don't have any element after that and of course the size of array itself is five you cannot go beyond that at this point I want is I want it to go back on this first one which is you can imagine this array in not as a linear array but as a circular array now this is just a representation so you can imagine we have an a circular array which we have four elements we have the first one in fact five elements uh this third one so four and five let's say we have this five elements so the in so the starting value would be here so this is let's say imagine your front and this is your rear itself every time you add value let's say when you add value five it's here re value will become two here and then seven here and then three here now if you try to match this with the runner what we just have to do is Imagine This is index value zero and index value one index value two index value three and index value four imagine this is how you work with and then after four I want to go back to zero uh how do we do that that's a question so the moment you add these four values we have added those four values and then when you say DQ it simply means you just need to shift your pointer right so your front will be shifted to zero and one it will shifted two times and your front will represent the seven value here so this is your front now this is no more your front now what about the rear value so rear will shift here so this is where your rear is now if you add a value here which is nine it is getting added what about this one the moment you try to add one it will try to go on index number five we should not be going for index number five we need to go to index number number zero that is where you call it as a circular array so after four the index number will go to zero that's it if you can achieve that your job is done oh now that's a question after four how can you make sure that your value becomes zero um okay so let's try now when I say uh zero so can I apply this operation because when I say yes so when you say 5 Mod 5 will give you zero right because 0er is a remainder so 5 Mod 5 is is zero now when your when your real value is equal to 1 1 mod 5 is equal to 1 uh when your r value is 2 R mod 5 is = to 2 then 3 mod 5 isal 3 and 4 mod 5 is equal to 4 and then here is a Twist now if you say okay now if you say five Mod Five is equal to 0er that's the beauty we wanted zero right and we got zero after that when you say 6 mod 5 is equal to 1 that means we are going to the same Loop so only thing you have to do is every time you perform this operation you just need to do a mod of five so if the size is five you will say mod of five same goes with front every because the front also should be in the loop right so you will say front and you will say Mod Five that's it this is what you do now if I onun this code it should work and you can see it is working oh it's not working still got an exception but why are we doing in a perfect way yes we are but it is giving you error while printing I guess that's the issue if I go back to Runner yes the problem is because of printing so if I go back here in printing as well I need to perform that operation because you don't want to say front plus I you want to say front plus I mod 5 because I don't know the current value of front because it is going in circle so I will run this code you can see it is working you can see we got the value which is 7391 this is the exact Loop can you see that it we got 7 39 and the next two elements are coming here which is one I mean 9 and one this is two is the previous element it's so simple that's how you can work with the circular Loop but we still have one issue what if you try to uh add more elements in fact I will say copy and paste let's see what happens I'm trying to add two more elements which is 19 and let's say 15 so we wanted the value here which is 73 okay these two values because we are removing these two values right five and two because of DQ so these two elements and these four elements in total we have six elements let's see if it is working and oh it's working you can see there's no problem and you're it is getting increased oh that's weird can you see that the elements the size is five and we are getting six values it's because of the loop so till this point we have seen how to add the element and how to remove the element from a que we here to add some methods some methods like size of the Que then we want to know is the Q is full or we want to know is the Q empty let's start with the two size method or the size method so I would say public so return the size so I would say size or maybe get size will make more sense okay now what it will return is simply it will return the value which is size that's it it will say return size and now if I go back to Runner and after doing all these things you can see I'm adding four elements and I'm removing two and then again I'm adding four elements so in total we have six elements there and unfortunately the size of our array is only five let me just remove this as of now so you can see we have four elements here we are removing two and then we are again adding two so in total we have four elements there now if I want to know the size of course I want to print the values but I also want to print the size so I will I will say system out. print Ln and here I would say uh the size and then I will print q. get size so it will print the size as well as well and let's verify it is working and the moment I this code you can see we got the size as four and that perfectly makes sense because we have four elements there now let's use is full or is empty method so I would say public now how do you know if your if your Q is empty so I would say public Boolean is empty so the way you know that it is empty is by returning if the size is zero so we'll say return size is equal to equal to zero if it is zero then of course it is empty right so that's what we are doing here now how do you know it is empty so let's go back here and I will not add any element I will not delete any any element there or maybe I will add two I will remove two let me just comment so you can see we are adding two and we removing two and after that if I say system. out. print I would say Q do is empty so of course it will PR uh true so if I run this code you can see we got true but if you add a value and if you don't remove it let's say if I UNC commmand this part and if I onun this code you can see we have one element there so it will print false so we implemented is empty as well and now let's go for is full so it's very easy let's go back there and say public bullion is full and here we just need to return if the size is equal equal to five because the Q size is five so we'll simply specify size equal equal to five in case if you're making Dynamic then you can also use a variable there let's go back here and you can check if it is full so we have done with the empty let's go with full and in full what I will do is I will add some more values I will UNC commmand this part and I will uncommon this part because I want to add five values and I don't want any any removal so you can see I'm adding five values there the moment I on this code it will say it is full true but if I add only four values you can see it will print false it is not full so we have implemented is empty is full and get size now how it will be useful now instead of using size here we can also use methods normally this is what you do in Java you always use methods to get the value so you will say get size equal equal to Z or you will say get size equal equal to 5 so normally we check with size that's one thing the next thing would be whenever you want to add the value so before adding the value we have to verify if it is not full so we'll say if we have to do we have to do this only when it is not full so if it is full how do you know if it is not full so we'll say is I mean not is full then only you have to execute this statement otherwise you will print else message you will say else and you will print the Q is full and here also okay we have to just format the code to look at good and in DQ as well we want to remove only when it is not empty because if it is empty then why what you will remove right so you will say if is empty and this code will be executed only when it is not empty otherwise you have to print a message so I would say first of all this format that and in else part I will print Q is empty simple right so here we are checking it is full or is it is it empty here let's go back to Runner and I will try to add more elements now so you can see I'm adding six elements there and the moment I run this code you can see it will print the Q is full for this element here and the size is five and you got all these elements so that means one is not getting added now what if I delete the element let's say if I don't have any element in the queue and I I'm trying to delete the element so of course if the if you don't have any element of course how can you remove that so if I run this code you can see it prints Q is empty so in both the scenarios Q is empty so yeah that's how that's how you implement this methods so recap we have get size is empty and is full and this will be used to check before adding the element and before removing the element and in this video we'll talk about a tree data structure now we have talked about link list stack and Q now tree is another ADT now if you talk about tree it is basically a structure where it's similar to linklist you can say so in linklist what we have is let's say if you have a node node and you have B node so what happens is a node will have a reference of B node right and then uh B node will have a reference of C node so we have this in linear format in three what we have is we have the almost similar structure but then with with a difference in three we normally create a structure like a tree but you can imagine a mirror image of a tree uh normally in tree we have Roots we have branches we have leaves in the same way if you talk about a tree here imagine this is a root node this is a root root of the tree and this a instead of having one reference may have multiple reference in this case I'm creting three references so a will be knowing about b b will I mean a will be knowing about C and then D so after a we have these three nodes maybe this C itself will have more some other nodes let's say we have X and here we have y and maybe this D has one more node here which is maybe K so K so we have all this all this nodes here now this is the topmost node right so okay everything every box here is called as nodes so these are nodes here and this the line between these nodes are called as Edge so I would say this is Edge so we have this as node b x y z all are nodes and then this is Edge and the topmost is called as a root node because this is where your tree is getting sted this is your root node now if you talk about this a so a has a node which is b a a has a node which is C and A has a node which is d right the same goes with c c has X and Y but what about this K what about this Y and X we don't have any other further nodes here and in fact b as well we don't have other nodes so this nodes are called as a leaf node because we don't have anything at the end of after that so the topmost is called as root node this is where you will start your travel Cal if you want to store data as well you will start from the root node and then you will go down and down and down so this is your node and then the end nodes are called as Leaf nodes so these are normal nodes in between but then a has a special name which is root node now this is about tree this is so you can represent this with different languages using Java C C++ python now with this we have a very special type of tree which is called as a binary tree now what is binary Tre means now binary means two right so if a node so let's say if you have a node which is a and if this node has two Moree nodes like C or D so maximum if you have two nodes this is called as a ban nodes so we have two nodes so ban nodes and that's why the tree is called as ban tree where every node will have Max to Max two nodes so either we can have a zero node or we can have one node or we can have two nodes not more than that so this is how you represent your ban tree now in fact in ban tree as well we have certain certain types let me just write it here so we have certain types in banet tree so first one is strict banet tree so we have the first one which is strict binary tree now what is B strict binary tree means a tree where and every node will have two sub nodes or no children so and again we have one more term here so the C and D are called as childrens so if I have a here and if a has two which is C and D then this is called as a stract banet tree in fact you can also have inside C we can have two more nodes let's say we have X and we have y this is also a strict banet Tre now you might be thinking about D so yes we so when you when you say strict it means either two or no children so here you can see we don't have any children to De now how about if I say we have let's say x has one more child let's say K now in that SC this is not a strict B Tre because we have only one element or one children node for X so this is not a strict so let me remove that so this is the first type the second type we have is full binary tree now what is full binary tree means where you have a you have a tree where every node either either has two I mean they will be having two sub nodes example we have C and D again and D has two let's let's say we have X and Y and D should also have two more nodes so so that they will come on the same so let's say we have p and Q here right so we have D also has two more nodes which is p and Q so a has c and d and c has X and Y and D has p and Q so all the leaf nodes should be on the same level so you can see they on the same level so this is what you call as a full B tree where all the childrens are of on the same level the third one is called as a complete banet tree when do you say a b tree is complete it's very simple where you have a tree where all the nodes are on a level so let's say if I if I Define it C and D again and here if I say X and Y and then V so this is also called as complete B tree because you have all the all the leaf nodes or on the level so let's say this level is let's say I will I will call this level as l so either it should be on L level or L minus one now which means if you have one mode here or two mode here let's say we have K and we have C now this is not a complete binary tree because the leaf node are on the are not on on L and L minus one because if I say this is L then this is L minus one but this is this will not work so there should be two more nodes here then it will be called as complete B Tre right so this is not a complete tree so if I undo so this is a complete binary tree now let me draw a simple uh simple tree here so if I say we have a and then we have B we have C and then we have inside B we have D we have e and inside e we have F and we have G and then I will draw a line here so these are all my nodes and inside this F also we have two more nodes here let me just draw it uh let's say this is X and this is y so now looking at this tree we have certain terms here so again this is a root node right so this is your root node and this c g y x I mean X and Y and D those are your Leaf nodes now we have to remember two more terms which is height and depth now what it means so depth means let's say if you talk about this e so what is the depth of e it is a b and e so that's a depth of this e what about the height of e so height would be it's the The Childrens of e so we have F and we have X right maybe this x has two more uh two more two more sub parts here let's say we have K and we have l so now for for E it would be f x and K so this is the height of e so when I say the depth of e would be two so we have so we have two because it is a and b right so A and B those are the two two two notes we have what about the height of e it would be f x and K so it will be three so right so three height is three now what about the depth of a root node it's always zero right because this is the first element so we don't have any depth what about the height of a root node is it again you have to say a b e so we have to go for the longest one so it is a b e f x and K so it's 1 2 3 4 5 so height of this tree is five oh that's a new term now so we we know the height of the root node right so height of the root node is same as height of the tree or you can say height of the tree is same as height of the root node so that's how you we have this two these two terms are important when you go for the coding part so yeah that's it that's what your tree fun tree thing is so we have talked about what is tree we have talked about B tree now we'll doing the implementation of this using different languages so I hope you enjoyed this video let me know in the comment section in the theory video of tree we have talked about different types of tree and we when you implement this we are going to implement that with the help of binary search tree now what's the difference between binary tree and the binary search tree binary search tree is a binary tree the difference is the way you add values now in binary search tree what you do is you always make sure that the smaller element is on the left hand side and the bigger elements are on the right hand side that means if you talk about a root node the elements on the left hand side of a root node will be smaller than the root node and the elements on the right hand side of the root node will be bigger than the root node is that simple that means when you try to create this tree how will you do it so let's say we have this values here now when you work with eight8 becomes your root node okay that's so simple you always get your first element make it a root node next you have seven now seven is less than 8 so it will go on the left hand side so that is eight seven here then you got 12 now 12 is bigger than 8 so it will goes on the right hand side now of course for the root node both the nodes have been covered what about the next 15 where 15 will go of course you cannot create a one more node here that's not possible for for the binary tree so what you do is you travel now where to travel left or right now 15 is bigger than 8 so it will go on the right hand side but we already have 12 there now 12 have an option of putting 15 left or right now since 15 is bigger than 12 it will go on the right hand side so 15 goes here next element is two now two is smaller than eight again we starting from root node so starting from eight it is smaller then it goes to seven it is smaller it goes on the left hand side of seven which is two here because it is Les less than seven next we have is five so we got we go to eight it is smaller than 8 we go to seven it is smaller than seven we go to two it is greater than two so it goes on the right hand side of two so five goes here so this is how the ban search tree works now once we got the basic understanding let's start the implementation if I want to code that first of all we need for sure we need a class called node right in fact I will not be writing this here let me just remove it what I want is I want from my main method basically I want to create a binary tree there are some in classes but we're not going to use it so let's say binary tree and we'll call this as a tree equal to new binary tree so we want to build a binary tree okay you can see we have some inbu methods we don't want to use them so let's use aary tree we don't have this class yet so what I will do is I will just go back here and you can see is importing this package we don't want any inbu things so if I go back here and if I say hey I give me sus more actions I want to create this class but iing the same package and you can see we got it I will just move this on this side I don't want to see the project structure so you can see on left hand side we have a main on right hand side we have a one tree so basically in this binary tree I want to do all those stuff now when I say I want to do stuff basically we have to say tree dot I want to insert value in this tree so I can say insert and I can pass the value let's say 10 I don't know what values I'm passing here or maybe I can I can f the same value which we have in our notes so we have 8 7 12 15 2 and 5 let's add that okay but unfortunately we don't have have this insert okay so what we need to do is we need to create this method called insert inside this B tree and you can see we got insert method okay but when you say insert that means we have to make sure that you're inserting a node of course you're passing data here but it should be added to a node right and we don't have a node implementation yet so I can create a node implementation by saying class node now what every node will have now if you go back to link list a node will have two things the data and the next value now in terms of this node here which is tree node it will have three things data the left node and the right node so I can say int data then we have to say uh node because when you say right node left node they are itself nodes right let's first write left and then right so yeah so we got data we got left node and we can we got right node I think the only problem is in some of the class I think in linklist we already have a node here that's the problem so what I will do is let me just move B tree and this main to some other package I I will just just move B to our package let say package com. telescope. three so sometime you have to solve the problems in a go need to import the package from here now importing done okay so problem resolved the problem was I was having two classes with the same name in the same package I just moved it to different package okay so now uh you don't have to do that if you're just writing the binary code you can just skip this line anyway so we got a note and then we are referring to left node and right node so that's not done but also what I want to do is maybe when I create a node I will I want to have a Constructor here which will take the data from me and I will assign that data so I can say this do data to data and that's it so we are basically done with the node concept but how will you implement this tree so every time you want to insert the data in a tree how will you do it so if you say this is a tree of course we don't let's say we don't have a tree here and let's go with the same value I don't know what values we have I can just use this copy okay so we got this value so if I want to draw a tree so let's say someone is giving you the value eight initially so what you do is you create a root node now we know that we don't have a node in the tree so basically the tree is empty in that case you will make this as a root node okay so how do we do that so when you say insert basically we have to create a root node that means every tree need to know about only one thing which is a root node right as I mentioned before for a tree the most important thing is root and then tree don't have to worry about other nodes the no root node will take care of the next two nodes so what I can do is I can say node root and then every time I create insert and then imagine that this is a first time so what it will do is you will create your root node here so you can simply say root is equal to new node that's how you create a node just create the object and pass the data and that's it you got your root node in fact you know instead of using this variable as I it should be data it will make much more sense so now if you can see our code this is the thing we have done so we created a root node called 8 and that's your root node which which looks good but then what about if I insert one more data here so if I say three insert I want to insert the next record what's the next record is seven so when I insert seven where the seven should go now don't you think the seven should go on this side is because we are implementing B search three s is less than 8 so it should be on the left hand side so when I say seven it should create a new node and we are doing it you can see every time you say insert it creates a new node but don't you think this time is not a root node it's a left node of the root node how will you do that and how do we even know that this is not a root node so in that case we need to do is we need to check if the root is null then you create a new node I mean then you create a root node otherwise you don't create root node every time so root node will be Creed only once if the root is null what else if it is not null then we can check for something else now see if you talk about eight yes this satisfies is because root is null till this point when you before executing eight but when you insert seven we already have a root node right then we have to go for if Els now the question is now we know that this is not a root node we have to either go for left or right so what you do is you basically check for data if the data is less than root. data then you go on the left hand side so when you say you go for left hand side what what you simply do is you say root do left do daa is equal to daa that's what you do but then we have one little problem here because see this will work for this data okay so we will get new new uh things but we not even creating a new node okay so the problem is we need to modify this to something else why something else let's say we have adding one more which is 12 goes here and then we add 15 now by our logic if the value is greater than root node just add it to the right hand side but 12 is already there right then we have to move to 12 and it becomes a right hand side of 12 that means we have to jump from root to the next element and then the next element oh that's a recursive process now so that means we have have to add a recursion here that's one thing second problem is every time you insert data we need to get a hold on root you know writing the logic here is not efficient way what we should be doing is create another method which is called let's say insert Rec and we'll say this will take two things because when you want to do recursion we have to get a hold on root element or root node so that means we cannot do that in this insert because the moment you a recursion every time you call the method we need to get the hold on the Node where you're calling this so this will not work but that doesn't means we have to remove this I will tell you in sometime why so basically we have to say node root comma data and here okay this should return on node because we are going for recursion so it should return something and now here instead of doing all this logic this logic should be a part of this not this so here we can simply say root is equal to insert record so every time you call insert it will call insert Rec in which your passing the root node and the data so when you say recursion it will go into recursion we will be using recursion on insert Rec not on insert so we have to change some logic here so this is correct when you say root I'm only concerned about this part so how do we implement this one so when I say I want to add element on the left hand side so if you have let's say two now we know that two should go here but then we have to jump from 8 to 7 7 to two that's a recursive recursive process right so what you will do is let me uncommon this now this is not how you do it so basically you say root do left and then you call the function once again by passing The Root do left because now we we need to followall the tree right as I mentioned before when you talk about the sub trees if it is not eight left then we have to consider this sub tree now this seven becomes your root so how will you send this as a root so you have to say root do left now this becomes a new root so when you call this function which is insert Rec here this becomes your new root and then you have to pass data as well so you're passing data but what if this is not smaller then you have to go on the right hand side so you have to say root. data if data is greater than root. data then do the same thing but for the right hand side so we will say paste here so this should be right and this should be right and then at the end you know your root node so just return root that's it so this is the recursion call which we are getting here so that's how basically you create a tree now this is tree is created but how will we know that this tree is created we want to print also right and the way you can print it is like this so if you want to print this tree so let's say we have this tree here and this tree is created by the way we have defined this example here how will you print this now to print we basically have to Travis or we have to travel to different elements here the way you do that is we have different travel cell for tree so when you talk about tree travel C uh we have to follow certain things first there are three three options here we have in order traversal we have pre-order traversal and we have post order the difference between these three is the way you print your root node okay so when you talk about in order basically what you do is you first go to the left then you go to the root then you go to the right so which is 7 8 12 when you talk about pre-order here you first go to root which is eight so it will print eight then seven which is left and then 12 which is right when you talk about post it means first it will go for left then right then root which is 7 12 and8 okay that's your post Auto traversal here we are going to go for in order so in order simply means first you print the left one then you print the AL not exactly printing but you go to the left one then you go to the root node and then you go for the right one so that's your in order now the way you can do that of course this is also recursive right uh so in order to do that whatever I will do is I will create a function called public white in order then you can work here but then since we know that in order is actually or traversal is basically a recursive operation where you go to it sub tree and print it or do some operations for the recursion I will create another method which is public void is because I don't want to return anything so I will say in order Rick so here we just want to print it now when you say print it how exactly we are going to print how we going to travel this of course the output will not be similar to the Val we have inserted it will have a different order so what it will do is first it will go for it will print the left one right so when you start from here it goes to eight but then we cannot work on the eight because that's a in order then you go to the left one because in in order you first go for left hand side left sub tree and then from Seven also you can't print seven because seven becomes a root node for the two so we have to go to two now we don't have any left here right this is empty so in this case you will first print two okay so you will go for two then you go for right since we we don't have a left we print the root node because we are considering this sub tree now so you will print two and then you will print five so here we have five then you go up then you print seven because we don't have anything so that's a parent for two so we'll go for seven then we print on the right hand side we don't have anything right hand side right so this is empty then you go up you print eight then you go for the right hand side right hand side is 12 on 12 left we don't have anything so it will not print anything but you can print 12 and then you can go for right hand side which is 15 and if You observe you got a sorted values so that's why we use BST which is sorted values is is easier to search as well okay this is the in order traversal okay so let's implement this so how do we do it so first we'll start from the left hand side but also we want to verify if the tree is empty if the tree is empty how will you print something how will you travel and how do you know if the tree tree is empty by using the root element so we can simply check if root but how do you know the root because root will keep changing depend on tree right uh uh so we have to also accept root here so we'll say node is root and then you check if the root is not equal to null then only you do it now how will you do it now first of all this is a recursive function right so basically you have to call itself so we'll say in order right and then you have to start from the left hand side so always start from left and then keep going till you find the last left element okay and then once you do that then you have to go for the middle one middle one is root itself which we got here right so we can print this value here so I will say print and if You observe for every node for every sub there is always a root node If You observe for eight seven is Left Right but don't you think seven in this sub tree is a root node so that's a root we are printing when you go to two two becomes a root node right when you go five five becomes a root node for their child which we don't have then we can so we can print data here so we can say root do data and then we can print a space in between as well just to differentiate the values and also I can skip the new line now once you have done with the root element of course not just printing you can do some other operations as well maybe you can add all the values if you want and then here I can say in order but this time you will go for root. WR that's it this is how basically you print the values but from in order we have to call in order Rec by passing The Root node so you will call this only once in order so that means I can simply create a tree by adding values here first of all now what values we have let me just do that quickly okay so you can see we have added all the values and now it's time for traversal so I will just print in order and it should do the job for us let's try so I will just run this and you can see we got the values we got 2 5 7 8 12 and 15 that's what expected it is printing in order but let's say if you want to do Post order so what I can do is I can just change their names or maybe I can say pre-order so I can say preorder and of course everywhere you have to do that now the only change you have to make is in pre-order first you print the root so that means this line will go up that's the only change you have to make in pre-order okay nothing much let's run this and see if this works save this code and run and you can see this is now pre-order so root element is something which will get print first I think this is the sequence in which we have added no what different sequence but anyway you got the point so this is pre order you can also do it post order let me know in the comment section if you have done that and yeah that's how you implement tree

Channel: Telusko

Views: 389,963

Keywords: telusko, navin, reddy, tutorial, Java

Id: xWLxhF3b5P8

Length: 307min 11sec (18431 seconds)

Published: Mon Nov 06 2023