Transcript for:
Java Collections Framework Tutorial

hey guys welcome back to my channel this is riti datta and I am back with my tutorial videos and this video is going to be my first video of the Java series the video on the series will not only help you to crack the Java interviews of the top radar companies as well as service companies but it will also help you to you know grasp the different concepts of java which will really really help you while you will be working for any company so now this video is very specific to DSA and uh this video is basically on the collection framework so I'm going to cover the entire collection framework in this video that is actually required in a day-to-day life while you will be working for a company and also it will be required specially for tracking your DS interviews so after solving multiple DSA problems in Java and cracking and giving multiple uh coding interviews for top tech companies in Java I am making this video you know compiling all the experience that I have and I'm going to exactly tell you that what are the things that you need to learn in collection framework step by step so that you don't you know get too much intimidated and I'm going to show you the implementation side of things as well and if you don't know anything you just know that Java Basics like loops and inheritance in this video is definitely for you trust me by the end of this video you would be able to understand uh like how can you apply collection Frameworks uh to solve your DSA problems in Java not only DSL will also help you to apply collection and understand code base of you know the companies where you are working on right but most of this would be specific uh for the TSA part I'm not going to cover all the interfaces and classes that exist but I'm definitely going to cover all the important topics that are required and that are used mostly so trust me by the end of this video you won't be having any issues solving DSA problems uh using Java Collections framework so without any further Ado now let's get started and we will get to know more about it in the video so first of all let's understand what is a connection right so a collection allows a group of objects to be treated as single unit now we will jump into this definition a little bit later while we actually start working uh with the collection framework right so the Java Collections uh framework provides a set of standard utility classes for managing various kinds of collections right so framework is provided in the Java util package and it comprises the three parts the core interface the set of implementations basically which are the implementations of the core interfaces and some static utility my collection and arrays which we are going to see at the end of the video so first let's take a look at the core interface right so I saw the top of the chain of the collection chain there lies this iterable interface now I know this is a little bit of theory so please bear with me because if you understand this part really really well then a lot of things down the video will be very very clear for you and also remembering the methods and classes would be really really easy for you right so also you can understand it how collection framework leverages the concept of interfaces right so even if you don't understand like why interface is required in the first place so this video will also help you to clear all those relatable Downs as well right so you'll understand a lot of things so just just bear with me right I don't don't get too much intimidated by the theory or get bored by because these all these things are very very important and trust me I've compiled this video in such a way that only the important parts I'm going to hold it out so now coming back to the video uh there is this iterable interface that sits at the top of this collection chain and this iterable is actually as you can see it's not a part of the collection framework it is a part of the java.lank package right so what is iterable and why do we require it we are going to come uh to it uh later in the video but first let's take a look at the the core interfaces of connection so now you see the a collection is an interface right and it is not a concrete class by the way so you can't instantiate a collection right so collection extends an iterable why it does so we will see it right later in the video and then from collection we have a list interface we have a queue interface we have a set and these are the three interfaces basically that extends a collection right and then a queue is extended by a DQ we are going to see all of these interfaces and their Concrete implementations in action then there is this uh set which is extended by sorted set and then the sorted set interface is extended by the navigable set so just to give you a family duty to get started so once we touch this topics or once we touch this interfaces uh towards the later part of the video you don't get too much surprised okay then we have a map which is again an interface which that is kind of extended uh by a sorted map interface and then a navigable map just like a software set you see on a navigable set a navigable map extends a software map and sorted map extends the map interface right okay so one thing to note over here that this map interface it is not extending a collection interface like the list Q or a set it is pretty much you know like separate and we would see why it is so also uh if you see uh this interfaces normally we see a class implementing an interface implementing an interface right but if you see here is an interface which is extending another interface so interface extending another interface is very common in Java and that is basically you can consider it as a class extending another class so when a class extends another class what it does is so whenever a Class B extends a super or parent class that is Class A all the methods of his parent class are now accessible by the child class and similarly then when an interface like when a child interface extends a parent interface all the methods that are there in the parent interface uh Jack would be there in the challenge interface as well on top of it the child interface will add a couple of more methods so as a result when a particular class will implement the child interface it has to implement not only the methods that are there in the parent interface but also it has to like Implement all the methods that are then the child interface so these Concepts these are basic concepts of java so just in case you don't know I'm just you know stating these things so that it you don't get confused as we go further in the video so now you see that uh if you want to go to the implementations so you can see there is this iterable class then again the interface extends the editable right and then uh this uh collection has an iterator right as an iterator interface and then this there's a list iterator that extends the itinerator we will see all of this don't worry but if you want to see the implementation side of things let's quickly see the concrete classes part so a vector and an address implements a list right uh linked list implements both DQ and the list so priority queue implements a queue and a queue extends in queue right and has set implements a set and then it has that extensor has set we are going to see all of it in action right and a tree set implements a navigable set and an error Deco implements a DQ so now uh let's see for the map so for the map you can see the hash maps and implementation of the map interface and the tree map is an implementation of the navigable map interface and the linked hashmap is also a class that extends the hashmap class you're going to see all of it in action between okay now let's start with it so let's consider in use case right so we will see that why do we need iterators in the first place so now let's say we have a genetic list we have created our own genetic list so basically uh this is nothing we are just going to create our own list and as a result down behind the scenes we are going to create a normal array right that we are doing here with a size of 100 and which is maintaining the size of that list right so the current size of the list and we are maintaining an array right so in order to like maintain a list we need to have an underlying data structure right so that is basically done by normal array right now one thing um this is basically a generic list so this T like I know many of you don't know Java genetics and this is something I would cover if you if you are interested I would cover genetics in one of my later videos in the series so do let me know if you want to have like understand genetics from very scratch and I would be more than happy to make a detailed video on it and I personally feel that under for understanding collections uh you need to understand genetics the genetics are the building block but if I started with making a genetics video trust me you guys wouldn't have watched it so that is why I started the collection so that at least you can start solving the DSA problems using the framework uh collection framework and also you can like it is just a quick start I can just see but uh in order to understand collections in depth because I won't be covering all the methods right I mean I would be covering all the important methods and 99 of the case of 99.99 all this video would suffice but let's say one or two methods here and there you want to read about right uh yourself and then you record the documentation then you would come across these you know genetics things of java in collection and then you might get super intimidated right and that is because you don't have an idea about generate programming Java in this video I would be trying to you know give you the basics so that you can follow me along the video but I personally feel that you should know Java genetics and probably that will be a video for the next topic but I will be actually teaching you Java generated from death and then these things would be a cake for you right so but for now don't worry uh and I would help you to follow along with me and uh I would like make you understand the things that you would come across so that is not going to be a big thing but yeah understanding genetics should be a priority once after you're done with collections right because then you would be able to understand things properly you would be able to read documentation properly because here what I'm doing is I'm reading the documentations and I'm presenting you two in a format so that you don't have to understand a lot of things in depth but when you have to go and read uh a different collections then you might face issues if you don't know genetics you won't be able to understand the methods signatures and all and that is why Java genetics are very very important people generally don't talk about it they directly jump to the collections because these type of keywords really sells uh but yeah I mean I personally would suggest you to learn Java generics but not now after we finish this video I would come up with a Java generates video from scratch I would be telling everything more Java genetics all you need to know and yeah you can watch the video and then I think it would be good to go so whenever you're trying to instantiate this our genetic list right uh we would be saying that okay this is a genetics list of integers or we'll be saying that it's our generate list of float or a double right so then this T that is the placeholder would the company calling it so in action very soon so let's say if you want to create this our generic list right if just this is let's say you want to do it with an integer okay so let's say this is the list okay okay and let's say new our generic list and that's it okay okay we are done so whenever we are saying it's an integer then this T the compiler will replace this t with an integer okay uh normally actually uh like when the compiler compiles it there's a tile per ratio that happens and then it gets converted to object uh class and all but we are not going too much into depth and I would be covering in the Java generates otherwise it would get confused so for now just consider this T is nothing it's just a placeholder for so that it so that Java compiler allows any type for this particular class that's it that's it nothing else and just uh remember this concept because we were using this a lot throughout the video right and also one more thing since Java 1.7 we don't need to put the integer on the on the right hand side so if you see this is the error that is coming so if I change this so that you can see that is not allowed for Source level below 1.7 so if you change it the project compliance to 1.7 and above so let's see this error is gone so basically before Java 1.7 we have to all we have to also you know uh tell the type over here as well but now if we just provide the type in the left hand side we don't need to provide it on the right hand side so that's it okay so now coming back to our code so we have this array of items we have the size right and we have instantiated this items to some like size of 100 let's say and now we are going to have an add method so we can add items right and we can get items okay so now you can see I've added two more methods that is uh the add a method and one is the get item at index so these are two simple methods we're just adding an item to this items array and you are getting an item right at that particular position okay so this is our own generic list right now let's go back uh to here and let's add some items right so let's say we add one and also let's say we add two let's add three okay now let's say you want to iterate over this list and do something how do we iterate over this list let's say we just use a for Loop can we do this no it will give us an error it says can only iterate over an array or an instance of java.lang dot ID we'll come to this but for now we understand that there is a problem we can't like iterate over the list right the reason you can't do this is because if you go to this class we don't have access to this array right we don't have access to the settings so now one thing you can say make this items array public and then we can access it from outside the client can access it from the from here right like list dot items but that value is principles that violence the encapsulation principle uh because you know one one concern is that using this items right we can like set or we can change the contents of the array from the outside which is actually a very uh bad thing to do and also let's say today we are using an array a generic normal array you know to uh like uh like maintain all this generic plus class next take if I want to change the implementation details I want to change it to an error list right then this particular code the client code will fail because uh one simple reason is an error list in order to get one element uh at a particular place you you use the dot get method but for an hour you don't have that right so basically the crust is that this our genetic list class I should only expose the functionalities I should not be exposing uh the implementation details my internal implementation details because I can change it the way I want but that should not affect my client's code right because that is very very important so that is why I really can't you know make it public that we are very backed into so now the question is that how can I now delete over this list there needs to be some way so that I can either it over this list and to help us with that our friend ital interface comes in so now what we have to do is we have to implement this either bill interface right that basically says that hey this class is an iter level that means you can use a for Loop to iterate over this class sequential or an object of this class sequentially so now it gives an error this error is because we have to implement the methods of the identical and you see that this method basically returns an iterator so once you implement an iterable you should you should Implement a method of this class that is an iterator which basically is nothing but gives you an iterator back to your client and your client can use that iterator to either it over the collection right or the list whatever is it so now let's look at the iterator interface like what exactly this is right because we have to return an object that implements this interface so you have to understand what exactly it is so this ID reader basically is an interface and it has three important methods one is has next and next right two important methods sorry so these two methods must be implemented right so whichever class implements the interface right they should Implement these two methods now has next method basically tells you that whether there is any item left in this collection right there is any item left in this uh all in this class and next is basically give me the next element in this collection on this whatever is it I will say collection because a list is one part of collection there will be other types of collection now so now we understand we have to return an object that implements this iterator and implements to those two methods that is next and has next so what we do is we create a class a private class my or our generic list iterator this is a class that implements that implements right because that is important and it should be of object of type T right and I will tell you why I need this private I made this class private because see this is an internal implementation of this like this iterator belongs to this class so I I don't want this class to be exposed and my client doesn't need to know that how am I exposing my italyters right my client should get the italyt that's it it doesn't need access to the class and that's why I'm making it an inner class and also private class so again there's an error so it has to add the address to implement the two methods that is has next and next right so how do we do it so to edit over this you know list right we need to have an instance of this object right so that's why you would have an instance of this object of Type e okay now inside the Constructor we just pass this list and uh yeah so we will just pause this list so this dot list is list date and here whatever what we're going to do is uh how do we understand it whether it still has elements right so we are going to maintain an index right so this index will be helpful uh so since we would be accessing sequentially so this index would tell us that hey uh where our current index lies so let's say I say give me the next element so index would initially be at zero right so it gives it will give you the element at position zero and then the index will move on to position one so next time again call the next it would give me the element at the index 1 and it will move on to index two we will see that in action right so but first let us see the has next in action so it's time it doesn't index and what you would do is you will just check that if a return this has to be a Boolean so return index less than um list dot size that's it cool and for the next what you will do is return uh list Dot items here we are accessing the inner attributes of the of this particular class but that's fine that's absolutely fine because this class is a private class of this class right so that is why we can access the private methods right and there is no harm in doing it right because this class is a part of the this class right this this iterator class is a part of this class so that is why it is fine to access uh the inner attributes of this of these classes and therefore it doesn't violence any principles right okay so listed items uh and then we do an index plus plus see I'm I'm like writing our own iterated functions and all these things very few few people will actually tell you these things uh but the reason I'm telling you because you are learning a lot of things as well like you're learning other importance of private class why iterator is coming why iterable is coming into the picture because once you understand these Concepts from very scratch you'll be able to remember the concepts right and it would be actually able to appreciate that why these things are happening that is why I'm teaching you in such a way otherwise I could have just you know told you hey this is collection has exposed method and you know I could have done it in a very shallow way but I'm not doing that right and and the reason you would figure out on your own while you get started with collections anyway so these are items index plus so basically what it is doing is it is it is checking that okay give me the current index they give me the item at this current index and then once we return it uh increase the index right so B it is like this only so this can put up in written as end item make also list or items index right and index plus plus and return item that's what it is so this this three lines of code I have written in one line over here okay so that's the thing so let's comment this out okay and now let's see how can we uh okay so now here we have to return uh return an object of this class so return new our generic list iterator and he will pass this object this is this particular object that is an instance of this class right cool I think we are done now let's try to iterate over this class now how will we iterate over this class so now let's get the iterator of this list right so we can Traverse over it so iterator of integer right since it's this this analyst this generic places of integer type um iterator is equal to this now we will use the next and the has next method that we wrote over here right two so basically this will return an object of this type right and we would use the next and the hashtags method to uh iterate so let's import this and why iterator dot has next system.out.20 iterator dot next so that will simply return me the uh the object one by one okay we are not running out of the elements so let's run this and let's see okay so there was this one error over here which I missed uh this is not a function this is uh like an attribute so let's fix this and now let's run our code um okay so you see that printed the list one two three that printed elements of the list one two three one by one right so you can understand how iterator is helping us now I will show you a fun tree okay so all this code that we wrote like taking iterator then you know traversing it one by one this is a bit Virgos and we can sugarcoat it using one line of code you can just comment it down right and using one line of code using the for each Loop uh we can write it like this and this is going to be the same thing okay this basically is going to do the same thing like these three lines of code basically the compiler will convert this piece of code into this piece of code right and to show you and to prove you that that they're going to call the hash next method and the next method I'm going to also do a print here as well so that you understand and you can actually follow that hey this is actually happening so we can just say hacks next called and here I will let's write this out you know next Point okay so now you can see I have like uh add the debugger over here and have uh like uh commented out this piece of code and I'm just using a for Loop now you will see the has next and the next method calls would be happening behind the scenes let's see you see as next called then the next was called then one so you see again this has next was called it was the element was there then the next was called then two and then again the has next was called then and then the element was there then since the next was called and then three was printed and then again has next was called valid event was found and therefore the next was not called and it came out of the model so you don't have to write these kinds of code this for each Loop would suffice right so whenever you see your for each Loop while traversing an analyst on linked list behind the scenes these things actually happen and that is what an iterator and iterable is so to sum up things uh a class which implements an iterable you can use a for each Loop to Traverse that particular collection right or that particular class or instance of that class right and if you are implementing an iterable you have to implement this iterator method mandatorily and this iterator will give you an instance of a class that implements the italyter interface which in turn has these two methods next and has next right cool now you don't need to worry too much about these things you just need to know these things because the collection framework and all the implementations of the collection has these things in store for you it's just for you to understand the internal implementations if this sounds too heavy for you don't worry when we watch this part again but trust me it's fine you don't need to remember so many things because as I said collection framework all the classes in the collection framework has these things done and done for you so basically you just use the forage Loop to Traverse the collections let's get back to the you know the core interface picture right you see the top of this chain we had the iterable interface and we are done with this we are now understand what is what an iterable is and now we understand that why the collection interface extends The Identical interface because a collection interface once the all the classes implementing that interface to actually implement the methods of ID level interface that means a collection wants to see that hey if you are implementing my interface that means if you are calling yourself a collection then you have to implement the iterable interface that is very important because a collection is saying that I am I terrible that is basically what it is meaning in rieman terms and that is the reason a collection interface extends the interface or the iterable interface right so that in turn when and other classes are implementing the client collection interface it also has to implement the methods level interface right so that would make those classes iterable so basically if you are extending or you are implementing a collection interface you have to implement iterable interface that basically means every collection out there is either and I will tell you one fun fact maybe we are going to cover that later in the video you see math is not extending or implementing a collection so that map is not iterable right so now how do you iterate a map that is something we would see later in the video When We Touch on maps and why map is not a collection we'll also see that but for now we can understand that okay since collection is extending and iterable so that means a list that extends a collection a queue that extends a collection is set is extending a collection that all iterables that means you can all use of college local drivers through these collections so if this is clear to you now let's start with the next part of the video so now let's look at do a deep dive into the collection framework so now you can see a collection interface it contains a couple of methods that you have to implement if you are saying that hey I am a collection or I am implementing a collection interface one is the contains one one is the add-on one is removal written on and here right so clearly basically clearing the collections emptying the collections and we are going to see all the methods in action later but just keep this in mind you will see once we uh start with the concrete implementation of a collection uh you see these methods in action okay right so let's see what is the list list basically collections that maintains the elements in order right and they can contain duplicates in order I mean the order of insertion the order in which you insert the elements that way you would get the elements while you would be traversing right the same order and they are position based that means uh you can like access those elements using their position and it follows zero based indexing that is the first position is zero that's just like Aries let's take a look at the list methods that you have so this e is don't get confused by it it is just a return type and return type as in like it can be of any type okay so similar to the T that we saw in our own genetic list this is just a placeholder for the any generic type that's it okay so these are the methods that we have get set and add all and remove we are going to see all of this in action okay so we have to touch upon all of these methods very soon don't worry so now let's take a quick look at the implementations of the list so the three implementations of the list interface are providing the Java util package and they are analyst linked list and Vector okay so yeah Vector is class is also there in Java we are used to seeing vectors in C plus but yeah also in Java you are vectors and we're going to see the difference between vectors analysis and which one we generally do use and why do we use it right I'm going to cover all of that okay so what is an error list let's understand this so analyst is a dynamic array right and it is to be used when we don't know the size of the area right let's take an example so let's say I give you a question there's a DSi question right you're asked to find out all the prime numbers between 1 2000 right and you have to return it in the form of an array so tell now tell me one thing that in order to find out the prime numbers between one two thousand you have to store it in the array that's pretty simple I told you in the starting on the question that you have to make it in the form of an array but tell me how to define the size of the array because when when you would be declaring that array right you have to declare the size of the array as well beforehand but do you know that how many prime numbers do exist you know that before and before you actually start Computing or filling the elements into the array no you don't know right so now here you will see a workaround this is basically you would create an array of arbitrary size of a large size and then you will start filling the diary from the starter right from zero index but in that case if you take a very very large number then don't you think it would be ending or wasting a lot of space right second is let's say you take a number right you take a guess but the number of prime numbers are greater than that then you would run into an exception you run into an error because you won't have you would run into an array index out of bounds exception right so in order to help you with these things where you pre where you don't know the size of the array what what it can be beforehand error list comes into the picture because in error list you don't need to specify the size yeah you can do that if you are very sure that okay this is going to be the size of the array but if you don't know beforehand that is absolutely fine so I would tell you now what Arrow list exactly does right so analyst internally it uses a normal array right and it creates a normal array set to some default capacity so basically it will create a normal array of some default capacity size you can also Define the size uh using the Constructor that we're going to see but normally gently we don't do it right now when the capacity is reached let's say we take an array of 10 elements and those 10 elements are filled up and we want to insert the 11th element then what happens it will create new array of bigger size normally it is 50 of the current's capacity and it then copies all the elements from the old array to the new array and then the new address reference is used for the internal usage so now instead of 10 you have 15 20 elements right and all the 10 old elements are copied relevant element is inserted and the old array is no longer new so it will be garbage collected and it is gone so now you are using the new array of bigger size and in this way the array is dynamically grows in size right so all of this internal implementation is done in an analyst now I can make a separate video where I can show you that how analyst has implemented internally but that if you want such a video do comment down below but for this video like this is the internal working of analysis and it's very similar to vectors right in C plus plus again don't confuse vectors of C plus plus and vectors in Java right you are both both are different anyway this is analysis right an analyst basically implements the list interface it implements the list interface because analyst is a list right that is why it implements there is interface the vector class also implements the list interface but let's see what is the difference right so the difference basically is both use dynamically resizable arrays uh providing first Random Access that is position based access and first list traversal that is very much it's very much like an uh ordinary area it uses an ordinary array right in the behind the scenes but the vector class is said c right and this unlike the errorless class and what do I mean by stretcher it means the concurrent calls to the vector will not compromise integrity so don't get too much into it these will be covered in the multi-siding part of the video where I will be covering later not in this video but really you don't need to get in the confidence side of things here and even in DS you won't need this so vector class just know this exists but it is like pretty much I don't need to know errorless knowing analyst is okay errorless and Vector classes almost provide a comparable performance but vectors suffers a slight performance penalty because of this thread set things and synchronization and all these things right so that is why analysters preferred and we would be using analyst okay uh in our most 99.9 percent of the DSM solutions that we'll be writing okay and then we have a linked list so linked list is also implements a list but it also implements other interfaces as well we will come to that later so the linked list basically uses a doubly linked list uh I'm not going to explain too much what a linked list is I guess you might be already knowing that otherwise if we assumes digression if I start explaining the English and the insertions and deletions in Adobe link list are very efficient right so let's compare an analyst processing case so this is a very very important question guys you would be getting asked an analyst versus linked list multiple times in every Java interview so that's why I'm covering this and you should also know why when you should use water right so analyst versus linked list it's very similar to comparing an array versus a linkage right and I'm very sure you already know that what is an array one what is that number 12 what is the difference in Array and Link this right so whenever whenever someone tells you that explaining the difference in Alice and a linked list you can think of it as an array versus linkage because an arraylist uses an array in behind the scenes so first of all errorless supposed position based access linked list also does that but since an errorless maintains an array the like getting up element at a particular index is constant time Traverse right you can't directly access you can randomly access that particular position it Traverse to the position as a result it can be linear time right so that is why position based access has constant type performance to the address but for the linked list it can be linear now let's say when we want to frequently insert and delete inside a list then link is the better choice why it is because uh you can do that in constant time with the help of pointers but in case an error list if you want to insert a particular element you have to shift the elements and that can take you a linear time right so whenever there's a frequent insertions and deletions occurring within the linked list always uh inside a list always you answer using an English overall analyst is the best choice so whenever we are using list we would be using analyst right so that is one hack I will give you we would be only using link list when you're using layers Stacks use later in the video you'll see that but Whenever there is a concept of array so whenever there is a concept of list so we would be totally totally using error list that's it let's make things simple for you okay and as I said in addition to the list interface the linked list also implements The Deco interface uh that allow it to use for stacks and different kinds of views which are going to cover in the later part of the video but yeah uh error list only implements a list but a linked list implements a list a DQ as well now let's quickly jump into the error list code and see error list in Action a lot of theory I know it has been covered so now let's create a arraylist okay so I'm going to comment this out and I'm going to create an arraylist so we always want to code against the interfaces right if that is the best practice always so that is why since analyst implements a list I am going to store the reference in the analyst object inside a list okay okay and we will implement we will like uh import the list from java.utel and this is the analyst you will create this arraylist and we will just add elements cool so let's add the elements one by one let's import the address from java.utl cool okay so again yes you can understand add method simply as the error list okay and also we can iterate over this list right also we can directly print out this analyst so let's do that only says out and we can do this because obviously we know that the tostring method of this class is implemented or virus is obviously implemented and that's why we can do that so let's print this out right if you have any doubts comment down below and I would be more than happy to resolve it uh okay so you can see that one two three got printed that means error is got printed so you can add elements like that now let's say we want to change a particular element like let's say you want to change this element at position one right so we use a set for that and we let's say position one we turn to change it to 100 so it would be changed and this set function or set method basically returns you the uh element the previous element that got changed so basically two got changed to 100 so this will return true although you don't really need to do that I know that because it is not of any use but just in case we want to use it it's better to know so I'll just paint it so let's see element that got replaced is equals to okay so let's quickly and yeah let's run this you will see the element that got replaces two because two was at position one and now the new added has been changed to arraylist is changing to 103. okay now let's create another error list and I'm going to show you a very interesting thing so let's create analysis too we're going to create a new analyst but let's see that we want to create this alst to the new wireless from the previous analyst or basically you want to create a copy of the server list so one way of doing this is like going through this elements one by one using the four is two because it's an iterable and adding the elements a list two dot add the elements right but um we can do this in one line so basically this errorless class takes in a Constructor where you can pass any collection so since error list is also a collection so we can pass um this a list and now if you just print this a list to you would see okay there's an azure here okay cool now let's print this you would see the like this element has been copied right uh now if you want to add elements to this you can also add right so add you know four and you can and then if you want to print all both that list explain both the address so now let's run the code see see this error list has one two three we then made a copy of this particular analyst and then we added four to this right and also uh please note that this is this second analyst was created as a copy so whenever we are adding a new element that is not getting added to the first address right that's why your favorite root design list so this is one thing second is you can pass an arraylist over here you can pass basically any collection right any collection you can also pass an asset you can pass in any anything that implements a connection so here I just took an example of an errorist right so if you want to create co-create a copy of analyst you can do like this using the Constructor okay one more thing I want to show you here now this is the concept of genetics is not a concept of collection but still uh instead of this integer you're writing that you're seeing that I am writing this integer with the capital I I'm not writing like this you see this will give an error right this will give an error because it says that you have to come you have to pass a reference type right so in genetics since uh the compiler like transforms this internally into an objective right uh so and since object is a reference type we need to pass or the genetics only allow reference types as parameters now I know this might sound a little bit complex to you so to make things easy for you let's just think in this way that we can only whenever we are working with collections because collections are generic types right generic classes or generic interfaces whenever we would be working with collections or any genetic interfaces or classes we always have to pass references right now to make things easy for you what Java has done is like int float double these are primitive types okay then reference types forever double primitive there exists this double class for float there exists Capital flow so the first letter is capital that's it you get converted in this corresponding reference type and now you can use it in collection right so this basically is called a wrapper class so you can read about it it's nothing much about it and there is also a concept of boxing unboxing uh so basically what happens is let's say here you see that this iterator like this this next method because you see when this is called this next method is returning an element and that is getting captured over here right so this this uh iterator is returning you a type of integer right but here we are using the small end so we are using the Primitive type I mean the compiler does this thing for you so whenever a compiler sees that you have a reference type of integer Capital integer and you want to store it in A Primitive type integer that conversion is automatically taken care by the compiler and that is what is called unboxing right so this is concept of unboxing boxing that you can break probably uh go and read about it but for now don't get too much confused about it right good okay so there is another one method which I wanted to cover so let's say now we have uh let's take this list only and let's say we create a new analyst and let's say we have we are adding four we are adding let's say lst2 dot add five lsd2 Dot add six okay now we uh so this is errorless right we have added four five six okay now let's do one thing Let's uh comment down this line of code and also let's comment on these two lines are good and now let's say you want to add all the items of this particular the first analyst to this second analyst after this you have added uh the four five six right then there's a method uh called add-on so basically here the initially what we're doing is we're creating a copy of that list using the constructors but here we are not necessarily creating a certain elements in our list and after having all those elements we want to add all the elements of the other analyst right and for that is a method called add-on so add all right and again it takes a collection right so here since analysts is also collection so we are taking we are passing this as T so basically what it will do it will simply add all the elements of this alerts to this also second analyst after this six so just print it I will just print it and you would see what is exactly happening so you see we had initially at four five six and then after six one two three what added and again this is a very useful method that you would be using a lot while you'd be solving DSA problems there is also a couple of methods like uh index of like see there are a lot of methods and you can or any time go and read the documentations of the of the Java Oracle docs but I'm going to cover the important methods right that you would be reading uh needing in data action so there's this index of methods which will give you the index of a particular element so let's say uh that okay so if let's say you want to find the index of 2 so 2 is at index 1. one more thing just one just wanted to show you this index of method what does it take it takes a method of object so ideally uh we can't pass a primitive type so ideally we should have passed an integer like this right uh we should have passed an integer like this but we don't need to do this because as I said instead of if we just directly pass to the compiler will automatically compile it to New integer like it will automatically create the wrapper class for this particular integer class so these things you really don't need to bother these things are taken care behind scenes and this is what boxing and unboxing are also there is a method last index of so basically when you have multiple elements let's say again you have like let's say I want to again add this element to right so in this here instead of if you use the last index of element it will now return because since 2 last was found at this third index so it will print three this has been treason okay so now also there's a method called sublist so let's quickly look into that so sub list is basically a little chunk in narrow this is a slice analysis right so let's say now we want to create a new error list let's say hereless T3 is equals to alsd 2 Dot sub list and we want it from index 1 to index port right and we want to print this lsd3 okay so what will happen is right now L is to lst2 has 4 5 6 1 2 3. 3 right that that's what it has right and now I want to like take a sub list from one that is from 5 to index 4 that is this is like one two three and this is 4 but it won't take 2 because this is exclusive this index is exclusive it's not inclusive this part is the form index is inclusive but two index is exclusive right so it will if this list will have a list three will print five six one right so let's quickly jump into this and let's see the let's run this and you can see five six one and two is not printed or 2 is not added to the list because this two list uh parameter is excluded okay now one interesting thing let's see if we now want to make some changes to this als3 lst3 let's say we want to set the first element of this sub list to 100. okay and then if we print alsd3 obviously we understand that now the sub list instead of like uh five six one it will be 1061 right but let's also print I think it's already printed so we don't need to print it separately yeah let's see what happens let's see the magic so see that 100 got changed in the Subways but also it changed the main list as well it also changed though and you'll see 100 being changed in both the list so that shows that b very very when you are using the sub list function because sub list function unlike the Constructor that we used to make a copy of that list it doesn't create a copy of the errorist right so it gives you a view but if you make changes to the view if you make changes to this uh analyst that you get from the sublist method if you change the dial list the underlying error list from which you did a sub list of will also get changed it will also change this contest contents as well so this is shallow copy that has been done over here so so be very very while using this sublist method if you want to make changes to this errorless please know that underlying analyst would also the contents of the underlying analyst would also get changed right so these are very common mistakes that happens and uh while solving DSA problems we just can't get our head around it and that's because we don't have our idea or we don't have the concepts cleared right that's why a logic may be fine but just because we don't know these internal things or internal workings we land up in errors right so sub list method always remember it's not a deep copy it's a copy of reference so if you're changing to the or contents of this unsubished uh then the underlying the main list contents will also get changed okay so we are done with analysts Now quickly jump into something what we call as a list iterator so let's first go into the picture and see what what we have covered so far so let's look at this picture so we have covered identicals we have covered collections collection extends in it Ripple we covered in uh list right which implements uh which again extends the collection at least as an interface and then we covered vectors error list and linked list linked lists we are yet to cover but at least vectors and errorless those are country classes which actually Implement stylist interface and we have covered that and now list interface contains something called a list iterator right and what is a list iterated at least you can see extends an iterated right so list iterate is also an interface but it extends the iterator interface right so since it extends the iterator interface obviously it is going to contain the next method has next method but what else does it contain and why do we need at least iterator in the first place let's jump into that now so you can see this list iterator is an interface that extends an iterator so this has next method and next method obviously it is it is going to have from the previous iterator interface that it is extending and on top of that it has a has previous and a previous method right and it provides two methods that is the list iterator and uh again another method is overloaded method where you can also specify the index and from that index it will give you the iterator okay so basically the iterator from the first method that is this method it will help you reverse the element consecutively starting from the first element right and while this method basically it traverses the list indicated by the specified index it starts from the specified index now why do we have these two methods let's see let's see that so basically the list iterator interface is a bi-directional iterator for list now we know that linked list it uses the W linked list right so linked list also implements the uh list right and we know that since linguist uses a doubly linked list you can like Travels by Direction in learning place right if you have studied English you would be knowing especially if it's a doubly linked list right so that is why you are providing this list iterate interface so that you can bi-directionally Traverse now in case of using an error list don't use it but whenever you are using a linked list feel free to use this list iterator interface because you would you might require to no Travis White so it extends iterated interface this basically this titanator extends the iterate interface and it allows the list to be traversed in either directions using the next and the previous so again uh this is like this is basically something we would use in in a linked list right so let's look into the link list a little bit uh what it is so link is basically since it implements the list so you will have these ad methods you will have these add-on methods you will have the set methods so these will be there and why it will be there make all the methods that you have in the error list that will be then the linked list as well right and the reason you know why the reason is both Implement a list and these are methods of list or collections right list interface extensive correct so all the methods of collection interface you have to implement it if you are implementing a list right because the list extends the correction right and then list has some methods on top of it like this uh like this set methods and all right so so analyst implements a list interface and linked list also implements a list interface right so both has a sensor method so whatever uh methods you have in our list you will get in English so that's the beauty of it you don't need to remember like separate methods oh errorless then uh these are the methods okay I need to know oh it's a link list and these are the methods you don't need to know no that's why interface comes into the picture you know that okay analyst and linked list both implement the list interface so just remember the method to the list interface and you're done that you don't need to remember separately the uh in the the the methods of validation language separately so even a linked list so just show an action so again we will take a link list of interior let's say and LK I'm giving bad names by the way I'm not following the naming conventions because that is not in the scope of this video so don't mind using bad variables we'll just Implement a new list since we always go against interfaces so that's why I change this to list um now you can add elements like you can do the same which we are doing in you know analyst right and since also we can iterate using a forage Loop right um now there's something called list iterator which I just showed you and this will give me a list item you can also have a list I did it in narrow this but in analysis we don't really require it to you know uh like do bi-directional traversal so that is the reason we generally don't use it uh but in linked list we might require and that's why I'm showing you in context of a link list right so yeah so by so that is what that is an iterator okay and yeah so sorry this is not at least I deleted this is a list it editor of integer cool and let's see this error how we need to implement it yeah we need to import it okay so now let's quickly check one thing over here so let's say we want to print the first element that is iterator dot next okay and then iterator dot next again so you can understand that one is going to get printed then 2 is going to get printed okay so right now we have like this now when we are printing iterated.priv what is going to be implemented you might expect one to get printed right no no one more capital so let's see what happens let's get surprised okay I think Venus need to comment out a few things um I think we are printing a couple of things so that might confuse you a bit so let's comment all these things down yeah now let's paint this so that you only enjoy painting what you require oh sorry I think this should have been next that's why it was coming as true now let's do this okay see so initially the pointer was at one so you called next so it returned we implemented the next number right so it returned me the one and then the index got to 2 right now we again called next so it returned you the two and it moved to cursor move to three make the order pointer like the index pointer that we used right while we were implementing the iterator and I will understand why I actually showed you implementing iterator now you'll be able to relate more better now when we call previous previous doesn't recite a different thing okay so what a previous does is previous will first move the pointer it will first move the pointer so with like what the next was doing is it it was returning the current element and then it was moving to the next position like let's say if you had called next year then you could have written three first and then it would have moved to the next position but what prev does is it first moves it first moves back right it first moves back right and then it Returns the element so that is why it was the cursor was a three right and now it moves first to two and then it returns to no no so now again if we call previous what happens is it will first move to one and then it will return one simple so basically if you want to know the internal implementation is something like this for next you are doing something like we just saw that we would we were doing return items of index plus plus that means this is a post text right so that means first return in the index at that particular position and then increment index one day pointer but for previous this will be something like return items first this is a prefix first decrement first decrement index and then return the element something like this is improved behind this thing so that this is something you wanted to cover otherwise if you would have been using the next and previous you might have got confused right so anyway that's that's it about linked list I think in linked list you don't have anything to know and fancy linked list basically internally uses a w linked list and let's see what does a link list does so linked list basically it implements a list and also implements a DQ as just as I told you right so errorless just implements a list but a linked list implements a DQ along with a list and you would see what DQ is Right In Action very soon when we read about queues okay so yeah I think for now linked list I think if you know this is fine but normally whenever we are using any sort of uh data structure that requires as an array you would use an analyst we don't we won't require link list when we require linked list you would I would show you that but whenever it's an array whenever you're solving a DSA question where you require a list or you require an array just go for an analyst simple as that nothing else is required okay do we require link list I will show you okay cool now let's quickly jump on to we are done with list iterators as well sometimes now what happens is if you solve lead code questions sometimes uh the lead code functions they ask you to return in the form of an array so let's say they give there is this question which we just talked about the return mean the set of prime numbers from one to thousand right and so basically as I as we just discussed we would be using a an error list to store the prime numbers between one two thousand because we don't know the size beforehand but what could be the total number of prime numbers between 100 000 right that's why you would be using another list but now when you want to return you see the function signature ask us to return in the form of a normal array in case you want to convert an average to an array and you might require it a lot of times in action I've used it a lot in in the code especially so this is the method that would be your friend so let's comment out this piece of code and let's comment again uncomment this part okay this part is already uncommented so let's take this line so let's take this alst so it has one two three two right and if you want to convert this into an array what you need to do is this is Method All two array and you have to pass like I have to pass an array right right and you can pass it of any size you really don't need to worry so basically you have to pass an array as a parameter to this to add a function and Android is also like what would be the size of the area that you'd be passing right so it can be of any size by convention we pass zero right and it returns me and integer array that is error so this is basically of digital type good and now okay this reverse to this array print out one by one and you will see that this error test has been converted to an array so just print it out quickly one two three two has been printed okay cool uh okay so a little bit about more about this parameter right so as I said you can pass any any size right you can like pass this area of any size so let's say if you pass the size exactly equivalent to the size of this error list then it is fine then it's well and good right so now if you pass an array because size is greater than the size of the errors what happens is the like the elements of this error list is copied into this array and the other remaining parts is there is null that is not a good convention because you're wasting space and if you are passing and uh array of size is less than this errorless size in this case what we are doing exactly we are passing 0 then a new array has been created whose size is exactly equivalent to this I release dot size so we are doing exactly that so you are passing 0 that means our size array size was less than uh this errorless size and therefore numeria was getting created equivalent to this LSI so you really don't need to bother what is going on behind the scenes uh just pass any size but I would say I would recommend and I've seen most people doing this they pass zero and you can let this even trust this two array method to take care of of the implementation and one more thing this would be optimidated otherwise this will run into error right so it cannot be of n type and here the unboxing Auto boxing offers unboxing offers where automatically the compiler understands that okay this is the wrapper class and this is the Primitive integer right so I will automatically do the conversion so you don't need to worry about it I would highly recommend you to read about the wrapper class right because this is going to be very very important as you see okay so now let's get let's get back to this picture again and let's see where are we so we have just done list iterators we are done with uh the vectors analyst uh we would see linked list what it is right so now let's move on to the next part that is the queue interface so as you can see just like list interface Q interface also extends a collection interface so Q is also collection and a DQ is an interface that extends the queue interface right so what is the DQ we will see that and now you see that you know DQ a link which as I said is implementing a DQ array DQ is another method uh a country class that implements uh the DQ interface and priority view it just implements the Q interface it doesn't implement the DQ interface right so let's see what is exactly a queue and what do we need it and right now so as I said the queue interface extends The Collection interface it has the fall into methods for adding then one is the adding and one is the offering so both methods insert the specified element in the queue the return value indicates the success or failure of the operation right that is true or false that is why it's Boolean the add method inherited from The Collection interface throws an illegal State exception if the queue is full but the offer method does not so that is why we should always use offer just in case we don't want to run into any unwanted exception right so offer is always the method like I personally prefer similarly for removing you have colon removed so both are used to remove elements but the only difference is the pole method doesn't show any no such element exception and returns null just in case if you are not able to that's the the queue is empty and we have run out of items but the remove will that's one exception so that is why again I personally prefer offer to add elements and poll to remove elements and that is probably normally what people prefer and now to find out that what is the element that is there at the top of the queue right what is the current element uh there are again two methods like uh Peak and element so Peak is the method that we should use because it doesn't throw exception just in case if there is no key just in case there is no item in the queue at all and we are calling the peak method it returns null but in case of an element if you call that element and there is no items in the queue then it will run exception so it's always better to use the peak for getting the current element uh the pull for polling items on the cube while removing items from the queue and the offer to add like your offering items to the queue right so this is the queue interface and anyone any class that will be implementing or extending the queue interface has to implement these methods right so now let's look at take a look at the implementations of the queue so both the priority queue and the linked list classes implemented Cube interface right actually the linked list like implements a DQ interface and The Deco interface in turn extends the Q interface so you can say that your link is also kind of a cube right okay now let's take a look at what DQ is so DQ is an interface that extends the queue interface to allow double ended queue so I'm very sure you must be knowing cues I am not going too much into depth so Q is something that follows a last and passed out uh approach right so you whenever you are adding an element to the queue it is inserted at the last and we are removing element from the uh queue it is being taken out from the first right interface so that you can allow double ended operations that means it allows operations not just at itself but also its state so the elements can be inserted or removed from either end right so it can be used as a fifo queue right uh where you know the element which is first going in will be first getting out of the queue and it can also be used as a stack which is basically forwarding that means the the element which was inserted last it will be coming out first right so in Java uh initially we had we didn't have any stack uh class now we have a stack class which extends the vector uh class but you can like in order to use a stack what I would suggest is you can use this DQ right because since it allows double ended operations on the Queue so you can use both as a fifo or a defo like a stack 154 is basically queue in order to use a stack I would suggest you to use the user DQ right and not use a normal queue you can also use a DQ but this one also use a link list as well right because linked list sends it elements a queue you can get all the vanilla Cube operations using a linked list right you can also use a DQ as well right and in case you want to use a stack then you have to fall with uh the DQ right you will see all of this in action which just in case it's so heavy for you so you can see in the DQ have a couple of elements so we have the offer first and the offer loss that means it is adding elements to the first and last then we have a push and we have an ad first so that is like pretty similar to the offer first and you know the difference already so I'm not covering it and you also have an address right and the push on the adverse method is like pretty similar they are similar right um similarly for removing uh we ideally should use the pole first and the pole loss method right instead of using the pop method or the remove first of the remove last method right and for examining we should use the peak first method or the P class method instead of using the get first and the get last and you already know the reason because we don't want to run into an exception so the added EQ and the linked list class Implement The Deco interface so there are two classes that implement this Deco interface because there needs to be some concrete classes right you can't use a DQ like that because EQ is an interface but you need a concrete implementation of this DQ interface so the array DQ has a concrete implementation of the DQ as well as a linked list is also a implementation of the DQ interface so whenever now please note this down whenever you want to use fifo order that is whenever you want to use something like a first and first out that is tax adq is always the class to go so analytic is also editable and the traversal is always from its head to it still and also dqs are not list so they cannot be randomly accessed based on their positions right as he can do in list also they cannot be sorted so please note this in mind and array DQ or DQ is something that we saw while we were doing the zero one DFS question in graph CD so go and go and check out that video right and you will have an actual understanding of the implementations but using these methods right so using this methods we can actually Implement an array DQ that I just showed you and we are going to do our demo as well so please remember whenever we need a normal queue we would use what we will use our linked list whenever you need a stack we would use addq right there's also a class called stack as well which you can use but I'm not going to show that in the video otherwise you would get you know confused at which you want to use so I'm going to keep things simple stack use id2 in case of uh normal queue user link list because linked list implements a DQ analyst also implements a DQ right so you have all these things at your convenience but to make things very very simple because in DSA you need stacks and cues just for Stacks use added EQ for Linked list use cues you're going to see that in demo in action right now so let's take a look at queues and stacks in action okay so let's say we want to create a queue okay so what you will do is want to create a view of integer and what is a queue by queue basically you want to have that key for ordering that is first and first down like you know Q what it is right right so let's get a Q and in order to instantiate a queue please remember in Java Collections we don't have a class named queue we don't have a class we have an interface named right and in order to implement the queue there are two choices right because we need a concrete implementation of the queue interface right and Q is an interface we can't instantiate Q right there are two options one is an array DQ but that is not a good choice if you want to have fifo ordering and another one is linked test because linked list is also implementation so always whenever if you see if you go to my graph videos you would see there are in BFS in BFS we use what you require a queue right and over there you would find that I have used the link list so just this code that I'm writing typing you would find that in my graph videos right uh where I've used DFS so always remember make things simple I mean okay these are there's a lot of theory I do understand and you might get intimidated but to make things simple for you always remember whenever we are using a proper normal queue that is like a proper fifo ordering queue we use a linked list to instantiate Okay cool so it will just include import importers just add Q dot add a couple of elements okay we don't use the add method we will use the offer method remember because that's the better way [Music] to right right and just print the queue or they will just print the you know Q dot e we will get one right and then we will just pull one whole and then we will use the product Peak okay so I'm just playing this uh let me just comment out other things since you don't have that printed and if you had any just you don't get confused and you see like I think we are printing something else you are printing the address let's quickly comment out that part yeah so you're using this save this let's run this and you see that initially we had one and two so when we when we uh called Peak this one got printed then when we called Q dot pole one was removed from the queue on the top of the queue because one was first inserted right so one got removed and it got printed and because it was returned by the phone method and then we again we are when we are calling P we are getting 2 is getting returned because now it is pointed it is very normal right it is like very normal to the two okay and there's one more method that is that it just checks this is also used a lot that is Q dot is empty I think this is not a method of uh a q it is a method of collection framework so sensor queue if you go up the change or up the chain so a link it's basically it's a linked list right so Q is nothing but a so basically this queue has been implemented by linked list right so now linked list implements a queue what does a queue do a queue extends a collection on the ending collection you have this is empty method so even if on all the collections whatever you know classes you have whoever implements The Collection somewhere down the line in the hierarchy order you are going to get this method right here is Q is not and that is why if you go to my graph videos in the VFS you know while I was implementing the BFS function you see that I have done this that while not U dot is empty and then I was writing my code cool so this was about a normal fifo queue right again don't confuse don't confuse uh this Q interface with the normal fifo queue that we do was this queue interface in Java is slightly different from our understanding of your understanding of Q is basically the first interest first of all right now you know that if you want to implement a few you can use the Q interface right in order to implement a stack we have the stack class so now we we will Implement a stack so stack of integer stack is equal to new stack right and it has the methods the economic stack will have Push right stamp dot push to why not stack empty that is while it is not empty so it is empty function pop right and before that stand dot Peak so pop Returns the last element that was popped out if you don't want to do that that is fine just off it we will use the peak to print it out and you will see now stack we'll just import it from java Dot not to go let's let's comment this part of code and this is the way you use taxes first two was inserted last so it was popped out first and right so stack is if you want to implement a stack use the stack class in Java if you want to implement a queue use a linked list use the in English that is you want to implement a FIFA queue if you want to implement a double ended queue we will use the ID please try to understand and add a DQ you can use an array du to implement a normal queue that is a FIFA queue as well as you can use an array DQ to implement a stack as well but we don't do that right because we have already a linked list that serves our normal fifaq purpose and we have a like a stat class that serves a normal lifo purpose right but since added EQ you can insert elements anywhere right you can insert elements at the top you can insert arguments the last or bottom whatever you want to term it and then you can remove and driven events from any from the first or last position but you can also move elements on the first position as it is last solution so therefore you can use it in as any type you want but normally to keep things simple and to keep the convention we will use array DQ uh only when we want to use double ended queues and for that double ended queues in DSA in action the very important question that comes to my mind is 0 1 VFS which you can watch my video where added if you are double ended queue as well so in so in Java we have the DQ interface and the corresponding concrete implementation of the decoy interface is the identity okay so that's it um so we'll Implement an identity now so let's have a DQ of integer DQ is equal to new array Q right and we'll just implement this we'll just add this quickly and now we'll have all those methods that we saw so we have offer first one we can have two that means we are adding it to the top that means basically uh right now if you print this DQ right so what will happen is it will basically be as a stack so you can understand you can use a DQ as a stack as well just as I mentioned so this will print to one if you see yeah you see this is because this here we are adding elements to the first only right and now if you want to remove elements if you want to remove elements let's say you want to DQ dot pole first right so now 2 will be moved that is the first and first out approach is followed so now it will be printed one so if you want to like you can also use that DQ Dot whenever you would be using this combination that offer first offer first so whenever if you want to use it as a stack if you want to insert it would only want to insert it the first you ideally want to remove it from the first as well right and that and then you will be uh using the offer first and the poll first methods so then it will be giving you the stack if you want to use it as a normal leave for ordering queue then you have to always offer last that means you have to always push at the end of the queue then it will give us a queue normal queue and always you have to pull it from the first right and the peak also from the first right then it will give us a cube and if you want to use it as a double-ended queue then you can based on the conditions you can like insert it at any place you can insert it in first and last you can like pull from the first you can pull from the last as I just you know mentioned in the added view while I was discussing analytical class so just read about it I mean it's it's nothing much these are the methods or could last offer first like as the name says speak first speak last whole First full last right but to sum it up to make things very simple using Stacks use the stack class using normal t4q use the linkage class using a DQ I get an added EQ use the editing class and added EQ is basically of type BQ linked list also extends uh like it also implements a DQ so if you see it implements a DQ so instead of taking a queue you can also write DQ over here but normally the convention is to write you and the stack it extends a vector but it does not get into that right so this was all about stacks queues and eqs from the correction framework cool now we are left with one more part of the Q that is the radical I think this is a good time to take a break have some water take a break or five minutes and we will continue with the video where we would cover another important part of this video another important aspect another important implementation of the queue interface that is priority which is slightly different from the normal Cube okay I hope you are back uh after a quick break and now let's first understand that where are we and what have we covered so far so let's again jump to our friend which is that particular hierarchy class so we have covered dietary Rebels right and we have covered collection interface as a whole uh then we also covered the iterator uh interface which The Collection interface has right uh and then again uh we also have seen the list iterator we have also seen the list interface we have also seen the vectors error list we have also seen linked list in action we have seen bqueues and we have also seeing the queue interface uh now from the DQ interface we also saw that you know how can we use text use so for queues we use a link list and for Stacks uh we use the stack class also we can use an arid EQ for the DQ operations and apart from that you see that there is one missing link that is the priority queue which basically implements this queue interface right so this is a concrete implementation and priority is also a queue the only difference is so in a normal key what happens is uh it is based on your insertion order right uh but in a priority queue it is based on the priority that you set for that particular class right so let's read about a product here but I'm very sure you must be knowing radical because I'm not going to like cover too much of in-depth pradages or data structures on a data structure video it's a collections video but I expect you to know these data structures between beforehand and I'm going to just show you that how you can Implement that in Java using the collection framework but just to give you a you know depth so basically practical as I said it works on priority the implementation is based on a priority key which is a tree like structure that is an element at the end of the queue according to the priority ordering right which is either defined by the natural ordering of its elements or by a comparator in new terms new terms and very very important terms and now we're going to jump right into to this but let's just give this for a while and let's move ahead so in the case of several elements having the same priority one of them is chosen arbitrary right elements of a priority queue are not sorted please remember this they are not sorted right it can only guarantee that elements can be removed in a priority order and any traversal using the iterator will not guarantee that you would get the elements in sort of form so never ever try to iterate over a radical that's a very bad choice in C plus plus I don't think you can get an idea to do that I forgotten C plus plus I've used way back in college but as much as I can remember but in Java you can actually use an iterator to iterate order ID and why is it so because a priority queue is implementing a queue a queue is extending a collection and a collection is implementing an iterable so if you go down that chain you would be able to iterate over a priority queue using the iterator if you want to but is it a good choice no it's not a good choice to implement uh iterate over the writing you because you won't be getting the elements according to the priority ordering because either you would be just simply iterating about the tree right the Heap tree okay so if you want actually so I will show you how to use priority uh straight up and you would actually get my point right so let's jump into creating a priority queue first so let's comment out this part of the code and okay by the way I will have a small task for you after watching this video while watching this video make notes right and share I mean create a document or whatever create a handwritten document whichever way you prefer and upload it somewhere in a GitHub or a Google doc or whatever is it and share the link in the comments down below and which of whoever creates the best node I will have some gift to you I will probably give an Amazon gift voucher I will announce the winners soon but I think if you do that it will not only fetch you a good reward for me but also it will help the others as well okay now priority Q of let's say integer you want to create of integer by the way I'm just reading integer doesn't mean that you can't trade of other classes right you can create a double you can create floor and all those things right right okay so let's let's let's implement this uh I think it's already already imported now let's use this have the default Constructor you know new priority queue okay and yes that's it we want to add elements so that is pretty simple but we can also do offer method is there as well because anyway it is implementing a queue right so it will have those methods from the queue itself so you will always use the offer EQ dot offer two dot offer 0 .4 00 it's random elements right now we want to see which element is at the top of the cube or let's do like this let's try to you know Traverse let's try to Traverse the priority queue not ideate okay not iterate because you I did it over the writing you one by one you might not get the elements in a solid fashion so ideally what you want to do we do like this so why not quickly let's say you want to get the top elements right so let's say I have this priority queue right and I want to get the top two elements from here so I have a practically like this and I want to get the top two elements so what I would do is very simple so I will get a list for this so let's talk L70 your LST is equals new wireless right here I will took the let's let's name it top K top two right let's name it top two elements what I would do is I will just add top two dot add TQ dot fourth okay remove elements and one more thing which I will do is let's say that int index is equal to zero if index is uh equals equals to return I'm just adding a very simple code uh I'm not taking okay take care of all the conditions top q w dot add view dot hole and what else yeah that's it okay so I'm just pulling the first two elements right and um we will return and we'll just print out the dialysis right we'll print out this error list and we will also print out the remaining part of the queue that is the PQ okay it's good now let's see what what we get right so let's print out this okay so we first printed okay I think we forgot to add the index plus plus that's why this we got the entire PQ okay now let's see this Okay so we've got zero and one right and we the Right View so the first two elements the first elements got popped out right and then we were left with 100 right now you might say that here is the uh I wanted to talk to elements but I got the bottom two elements why is it true now that is because okay I won't tell you now I will tell you later okay let's hang on that's all we will come to this okay so now let's say instead of the top two let's just say you want to find the bottom two and we get this bottom rule right so now you understand at least how you like want to Traverse and try to you've got a feel of the methods like same methods as a queue right the whole offer that's the beauty of coding in these interfaces right and that's why interfaces are made so that you don't remember you have to remember all the specific methods for every class common methods have always the same names now let's see answer your first question what if you want to get the top two elements right what should we do second is now let's go and create a class okay our own class so far we have been using the integer classes and all those things right so now we have one question okay so now let's part this question what if we want top two elements instead of bottom two so you are parting this question as of now okay and we are going to create our own glass that we would call our like maybe we will call this class student marks okay yeah stupid marks answer I know I'm very bad with examples so please bear with me let's say we store the marks of maths and we store them the mass of physics okay and we would like probably describe it you would have this private you would have some you know okay you would have the constructors just they will generate the constructors using the source so generate during the two stream methods that's important that will help us to print the class um then we will generate the Henry T Getters and the setters you don't need to Setters and such so we will click not have it we just have the getter methods and we would use the constructors for this to generate Constructors using Fields you'll have both the fields and we are good approve the super call is not required we are not implementing or extending any class cool so this is it so we have this class right now let's say we want to have a priority queue right let's let's now comment uh or let's not do anything let's just recommend this two lines and let's see we want the priority queue with us understand the question what you're trying to do get me the top two well what I'm doing what should we do okay top two students get me the top two or top three students Force according to their physics marks according to their match marks okay this is what I'm looking at right so we have a priority queue okay and we would have we have to click create a priority of which class we have to create our student box you now we are using our own custom plans okay please understand this PQ and B follow me along because we are going to learn a very important concept and I don't like there are very few videos we're going to like like take you like build things up from such depth right uh because otherwise they're very you know what I've seen mostly which they give you a very high level of understanding and they generally don't go deep and they don't show the inner implementation so as a result sometimes we have a problem of struggling and that's why I'm like telling you all these things so that your Kindle concepts are very very clear and they are often asking interviews right cool so now you create a new credit again and trust me these are actually asked an individually test upon tested upon these things they would actually go deep and see whether you know these Concepts also if you're like let's say it happened between a couple of interviews which who asked Java like let's say one of the companies or Autism one of the companies or Goldman Sachs who really really ask a lot of questions from java JP Morgan is one of those companies right so all the banking companies fintech companies mostly they will ask you a Java then there are the service based company so yeah I mean Java is really asking a couple of a lot of companies wait uh so don't need this in Java 7 we only need on the left hand side the type and now okay so let's name it what you call it uh getting spq that's very bad name I know but just to keep things short and one size and clean now we want to insert let's say we have a uh okay now let's try another let's show you another method let's say we have a list of students my list of student marks SDM sdl no no it is equals new analyst and let's say that you have you want to add student marks right it's a new student marks and let's say adding 70 and adding 80. and in this way we add five more marks or let's say yeah five more marks okay okay so I feel this uh student marks right and now I want to add these marks so I have to add all of these marks into the priority now what we can do is we can Traverse we can Traverse this uh our list and we can add it to the priority one by one right using the for Loop but instead of that writing so much code we can just do it in one link that means whenever we are using the priority queue when we are instantiating the priority queue remember in our list we can take another collection similarly in prior to you inside the Constructor it can take a collection and since a list on analyst is a Constructor is a as a collection itself so I can just pass the St Marks over here and automatically uh it will take the list and like the list all the contents of the list will be there in the priority key Okay cool so now I want to find a top three students according to the maths marks so what I would do is again I would like follow this approach right and maybe I would like copy this piece of code I know it's a very bad piece of code but yeah I I really don't want to focus much on the coding part otherwise things would get a bit uh different otherwise think I would be digressing a lot so since it's top three and what I would do is I would add make this angle to zero okay so basically what it will do is it will uh I will print the top three so what it is doing is basically very simple I am like putting the student marks inside the priority queue and holding the top three elements the top three elements from the Right View and uh I'm printing it now let's see what happens what do you think what happens comment it down below pause this video and comment down below what exactly it should happen let's run the code okay yes we run into an exception what is this exception Java dot Lang dot Class cast exception that means that it was this internally it was trying to cast something was happening where it was trying to cast it to a type but it was not able to and what was the type this riddhi the student marks that means this class it cannot be cast to this interface or any object that is implementing this compatible interface and the priority queue needs it why why and we were doing this integer and we are doing for adapter class we're not getting any such exception it was working it was not working for bottom uh talk to that's a different thing but it is it was getting me some results right but here it is not getting any results from me and it is getting an exception whenever we are using a custom class class what is that problem so in order to solve this problem we are going to learn two important and very very important concepts of Java Collections that is comparators and comparable interface so let's now jump into this so now as a programmer want to get the top three uh students according to the maths marks right now how would this try to take you know that hey I want to know like give me the top two students according to there was sort or whatever you're doing they create the Heap in such a way that the always the student with the highest maths marks remains at the top how would it know it it can't get into my brain and know it right I have to somehow tell it that he writing you please do something uh so that at your top you have the student with the maximum Max marks now I am not defining it I'm just adding it to the queue and expecting out from him right so this is this is not going to work right so in order to tell the priority queue in order to tell the Practical hey priority you I want the student box to be at the top which has the highest Max marks there are two Fields right when is the math and one is the physics so which one do you want I want the Sorting according to the Maxima so in order to tell the Gratitude is there are two options the first option is using the compatible interface which is done at the class level and by class level I mean this class which the this class which is the type like of the priority queue of this current priority queue which you're using so what we have to do is the Friday you would expect two things either it would expect that this class will implement this comparable interface and as the name suggests if the priority queue sees that hey the student marks implements this comparable interface it means the student marks has some comparison strategy and if it has a comparison strategy then only we can sort that object right so you see uh like if you have if you know any sorting algorithm like bubbles or whatever algorithm it is you see how do you sort elements you sort the elements by comparing right so basically if you're sorting an integers you compare to integers right greater than less than stuff like that but how do you compare the student marks right so you need that comparison strategy so if you don't have that comparison strategy how would the product you sort uh this particular student marks for you right so whenever you are creating any custom class and you want that you know custom class to be as the type of that priority queue right you should implement the comparable interface so Java has that class right and you should do it at the class level that means that hey this uh class is compatible okay and whenever you're implementing an interface there is a methods that you have to implement and in this case there is this one method that is compared to so in this compared to Method you can see that there is an object that has been passed so basically going to compare the current object the current instantiate of the object basically this with the uh object that is this like the other object that has been passed as a parameter so how does this comparator works let's see that so there can be three instances right so let me write it down so let me remove this so there can be three instances always remember this so let's say you're this or the current object current object is less than the other object then it should return minus 1 okay this is how the compared to works right and that is why it doesn't end if the current object is greater than the other object then it should return one okay one more thing it doesn't necessarily has to be minus one it can be any negative number here I am writing minus one okay it can be also minus 100 as well any negative number right similarly for this if it is greater it can be any positive number does it necessarily has to be one and if the current object is equal to my other object then it has to return 0. so again summing up even is equal return 0 if it is current object is data then return any positive number or if it is less than the other object then written any negative number so with that in mind you will write the code like this so once I write the course you will understand if this since you're comparing these on the match marks if this dot match this is less than or Dot maths return any negative number Plus data minus one okay cool if this match is greater than old or maths then return any positive number okay and if this is not Max is equals equals to that Max then return View that's it and we are done with our writing or compared to Method okay now we can replace we can replace these three lines of Code by just writing one line of code this will sound really YouTube you would find very cool that is instead of writing this three lines of f uh we can simply do this this got maths minus o dot Mass this will basically translate to this lines of code right okay cool now coming back coming back now we have this class implementing the comparable interface and since we are implementing this comparable interface we have implemented the compared to methods so now whenever we are saying that okay priority queue this is the student marks right object and the priority what it will do is it will try to see okay I have a student my type student marks the student marks implements are comparable and if it does then it is going to call the compare to Method it was not able to find the comparative methods and that's why it was like you know uh throwing that you know class cost exception because it was trying to cast it to some compatible interface or a class that implements a comparable interface but since student marks was not a class not a not a class that was implementing the comparable interface it was not able to cast it right so you see that now the radical won't throw any error right one thing since we want to find a top two therefore we have to sort it in uh in a different order so this should be o dot match like we wanted this should sorted in ascending so we want it in descending because we want to talk to first so the top element should be in the first so there should be o dot Max minus this dot Max okay the other object should come first okay now if we go here you will see that this would be working because now the priority queue will search for the comparative method it will call the comparative method if you also want you know I can just have a debugger over here just to see images to let you know that yeah comparator compared to compared to method is called to show you okay just before running uh we need to change this to student marks okay okay and this is also student marks I think this is fine um okay and also we need to change this I think we coded it against the other prior to you so this should be spq and this should be spq as well right and now let's run the code and see okay so you can see the comparator is called multiple times so just to show you that right EQ is internally calling the comparative function of our class and as you can see you get the math 100 and mass 97 and the max 70 so these are the top three marks if you compare from here this 38 and 40 was not shown right so now you understood uh like if you want to create a particle of a custom type what is the way to go like one way of is obviously of creating the class uh like or allow our class to implement the comparator interface right and in turn which will have a comparative method which will Implement rate anyway now the first question is the first question is obviously we are going to look at this question which we were stuck at earlier but before that let's first try to understand that he in case when we were using an interior right we didn't have to use or do all of these things right so how did the integer worked right I mean like let's not get into the top two part but at least we're getting the bottom two we are not getting an exception right because if you go to this integer wrapper class it implements the comparable interface so so since it implements the comparable interface the priority queue was calling the compared to methods of the integer uh class and as a result it was not getting any error right but now it's a problem there's one problem we'll see what that problem is so now the like the integer the integer glass the comp the way the comparative method is written in integer class it sorts in ascending order right and that's why we were getting the bottom two elements first right but in order to get the top two elements right we need to change the compared to function of the integer class but are we allowed to do that no right because the integer class we are not allowed to access the class it's it's a class that is defined in the Java package right and we can't make changes to that and it's not a good way of as well because a client we are the clients because we are using the class we cannot go and change the internals of this class we can't do that right so what can we do over here so let's sum up the problems and what have we solved so far so the first problem is like whenever we want want to like use a custom class uh we have to use a comparator and we have to line our own compared to function right and if we do that then right again we can you know use it like we can sort it right uh using the right key thought I mean not sort but yeah we can use the priority with that class but let's say now in case of an integer if we want the integer class or whatever class you want who which whose comparative method is already implemented we can like use it no issues the comparative method will be called but what if you want in a different order right what do we do in that case in that case the comparator comes into the picture so what is that let's now try to fix this let's try to let's now let's try to get the top two into the bottom two let's let me just copy this first and let's command this out and let's comment this out and let's type it down here okay now what do we have to do is what the priority view does can we are instantiating apply to you it takes an object of the comparator interface right so what is a comparator interface okay let's first create a class okay and things will be more creative so let's create my custom comparator class okay and let's say that it implements let's say of type integer now we have to implement okay so as you can see here this is like giving an error so let's add the unimplemented methods so you can see that the comparator whenever you are trying to implement a comparator interface we have to implement this method that means that this comparator interface has this method that is compare now what is the difference between the compare method of this comparator interface and what is the difference between the compare two method of this comparable interface basically both are same right since the compare two method is within this class right so therefore you already have this object so you need one more object to compare yourself to right that is why that there is one parameter when you're using the comparative interface it has a compare method so basically now you can't even have that class right with you so therefore you need to pass two objects so here I would be creating a comparator of student marks I think I shouldn't have done for an integer so this should be uh student marks Okay so again the difference between a comparator and a comparable interface is a compatible interface should be implemented by the class itself and the comparator interface uh should be implemented by a comparator class right and here it has a compare method as compared to the compared to method and the compile method you should pass two objects as compared to one object in the comparative method because the class implementing that already has itself to compare it with right so now now here we are simply going to write so what we're going to do we are probably going to okay so if you want to compare the student marks object right so then we would be doing one dot get Max minus O2 dot get max if you want to do it for the integer write that which will be the problem that you are solving and now we want to do it for integer I'm sorry I should have used integer only this should be o1 dot dot uh one minus you know O2 right or O2 minus 1 because we want to compare it uh and descending order right so now we have this custom comparator which implements a comparative integer it takes to integer and it returns O2 minus 1 that is basically it is comparing in terms of descending order okay so now how can we use this comparator right so this priority queue when you are creating a priority queue it takes in its Constructor it takes a comparator right so if we just call new my comparator class new my custom comparator class what happens is now instead of the ordering that this integer class is falling it will now follow the ordering of this my custom comparator right so basically the whatever ordering the class is implementing that is called a natural ordering and whatever ordering you're passing to the priority queue as a comparator right that is called total ordering right so the total ordering has always more precedence than natural ordering right so let's say the passing a comparative to the parity queue that means you have a total ordering right so irrespective of whether the type or the class has a natural ordering or not whether it implements a comparable interface or not your total ordering or your comparator function or the compact compare function would be called Always if you don't pass a comparator then that class the type has to implement a comparable interface and then that comparative method is called right so first of all let's solve this problem so let's now we have passed a comparator and let's see what happens here so before running the code let's first uh comment out this part of code as well this list part otherwise there will be some unwanted calls that would be going to this comparative method and that will confuse you confuse you so let's now run this and uh we should be getting the top two elements right so it should be giving me two 100 so let's run the code you see we get what we get the 200 right that's what we get the top two elements 102 basically and our priority is left with 1 and 0 right we just implemented a custom comparator that gives us a prop tournaments instead of the bottom tournaments now let's say we uh the student marks let's say we have the same problem over here right so let's say now we uh comment dot is part of the code right now before moving forward we created a class that is new my custom comparator right and we passed it to this particle basically this priority needs a class or object of a class that implements my custom comparator and in turn implements the method right that compare method instead of creating a separate you my custom comparator what we could have done is we could have created a new Anonymous in our class which is basically a concept of java so I'm not diving too much into it so instead of doing this um you we would have instead of creating a separate file for this class we could have passed this as an anonymous inner class which is the concept of java and even better we could have used lambdas that is what I'm going to use now uh and from now on whenever we're going to pass a comparative I'm going to use this so basically what the slam does that's why if you are not familiar with lambdas that's fine you can read about it later but for now I will tell you how is it going to be so this since it takes a comparator so we can write it like this so just think it like this basically don't forget about the comparators the lambdas will do it for you now just think like this you have to basically pass a compare function to the value that's all you have to do you have to pass the compare function implementation to this particle that's what you have to do so what you will do the converter compact function takes it takes two objects right so just take two objects um you don't need to mention the type because lambdas doesn't require you to require you to define the type right so just write like this ab and then just do D minus a that's it you're done okay so now uh we're getting an error because that's because lambdas are only allowed at source level 1.8 and here at 1.7 so we will change it to 1.8 and we will see that it is gone now uh landlords say that if you have just one line of code basically we are just writing this you see this is what we are doing right we are doing B minus a or we are writing O2 minus 1 that's what we are doing here right since it is just one line of code uh we don't need to write a specific return or we don't need to have the curly basis and all these things is the Lambda specific thing so maybe I will I will make a separate video on Java lambdas just like this but for now you can think it like this we are passing the compare function right and this will give us uh this will do the same thing that we are doing now we don't even need this my custom create a separate class and all those things right okay now let's run this and you will get the same thing okay let's run this and let's see the console okay let's I think we just forgot to print it out for Android being printed and we are left with one zero right now actually you would be should be able to solve this problem by now that is now let's see that we comment out these two lines and we uncomment this line right okay so let's create a paradigue so how will you pass the comparator let's see so first of all variety queue of student marks right s uh PQ right a new priority queue and again uh we are going to add we are going to Traverse this analyst foreign marks from or maybe in student marks um SM from SD marks we are just going to add it spq dot add do this you know this uh SM right and here in the Constructor we can also we can pass the comparator just just what just what we saw right now so here we will pass the comparator S1 and this will sort according to the top physics marks so S1 dot get physics minus s1.cat physics and what it will do is the student must have a natural ordering right but since you're passing a comparator or a total ordering function so whatever we are passing will override the natural ordering that already exists for that class right always remember a comparator always will override like a compare reveal right or the natural ordering so just to make you aware of this uh just to show you this what would be called let's say that compatible is called that's not a comparable but a comparative is called but let's say comparable so ah compared to is called right and let's copy this piece of code and let's go to here now since we have to there will be two lines of code because we need to print it therefore we have to give this okay so let's paste this let's copy this again this first print is we are writing this curly under curly braces because I know there are more than two lines and Lambda requires that if you have more than two lines and you have to put this under curly basis also you have to use a return statement um yeah so this will now go here and you have to say comparators compared to what's called now we'll see which one wins which one wins okay should uh like either this compare status compared to method is called or this student marks where the natural ordering is present that means the compact two methods is called let's see let's see so let's go to the collection test class and let's find the top three elements so you see the comparator is compared to S gold that means whatever function we are passing that means the total auditing wins and you see the student with the high specific marks 88 with an 80 and then 30 is being sorted so now to sum of things for you normally we would be using comparator functions especially when most of the time so normally we'll be using comparators interface in most of the problems in DSA 99.9 we are using going to use comparators and the reason behind this is you see a lot of predefined classes that exist in the lead code questions and you don't have access to this class do you have access I don't think you have access to this class right therefore you can't run at the compare comparable interface or maybe change the comparative method of those classes yeah so therefore always you have to like pass comparators uh like this to the priority queues instead of depending on the natural ordering of those functions for a couple of wrapper classes if you want things to follow the natural ordering that is the ascending order then you don't need to pass a comparator and you can just can let integer class uh have its own comparative method do you have a job for you but let's say you want to change the logic of the comparator uh but let's say you want to change the logic of the natural ordering of the integer that's just as we showed shown just as we just saw then in that case we have to pass the comparator also in classes which doesn't have any natural ordering of their own that means they don't implement the comparable interface then also you have to pass the comparative function so just think like this whenever whenever we have to Define our own ordering of a class that either doesn't Implement a comparable interface or implements but doesn't have implement the same contact logic that we ideally want to then you have to pass the comparator function and the comparator function compared to method would be called and that would be sorted accordingly right so this is all about priority queues this is all about the comparable comparison we will see more of comparable competitors in action in the next set as well when we will be reading about research team apps right and then these things would be a key for you but again if you haven't understood what is compared to comparable please request this section right because this is going to be a very very important thing for you again comparators is something we would be using in most of the DSA questions that we'll be solving so comparators is a total ordering comparable is a national ordering natural to the particular class comparable is something that we're using in the inside the class itself and it is not really very flexible because once you define it inside the class you can't change the logic from outside so change the logic from outside you have to use the comparative we pass the comparator right and comparators are very flexible because it's just plug-in you just pass that functions and you can the client can pass any functions according different clients can have the different comparative functions very easy but the comparators it is very specific to the class right so that's it comparisons comparables try to use with this we come to an end to the queues and maybe if you want to take a short break take a break have some water right and next we will be looking into sets Okay so let's now again jump to this picture once again to this hierarchy and we are done with queue interface we are done with dqs we have seen priority queues in action we learned about comparators and compatibles we learn about iterative Blues as well so we are done with you know this side of the hierarchy we are left with set now which is going to be the last part of the collection which you are going to cover so set bicycle is an interface right and hash set is an implementation of set and linked has set is something that extends and has that you already see all of that in action and then we are service order said that again extends it in set then there's a navigable set that extends the sorted set and then a tree set which ultimately ends up implementing a navigable set right so let's see what all of these are so the sets contains the following methods uh the contains all add or remove all uh clear that means basically empty the set this either some of the functionalities that the sets interface brings in now as we see that asset basically implements the set so let's first quickly look at what a hash set is and how we can Implement that okay cool so let's now comment all of this code uh we don't require this code anymore so let's quickly comment out this part okay so now let's create a set okay so one of the implementations of the set is the hash set so let's create a set of integer set is equals new asset now what is a set so basically set is a collection unique element so even if you try adding a duplicate element to a set it will remove the duplicate elements okay so now let's try to add so we will use the admitters because that is a part of uh a collection so we will chat is also collection so basically it will be able to add so now let's try to add a set now we have added these elements and now let's print this at so we will see that these things are there in the set so we will see two three four okay now let's say we want to add set dot add for 2 again and if we try to print it you would see that you will have only one instance of two because a set doesn't Supply allow duplicate elements it only allows unique elements okay so now uh we can also create a set from an Adder list so because a set takes a collection as well so you can add this alsd that which is created what was the name of the list we added a list right so a l i s t you can just add in and if we print this you will see one two three four right because it is only storing the unique elements okay we can also remove from the set by this element so say if you just do set dot remove two you will see two is being removed and we can just see one three four okay there are a couple of in the set like if you want to do a set dot clear you just do this and the set would be emptied so we would be seeing an empty set just like this also if you want to do the set intersection there is something called a retain all method so basically it give you this intersection of two sets so let's for example let's say we have a set one and let's say we have an intersection we have a set of integer let's just set to new asset right and let's say we let's see change this okay so now if we do set one so let's first print the access set one and set two okay let's print the set one um now let's print the set two so now if we print the set one okay and now let's try out this method set one dot return all set to and then we print the set set one and then you print the set to and you will just write another function here after retaining I'm sorry you just print out this so that you are able to understand so let's see what we're doing we're adding we are creating two sets and we want to like first print this Advance at two and then we call the retain all method on the set one passing the set two and let's see what happens first and then we will see okay so let's just move this line and let's save this and let's run okay so initially we had this Set uh that is the first set is one two three and the second set is two three four and now after retain calling the retaining all retain all function right uh so you see in second set is unmove the set which we passed that is unchanged but the set which uh on which this retain all method was called you see the one is deleted because it is giving you the intersection of two sets right so please remember the set which are passing as a parameter of the return all that would remain unchanged but the one on which you are calling that function retain all uh that set would be changed right and you would be getting the intersection of the two sets right so that is the retain all method then you have the remove all method as well that basically gives you the set difference right and again the set two will remain unchanged but all the changes would be done on the set once if you run this method you see that it is a difference that means 2 3 the intersection was removed and you only have one right so that is what you call a set differences or basic operations related to set now if you want to do an Union you will do an add all right and if you just print the set again you see that one two three four is being added basically the two unions are being done right so this is very basics of set now what is basically a asset so in a asset since the concept of hashing is involved I'm not going too much deep into how hashing is done and all but that is separate video altogether and I would be implementing a hash map and a headset from scratch in one of my later videos on the series but for now what I would say is so in a hash set right the insertion and the deletion takes constant time roughly constant time or average complexity is constant and the order there is no ordering over here and the elements are not sorted as well so let's say if you want to Traverse this set I want to iterate over this set so let's say now if you just have this we just remove the uh we have the set one right and let's remove let's comment out these lines and let's say you want to Traverse or iterate over the set two so we can do that because the set 2 is basically a set is basically a collection and collection implements the night variable so you can iterate it like this so if you do X you see there would be no ordering right at all like it doesn't follow the insertion order it doesn't follow anything at all right so if you just let me add one more item set to add zero so you see that no ordering is followed at all this is zero two three four right I mean neither it is following any order like it uh you might feel that hey this is maintaining a software but actually it is not it is pretty random like so so whenever using a hash set there is no ordering at all and you cannot sort as well sort the elements as well right so only use has set when you don't need any ordering so whenever you want the first insertion or a first removal uh of elements then a asset is very very useful now what if you want to you know maintain the insertion order right of one hash set what do you do so that's where the linked asset comes into picture so if you see in this pick again so there is this link has said that extends the hash set right so basically it is a hash set but it also maintains a linked list uh behind the scenes that kind of remembers the order invested the elements are inserted so if we just copy this piece of code and instead of a set now if we use a link asset right and we just you know let's use the set three just import it so link acid is an extension of the asset right distance asset it all same it has the same functionalities on top of it it just maintains the order with the help of a linked list right so now if you Traverse to let me now Traverse to the set to and set 3 as well so you will see here the insertion order is maintained but over there the insertion order is not right so let me change it to set three and you will see the difference okay uh let me change it to set three as well let me also change the print statements okay now let me know the code we have set so you see here uh the insertion order is not maintained it is being printed randomly and here if you see uh the like the insertion order is actually maintained in the next set that is linked access so you see two three four and zero right so this is the basic difference between our asset and links are linked asset linked has said has slight performance issues over asset though like again the complexity is like a line like almost the same but still since it has to maintain the link uh list in between apart from the hashing that has to do so normally we use a asset but in very specific cases like probably when we are implementing an lrl cache there we actually use something called a linked hash map which are going to come uh very soon on this video itself but uh very very similar to this you know linked has set so yeah I mean normally we use has set okay we don't really require link acid unless we have a very specific use case where we also want to you know also maintain or also remember the order in which the elements were inserted right again I think this takes two parameters uh the one parameter is basically when uh like now there are two options either you want to like uh maintain the order in which the elements were inserted or we want to maintain the order in which the elements were last accessed right so in that we can just pass a parameter to this linked hash set right so not going too much deep into that because you really don't require and that depth in DSS so you just can read about it okay but yeah so this was about sets now one last important thing that I want to show is here we used a set of integer now what if we want to use a set of student marks so let's change this to has set let's comment this piece of code right and let's make this to student marks class and let's you know uh instead of adding like this let's use the uh like this list that we have and pass it to the set because a set can also accept a collection as in his Constructor and list is a collection so yeah it will accept that so what is what was the name of the student list let me get that St Marks right so let's pass that address to student marks to the Constructor of the set right and then try to print the set okay uh this will be student marks and yeah let's make it X Okay cool so now if you want to like instead of using an integer or the Primitive or the Raptor class or the primitive data type end if you're using our own custom class okay so let's see what happens nothing much we like pretty much get the set right uh so here we can see that we have like five instances five records of the set let's say you want to see that whether this particular element is there in the in the set or not right so ideally when we when we had this set one class right and it took alsd so let's say that in the set one uh we wanted to check that whether this contains the element one right and let's say he we also wanted to check that whether this set contains set 1 contains the 1100 or 200 which is not there so it contains 11 1 when it doesn't contains element 200 right so in that case it should give me two and false because the contents method checks whether if an element is present inside the cell it returns to otherwise it returns false okay so here we get true and here we get false okay so now let's do the same thing for this uh this class that is set to uh sorry set 3 which basically is a as a type our own custom class that is the student marks now let's say if we want to get set 3 dot contains and let's say we create a new student marks of let's say we we just copy this the first one okay that is of 70 and 80. okay let's say and we pass this here okay let's comment these two lines out and now let's say that we don't want to print the set as well uh otherwise it will create a confusion so yeah so now we want to check the inclusivity of this particular entry inside the set right of student marks type now ideally this should be there and this should return true right uh and also uh we print this out so yes uh cool so now let's we'll try to print this out and ideally this should give me true because this entry is there obviously this entry is there inside the set right uh because we just thought that it's that so let's see oops it gives us false but if we print a set let's print a set this entry is definitely there then white is getting false let's print this out so we just saw that this entry is there so let's print it again you see this is giving false but you see the same increase 70 80 is there you can see Mass 870 and physics 80 this entry is there but here when we are trying to check the inclusivity it is okay saying no it's not there it's false okay so understand that why this is happening you have to first understand a little bit about how how a hash set Works behind the scenes right like whenever whenever you insert an element into the into a asset right a asset not all this Hindu has said hash code of that element is being generated right let's say okay go from java after Java 1.5 I think it is like a balanced binary search tree but for the Simplicity we will consider an English right uh so now whenever we are like putting an element inside and hash set the hash value of that element is generated right and after that hash value is generated it goes to that particular bucket where that element might lie and that bucket is a start of a linked list so it will check the linked list one by one and then it will try to compare hey is is the value of the current object that we are trying to check the inclusivity of that is passed in the contents man that is it is it equal to any of the methods in that particular list that is then inside the bucket right if it's not the case then we return false so you can see there are two methods involved over here one is to generate the hash to generate the hash of that particular uh like like object or the particular element the hash code is being called the hash code method of that class is called and when you get that hash code method of the class that you get from the object class so if this method let's say the student marks method is not implementing the hash code class we would be taking the hashcard method of the object class that is the parent class of the student marks every object class has its own hashcode method which is basically nothing but the memory address right so first based on the hash code of that particular object you have to figure out that what is a bucket number where your element might lie right and once you figure out the bucket number you go to the all the elements that lies in the bucket where I traversing the linked list or the binary search to whatever is it and it just basically compare the two elements right now this comparison is done by again this is a class of the this is the method of the object class which you can override and Implement your own equals method for your object class right now the thing is there are two two things two things we clear once we like implement this class on our own so if you don't follow everything that's completely fine the end you would have get a hang of the things right if let's say where the student marks right we have not avoided in the so you can see if I just go over here I have not overridden the hash code or the equals method of this class right so what is what is the parent of this class the parent of this class is object class because every class in Java is has its parent as an object class if it is not extending any class so in the object class the hash code is implemented such a way that if you are asking hit a what is the hash code of my current student marks it will give you the memory address right and if you are asking for the equals method it is going to like the compare the reference values of the two objects that's it that's it right so therefore what you can understand is that whenever we are creating a new object right the hash code of the memory address is changing right because when we inserted the entry of this particular student that has iron Mark 7 1080 in that particular set it at a different hash code there are a different memory address hash code is equals memory address since we haven't implemented our own hash code function right and then we again created a new student marks again we created a new object in the memory it's a different memory address and as a result as a result the set is treating this as two different objects that's it that's why it is saying hey this object doesn't exist the object of the passing has a different hash code that is why it is going to the wrong bucket and that is why it is not able to find out the this particular object do it exists inside the set right because how will the set Compass understand that hey this object that you are passing new student 7080 and the object that lies inside the set that is this 7080 this object right are same for that we have to override the equals and the hash code method in this custom class right now you will again ask that hey for integer we didn't have to write and do all these things no because integer already has his own equals and hashcard method implemented right and hash code you have to implement because otherwise how would you find the right bucket maybe let's say let's say you implement the equals method okay you just implement the equals method right so in that case what happens is this will still give you an error because if you if you don't implement the hash code method you won't be able to find out the right bucket you would you might end up going to a wrong bucket and then like you don't even hit the right bucket right and that bucket won't have your elements so obviously it is going to say no uh like it my set doesn't content is pretty element and if you don't uh like override B course method let's say just write the inverted the hash code method in that case you would go to the correct bucket but then once so you go to the bucket that is a starting of a link list now you Traverse the link is one by one but and they're like now it will be checking the equals method like hey uh this this current uh linked list uh node right is this node of the link list value is it equal to the element that we are trying to compare with and if they are not equal then it is like going to return false and if you haven't implemented the equals method it is just going to check reference which is obviously not going to be the same and it will return false and won't be able to find it so like to an action like I understand if it is too heavy for you just try to remember it like this whenever we are using a has set and we are using our own custom class right we have to override the equals and hash code method of the class which is exactly what we're going to do right now and that is going to solve our problem otherwise this contents method will fail right so let's go to the student marks and we are going to generate a hash code and uh equals to Method again these these two are very very important questions that you would get asked in every interviews and not only for interviews this this why should we override equals natural method apart from that uh you would like me there will come a lot of cases in your DSA questions where you have to implement you have to create like insert your own class inside and has set your own custom class inside the hash set and there you have to actually implement the equals natural method otherwise you're going to run into trouble so and then you would be having a very very hard time in debugging the code trust me uh so that is why these things are very important so let's generate the hash code and the equals Merit from here so you see just just generated the hash code this is like like this is what the ID generated for me so I'm not going to bother too much into it and then there is this equals method so equals method is first comparing whether these two marks are equal first they're checking that whether this is the same reference object then it is obviously true if it is not only returning false then it is checking that whether it is the two objects at the instance of the same class because it takes an object class right because it is overriding the equals method of the object class that is why it takes the object as a parameter so then we are doing the type casting right into student marks and then we are checking that whether the math set physics was equal if both the Max and physics marks are equal then I can treat it as the same object right so we save this uh and then we go here and now if you try to see that whether this this contains this particular object or not now do the reference value would be different because you're creating a new object here still this actually will say no this object is being contained in a Cell because now the hash code is no longer generated by the memory address and the equality is doesn't work on the reference values of the memory address now we have our own equals and hash code method in place and therefore it with the set will say that hey yes it will go to the right bucket for this object then it would Traverse the list in the bucket and it would one of the values inside that linked list on one of the nodes inside the link list will say hey this equals to the current object that you're passing and therefore it will return true so now you see it returns true so so to sum up things you should always implement the equals and hash code whenever using a hash set right okay so this was all about sets now we are done with hashtag and linked asset and in this picture we will see the sorted set the navigable set and the preset which is again a very very important part right so the sort of set as we saw extends the set interface to provide the functionality for handling sort of set so here uh there would be an like the here the sets would be solid so if you are trying to like pull out elements you would get uh in a sorted fashion right so the sets basically would be sorted and this is done by using a balance binary search fee so if since the elements are sorted if your Traverse in this set using an iterator or a fault Loop you would find that the sets are ordered right and and the sets are ordered according either according to the Natural ordering or according to the total ordering that means if you have passed any comparator to the set so we can pass comparator to the sorted set as well you will see that In Action Hardware coding just similar to the parity views so what are the elements we have we have this first and the last method the first method returns uh the first element currently in the sorted set and the last method Returns the last element currently in this order set okay the elements are chosen based on the ordering used by the solid set okay then we have a navigable set interface which again extends a software cell interface where with navigation methods to find the closest match for specific search targets so basically uh we can search for elements right and in this Navigator will set and it adds extra functionality on in terms of a solid set right and here you have couple of methods in the navigable set interface that is pole first pole last words are ceiling flow higher and lower these these are very important methods uh that you know power up your solid set so as the name suggests the pole first method removes and Returns the first element and the pole last method removes and Returns the last element right that means last as in according to the sorted order uh ceiling method Returns the least element in the navigable set or in the set that is greater than or equal to e right and the flow Returns the greatest element in the set that is less than or equal to higher Returns the least element in the set that is greater that is strictly greater than e and the lower is like strictly less than the argument T that you are passing now these are very very important methods and these are very very often be used in in range interval problems if you haven't checked out my range interval series range interval pattern problems so very very important form especially for Google interviews Google asks a lot of problems from there so please go and check out that video on pattern interval and in most of the videos you would find these navigables at the ceiling floor are lower in action if you also go to my calendar series problems right I have four problems in that series if you go to the video Root find it in that tree map video I have used flow higher lower so I would highly recommend you to go through these videos so that you can actually can actually understand how these ceiling floor and these these methods are used right uh so yeah I mean you can definitely go and check out those videos that will really help you a lot also you can solve a couple of questions right and like Range model is one of those questions that is a lead code hard question very frequently Asked Google and there you will find most of these tea sets stream apps these these these methods in action and then if you if you just after understanding this reading this you will solve this problems you will understand it how this is going to use so I would suggest after watching this video go and watch the point calendar series four problems I would attach the link to it in the description and then you would to like see this more in action right but I anyway I want to like uh working through a couple of methods okay now let's jump into the preset uh so we were done with has set now let's go for the three set so as we say we want to code against the interface so we want to use a navigable set or maybe we can use a setup that that also works so let's use a set only so let's say a set of student marks let's use this um three set equals to new preset right set let's import preset okay so you can see in this reset I've added this couple of entries or student marks now if I want to like uh Traverse through this reset one by one so let me just copy this and uh let me try to Traverse this preset you will find that I will be getting elements or I will getting the student marks objects in a sorted order right now the thing is key uh I am not personally comparative to this preset so that would ideally mean that the compare to interface that the comparative method will be called because the student marks implements are comparable and compared to Method will be called and based on Match marks this will be getting sorted so let's see so you see the comparative method is called comparables compared to method is called and based on Match marks it has been sorted right now let's say we don't want this and we want to sort it on the physics mask so we would pass our comparator just a resource so S1 comma S2 we will just pass the comparator the three set like a paradigm accepts a comparator and we will just say S2 dot get physics minus S1 dot get physics and now you will see this being sorted based on the top physics mass and descending order so you see this is solid on the descending order and similarly like a priority queue if you are not passing any comparator then it would expect that the type of object that you're passing should have Implement a comparable interface and if it is not implementing a comparable interface then it would give you a class cost exception as we got in the priority very similar to that right so this is preset now let's take a look at the couple of more functions like ceiling floor and all so let's create another set uh set of integer set for easy set five let's call it set five I know I'm giving very bad names today but it's fine um and since this is an integer so I'm just uh thinking that natural ordering is going to be followed because in teacher implements are compatible and that is why I'm not passing the comparator and set 5 dot at 8 set 5 dot add three okay so that's I just wrote a code where I added this uh four elements which is set five and which is basically that reset and it is going to be sorted in ascending order so it is going to print 0 1 8 3 Let's create so let's print this and let's see what it is printing let me just disconnect this power code now let's run this code and see so we get 0 1 3 8 that is it is being solved in the natural ordering of this integer class right that is the compat comparative method has been called okay cool now let's say so we have this app so now let's say we want to find the element uh that is you know we want to find a flow of a particular number right let's say you want to find the floor of 1. so flow means that we would get a number would find a closest element that is just you know less than or equals to that particular number so in that case in this case it should return one right here we have a problem because the flow method is a part of the navigable set not a normal set so that's why it would be a good way of defining this as a navigable set and that way we would not be having this compilation error because this flow method is a part of the navigable interface not the set interface right let's just uh do a print in here otherwise it would be tough okay to differentiate now if you print this you will see we get one right now if you want to say okay give me the element uh which is just less than or equals to 2 that means that is 1 again right now if you do higher in that case is strictly higher as a strictly uh greater than one the element is strictly greater than one then in that case we get three the limit is strictly just strictly greater than one is three similarly if you do lower for one we get 0 because the element which is the greatest field version one it is zero and if we do ceiling of 1 we would get 1 because 1 exist right but if we do for two you will get 3 right the element which is greater than equals to 2 and this and the least element is greater than equals to in this current set so that's it about 3 set so once again recapping in this picture we did see the set interface we saw has set right where we saw that if we have to implement the equals methods then if you have to maintain the order in a asset then we use the linked asset then we saw storage set navigable set when navigable cell gave us extra functionalities over a solid set and this normal set like giving this ceiling floor key functions and then implementation of the navigable server solid set was this preset where the elements were sorted and as a result the insertion time and the removable time of these sets were you know login time logarithm complexity because the balance binary search is well into action but for a hash set the insertion time where you know oh constant so whenever the order doesn't matter and we don't want to sort the elements then headset is definitely preferred because of better performance but in case of where we need ordering where we need sorting uh then we have to use a preset so that's all about sets and with that we run to an end to the collection inter face but we are still left with one very very important topic that is Maps so now let's jump into Maps so basically in Java collection framework map is very analogous to set right the only difference is a set is a collection but map is not right so set extends a collection but the map interface doesn't extend the collection as we saw in that hierarchy structure and the very first part of this video so let's Now quickly jump into the picture first so as you can see over here is that you know you have an iterative build right and the collection interface extends the iditable that means the collection can be iterated at every collections can be iterated then we have the list q1 set which we also but if you see the map a map interface has no relation with collections at all which idly means it's a separate interface altogether and the reason behind this is very simple so map is nothing but a mapping of a particular key with particular value that's it right so that is why it doesn't you know extend the collection interface if you want to you know like zoom in into this map interface you see that a map interface has basically again like very similar to an asset and there is a hash map that implements this map interface and then there is a slim test map that extends this hash map if you want to have an ordering of the elements we are all going to see this later in the video and then we have a sorted map interface very similar to a sorted set that you know extends the interface of a map then we have a navigable map very similar to the navigable set and then we have a tree map and we also have a new class over here that is the hash table that implements the map interface we are going to see all of this in action very soon uh so now you can see over here for sets right if you go up this first set we have a set of e right one element right and here we have a map of KV now this KV is nothing but a genetic type or keyn value this map takes two parameters two inputs and that is why here uh like it's basically two generate types are mentioned over here uh as compared to uh like list or a set which takes in one parameter right because a map is defined by an entry and an entry consists of keys and values right so as you can see in this picture this map interface has no connection with connection at all and neither it extends the iterable interface right so as a result a map cannot be iterable but what if we want to Traverse a map we want to iterate to a map we might need it right we might need to Traverse to the entries of the map right then what do we exactly do so basically for that we have this map drop entry uh interface that the this map consists of and we have certain methods exposed right that converts this into a set and we know that a set is a collection right so once we can convert this map into a set right a set of map dot entry right then we can Traverse that set because we know that set is a collection which is basically an itable so we will see all of this in action don't worry and don't get too intimidated yet okay so let's uh first look at a little bit of both Maps so as I said a map defines mappings from keys to values right uh the key value pair is called an entry right a map does not allow duplicate is very similar to set but it won't allow duplicate keys so now let's see why the duplicate keys are not allowed right because let's say that you you say that okay with these wall number is 34 right and then you want to you know the map would be confused right because it can only maintain one value of a d right uh so that is why uh the map does not allow duplicate keys and hence all the keys are unique uh and both the keys and values must be objects right that means uh you cannot have primitive data types if you have you want to have primary data types then you have to use the wrapper class right it's it's very generic right a Mac is not a collection and the map interface does not extend the collection interface right now the mappings can be viewed as a collection in a various ways which we are going to see in code very soon so it can be seen in three ways one as a key set so basically you can convert all the keys you can tell the map hey give me all the keys that you have in the map right and give me it in a form of a stack right the second thing you can do is you can you can ask the map to give all the values that exist in the map as a collection as a list right and then you can ask the map to give a set of entries and entry basically as is any object that implements that map.entry interface so we will see that in action as well so these are the three ways that we can Implement a map right so now let's look at the map interface methods so there is this one put method right that basically puts an object right inside a map so it inserts the key value entry into the map right it Returns the old value previously associated with the specified key if any otherwise it returns a null value okay then we have the get method which basically gets for a particular key it gets you the the required value for that associated with that particular key and if there is no value Associated then it returns null right then we have the remove method as the name suggests it you know basically you know removes that particular entry from that map or particular key from the map then we have the contents key very similar to a set like the set we had contains and here we have contains key and contains value and then there is a size that indicates the size of the map and then is empty function right which basically indicates the map is empty not very analogous to the set interface methods now one thing to note over here is a set is a collection of elements right and map is all about entries right and entries again consists of keys and values right so we are going to see all of these methods in action very soon when we would be having a concrete implementation of a map right so these are the methods of the map interface and whichever concrete classes would be implementing a map interface they would be having these methods and that I will show in code very soon cool now we have some Baroque operations like put all methods so put all methods is basically you can you know it's very similar to the add-on methods of a collection right so in case of a collection we have ADD right and add all instead of in case of a map we have put and put on so basically it's not adding its voting right so whenever it's a map try to remember this boot method right and then we have three more methods as I said you know if you want to Traverse the map I trade over the map we have to convert this map into connection and for that we have a key set that returns gives us a set which is a collection in turn then we have a set of values which gives us better collection it can be a list it can be a set and then it basically is an entry set which basically gives a set of map.mg right so you will see all of this in action as well now one thing the values in a map can be duplicate right but the keys in a map has to be uh unique and that is why if you see so whenever you're returning a key right it is basically a returning your set right so if you want a collection of keys it gives you a key set right because keys are unique right but the values it is a collection but for when you're calling the values method it is returning a collection because values can be duplicated now let's look at this interface that is entry uh so basically each key value in the entry set is basically represented by an object implementing the nested Network entry interface right so if you if you go inside the map right if you go inside the map class or the map interface you would see that this there is a there is this interface there is another interface called map dot entry right and uh any in any object right any object or any class which is implementing that map.entry interface right it is basically it contains this pair that is this key value pair right and and entering the entry set view can be manipulated by the methods that exist in this interface which you can see over here so there are three methods get key get value and Z value right so now let's look at the implementations of a map so now a map is a very analogous to set in terms of the class and implementations right so you can see the classes hash map and the hash table implements the unordered Maps the class link Dash map implements order values so basically uh let me break it down for you right so we have this map interface and the hash map implements the map interface right and and hashmap works very similar to a hash set right so you know the time complexity of the hashmap right if you want to insert and you want to remove an element it is like average constant time right but the ordering of the elements in a hash map similar to hashtag is not there so if you want a ordering right if you want the ordering according to its incision order similar to a link has said here you have a linked hash map that extends the map class and then you have a sorted map very similar to a sorted set where the tree map is an implementation of the sorted lamps now let's look at the hash table class so basically the hashmap class is not thread saved the end term is only one null key however the hash table class is very similar to National the only difference is it is thread save and permits non-knowledge keys and values only right so in hashmap you can have uh one novel key right you like can mapper user key which is a null value right it's pretty weird we don't use it but yeah it's possible now the threat safety provided by the hash table class you know comes with the performance penalties so basically hash marks are always the better to use we don't normally use hashtag unless it's required and in interview people will ask you these questions that what is the difference between a hash map and a hash table right so Hashem implementations basically are based on a hashing algorithm that has just mentioned the operations on the map rely on the hash code and equals method the key objects very similar to an asset so please remember whenever we are implementing a hashmap uh for any particular type we must ensure that type has this equals and hash code method implemented because hash map behind the scenes works very similar to a hashtag we have this bucketing Concepts and all those things that is working and for that the equals and the hash call method is very very important I've already covered it uh during my Set uh part when I was covering the sets right and it is very similar to that right so here the hash code of the equals method will be based on the keys and set we have the elements that we were writing the dashboard and you know the equals method on and here we'll be comparing based on the keys that's the only difference right okay so this LinkedIn hash mark maintains its element order in the way they were inserted however there is another way we can also maintain its elements in the access order right from least recently access to most recently accessed and the ordering mode can be specified in one of the constructors of the linked hashmap class which is basically also you can go and search up uh the lru cache question in lead code and you can see it you can basically solve that question using link touch map if so linked hashma find its usage in in a lot of cache basically so you can go and code out that question so then you can understand right or maybe I can cover a video on that okay so both the hashman and the lake hashmap classes provide compatible performance but the hash map class is the Natural Choice obviously if the ordering is not not an issue because again like similar to a linked assetting and handling test map also maintains a linked list uh to maintain the order so therefore uh it is suggested that if you don't have the ordering issue please go and use hash mark because it's slightly better in terms of performance than a link Dash map operations such as adding removing finding an entry based on keyword and constraint time as these hash the key as I said and finding an entry the corporations such as finding an entry with a particular value adding linear time because you actually have to go searching through the entries right so if you're searching via key that takes constant time right but if you're searching to a particular value now that we normally don't really need then you have to go through all the entries right and as I said in a linked hash map adding removing and doing the other operations can be a slightly slower because there is a link list that is maintained the traversal of map is to one of its collection views which already talked about and we will see it in code uh and the traversal time for a link has not disproportional to the current size of the map right like regardless of the increase that the map has but for an underlying hash map it is based on the it is proportional under the capacity of the map so now can you tell me that why is it so let me know down in comments down below and I will pin the right comment okay now okay so I think this is a good time to start you know with some coding uh demo for at least the hash map and the linked hash map and let's jump onto the code so let me just comment out the previous code that we had okay so let's let's create a map right so we have a map and let's we always scored against the interface so we won't in the left hand side we'll have a map class instead of a hash map right and let's create a hash map right and very similar to asset we can create a hashmap using this Constructor uh let me in Port this now please note Whenever there is the concept of hashing and asset you have to implement you have to make sure that you have you are implementing the hash set and the equals method uh you are implementing the hash code and the equals method okay so this will give an error because let's say we want to create string to integer and let's say we want to say okay uh with these ID is one let's say we take some more values map.pot Raj um to you know to and let's put some more values like Chandler and let's put seven okay so now if you want to get one of these values so we'll write map dot get ready we will search according to the key and we will get one okay so let's run the code and we'll see this is one right now let's see that we type a value that doesn't exist right then it will it will return me a null so it returns me a null now since it returns a null right what the problem that might occur is that you know you can sometimes run into an exception right okay so let's say that you know uh this map this string this this key value pair is basically of string and this is some of some like student marks let's say okay and we want to do something like this so let's say we put uh so whenever we search for this particular key we get the student marks and then we want to do something like this like dot get maths right so let's say this entry this entry if it is not there it returns null and then since it is null so null dot get Max will give me a null pointer exception error right because you can't call any method on null object right so in order to do this in order to like get rid of this is another method this is another method that we can see that is the map dot get uh that is get on default which is which really helps us a lot uh especially while we are solving BSA problems in a lot of other places so let's say if this entry doesn't exist right uh let me now change it to integer once again right so let's say if this doesn't exist then it will return me that's a zero right something like that but if this exists let's say if this entry exists like this this in this case the entry for Raj will exist and we will return two so we'll just print out the values and see for first it should return 0 because DJ Square doesn't uh is not there in the map but Raj is there right so we would get 0 and 2 right so basically we are like keeping null out of the window right and therefore we are ensuring by using this getter default method we don't run into any sort of Exception by always making a return a default value also there is this contain key method uh which we can see so this contains which is going to return true uh so you can just see this so basically it just checks out whether this key is present or not also we can remove a particular entry in a map by its key so let's say if you want to remove Raj okay so now we have removed Raj so let's now check whether this Raj is contained in the map or not it should return in false and it does right so I have removed Raj from the map okay so now let's also look at a very important concept that is very important while we are traversing graphs right let's say we want to create an adjacency list so a good way of doing so is so basically what is an adjacency list in a graph it basically is a node a collection a mapping of a node to the list of nodes it can be traversed from that particular node so ideally it is like this so this is this node let's say this this is uh like uh identified with integer so this node is adjacent to a couple of other nodes right so that is why this mapping is from an integer right it's this is the node number and this is a list right a list of node numbers which are adjacent to this particular node right so let's call this adj dot Nu attachment great let me just give a briefly work to it so that your Concepts gets clear at least on this map part so let's say this one has an edge with two right and this one no our node has an edge with three right and let's say there is this another node which is three which is an edge with five let's say these are the three nodes so let's say and this is coming uh with the help of an uh like an arraylist right so this is maintained in some sort of error list or list of pairs or something like that right okay so now let's say that we want to put this entry right so what we would do he would do put right so we would write a code like this so we will first check if adj dot get if adj dot get one right uh is equals equals to null okay then what we have to do we have to create a new error list for one right otherwise we because see right now if you if you print this error list there is no entry for one right and since there is no entry for one this there is no list right so how can you insert or uh like how can you insert uh into an analyst which doesn't exist so we have to create an analyst first so that's why we have to first you know create this error list right and once you have created this error list then we can you know put a like basically we can get the error list that is there for one or basically the adjacency list that is there for one and then we can add the element two so basically this is what we have to do so for every node basically first we have to check that hey do we have an entry for this node if there is an entry then it's fine then just add this particular node to this particular list but if there is no entry there then I know that there is no list at all so first create this list and then get that list and then add that note right so instead of writing these three lines of code it can be done using one method that we have so we don't need to write these methods right instead we can do like this so a DJ dot compute if absent right and it takes an integer the key and a function right the function is basically a Lambda right do so don't worry too much about it I'm going to show exactly what it is so basically it will says okay give me the key that is one and the next is basically nothing but the function which you want to do or which you want to execute if this key is not present and that is very simple that is just this is a function right and it just says Hey create me a new error list that's it so this is basically nothing just remember this one line of code basically it is going to say hey if this key is present okay then return the corresponding value but if that key is not present then call this function and this call function is nothing but it is creating a new error list it is assigning this error list to 1 right and then it is returning me that error list and since it is written this method computer absent is returning in that error list I can easily add the to or whatever element I want to over here so let's now look at the ways we can Traverse a map so one of the methods is uh like uh using the entry set function so let's call this map Dot and reset right and basically this gives me a set of entries uh so this is going to be set of map dot entry of a string and integer so since this map is of string and integer type so that's why this map would be of a string and integer so this would be an entry set now why are we converting this to an into a set as I told in the video that map is not a collection so it is not iterable but we need to Traverse uh through this map so therefore we need to convert the map into a collection and to convert a map into collection one of the methods is mapped out entry set which basically gives us a set of entries and since set is a collection that is an iditable we can now iterate it over the step like this so using the fault each Loop we can now iterate over this set so now it's map dot entry string and an integer we have an entry from the entry set and we can just reverse to the map and we can grab hold of the entry entry dot get key plus entry dot get done so let's now print this you see with the one and channel 7 right so now there is another method that gives us uh the map.keyset now instead of giving us the entries back it will give us the set of keys and keys are said because uh keys are unique so that is why it is running as a set so it is a set of strings right key sets from this you know map and then we can just Traverse the preset uh that is key from the key sets right and we can just print out the keys and we can also print out its corresponding values by using the map then map dot get the key right so you can also do like this and you can also Traverse the map like this so you can see with the one and channel 7. okay so these are the two ways in which we can reverse a map right so now I think this is all about the hash map so and as I said a linked hash map is just nothing it has the same methods it's just that the ordering is maintained so I'm not going to show you that uh now let's quickly move on to the next part that is a sorted map so let's now jump into the picture once again so as you can see that we have a map and this map has a map dot entry interface and using this map dot entry we can iterate over the map and then we have the hash map which implements a map interface and then we have a link that extends the hash map which basically if you want certain ordering and then hashmap uses the hashing methodologies right so you've got to have the equals and the Hashem methods implemented for a hash map now we have the sorted map interface that is very similar analogous to the storage set interface right and then we have the navigable map very similar for this very similar to the navigable set which extends the sorted map and adds some extra functionalities like searching right and then we have the tree map and hash table we are not going to talk about the hash table because hash table is very similar to an hashmap with as I said just uh illustrative and all those things so just know the difference but in reality we don't really use hashmap or we don't really need it for solving DSA problems but tree map is something that we will use a lot in action and we will jump into that okay so let's first look at the sorted map so the sort of map and navigable map interface are the analogs of sorted set and navigable set as I told you the sorted map interface extends the map interface to provide the functionality for implementing maps with sorted keys so here the keys would be sorted right in hashman the keys are not sorted and here the keys will be sorted according to your order that you'll be mentioning right so now let's look at the sorted map interface methods so in like very similar to the soft head set where you have the first and last methods here you have the first key and the last key right so basically the first key returns you the smaller scheme and lastly returns to the largest screen the software map so basically it is based on the ordering that you would be mentioning and how can you mention the ordering it can be either a natural ordering that is the type of the key or the class of the key right has to implement the compared readable interface right where it will have the comparative method that is a natural ordering and if you are like passing a total ordering that is if you are passing any comparator to the 3M are very similar to what you were doing in the preset and value here in the tree map Constructor also pass a comparator and then the comparator function would be called for comparing the two elements and according to the key sets would be sort we will see that in action as well okay and now we have the navigable map so navigable map basically just like a navigable set extends the sorted map interface to uh find the closest matches for specific targets right and basically arising methods right on top of the sorted map so you can see that there's this pole first entry pool last entry first entry last entry right it's very similar to you know the sex methods and this then you have a ceiling entry floor entry higher entry you know closest entry so these are the methods for finding the closest matches so uh like you can probably go to my my calendar video series where you would find these uh methods in action like floor entry higher entry lower entry and ceiling entry so very similar to three sets uh like when we were searching on the elements right these would be searching based on the keys right the searching would be done based on the keys and all will be done in logarithmic time right so I think these are very self-estimatory and uh like and also I've put this function interactions in my calendar series video and like in other DSA videos okay now let's quickly jump into the tree map so tree map is now the concrete implementation of this uh navigable map right and and therefore it has all the methods of a map it has all the methods of a sorted map as well as a navigable map so operations on software natural ordering of the keys but if you can pass a comparator a customer is compare it to the Constructor then that function would be used right so it GMAC uses a balance trees which delivers excellent performance for all operations but searching in a hash mark can be faster than a tree map as hashing algorithms usually prefer better performance for search because it is constant time but gmap is basically a logarithmic time but however if you want to maintain your keys in a solid fashion then tmap is definitely the way to go now let's quickly jump into the tree map code a little bit so navigable map it will code against interfaces so navigable map of let's say we want to sort we want to maintain an integer integer map or let's string integer to string map this time and let's say you have a map tree map equals new tree map right and we want to put some values the methods will be same and these put methods are coming from the map interface so there's nothing uh like fancy that we are doing here right then let's quickly insert some values or like you can basically you know take the values from here so these methods are going to be same so just to show you right and even for traversing a tree map you have these entry set methods right so these are like pretty simple uh let me just copy this code and I think uh this should be two comma Raj okay so let's um like quickly you know print the tree map so now let's run this code uh so you would see that one is with dn7 standard right so you can also Traverse the tree map like this so let me just copy this part and show you um so this is going to be very similar this let me make it to tmap and let's have to change this to integer and string so basically you can also Traverse a tree map like this okay cool so let's Now quickly print this CC one with the and seven Chandler okay so these are pretty similar so as I said the put in method put methods and remove methods will now take login time since we're using a tree maps to be very careful about it so as you can see uh the the stream apps are sorted according to the Natural ordering of the integer class that means ascending order first now if you want to like pass a comparator like you want to sort it in descending order right so then you can pass a comparator right like this where you would be saying okay sort the keys and as you can only sort the keys you can't sort according to the values uh so yeah sort the keys according to this order that is the reverse order that is the descending order so now you see the channel method will come first right so let's recommend it now this down and you will see the channel will come first then the Raj and this then this one right so this is sorted according to its order okay so there is another method like let's say we if we want to find the pole first method give me the like the first uh pull first entry or it will give me read the because right now remove the comparator so it is sorted in ascending order so the first first key is this so it will give me vidhi right cool uh then we have the whole last entry and all these things you also pulled firstly last key so I'm not going to show you that also one more method I will just show you get ceiling key right and ceiling key basically is the give me the key that is just greater than equals to a particular key so let's say let me pass three right and this should give me channel let's see yeah just greater than equals to 3 is this particular entry that is 7. since we search for the key it returned to be 7 right if you want to search for the entry then it should be ceiling entry and then we can get whatever like we can get the value we can get the key right so this is all about three Maps again this is very similar to the uh to a preset uh and three math finds it uses in a lot of places in DSA questions right so please please you know you can go and check out my calendar series and also my graph series and you would find all of these in action uh also I would highly recommend you especially after done with the asset and the hashmap if you want to have an extensive practice go to my hash map SD series video and solve all the questions from there that way you would be also learning about the hashing algorithms also you would be getting an extensive practice on the hashmab has said you know all these things uh and because these These are Concepts and if you're not uh like coding this out on your own uh you or muscle memory won't come into picture and as a result you won't be able to remember most of these methods right uh just remember the interfaces right try to like know the methods of the interfaces uh don't really try to memorize the methods in terms of class level because that won't help right because that's why your interfaces are there for right because let's say you have this ad method that is a part of collection and since it's a part of collection we remember that list use sets they all implement the collection interface so that's why all these methods will have added right but let's say map doesn't Implement a collection interface so Mac will have a put method instead of an ad right and then in order to Traverse a map since it doesn't extend the collection so we can't iterate it to a map like we can do for any collection so here we need this keysight methods or the entry set method to Traverse to a map right so these are very uh so like try to remember things with the logic and eventually with practice you would remember these methods and all like it won't come in a day even sometimes I also forget so I can look up uh through the documentations the Oracle Java of documentations right so don't worry about remembering these things too much eventually we'll solving a lot of questions and you know putting these things into action this will eventually get embedded within your head and sometimes even if you follow certain things you can obviously come back and come back to this video and also you can you know check out the Oracle Java Oracle docs right so if you go through this picture once again we see that we have covered it levels you have covered collections you have covered it readers you have covered all all the implementations have list almost all the important implementations of list we have covered dqs priority queue linked list you know we have code sets we have code Hazard three sets then we covered Maps we covered hash Maps linked hash map sorted map navigable map free map everything right so yeah our collection framework is mostly covered all the important things that we do find in action in our day-to-day uh software engineering life and also during the interviews as well I've covered most of them so this not only will help you in solving DSi problems but it will also help you while you would be working for a company when you're joining a company and also when you would be setting for any Java based interviews because a lot of companies ask the questions from Collections and most of the questions that I talked about trust me these questions are actually asked and if you understand these concepts are very scratch you'll be able to explain it in a better way from here I would be making extra couple of videos like let's I would like to make a hash map or a hash set right from the scratch right in my own because many companies do ask you to create your own hashmap right or maybe your own added list right so these are the videos that I can make tutorial videos if you want such a video do comment down below also I would like to cover generic classes so that you can better understand what these things signifies and how this type Erasure and all these things and they are converted by the compiler to the generic types and how these things are working against so that's why generic one video one dedicated video on Java generics I would be bringing out to you guys soon so don't forget to subscribe to this Channel and press the like button for more such videos and to motivate me to create such content because this content takes a lot and a lot of effort to create units we understand that you might be seeing this one video right one chunk of video uh dished out to you in front of you but this took me a lot of time you know to you know press start to read to a couple of things and then I have to jot down one of the things that I want to teach you how can I teach you what are the order that I should follow so that you don't get confused then then recording this video on right I couldn't record this video in one shot because it's such a long video then editing this also yeah it takes a lot of effort guys to you know come up with such videos tutorial videos uh they're always uh like paying for the creators to create it as compared to the other videos that we create so yeah please please have like motivate me to create such videos by you know sharing this video among your friends and the community liking this video and also don't forget to subscribe to my channel last couple of things just before going these are the things that you can probably look into and these are helpful while you're solving DSA questions uh one is this arrays.sort method right so let's say we have an array right so now let's quickly there are two methods right for sorting so one is like this arrays.sort so let's say we have a method uh new lsv create and add it like let's say we have one two three and let's see okay let me just quickly put some random numbers seven okay now if you want to sort this array you can use this sort method is arrays.sort and it will sort out the array right then we have also called a collections of sort so let's say you have a list so you can use this collections.sort right and you can pass the arraylist right so it takes this method if you see it takes an error list right and along with the arraylist you can also pass a comparator right and you know what a comparator is basically it will give you the compact function right uh also there is one more thing let's say you want to sort a list like this and that is an array right and you want to sort it in descending order so instead of just passing a comparator like doing the B minus a which you are doing you can just pass this collections dot reverse order this is also a comparator right if you see this method returns a comparator as well right so basically it is not this does nothing this collection is a reverse order reverses the ordering now natural ordering that you ideally have for this uh type right so if it is an integer and it is not an ascending order this will reverse it so it will do it in descending order so whenever you want to do anything in descending order right do the collections or reverse order or else if you want to you know do like have pass any custom comparator you want to Define your own logic based on any field also if you feel free to pass any comparator function and if you want to do it in the natural ordering like in descending order of descending ascending order of integers or something like that then collections are sort yeah is is the right way to go right and normally hit sorts a list one more method we saw from the list we can convert it to an array using the two array method at the start of the video below let's say we have an array like and you want to convert it to a list you can use this method that is arrays.as list and it basically takes a uh like an object of Ip use this method where we can pass this array right and we can store it in a list of integers so yeah one more thing to remember uh we can only do this if this is of integer edit type because it works on genetics so we have to convert this indirect into a generic uh integer then only this will work otherwise this will give an error from that um like instead of passing an array you can pass variable editing methods you can do something like this by separating a comma so this initial in turn would be getting converted to an array and then it will become getting converted well so basically you don't need to even create that so basically you see uh over here this this takes this if you see this Ellipsis right these three dots means it's a variable additive method which means that this function can take n number of parameters and behind the scenes it gets converted to an array right so if you can pass four parameters five parameters six parameters one parameter and so on right but ideally we don't need to use this normally when we use this we generally pass an array and this please remember whenever we are passing an array this should be of the wrapper class and not the primitive data type otherwise you would run into errors and one last method before we end this video is the collections that bind research uh which basically helps you doing doing binary search that takes you know a list right it takes a key right so it clicks in this it takes a key and also along with the list uh that on which you want to do the Sorting on and please ensure that the list has to be solid as we see by research rules uh and along with the key which you want to search you can also pass the comparator right so whenever you want to do some my research uh in Java uh there is this already method that is being created in collections or by research you can use that so if it finds element it will give you that index if it cannot find an element so it will give you a negative Index right and then and it will be of the formula minus insertion point minus one but the insertion point is the actual point where it was supposed to be inserted so read about it it's nothing fancy but normally in Java I would say the final resource methods uh like a lower bound report methods that we normally use a lot in C plus plus those are not really that are there in Java but they're kind of complicated and that is not going to really bother you that much because in most of the DSA interviews uh you have to write your own binary search you have to write your own upper bound lower bound the interviewer won't really allow you to use this Collections and mind research unless there is any specific use case so yeah I mean don't worry too much about it because this collections are 90 so I didn't cover it in much detail because this is not really required I have not seen it much in action especially in the DSA interviews because most of the buying such question it involves you to solve the upper bound Broadband research it requires you to implement those things from scratch right and most of the questions will enter you to do that as well so I'm not you used collections on my research a great deal but you can go and read about it I'm just telling about this giving my heads up so just in case you want to read about it you can go and read about it but other than that extremely important so don't forget you know uh also practice these videos uh so that it stays with you right and you know what's an empty so that's it for the video guys it's been a quite a long video so let's end the video here and let's not drag it any further I hope you have enjoyed this video please please press the like button and that will motivate me a lot to make such videos also do let me know down below that what are the next topics that you want me to make a video on and also let me know whether this video added any value to you and it was helpful for you also don't forget to subscribe to my channel press the Bell icon so that every time I upload such a new video You're notified and also also uh do share on Twitter or LinkedIn tagging me then what is the best part a new part that you liked about this video you learned something new from this video visited new prior to the video so I will be reading to all of your posts and comments so yeah that's it for the video guys I will see you in some other video with some other tutorials till then stay safe and goodbye [Music] laughs [Music]