Java Data Structures Tutorial

welcome to amigos code in this course i'm going to teach you everything you need to know about java oops i want to teach you everything you need to know about java data structures so data structures is pretty much a way for us to organize and manipulate data and java has you know various different classes available to us that we should be aware and how they work so this was because you guys have been requesting um that i should basically explain all of these different data structures that the java language has to offer so there you have it if you're new to my channel go ahead and literally just take two seconds like literally one two and smash that like button so i can keep on recording uh videos and courses like this if you're not part of the amigos code community go ahead and join also um the discord has been really active so go ahead and join their private facebook group is growing as well and yeah also let me know what you want to see next uh but i do have a lot of awesome content coming so make sure to subscribe if you haven't done so without further ado let's kick off this course all right so let me go ahead and create a new project just for data structures where you can have the source code on git so in here i'm inside of intellij and if you want to install intellij you can download using toolbox so this is how i basically manage all my ides provided by jetprings so in here i'm going to create a new project and in here let me pick a maven project and for the project sdk i've got 17 installed but if you want to basically choose any other version or even download any other version you can do so by saying download and then you can pick the version that you want in here but in my case i'm going to stick with the latest version as i speak which is 17 but everything that you'll learn here it will apply to pretty much all versions of java so here let me just cancel and don't create from an archetype just say next and then pick a project name so java data structures and let me also store this in my desktop there we go and for the artifacts coordinates in here you can say for example com dot amigos code and then the name of the artifact leave everything as default just give it a second okie dokie so all good now this is a maven project so you can see src main java sources resources and then tests so on and so forth so we're not going to focus on testing but we're going to basically create all the examples under this folder right here called java so what i want to do is i want to create a new package here and i'm going to say com dot amigos and then code so make sure that this is your domain press enter and there we go next let me go ahead and start with erase all right so before we actually start learning about the collections framework what i want to teach you is a race so we're going to learn first about arrays and 2d arrays because knowing how to use these moving forward you'll see that arrays are building blocks of many other data structures that java has to offer so what is an array so basically an array you can think of it as basically a list of cells or a bucket or list of buckets where you define the size now when you define the size the size is fixed so here we've got an array of five elements so it can only have five elements and the size is five now the index for the array so this is how you access an element inside of your array the index starts with zero right here so this is the zero index one index two index three index four index right so basically if you wanna access for example this blue um let's say item inside of this cell you refer to it as so the array name and then the index one and then it will give you this element in here now arrays are really fast for data retrieval because you kind of just basically define the data structure or the array itself and then if you want to access a particular element uh it basically just needs to know where it is in memory and it doesn't have to do any computation so uh later when you learn about you know big annotation so for you to retrieve a element from an array is just o of n right so it's really fast so it's compact for memory usage if the size is known delete operation though it's a little bit hard because if you want to for example delete let's say that this is here right so if you want to delete this element and you have a bunch of other elements here you kind of have to basically make sure that you kind of bring or reshuffle everything so that you leave the array with some extra space so there isn't like a delete method on arrays so this is something that you have to implement yourself but you know the lead is hard and also uh arrays or basically arrays actually they are the building blocks for 2d arrays that you're going to learn later next let me go ahead and show you how to work with arrays all right let me go ahead and create in here a class and i'm going to name this the and then erase this is because there's already a class called array so i don't want to have any conflicts with any classes that java provides so here i'm going to press enter and i'm going to have a main method and this is where we're going to have all the examples to create an array you basically have to specify the data type so here let's say that i want to store integers and then you need to specify these brackets so this tells it that it's an array now here i'm going to have an array of numbers equals 2 or in fact let's just say array of strings so here i'm going to say colors or colors depending if you are in in uk or us so here uh now we initialize this by saying new and then string and then the array now inside we have to specify the number of elements that this array can hold the capacity so here let's just say five there we go so now we have an empty array that has five spaces so if you take this example in here we have this ray that has five spaces where currently there's nothing inside index zero one two three and four so inside let's just so now instead of this array in order for us to add an element inside we have to say colors we refer to it and then we basically tell it to which index that we want to add the color so here i'm going to say index 0 equals 2 and then purple and here i'm going to say index and then this will be blue so index 1 and then we have the blue color in here so index 0 contains purple index 1 contains blue so if you want to see the array so if you want to see the contents for your array you might be tempted to say south and then colors and if i just run this for the first time in here you'll see that this gives me basically this uh random string right here and that's because in order for you to print the array so if you want to see the contents there is this helper method in here so say arrays dot and then to string and then you pass your array so this is why i didn't want to use the class so this class as a raise because there's already a class called the raise that gives me a bunch of static methods so now i can basically run and you'll see that it will take the array and stringify it so have a look so we have purple and blue so index 0 and index 1. now here you can see that the rest are no and this is because we haven't specified any values for these indexes so if i collapse this if you want to access an element at a particular index you could just say so here let me just say south and i can say colors and then square brackets and then pass the index that i want now this index is very important right so arrays index start from zero so if i say minus one in here this is not valid index and also so let me just run this i'm gonna show you something so you see that we have here purple now if i take this and then say one and let me just do this two three and then four so this indeed does work right here because you know that our array has five elements inside now you might be tempted to do this so five right so index five but this will give us an error because we haven't got anything inside of that index and in fact it doesn't even exist so you can see that intellij is telling me array index is out of bounds so always remember arrays start from zero so the zero index corresponds to the first element the first index corresponds to the second element so on and so forth so if i run this i just want to show you the error so you see that i'm not lying there we go this is an error so here this does not work so if i get rid of that and also if you want to change the uh basically value you could just reassign so you could say call is and then at index and then let's say 2 because currently it's null so here i'm going to say yellow for example there we go and if i basically take this line and then paste it here and you should see that now index three or two my bad see i even myself i got confused there so this is zero one and then two now is yellow so let me just collapse this now if you know the number of elements that your array will have then instead of having to define the array like this you can do this way so here this is the shorter way of you doing things so here let's have another array i'm going to say int this will be an array of numbers so numbers equals two and instead of saying new int and then say that i'm only going to have two numbers and then say numbers and you can see that this is long-winded this will be number let's say uh 100 and this will be index one and let's say that we have 200 right so you can see that this is long-winded so instead what we can do is we can replace all of this with curly brackets and then just say 100 and 200 and then get rid of this so this is when you know the elements that your array will have now what you have to bear in mind is once you define the array you are no longer able to change the size now how do you loop through your arrays so that's a very good question so there are a couple ways that you could loop through arrays and they are so let's start with the traditional for loop which is four and then i equals to zero so we start at index zero and we're going to loop while the uh i index or i variable is less than columns.length and then we increment i at this point we could just say south and then print the color and right here i need to access the index as you've seen so i just say i if i run this there we go so you can see that we have purple blue yellow no no if you want to have this loop in reverse you could just say for i equals to columns dot length and then here instead of i uh basically this will be greater or equal to zero and then you say i minus minus now you have to be really careful because in here so colors.length this will give you five and as i said right indexes arrays start from zero so here i need to deduct one and now if i run this you should see that the second loop right so this one here starts in reverse so null null yellow blue and then purple so let me actually show you so here if you want to know the length of your array you could just say south and then uh colors dot and then it has a length property that you can access in here so this is the length of your array and not the numbers inside of the array right because if you have no values then this will basically count them it's just the size of your array now the other way that you could loop through so let me just put this right here so the other way that you can loop is by using the enhanced for loop so it goes like this you say four and you say the data type for your elements inside of the array is a string you assign a variable in javascript you'd say in and then colors for example but in java you just say column in here and then here this is the same thing so south and then color there we go and yet another way is by using arrays dot and stream and here i'm gonna say colors dot for reach and this takes a consumer system dot out column column print line so this is method reference so this is enhanced for loop and this is using streams and for reach maybe this is very familiar if you come from javascript for example but this is one way second way and the third way that i can loop through a race if i run this there we go you can see that we have things working now one utility class that you should be aware is arrays so arrays from dot util so if i press enter have a look you have you you have stream you have fill you can fill the array to string as you seen as list if you want to convert an array to list if you want to use binary search on your array so if you want to search for an element you can compare copy copy range check whether two arrays are equals mismatch parallel sort sort you can sort your array split iterator so on and so forth so be aware of this class because it has lots of utility methods and also one thing that i think i forgot is that oops we don't need this guy here so i forgot to mention that arrays they come from this package right here so java.util.arrays so if i just click on this class and then click on this icon in here in intellij it brings me directly into this package util and you can see a raise in here and you can basically go and see how things are implemented so if i show you the structure here and collapse this have a look so these are all the methods within arrays so if you have any questions on arrays please do let me know otherwise let's move on oh right let me teach you about 2d arrays so you know about arrays how they work what exactly is a 2d array now a 2d array is you can think of it as basically a bunch of cells right here right so if i was to take basically uh all of these cells so this one and this one and then just left with this one so this is a array so this is an array basically that you've learned right now a 2d array is basically dimensional so on the y-axis and x-axis basically right so it goes up and down and you can think of it as if you want to build applications that make usage of a grid then you should use a 2d arrays now the indexes work a little bit different so here you see that 0 0 corresponds to this one and then 0 1 corresponds to the second one 0 2 this one and then as you move downwards so the y position here so becomes uh one so here becomes one and then two and you can see this is one one because so this is the second row and then the second column so one one right and the same for the rest now let's say that you want to build a tic-tac-toe game for example right so 2d arrays is the perfect scenario or maybe minesweeper i think that's the name it's also using 2d arrays and a bunch of other games that you can build way to the race let me go ahead and show you this in code so in here i do have this file called working with 2d arrays and let's go ahead and basically build our board for our tic-tac-toe game so here let's say that we want an array or a 2d array of characters so have these square brackets twice so you saw that with arrays you just have one so just like that but with 2d arrays you say two square brackets then here you give a name equals to new and then basically the initialization is the exact same thing so three and three so this is how big the the 2d array is now let's go ahead and fill this array so let's say four and here i'm going to say int i equals to 0 i is less than 3 and then i plus plus and inside i'm going to have yet another for loop in here and this will be for j while j is less than three just like so just like so and you can see that intellij gave me auto completion at this point if i want to fill the board i can just say board and then i and also j and here i'm going to say that the default value for now will be single quotes and then dash just like that so if i basically format things and basically what we have now is so we kind of basically filled the array with these empty dashes in here by having two nested loops so if i had just one loop i would just be able to loop through one single array but here we have a 2d array now let's go ahead and print the array so in here you saw that with arrays we can basically just see the contents by saying arrays dot to string but here because this is a 2d array we have to say deep so deep to string and then pass the 2d array so in our case board now if i run this there we go so you see that this is our 2d array so this is the array outside and inside we have more arrays in here right so this is a two-dimensional array now what i want to do is i want to show you how to basically set this winning player in here and basically all we have to do is just set these indexes right here so zero and then one zero and then two zero so these are the indexes for the corresponding cells so if you were to have for example a winner this way the cells would look different right so it would be 0 0 1 1 and then 2 2. so before i print if i in here say board and then i want to change the cell at 0 and then 0 equals 2 and then this will be the character and then duplicate this and this will be zero and then one and then zero and then two and then this will be one zero this will be two and then zero now at this point this is basically this scenario in here so obviously i'm not filling these but you can see how it works so if i run this again you should see that basically we don't have the exact same representation in here but you can see that now we have the values for our 2d array so 0 0 0 and then the rest are empty and to be honest because you know how to work with a race then basically 2d arrays work the exact same way but the only difference is just when you basically loop through them now what i want to show you also is if you want to inline create the array you could just say as follows so here let's just have a second board board and then two and then i can say new and then basically char array like so and instead of specifying the size inside here i can now have the default value so i can say new and then char and this is basically an array so you've seen this right so here this will be uh dash comma single quotes dash single quotes and then dash in here comma duplicate this and there we go have a look so this now is our board and now this board right here is exact same thing as the above but we just have the default values instead of filling it with a nested loop so here if i just uh format things and the board that we had was i think it was zero zero and then zero or oh my bad so uh there you go so now if i basically just loop uh board and then two you should see that this will be the exact same output if i run this have a look we have the exact same board in here but the way that i basically constructed this one was a little bit different so obviously we're not implementing the full tic tac toe game but i just want to show you how to work with 2d arrays so basically anytime that you want to have a grid use 2d arrays so you know about arrays and 2d arrays now let me introduce you to the list interface now if you recall so you've got the iterable interface then you've got the collection interface and then from the collection interface we've got various different implementations right such as the list which which we are learning about now the difference between the collection and the list is that the collection interface has details basically it's just a collection just think of it as a collection right so you can add stuff into it you can remove stuff into it and basically just a collection of elements now the list itself has way more information on how to perform certain operations with your collection or your list right so if you want to delete at a particular index or retrieve at a particular index then the list has basically that functionality which any concrete class that implements the list interface knows how to do it so you've got um basically the implementations you've got red lists you've got stack you've got vectors and others and all of these they differ the way that you access the elements so that's basically it so the list allows duplicates it's not fixed in size like arrays it's very fast for data retrievals and so that you know a list is backed by an array right so this is why i say so this is why i was saying that the array is basically the building blocks let me go ahead and demonstrate that to you in code all right in order for us to use lists in java it's as follows let's just say list and in here let's just give it a name so in my case i'm going to say colors equals two and let me just import list so this comes from java.util and there we go so you can see the import right here now with list so this is the interface and we have multiple implementations if i say new and then shift control and then space you can see all of these different implementations in here right so here the most famous is array list and it goes like that so this is now our list now if you want to add a value to your list you just say colors dot and then add so here let's just say that we want to add the color blue and we also want to add the color and then purple now this arraylist itself it's backed by an array and i'm going to show you this in a second so the way you access an element by the index you could also do it in here now what i want to show you is in here if i say colors dot and then add and then one so this works right here collis dot add new and then object this also works now when working with lists we should basically tell it which data type that we want our lists to hold right so the elements itself because it doesn't really make sense for you to have array lists or lists with a bunch of different types so to fix this you use these diamonds right here and then you say that here i should only have strings in my array and you can see that all of this now goes away and i also need to have the diamonds on this side and i'll show you what this means in a second so here now you can see that i cannot add the number one or also this object in here so i can only add strings into my array so there we go now if i want to print the array i could just say south and then colors and then run this right click run and have a look so we have an array with two elements now if i add a third one so here if i say yellow and then run this you should see that we have three elements in yellow is right here if you want to know the size of it you could just say south and then colors so the name of your list dot and then size if you want to check whether it contains so contains right here if it contains an element let's just say yellow and let's check if it contains pink as well run this you can see that the size is true it contains yellow but it doesn't contain blue right here so the api it's really straightforward to use and it should be really self-explanatory if you want to loop through your array you have the for loop so here you say string so this is the data type of the elements inside of your list and then here i'm going to say color so this is the name of the variable and then column and then colors the variable name and now i can just say south and then color there we go you can also loop using the for reach so here i'm going to say colors dot for reach and this time we don't have to say stream and i can say system dot out column column print line and finally so i just want to show you that also if you want to loop using the traditional 4i loop you can do it so here i'm going to say 4i zero i is less than and we know the size so call dot size and in here i could just say south and then i can say colors dot get and then have a look index and then i can pass i inside so three ways that you can loop through lists but to be honest i wouldn't use this one here unless you need access to the index itself so here if i run this you can see that all of this works now let's tackle this uh basically the diamonds and also let me show you the list interface so if i click on this list interface right here so you can see the keyboard shortcut down below and this is an interface and then list basically extends collection in here but have a look list and then diamond e so this is using generics right here so this is using type and basically it's the type parameter and if you're not really sure about generics i've got a complete course teaching everything you need to know about generics so i would highly recommend you for you to go and learn so basically this is the interface and then if i click on this eye icon i can see all of the implementations so have a look including arraylist so arraylist is one implementation so if i click on arraylist right here so this is the class that in here we said new and then array list so let's just have a look at this class so i want to show you that have a look the default capacity is 10 and then what's more important is have a look object and then element data so this is an array so array buffer into which the elements of the arraylists are stored so basically the arraylist is backed by an array and have a look so this is the constructor how it how it gets initialized and it says new object because we work with generics in here but what i want to show you is there is a method so if i click on structure and have a look grow there is a method called grow and all grow does is so in here it uses the arrays.copy element data with the new capacity right here so basically arraylists they use arrays under the hood so i'll let you go and explore this class but one last thing i want to show you is if i collapse lists and what i want to show you is you see in here where we say list equals to new arraylist now it is absolutely fine for you to say arraylist equals to new list but the problem here is that if you want to basically switch implementation then you have breaking changes right because you'll be referencing array list type throughout your code whereas instead you could basically just say list and then it doesn't matter whether it's an array list or any other implementation so here let's just say new and maybe let's just say linked list in here and you can see that things still work so the add method works the size works contains work the loop everything works and that's because this satisfies the contract for the list implementation so obviously we're not learning about linked lists that's going to be later but always use the interface type and then basically you choose the concrete implementation in which in our case it's a raid list now just to be clear array lists uh is basically the data structures that you're going to be using i would say maybe 90 of the time so you're going to be using array lists and this is because memory these days is not a concern again memory these days is not a concern right if you need more resources you can spin up more virtual machines on the cloud where things run these days one last thing i want to show you is so if you want to basically construct so a list right here let's just say list dot so the list class has useful methods so here have a look list of and copy but basically if you want to have a list you could just say list of and then instead of saying add blue add purple add yellow you could just pass the elements like so so blue and then yellow so on and so forth and this list right here i just want to be clear with you so this list so this uh let me just say colors and more defiable and the reason why i'm saying and modifiable is that if you want to add to this list so let's just say colors dot add and then let's say pink it's not that i like pink but basically i have a look this tells me that immutable object is modified so if i run this this will not work because so this list is immutable so have a look we have an error in here so if i show you this uh method so of have a look it says returns an unmodified list in here and you could pass as many elements as you want because they have a bunch of method overloading in here so there we go so sometimes you need to have a list like so where you kind of just want it to be immutable so this is how to do it so let me just delete that and i'll leave this here for reference if you want to have access to it but to be honest this is pretty much everything about arraylists if you have any questions please do let me know otherwise let's move on all right let's go ahead and learn about the stack so the stack data structure is one which is very interesting so basically it represents a last in first out stack of objects and the easiest way for me to explain what a stack is just think about the pack of pringles right here so you see that you've got the pringles itself now if you put one pringle inside so let's say that you stack all the um crisps right inside of the of the the pack the the pack right so the last one that goes in is the first one to come out right because there's no way that you can pull all of them and then start eating from the bottom unless you open it right but basically the last thing that goes in is the first one to come out so it extends the vector with five operations that allow a vector to be uh treated as a stack so you've got the push so the methods are push which basically allows you to push an element into the stack you've got pop which removes the element at the top of the stack you've got the peak method which allows you to see what's at the very top of the stack without removing it so pop actually removes it whereas peak it just gives you the value inside so um yeah and you've got methods such as is empty you can basically loop through it and to be honest this is a stack in a nutshell so it follows lifo so lasting first out let me go ahead and show you some code so in here i've got a class called working with stacks and in order for us to create a stack we have to say stack and then we have to pass the type that we want to store so here let's say that we want to store numbers so here i'm going to say integer and this will be my stack i'm just going to call it stack equals to new and then stack now the methods available within a stack are the push so if you want to push something into the stack you say dot and then push so here let me push one there we go and let me push a couple numbers so one two and three there we go so now we have a stack with three numbers where three is at the top of the stack so if you want to find out what's at the top of the stack you can just say stack dot and then peak so peak will basically give you the element at the top of the stack so here if i just run this you can see that we have three which is at the top now this does not remove so let me just say first south and then stack dot size so that gives us the size now if i say south and then stack dot and then pop so pop will basically at the top of the stack but also remove it so if i duplicate the size and then print it and run this have a look so we have three right here which is the first one when we peaked then the size was three in here and then pop gave us back three so basically it removed it from the stack and now the size is two so basically you see that the api is really straightforward to use so here if you want to so let me let me just say stack dot and you can check whether the stack is empty so on and so forth so here i can say empty and this will give you a boolean source out there you can see that it's false because it contains steel elements now what i want to show you is if i navigate to stack so i want to go to this stack class and let's have a look at this stack and then see exactly how things work in here but this stack have a look it has a public method push and in fact let me just show you the so let me just collapse this and open up the structure have a look the structure for this class or the methods available are push pop peak empty and search so we can search for an element but if you look at the implementation in here so within the stack whenever we say push this calls add element now where is this add element coming from well let me come back to this in a second but let's have a look at the pop right here and you can see that this has a synchronized word peak synchronized check if it's empty search synchronized and basically you can see that this is a small class but basically synchronize basically this is to do when you are working in a multi-threaded environment where any access to your stack has to be synchronized and this basically slows down the operations when working with a stack so you have to be careful when you decide when to use a stack now in here you can see that we have remove element at add element so these are coming from so if i basically click on in here show inherited have a look so i get a bunch of other methods have a look so in here a bunch of other methods now these methods so you can see that some come from list because basically the stack is all the way back to a list right but what i want to show you is so this class right here which is the vector right so if i scroll up you can see that it extends vector in here so if i click on vector have a look so vector implements list right here and if i scroll up you can see that they have some definition so basically the vector class implements a global array of objects like an array it contains components that can be accessed using an integer index however the size of the vector can grow or shrink as needed to accommodate adding and removing items after the vector has been created now the difference really between the vector and an array list is that you can see in here they say vector is synchronized vector is synchronized so you saw all those synchronized methods if a thread safe implementation is not needed is recommended to use array list right here so you can go through and basically you can see that this is the exact same thing as the array list but it is synchronized so have a look synchronize methods synchronize trim and a bunch of other synchronized methods you saw that basically this is your capacity right here so it's also synchronized and set size as well capacity so on and so forth so there we go so this is basically how stacks work in java they're very straightforward to use and basically the methods are really peak pop push and if you want to search you can do so now obviously here i could say list and then this is a stack but now instead of saying push i can say add in here and add as well and add and basically whenever you say stacked or add what it's doing is actually calling the push method in here right so it's calling whatever implementation it has for the list interface so in my case i'm going to leave the stack like so so this is usually how you use stacks in java but you know that so if i go back to the stack class it extends vector and vector implements a list if you have any questions for using stacks please do let me know otherwise let's move on so as you saw with the stack it follows the last thing first out whereas with a queue it follows the first in first out and basically it's a collection designed for holding elements prior to processing now a real world example would be for example if you go to a supermarket right so you got some groceries and you want to go and pay at the checkout now technically that is a q data structure so if you get in first you are the first one to come out right if you're getting lost you are the last one to come out so basically first in first out now the application usage would be for example if you want to build a printer right so printer is a very good example so you can submit as many pages as you want as many documents and then basically those elements or pages are in the queue for processing and the processing is basically to print the actual pages now with queue so a queue is an interface and you have various different implementations but i'm going to show you uh one of the most popular ones which is a linked list and i'll also show you how it works internally but yeah this is eq and let me actually show you in code all right let's learn about how to work with cues so cues right here we basically use the interface and here we have to use generic so this is the type that we want so in this case let's just pretty much just have a static and then record and i'm going to say this is a person and in here this person will basically have name and age so i'm going to say string name comma and then int and then h so now in here let's just say this will be the type of person and here i'm going to say supermarket equals two and then i need to say new and then because this is a queue we have a couple implementations so you can see that we have really uh you'll be using most of the times a linked list or a priority queue so let's just use linked lists because later i'm going to show you exactly a linked list and how it works behind the scenes so here this right here is the implementation of this q interface and in fact if i click on this and have a look this is an interface that extends collection and if i open up this structure it has all of these methods right here so add offer remove poll element peak and the rest come from collection so if i go back in here and let me just close this open up the project collapse this so the way that we add someone into the queue is by saying supermarket dot and then add have a look we can say add and here i need to say new and then person and let me just pass name and age so here i'm gonna say alex and let's say alex is 21. there we go so i can keep on adding so multiple people so here let me just say mariam and she's let's say 18 and then let's just say 40 here and then this will be ali for example so now we have a queue with three people now alex was the first one to be added to the queue so he's going to be the first one to come out so here if i say south and i just want to see who's at the front i'm going to say supermarket dot and then peak so here if i run this have a look we have alex so alex is at the front so peak pretty much just returns the element which is at the very front but it doesn't remove if you want to remove the person you just say south and basically supermarket dot and then pull so paul basically removes now you might have seen that we have so let me just basically log so south and then supermarket dot and then size just before and then south supermarket size in here as well so what i want to show you is if i run this there we go so you can see that we have three so this was the size then peak gave us alex and then paul basically returns alex as well but it also removes it from the queue and then we have two now the person at the front should be mariam so if i say south in here and then i just want to peak so supermarket dot and then peak and if i run this there we go have a look so mariam now she's next in line to be processed now here i'm trying to model a supermarket cue but for example if you're in a model for example a printer so this is a good data structure for it as well now what i want to show you is you see that when so let's just basically have a look at the methods in here so paul right here so have a look we have pull which retrieves and removes the head of the queue and returns now if the queue is empty so this is quite cool but you also saw that if i open up the structure in here so have a look you saw this one here so when i say add you so offer so let's just have a look difference between these two so offer in here inserts the specify element into the queue if it is possible to do so immediately without violating capacity restrictions and then it says when using a capacity restricted queue this method is generally preferable to add which can fail to insert an element by only throwing an exception in here so this is quite cool right so you should use offer when there is a capacity constraint on your queue so very similar to so in here you saw that we have paul and basically paul oops so paul retrieves and removes the head if it's not null but have a look at the remove method here retrieves and removes the head of this queue this method differs from paul only in that it throws an exception if the queue is empty right if the queue is empty this will return an exception in here so you could basically use this one pull because it will either give you the element or no but you know that you can use the is empty method to check whether the cue is empty or not so let me just go back and basically this is pretty much how you use the queue with the link list implementation and you can see that it's not that difficult so this is a supermarket queue but for example if you want to have a printer then maybe uh maybe i should have said supermarket and then q in here or just simply q right you have any questions please do let me know otherwise catch me on the next one so you saw that the linked list is one implementation of the queue interface now let me show you basically how the linked list works internally and then i'll jump into code to show you uh the actual logic so basically the linked list has is made of multiple nodes in a nutshell where you've got the head so this is the head node right here and the head node contains or each node contains a reference to the next node and the reference to the previous node now the head right here is a special one so the previous node for this uh first node points to null but then you can see so the second node in here so it has a reference to the previous and it has a reference to the next same with this third one so it has a reference to the previous and the reference to the next and then you have the tail right here so the tail has again the reference to the previous and then it points to null right here now basically this data structure and it's called a doubly linked list because you've got the reference to the next and the previous if it was bi-directional you would have just been called a linked list now each node itself contains so here so the data in it is one and basically are integers but this could be literally any data type that you want so this could be a person object it could be a car object literally any complex data type that you have you can stick it inside of the nodes themselves now link lists are very expensive on memory and that's because you kind of need to know the reference to the next and the previous so those will actually um have some weight on basically when i say weight i'm just saying that basically has extra space in memory memory these days is not a big concern i'll be honest with you but just just so that you're aware right so the reference so these two reference here so these two references they actually um need you need some more memory as well as the data itself that you store within um the node itself so i can't remember exactly uh how many bytes each of these or the reference to each node has plus the date itself but depending on whether it's a primitive or not an object then obviously it will be um a little bit more right so the the memory consumption will be a little bit more but basically so you've got the linked list now what happens when you want to maybe insert so in here let's say that you have this doubly linked list and you want to insert two right here so for you to insert a new element what you do is you basically need to create the node itself and basically have the previous and the next but basically if you want to add this node right here you kind of basically update the reference so next we'll point to the new node and then the next for the new node will point to the this node here right here just like that and then we update the previous so this one uh basically comes here and excuse me for uh this is kind of difficult for me to kind of just draw like that and so and then you have the previous one which will come from here right so the previous will point to this and you can see that it's kind of ugly but basically this is what you do in a nutshell and it represents this uh doubly linked list in here let me go ahead and show you how it works and basically you fully understand this all right so still within the working with cues class what i want to do is let me just extract this to a method so you have it for reference so here i'm going to say cues just like that and i'm going to basically remove the invocation of this method now in here to use the linked list is as follows so here just say linked list and let's also have a linked list of people and here let's just say linked list equals two new and then linked list so linked list is one implementation of the queue interface now if i open up the linked list class i just want to show you the methods that it has so let's have a look here so at the structure you have a bunch of uh public methods so have a look get first get last remove first at first contain size so node index of peak and basically uh it has a bunch of other methods that come from dq as well right so this is yet another uh basically interface in here now have a look we have the node so this is the point to the first node and we also have the pointer to the last node in here so remember you saw the head and tail so basically these are those so here they are now if i show you the uh so let's just show you the add method in here so add have a look so add we can basically pass an element into it and all it does it says link last so let's have a look at the implementation so here basically it gets the last element or the last node and then what it does is it basically creates a brand new node by passing l and e so l is the last and e is basically the data right so the element so if i show you the parameters so basically l is the previous node and e is the element and the next is null at this point now what it does it says right so now i'm going to assign the last to the new node because this now is the last thing added and then it checks whether it's null if it is then it must be a new node so it assigns it to first otherwise it assigns what used to be the last node dot next to the new node and then it increments the counter in here so you can see that also if you were to so let's just say um this is add but it's also add and then passing the index so here check position index and basically what it does is uh it does some logic whether it's not out of bounds and if i go back in here then basically just links the element if index equals to size otherwise it links before with the element passing the node at that particular index now obviously you can go and basically read through this class and just to show you that as i said if you want to get an element so you have to traverse the linked list so here get and then int in here so this gives you the node at index so let's have a look at this one here so you can see that this basically it has some logic in here but then look it has the loop in here and then it checks uh that the index is what you are looking for and then it assigns it to next and gives you back the [Music] the node that you are looking for so you can see that it has to loop through the list so basically you can go and read more about this class but now that you know how it works let me just show you so here if i say linked list dot add you can see that i can add a person or tweet this over to a specific index and at this point it works at exact same way as the one that you see here but i just wanted to show you how basically it works internally so now if you want to basically let's just have two people so let's just say alexa in here and inside now if i was to say linked list dot and have a look you've got a bunch of methods but if i show you so here we have pop we have push remove to array so and so forth but if i say for each i can loop through the linked list or i can get the iterator so dot and then list iterator and what this gives me is so if i put this full screen so this now gives me the ability to say if i want to loop if i want to loop front to back or back to front so here has next have a look right so if i say wow and then person.iterator and then has next so what i'm going to do is i'm going to say south and then person.iterator dot and then next so this will give me alex and then alexa there we go alex and then alexa but now if i want to look backwards i can just say if has so here if has previous and then i can get a previous or in fact let me just copy this in here so you see so let me just say south and then uh basically paste that in and then has and then previous and here instead of say next i just say previous there we go now if i run this i should get the reverse there we go so now i'll go alexa and then alex so you see that if you need more functionality than a normal queue then you can use a linked list without implementing the actual interface and using the the class directly now one thing that you have to bear in mind is using linked lists are a bit costly because internally it uses a double linked list meaning that there is a pointer to the next element and the previous element so that plus the data itself adds to memory and to finish off because this is a linked list right here and not the q interface directly that we are implementing we have the option to add so here i can say linked list dot and then add and have a look add last or add first right here right so i can add last or first and also you saw that we can basically add to a particular index and all the pointers to the previous next node are changed as you saw within the implementation so there you have it this is linked lists in a nutshell and in fact let me just have uh basically ali in here and let's just say ali is 18 and in here i'm going to say add and then last or if you want you can add first right so at first and now so if i print this we should see that alley is at the very first in the beginning and then the reverse is at the very last in here right so there we have it this is pretty much how to work with linked lists if you have any questions please do let me know otherwise catch me on the next one all right let me teach you about the set data structure now the set is a collection that contains no duplicates as you saw with a list you can have duplicates but with sets no duplicates are allowed and you can think of it as a bag which you don't know what is inside and why am i saying this and that's because the set doesn't guarantee order right so if you add a bunch of elements inside and by the way no duplicates if you want to get them in that particular order it's impossible so set doesn't guarantee order which means that you kind of have to go into the bag and basically you kind of don't know what's inside and you just take one bowl in this example let's say that you've got a bowl of different colors and you just take one and whatever comes is whatever you get so uh basically sets contain no pair of elements e1 such that e1 equals to e2 and um at most one node element now as implied by its name this interface models a mathematical set abstraction now let me go ahead and show you in code it's really useful when you don't pretty much you don't want to have any duplicates inside so in order for us to create a new set we basically say set and right here we can basically have the type so let's just have a static or we can just have a record and this will be a ball right here so ball and inside i'm just gonna have the color so string and then color just like this now here i'm gonna say that we have a set of balls there we go so i'm going to call it balls equals two and then here i can say new and have a look we have a couple implementations so we have the tree set or we have the hash set so tree set basically uh gives us order so it preserves order and is backed by a tree map in here and we have also the hash set and this is backed by the hash map in here and you'll learn about hashmaps later but let's use the balls with the hashmap so we don't really care about ordering so if you want to add something to your set you say balls dot and then add new and then bow just like that and then let's just say blue for example there we go so now let's also add a yellow ball and let's also add a red bow right here so now remember i said that if you want to basically get something from the set so if i say balls dot and have a look i can only check whether it contains an object it's empty to array but to be honest that is it right so if you want to basically get a particular ball in here so if i say get there is no get because the order is not guaranteed right so just imagine a bag of balls and if you put your hand it's whatever you get from it so if i use the iterator so we can actually loop through using iterator or for which so let me use for which here and if i say system dot out column common println what i want to show you is so if i run this have a look we have red blue yellow so even though the first ball that we added was blue when we read it back out the order is not guaranteed so now we have red blue and then yellow right so yellow was actually added uh second but it's given to us third so now what i want to show you is so if i was to add so if i say balls and basically you've got methods such as size contains and by now you should know all of these like it's empty so on and so forth you also have a retain so you can retain based of another collection so you can imagine have two balls and you want to retain only one one bag that contains all the ones in a different bag then that's what you use and if i scroll down there's a bunch of stream methods and basically if you want to learn about streams i've got course on streams but what i want to show you is so the api is really straightforward but if i say uh oh actually let me just duplicate this line in here and if i say south balls dot and then size if i run this check this out we have three inside right so even though so even though i have this second statement here so i try to add something it basically rejects it and remember i said duplicates are not allowed with sets so that's the the reason why why you'd use sets so also you can actually specify your own way for how these work but basically if i wasn't using a record and if i was just to have a static class and then ball and in here let's just have so i'm going to say string and then color and have a constructor to this so what i want to show you is the following so if i run this now check this out so now the size will be four so why is this right so y is the size four well that's because in order for you to use sets correctly you need to override d so the equals so right here i'm gonna say equals there we go next next next and now i did override the equals method and this is how um it works with records as well so here let me also override it to a string method there we go and now if i run this there we go so now you can see that we are back to three in here so again if you don't override equals an ash code so equals and hash code so these two methods comment you'll see that even though you think that they are the same right so what is actually doing is comparing uh the values in memory so whether they are pointing to the same object right but what we want is the actual fields and properties within it so for that we just basically uncommon this and there we go so i thought i would show you this because it's really important i understand exactly what is happening now obviously so balls dot balls dot and then remove so you can remove a bowl you can remove you can remove a bowl from it so if i was to remove this uh let's just say that we want to remove the red bull right here so if you want to remove you just remove it like that and if i run this we should see only two balls now inside because here's the duplicate and we removed red and to be honest this is it so if i'm curious about how this works internally i always suggest you to go and basically open up this method for example remove and how it works right so here we have the hash and then set so have a look because it's backed by a map it just calls map.remove equals equals to the present right so if you want order to be a factor in your set you could use the so tree set in here and also there's an enum set that you can use and other implementations so this is pretty much how to use sets in java if you have any questions please do let me know otherwise let's carry on okey-dokey so you've learned about the collections and iterable and lists and all those interfaces and their implementation now obviously because we're learning about data structures uh i need to cover about maps right so maps also are one data structure that you're gonna be using and i would say you could basically use maps to solve majority of the coding challenges that you are faced with because they are so powerful now a map is just a collection of key value pairs to be honest and basically so this map right here is the interface and you have a couple implementations so you've got the hash table right here and you've got the hash map so here nulls are not allowed and it's synchronized so you'll see if you want to do a bunch of multi-threaded stuff then hash tables there's a bunch of synchronization which slows on things and you've got and then you've got the hashmap right here where um nulls are allowed in here and it's not synchronized in a nutshell right and then obviously you've got the linked hash map so you've learned about linked lists so basically uh it works based of a doubly linked list which is a little bit slower then you've got the sorted map right here which then basically this map right here so navigable map which then you have the tree map which basically is just a map which is basically sorted and nulls are not allowed as well so this is the general overview of the map implementation that java offers so obviously let's go ahead and learn about it so as i said a map is a collection of key value pairs the keys cannot be duplicate and each key can map to at most one value so here you can see that the key right here is one for example so this is the number one and then you have a value assigned to it now these keys they cannot be duplicate and you can assign at most one value to each key and if you come from languages such as javascript an object right so an object is a collection of key value pairs is the exact same thing in java let me go ahead and show you how to work with maps so to create a map in java we need to say map and the map takes the key and the value so here let's say that we want the key data type to be an integer and for the value we want this to be a person so this could be literally anything that you want so obviously we don't have the person yet but what i'm going to do is just say new and then uh in here let me just have the record first so record and then person and inside it's just going to take the string and then name just like that there we go so now if i put this full screen and press shift ctrl and then space you can see that we have a couple implementations so we have the hash map we also have tree map we have hash table identity hash map linked hash map weak hash map concurrent so on and so forth you can see that there's a bunch of them also we have this interface here for a sorted hashmap basically we have a bunch of these implementations and if i click on the map class and then basically just click on this icon and here you can see all the different implementations that i have in here including inum map empty map so on and so forth so let's just stick with the hashmap so this is the most common one so hashmap now first to insert to a map we just say map dot and then put so here if i say one and then here i need to say new and then person and just pass the name so here i'm gonna say alex so now our map has one person in it and the key is one so if i was to basically add key number two in here and then let's just say this is alexa and key number three let's say that this one here is mariam now just be aware that the keys must be different right so the keys this is what uniquely identifies an element inside of this hash map so if i now let me just say south and then i can say map and i just want to see what's inside of our map there we go you can see that our map contains three entries so this is alex this is alexa and this is mariam so here if i was to duplicate this and try to add miriam again watch what's gonna happen there we go so basically you can see that it has no effect right so we didn't add mariam two times right and in fact if i was to say mariam and then two what's gonna happen is the latest insert in here will override the key that you have initially provided for mariam right so be careful so the keys must be unique otherwise you'll be overriding things so with the map we can basically check how many elements we have inside by just saying in here we can say south and i can say map dot size we can also get d so uh map dot and in here i can get so i can say get and this is basic based on the key so key number one and this should give me alex we also can so south and then map and in here we can check whether it contains the key or not and then let's say four we know that there is no one with uh key four so let me just also say south dot and here we can get the entry set in here so entry set this will give me all the entries we can also get the key set so map dot and then key and then set let me just swap this around and let me just run this so you can see what we have so there we go so you can see that the size of our map is three we say get one so this is alex we said contains key four this is false and then the key set you can see that this gives me back a list of numbers and then we have the entry set which basically just gives me the entries in our map so obviously you can basically then loop through so uh i could say for example uh map dot entry set dot and then for reach and i can say system dot and then out column column print line and what this gives me is basically all the entries so this contains the key and the value so if i was to in here replace with so if i just replace with the lambda instead so here i could say x dot get key plus and then plus x dot get value so let me just put this on a new line so basically what is happening now is you can see that we do have this loop where we looping through each element by getting the key as well as the value so we could also loop by saying map dot for reach and this takes the integer which is the key and then the basically the value itself right if you don't want to use the entry set so you could do it this way right here where i can say south and then integer so that's the key and in fact let me just rename this to key and then plus and then plus and then the person itself so if i run this you can see that this should also work there we go so this is the second loop in here you can also delete from the map so here you could just say map dot and then remove and to remove you have to pass the key that you want to remove so here let's just say that we want to remove three so three was mariam so if i run it you should see that so initially she's in here mariam but then we deleted it and she's no longer in here when we loop through the map so you can see that this the api is quite straightforward you can also say map dot and you can have these compute if absent which takes the key and then um the function so this is whatever you want to perform if the key is not present or if you want to compute if the key is present then you can do so if you want to remove everything from a map you could just say dot clear this gets rid of everything from the map you've got get or default so in here so if i was to say south and then map dot get and then we know that three so we've deleted mariam so if i run this you can see that this gives me null but you can say dot and then oh actually not dot but get or default and then you can specify the default so three is what we're looking for and if it's not present i'm just going to return a brand new person and i'm going to say default so run this and instead of no we should get the default person in here so the api is quite straightforward to use and there's a bunch of other things so replace replace all you want to get all the values so without the keys you could just say south and then map dot and then values i think i've showed you the keys as well right so uh where is it yeah so key set in here and if you want just the values this is how you do it and in here let me see if there is keys all right so yeah so it's called key sets i've showed you already the key sets and you've learned about sets you should know that with sets there shouldn't be any duplicates in it so hence a set so if i run this there we go so you can see that these are all the values so alex and alexa so this is pretty much how to work with maps in java next i want to cover something which is really important that you should know when working with maps okie dokie so let me go ahead and show you what exactly is the hash code and hash functions what they mean and how they are super useful when working with maps so when we say map.put we have to pass the key and you saw that we could use basically if you want a a an integer you just pass an integer and the keys cannot duplicate right now this key right here it goes through what is known as a hash function and a hash function basically is a function that produces something known as the hash code now what the hashcode really means is mapping an object to its integer value now you can call the hash function on the same object and it will always produce the same hash code it will always produce the same hash code now internally when you basically say map dot po and then one so one goes through the hash function it produces the hash code in this example here it's one and then it stores one and then the value associated with it now for integers the hashcode is the number itself and you'll see this in a second but for example if you were to say map.put and a new person jamila right here so this new person jamila goes through the hash function associated with it it produces the hash code and in this example you see it's -2083 four seven six nine eight five and basically this integer right here so this negative integer right here is what maps to this person right here called jamila so i can call the hash function on this person one million times and it will always produce this hash code right here and this is what internally the hashmap or all of them or all of the map implementations use internally right so it's not efficient for it to use for example the object itself to perform the key lookups so with maps lookups are very very fast because of the hash code and obviously there's a lot more to these hash functions and hash codes but this is in a nutshell how it works now obviously i'm going to show you exactly why do you need to override the hash code so this is something that i've mentioned before but you i didn't actually explain but let me go ahead and teach you why you need to override the equals and hash code on your classes let's go ahead so to demonstrate this what i'm going to do first is let me just extract this so you have reference to it i'm going to say maps and in here what i want to do is i want to have a new map so i'm going to say map and now what i want to do is i want to switch the keys for a second so here this will be a person right here and let's say that each person has a diamond so here let me go and create the record so this will be a record and then diamond and then string name there we go so we have the diamond in here and i'm just thinking out loud so here this will be a map equals to new and then hash map there we go now let's add a person so map dot put new and then person and let's say that this is jamila for example and jamila has a diamond so neo and then diamond and let's say that this is an african diamond so african diamond and to be honest i know nothing about diamonds so there we go so now we have this map that has one person which is the key and then the value is the diamond now what i want to do is i think you've seen this so let me just change this from a record to a class so class and inside i'm going to have the string and the name and add this to constructor there we go let me also override the two string and there we go and also so in here i need to make this static so let's just make this static just like that and the errors went away now if i so i just want to show you that what happens is if i say south and then map dot and then get new person and then jamila so let's see what's going to happen here so i'm going to run this and check this out we have no who what is happening here so we kind of have this key right here which is person but when we say map dot get new person and then jamila so this is actually saying that there is no one with that key well we know that there is and that is jamila right here but we are missing something very important and that is to override the hash code so usually if you use records all of that is provided for you by default but what we have to do is we have to basically say a hash code right here there we go and by default the contract is if you override the hash code then this will also override equals so equals is when you want to compare where the two objects properties are the same so all the properties and then this hash code right here this is what internally is used for the hashmaps so this is the hash function that returns this hash code right here so this comes from objects.hash and if i look at the implementation of this this uh basically looks at the eraser hash let's just follow that through and you can see the implementation right here but basically what is happening now is so whenever so if i say let's just basically do this if i say south in here and then let me just grab this line and then paste it here so this is uh basically these are two objects which are completely different right but if i invoke the hash so let's just invoke the hash code on these objects so hash code so these they'll be the same no matter what and this is what's internally used whenever we basically want to find a person so basically it takes the person it gets the hash code and then it looks up so it performs a lookup on the hash and never on the object itself so if i run this i just want you to see that there we go have a look at the hashcode the hashcode will always be the same have a look so this is the hashcode and right here we no longer get no but we do get the diamond associated with this person in here so if i just for a second so let me just remove this and then run it again you'll see that this will break and have a look at the hashcode so now even though there are two exact same uh objects right so new and then jamila so here have a look so new jamila and new jamila so these are basically uh identical but because we didn't override the hashcode so what it's doing is so again everything is an object in java so if i click on so not here but if i click on structure and then basically click on hashcode have a look so this uh will be implemented in subclasses right so if i click on it you'll see that there's a bunch of things which are in red in inheriting this but by default if you don't override then the hashcode will be different so if i go back in here and the reason why it works with integers so with integers for example you don't have to override any hash code and that's because so let me just collapse this so that's because with integers so let's have a look with integers so here if i look for the integer class so integer and in here have a look we have the hash code so this is a method which gives us the hash code and by default is just the number itself if we look into the string class so string have a look this string class it's a little bit different so the implementation is a little bit different and you can see that this will just ensure that for any given string if they are the exact same continent value they will produce the exact same hash code so hopefully now you are pretty much aware of how to use maps and just remember that you need to always override the equals and hash code so equals is for equality and this is to be used within the map itself so that for any given identical object they will always return the exact same hash code so to be honest this is it if you have any questions on maps please do let me know and also as i've said there are other implementations so here new and then have a look we have a sorted map we have hash table this is actually an interface but we have hash table we also have linked hash map wake hash map concurrent for concurrency and others so if you have any questions on hashmaps drop me a message otherwise catch me on the next one okey dokey i hope that now you have a complete understanding of the data structures that the java programming language has to offer so i would say lists and maps are the ones that you're going to be using most of the time unless you are working within a multi-threaded environment but i would say lists and maps are the ones that you're going to be using most of the time and to be to be more more precise lists right because these days memory is not a concern if you need more resources you just spin up a new pod or a new ec2 or a new vm somewhere in the cloud if you need to my channel go ahead and subscribe give me a thumbs up so i can keep on recording these videos also if you're not part of the immediate school community join both the private facebook group as well as discord the community is growing and yeah it's all for now and let me know also what you want to see next and i'll catch you in the next one

Channel: Amigoscode

Views: 37,437

Keywords: amigoscode, java tutorial, learn java, how to code, java data structure interview questions, java 17, maven tutorial, intellij idea tutorial java, intellij idea, collections java, lists in java, arraylist in java, arrays in java, maps in java, sets in java, java data structures cheat sheet

Id: 8MmMm2-kJV8

Length: 99min 49sec (5989 seconds)

Published: Tue Nov 23 2021