Computer Science: DATA STRUCTURES (Java) | Scott Reese | Skillshare

Computer Science: DATA STRUCTURES (Java)

Scott Reese, Engineer & Investor

Computer Science: DATA STRUCTURES (Java)

Scott Reese, Engineer & Investor

Play Speed
  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x
9 Lessons (1h 35m)
    • 1. Introduction

      1:16
    • 2. Arrays

      9:25
    • 3. Stacks

      7:26
    • 4. Queues

      7:42
    • 5. Linked Lists

      13:23
    • 6. Maps

      11:22
    • 7. Trees

      17:47
    • 8. Graphs

      24:15
    • 9. Wrapping Up

      2:32
  • --
  • Beginner level
  • Intermediate level
  • Advanced level
  • All levels
  • Beg/Int level
  • Int/Adv level

Community Generated

The level is determined by a majority opinion of students who have reviewed this class. The teacher's recommendation is shown until at least 5 student responses are collected.

140

Students

--

Projects

About This Class

Welcome to an introductory course on data structures! These are the fundamental building blocks on which all efficient and elegant software applications are built. If you have an interest in learning how to code, or you are intentionally pursing software development as a hobby or profession, knowledge of common data structures is absolutely paramount! Without this knowledge, your application performance and design will suffer, and so will you in any technical interview. The good thing, however, is that learning the various popular data structures used in software development is honestly quite simple and fun! Watching this course will expose you to the 7 most commonly used data structures out there, and afterwards, you'll just need to do some practice. Enjoy!

Meet Your Teacher

Teacher Profile Image

Scott Reese

Engineer & Investor

Teacher

Class Ratings

Expectations Met?
  • Exceeded!
    0%
  • Yes
    0%
  • Somewhat
    0%
  • Not really
    0%
Reviews Archive

In October 2018, we updated our review system to improve the way we collect feedback. Below are the reviews written before that update.

Your creative journey starts here.

  • Unlimited access to every class
  • Supportive online creative community
  • Learn offline with Skillshare’s app

Why Join Skillshare?

Take award-winning Skillshare Original Classes

Each class has short lessons, hands-on projects

Your membership supports Skillshare teachers

Learn From Anywhere

Take classes on the go with the Skillshare app. Stream or download to watch on the plane, the subway, or wherever you learn best.

phone

Transcripts

1. Introduction: Hey there. So if you are currently pursuing computer programming as a hobby, a major in college or as a profession than understanding the data structures coming, the used throughout the software development world is going to be paramount to your success as a developer. Thes things come up in interviews, they come up on the job. And quite frankly, I have never written application. That doesn't leverage one or more of these different data structures. And this course is designed to give you a great introduction into the seven most popular data structures in the field. You're gonna learn about a raise, stacks, queues, linked lists, maps, trees and graphs. And once you understand all these different concepts, you'll be able to leverage them in your own applications so they can run in the most simple and efficient manner possible. And that's indicative of a developer who certainly knows what they're doing, right. And just as a introduction into who I am. My name is Scott Reese. I'm a recent college graduate from UC Berkeley. I have degrees in computer science and economics. I currently work as a full time software engineer in the financial services industry, and I could tell you that from experience, hardly a day goes by or I'm not actually writing code and using one or more of these different data structures with the various applications that I work with. So with all that being said, let's dive in. 2. Arrays: Okay, welcome to the first video of this course on data structures, which will be taught in Java, obviously, as you can see here. And I've designed this course so that every video is going to central around one specific data structure. And in this first video here, we're gonna be talking about something pretty simple. We're gonna be going into what's called a raise. And you know, if you have any prior experience or background in computer programming, then array should hopefully be something that you're already familiar with or have at least heard of. Um, simply because, you know, these things are so commonly used and are available on pretty much every computer programming language offered nowadays. So and they're they're honestly, very simple and easy to use and offer some great run time benefits. So I'm beginning until that in a second. But first, conceptually speaking, what is an array? Right in array is simply a container of sorts that gonna hold pretty much anything, anything that you want continuously in memory. And so what I mean by that is let's say, you know, you wanted to create a list of numbers, right? Maybe 100 numbers Well, an Array would be a great candidate for a data structure to achieve that goal, because by its design, it will hold all those numbers in sequence of memories. So every number is gonna be stored one after another in memory. And as you'll see in a minute, that's going to give you some really great runtime benefits in terms of trying to access different elements or numbers in that array, it's gonna be very fast and efficient. So, um, gonna dive right in here with an example. And, you know, even though this is a data structures course, you know, these examples are all gonna be in Java. So you know, if you need some brushing up on your job Oh, or you've never seen it before. I'll try and be as descriptive as possible with what I'm doing. So that, um, the syntax of the language is that is not something that will confuse you. So we're gonna do here in this main function is we're just gonna create in a rave as a variable. It's gonna hold 10 integers. We're going to assign some of the positions in that array with some numbers and then at the end, we're gonna create a little four live that's gonna live through each number and print them out. So something very simple and easy, but well, certainly demonstrate the the benefits and the capabilities of in a rape. So to create a variable, that's gonna be an array in Java if to specify the type of the variable first. So the syntax here means we're gonna be making an integer array, and we'll just call a variable array to make it simple. And then two and Stan, she ate it. This is what you would do. You need this new keyword here and then with a very similar sin Taxes. You see, Over here, we're specifying the length of that array. So this variable is going to be an integer array that holds 10 numbers. Very simple. And so the way you would assign values to certain positions in this array, right. We have 10 total positions to play with is simply through the syntax of the name of the variable. And then you have to specify an index equals, and then whatever you want, right, Let me just make a few of these here so it can phase the point clearly calls to three. There you go. So what this is basically doing is, um, before actually proceed? One thing to note is a raise. Are what's called zero indexed. Meaning the first position in the array is going to be accessed with this zero as an index , right zero corresponds to the first position in this array. One corresponds to the second position in the rain. Two corresponds to the third position that a rape so might be a little bit weird to see this if you're, you know, if you're a brand new beginner with a raise and data structures. But this is simply how arrays across really every language that I've ever seen, um does things in terms of how you access and assign values. So what we're doing with these three lines of code, as we're saying, you know, the first position in this race is going to be a sign of value 10 and in the second position in this story is gonna be a sign of value 20. And then the third position is gonna have the value 30 right? And with Java, one cool thing, that one cool thing, That job a does is, you know, when you create an array for the first time, all the numbers in that array are going to be just by default, initialized to zero, right? So even though we've only assigned the 1st 3 positions of this raid to certain numbers, all the rest are going to just be zero, right? So it could be a a nice default behavior that you I wanted to have, so just keep that in mind. But, um, here we have a signed the 1st 3 positions of the right to 10 2030 and then we're just going to make a four loop. Um, that's going to generate over this array and just print out each number. And so the way you could you could do this in Java is through the syntax here. And so one cool thing with Java is as well. In terms of the rays, they have a length attribute that you can quickly access to just pull out the length. And so this full it is basically saying, you know, we're gonna create some integer, I it's gonna be our index. And as long as eyes less than the length of the array, which is 10. Right. So as long as eyes less than 10 we're going to do something. And that specific thing that we're gonna dio is like a print. Um, I want to see her. Here we go. I'm still I've been a lot of go programming. So some of the this in tax and the difference function names went out are still a little bit out of whack for me. I haven't used job in a while, but this is how you would do it in Java. And so what we're doing here is printing out each number, and the I variable that we've made within this four loop is gonna act is gonna act as our index, right? So every time this loop it a rates, we're going to pull a certain number out of the array and printed out right, and I was going to be initialized 20 to begin with. So it's going to pull out the first number in the array, and then I was gonna become one, so we're gonna pull it the second number in the array than I was gonna become to pull it the third and so on and so on until I becomes 10. Which, um you know, with the way you index arrays, there is no 10th index unnecessarily with this a raver. Very. But we've made the greatest index Will be 99 corresponds to the 10th position near a. And so once I becomes 10 this Luke's gonna break, and then that'll be it. This function is now done. So I'm gonna go ahead and run this function. It's got to compile and then build and then run. So there we go. So, as you can see here, um, as we were iterating over this array, we put it out. Each number in the 1st 3 numbers are 10 2030 as we had specified. And then the remaining members are all just gonna be zero right? And you can you can come if you want 10 numbers, makes everything checks out. But simple. Is that right? And so, before ending this video, just want to talk about the benefits of an array. Um, so if you wanted to do something like this, you wanted to have a list of numbers or list of strings, a list of objects, whatever it is you want and you want to be able to access various positions or various elements in that array quickly, an array is definite something you would want to consider right? Because of the way these things are stored in memory, right? Every element is going to be stored next to each other in memory. Then, if you want to pull out some random number, right? Maybe if we had an array of size a 1,000,000 you wanted to pull out the 426523rd element in the array, right, as long as you know. Or as long as the operating system knows where that array begins in memory, then it's simply a matter of doing a very quick, um, a little bit of arithmetic. Just some addition, basically to figure out where that random number is somewhere in memory as well, right? So whether you have a small array of size 10 or a very large array of size 10 million and you wanted to access random numbers or in an elements not array, however you wanted Teoh, it's going to be a constant time procedure, meaning it's going to take the same on a time to access any position in that array. The operative system simply has to dio some arithmetic, some addition really quick. And then it will know exactly where that number is in memory. So, um, definitely, if that's a use case you wanted to have in your program, a raise would be your best bet in regards to that. So I hope that all made sense. And I'll see you in the next video where we're gonna be talking about stacks. 3. Stacks: All right, welcome to the next video in this course, and in this one, we're gonna be talking about stacks and as we'll see here in a second stacks and queues, which you'll learn about in the next video function pretty similarly to a raise and, in fact, under the hood there typically implemented using a raise. And then there's just some abstraction on top that actually provides their core functionality, so you can understand the rays, then understanding. Understanding stacks and queues should be very straightforward, Um, and so before I get into the example here, just conceptually speaking, a stack is also a container of source, just like in a rain. And you know, you can store whatever you want numbers, strings, objects, etcetera. But the major difference here, between stacks and a raise is with an array. You are able to assign values to any position in that array, right, and likewise, you can take numbers out, or look to see what's in the array at whichever position that you want. Stacks and queues, as as you'll see later on, don't function that way. You basically can just put things into it and then take things out and stacks and queues will function in just a different manner in regards to how they do that. So a stack coming with a common phrase you might hear is they, um, operate in a last in first out ordering. And what I mean by that is, you know, um, if I had a stack that just holds numbers and I'll make an example showing on this in a second, but five a stack that just holds numbers and I put numbers 1234 and five into it. Well, five was the last number I put into the stack, which means it's gonna be the first number that comes out when I start taking numbers out of it and want to take five out than four was the most, most recent number I put into it. So that's gonna be the next number that comes out. So if I put numbers in 12345 in that order, and then once I start taking numbers out there, basically gonna come out in reverse order 54321 So that's the example. I'm going to walk you through here, so I'm gonna make a variable called, um called stack. It's gonna hold numbers. We're gonna put things into it, take things out and then print everything out to the terminal so you can see exactly how it's it's operating so and job others a class called stack that you can use to And Stan sheet one of these things. It's gonna hold integers as I said, and let me just write this out here for a second, right? So similar to what you saw with the Rays in the previous video. To make a variable, you got to specify the type first before you get to the variable name. And so it's gonna be a stack that holds integers. And we're calling the variable stack right to keep things as consistent as possible. Um, so that's very simple. And then what we're gonna do is we're gonna make a four loop that's just going to loop through numbers zero through nine. Basically, Amber is gonna put those numbers into the stack, and the way you would do this is, you know, this is not specific. Just to Java. A lot of languages that have stacked classes built in, they all kind of use the same nomenclature in terms of the methods you can call on them. So typically, when you're dealing with stacks, when you want to put something into it, you're gonna want to use this push method, right? And this is the function that you are the method that you would call to actually put something onto the stacked, push it onto the stack, right. And so right here we can see little four loop just going to reiterate through number zero to but not including 10. And every time this Lupita rates, we're just gonna push the value of I onto the stack right now, actually, make a little prince statement of here That just says, you know, um, putting numbers in something like that, right? And then I'll actually print out each number that we're putting into the stack as we're doing it. So everything becomes very clear once this main method runs. So there we go and then something cold in there. So once we're done putting numbers into the stack zero through nine, we're going to then have another loop at polls number out. And so all this stuff another little prince statement that says, um, you know, pulling that could spell correctly pulling X pulling numbers out, dot dot And then, in this case, we're gonna use a while. Loop numbers can say, while the stack is not empty. So what this means here? You know, this stack class, this or the stack instance we have right here has another method called is empty. And this method method will return true if the stack is indeed empty and the exclamation mark here means the opposite. So this is basically saying while the stack is not empty, we're going to pull something out of it and then print it out. So the way you take something out of a stack and again, this is gonna be something that you'll find across a lot of computer programming languages is there's gonna be another method called Pop. And this is how you just taking number out of the stack, right? And that's it. This is gonna be a little main method that simply creates a new stack, puts numbers zero through nine into it, and then pulls all the numbers out of it until it's empty. Simple. Is that right? Um, so I'm going to run this main method going to compile and then run. And here we go. So you can see or hear putting numbers in. We're putting numbers 0123 Hold up to nine in that order and you'll see right here right again. As I said, stacks function as a last in first out kind of ordering. So since nine was the last number we put into the stack, right, it's gonna be the first thing that comes out, and then every number thereafter is basically gonna come out in reverse order, right? And that's all there is to it. That's exactly how stacks work there. A simple, neat little data structure that just allows you Do you know, hold some data or whatnot temporarily and then pull them out when you need Teoh in reverse order. And it's a simple Is that right? In my experience, whenever I've had to use stacks on, they do come up in interviews quite a bit, actually. So these were definitely something that you won't understand, but what a typical use case is. You know, the are often a part of some sort of algorithm, right? And you'll see this later in the course when we get to binary search trees. Um, but you know when you want to traverse that tree, for example, and this all makes sense in that video. But when you want to traverse a binary search tree, one way you could do so is using a stack. So they're very helpful in that regard. And so, with all that being said in the next video, we're gonna start talking about cues which, as you see, are almost identical to Stax. Except we're just one little little little difference. So when you ready to move on to that one, I'll see you in the next video. Thanks. 4. Queues: welcome to the third video in this course on data structures. And in this born here we're going to talk about cues. And, as I said in the previous video, cues and stacks are basically identical in almost every way except for one major difference . And that's simply the order in which things can come out of cues. So with stacks, you know, if you remember, the last thing that was put into a stack is the first thing that comes out with cues. It's the opposite. The first thing that goes into Q is the first thing that comes out right. Stacks are last in first out cues are first in, first out, and this will become a little more clear once I start walking you through this example here on the set up is going to be basically identical to the previous video. We're just gonna make a que variable appear that's just gonna have a for loop afterwards. That just puts numbers into it and then a loop afterwards that takes numbers out, gonna print everything out to the terminal so you can see exactly how these numbers are being put into the Q. In terms of their order and then, most importantly, how these numbers are then coming out of the queue, right in terms of their order. So just kick things off here. Gonna make that Q variable. Java has what's called an interface that allows you just to make Q very, simply easily. So we'll just call this variable que keep things simple and the little more weird or confusing thing that you might see here with making a Q and job of. There's a couple ways you can do. So, um, one of more common ways is to use this new linked list statement, which has the same might seem a little weird, right? Cause with stacks, you just say new stack well, with queues, you actually can't say new Q right, cause since accuse are this is going a bit too Java, but cues on interface, you cannot actually in Stan Shaitan interface. And so, with Java, you know, one the ways you can make use is using this linked list class, and the next video will be all about link list. So don't worry about if you know, if you're confused about what this means. Anything yet, um, linked lists or a sense of just another data structure that is going to form the basis of this queue right under the hood. This Q is going to be implemented using a link lists, and so, since that's going to be covered more next video for this one here, I would just say, Ignore this piece right here. Just focus on the Q. Don't worry about how this queues actually functioning under the hood by point here with this video assembly just to convey conceptually how cues work, Right? So ignore this. Excuse me, ignore that, and then just focus on this piece right here, Right? So now that we have our Q variable set up, we're going to have our print statement. That's just going to say, um, you know, putting numbers in the dot righteously before and then we'll have our four loop that just loops through. Zero up to and including nine, but not including 10. And you know, with stacks, right? You had that push method to put something on the stack with cues. It's little more common sense in terms of how this methods call that just called ad right? So we just want to add on this ah value of I onto the queue, right? And then we'll also print out the numbers so you can see the ordering in which these things were going in. Although it's obviously it's pretty self explanatory would order in which these numbers are going in. But just to make things explicit, we'll just print out the number right there and there we go, Right. So then we'll have another print statement that will signify when we're starting to take numbers out. Right? So taking numbers out that data and I'll put some new lines here of caps lock is still on new lines. They're just two separate things a bit. And then I will have, ah, while loop, just like in the previous video. That's just going to say, while you queue is not empty, right? This cute is empty. Method will return true if a Q is indeed empty. And if you remember, this exclamation mark means the opposite of that. So this is saying while the queue is not empty, we're going to take something out of it and then just put it out to the terminal, right? Uh, so print line and then, typically with cues the common nomenclature is going to be this pull method when you want to take something out of it, right? So with stacks, it was, ah, pop method. When you want take something off the stack with cues, it's typically a poll method. Just some nomenclature that you might want memorize. And that should do it right. So I'm gonna go ahead and run this main method once it compiles in a second. There you go. It runs and they can see right here. When we're pretty numbers in, they go in in ascending order 0123 up to nine. And then, as I said, cues are first in, first out, right? So when we start taking numbers out, the numbers are coming out in the exact order that we put them into the queue. Right? 0123 up tonight, right stacks. They come out in reverse order. So and that's that's really it. Right? Cues are identical in every way compared to Stax, except when it comes to taking numbers out, they just are taken out in the order in which you put them in right? That's the only major difference. Um, and you know, in terms of use cases, you know, my experience have typically use cues similar stacks, as you know, part of some of them, right? And, you know, depending on how you want Teoh deal with, Ah, the order in which things come out of the queue or out of stack, right? You know, that order is gonna you know, whether you choose a stack or accusing is going to depend on the order in which you want things to come out of that data structure. Right? So subtle difference. But certainly depending on the use case stacks, we're gonna be better than cues and vice versa. Um, another pretty common example, though with queues is you know, if you have an application that has a lot of requests coming in, or jobs or tasks coming in, they need to get processed. And the application cannot process them a lot once that be done sequentially. What we could do is as each request or as each task comes in, you just throw them into a queue, right? And then whenever the program is ready to take on the next task or the next request, it just pulls something off the Q executes that and then goes back to the Q. Take something off the queue again. Executes that. And there you go, right. So that's a cue in that sense, were just function as a buffer that holds a pending Q of requests or task that need to get processed or executed. Right? Um, that's certainly I think, more common use case that I have at least experience with cues. So I just wanted to give you a couple examples or some context. So I have some ideas on which you can use these four in the future. But, uh, in regards to this video, that's essentially it, right? Very similar to stacks. Just that subtle difference. So in the next video, like I said, we're gonna start talking about linked lists. And you know, this will become much more clear in terms of what this means and how this queues actually working under the hood. So when you're ready to move on to the next video, let's dive in. Start talking about linked lists 5. Linked Lists: already in this next video here, or give me talked about linked lists, and I already got some code set up here. As you can see, you have to worry too much about you know, the syntax and what and what Not like I said, This is not a job, of course, by any means, but I'll try to still walk you through this as much as possible. So you understand, obviously, what's going on. Um, but before I get to the code, I just want to walk you through a diagram of what linked list actually looked like, right. It's best to conceptualized these things with a diagram, and I'll be using diagrams to show you what search trees look like, as well as graphs and things like that later in the course. So with like lists, they're pretty similar in terms of what they do. Um, compared to a raise right there basically lists that store values of some sort number, strings, objects, whatever. Um, the major difference here between link lists and raise is, you know, within a rave, you could you can index into the array, look at any position in that array in constant time right. So whether the array was of size 10 or size 100 million, looking at any particular element in that array was a very quick, simple, efficient procedure with link list. That's not the case, right? With like lists, you're gonna have a a grip or pointer to the first element. The first node, as it's called in the link list, right? Ah, the first notice typically denoted as the head. And if you want to get to any other node in the list, you'd have to start the head and then traverse the list one by one. Note after note after note, until you get where you want to get right seek. Imagine if you know you had a linked list of size 10 million and you only had a reference to the first node in the list, and you want to see what was in that last Know that 10 million to node like, what value does it store? Well, you'd have to traverse 10 million nodes before you get to the end to actually see what it holds right, And that's obviously gonna be far less efficient than if you just had an array Where if you want to see what was in the 10th 10 million index and an array, it would just, you know, take a nanosecond, right? Or very, very small fraction of a second to do that because it's a constant time procedure. Right? Um, but link list certainly have their use cases. Right? As I mentioned the previous video, a very wise you saw in the previous video, the cue that I made was under the hood implemented using a length list, right? Why was that a good choice? Well, with the Q, and I'm gonna go back to the brief example I talked about with a nap location that has a lot of requests coming in that need to get processed sequentially. Right? Well, in that application, right, you might have a lot of requests coming in at a faster rate than they could be processed. So the amount of requests coming in or going to be building up and so you'd wanna put them somewhere and a que ah, that's if many using link lists is a great candidate for that. Because let's say each of these nodes represents a particular request. We have request A, B, C and D and it was the first thing that came in to the applications. So it's the first thing in the queue. That's what the heads pointing at and then became in next and C then D and let's say the application was somewhere else processing another request. And you know, these guys are just sitting here waiting. Well, since the requests have to be processed sequentially, all we care about is the next request that needs to get processed. Right. And that is gonna be the first request in the queue. Request a right. That's what heads pointing at. So when the application is done, processing the request is currently processing. And starting from the next one, we can just come up to the queue here and just see what's the first thing in the queue. Whatever heads pointing at that's request A, we just pull that off the Q. And before we process it, we just point the we direct the head to now point at the next guy in the queue request be and then we start. We start processing request a and then when request is dumbing processed, we come back to Q head would now be pointing at node B, and then we just pull, not be off the Q and A process, uh, quest be, and we just continue in that order. So if you have ah, use case where you need Teoh process or do certain things sequentially right, then you won't need the ability to look at any particular node at random, right? Like with an array, you have that constant time ability to look at any index in your A or with a que in this particular use case. You don't even need that functionality, right? You just need to know what's at the at the head of the queue at the head of the linked list , pulled the guy off and then process what's there and then go to the next one and then go to the next one and then the next one, right? Simple. Is that so? In that sense, in this use case, a linked list is as efficient as you need to get right. Don't need an array. Don't need anything else. A simple length lists functioning as a cue works just fine, right, And now you'll see here with each note, there's basically two pieces of each note there is the actual data component, the value that stored there. Right? So each node basically just holds a letter letter a B, C D. And then you have another piece that is we're gonna refer to it as next right. It's basically just a pointer to the next note in the list. Right? So, you know, eh is pointing to B B is pointing to CC's pointing to D and India's pointing to know which is basically nothing, right. No. D is the last note in the list. So and that's it. That ZOLL length list is this diagram encapsulates everything that linked lists really are . So they're very simple little neat data structure that honestly serve of Roddy purposes. But, um, one of the major use cases, at least in my experience, is just using them as cues, right? You don't need Teoh have anything fancier than that. So diving back into the code here, What I'm gonna do is I'm basically basically going to create this exact link lists in code so you can see how something like this would look and then we're going to just generate over the Q and print out every letter that stored in each note, right? And so, as you can see, what you got some code set up here and again, you know, don't know too much about all the syntax and whatnot if you're not familiar with Java, But you basically have four variables that I've already made up here. Each variable represents a node node, ABC indeed. It's the variable names, and each node holds a specific letter A, B, C and D, right, Just like this diagram. And so what we need to do next is you know, you can see here. We just made four nodes, but they're not connected in any way, right? Based on the way of Britain's code. Um, when you just create a new node variable, it's not connected to anything yet, So we have to do that ourselves. Each note has a method we can use called set Next, and this is what we will use to actually link these notes together. So to recreate that diagram, we can just say a referring to no today, right when you say a dot set next be and this command right here, this line of code here connects note A and not B basically says, you know, for note a the next pointer component of that note, I want you to point towards no B. That's what that line of code does. And then for the connection between being see we say, be dot set next, See right, So that connects node B two notes, See? And the last thing you do is connect Notes C to D. So he say, see dot set next the right simple is that so? This point we have are linked list, just like in the diagram that has thes four nodes that are all pointing to the next one in line. And so now what I'm gonna do is make a while loop that's going to generate over each note in the list and just prints out what letter each note stores. Right? ABC indeed, right, Um, And so before we get to that, we want to make another variable called head, and this is going to point to note a right just like the diagram. We have another little variable that's just gonna act as a pointer. To which ever note we're currently looking at whether it's note a note B, C or D or no, eventually, once we get to the end, right? This simply just marks where we are in the linked list right now. So we create that variable, and we're basically saying point head to notice A. That's the first thing in the list, right? So now in a while loop, we're going to say, while head does not equal no, right, because right now, head is pointing to note a No day is not No, it's not nothing, right? But eventually, what we're gonna do is you know, once we print out the letter that stored here, which is a and we move head to point to be, and then we move ahead to point to see and then to d eventually heads going to get to know it's gonna get to the end of the list. And when that happens, this look, this loop is gonna break, and then our application is done, right? So we're gonna dio is what we're gonna say system dot out front line. This is the way we print something out to the terminal. Right on. We just say head dot Get letter. Right. Each one of these nodes. I've created a method on each one that just returns the letter that stored at that note just called get letter. And on this, if you haven't seen this kind of syntax will set up before it might seem low confusing. With were saying, head dot get letter and when I actually affront to any one of the actual nodes we created. Well, because head is is a pointer to a specific node. When we say head dot get letter, it's the same thing as you know, whatever heads pointing to in this case, it's pointing to note A It's the same thing as saying a dot get letter. So return the letter that stored at note a right, That's all it's doing. And so it's gonna print out a in this case, and then now we gotta move head to point to the next node in the list. So we do it for that. As we say, head equals head dot get next, right? I have another method here that returns that next node, Um, when we're looking at any particular node, so Head was originally pointing at note A and when we say head dot get next, it's the same thing that's saying a dot get next. So we're gonna go see note B and since we're saying had equals head out to get next, we're basically now a signing head to point to note B That's all that statement is doing, right? So now head's gonna have point to know would be. And then when that loop it writes again, we're going to say head equals head dot Get next again. And when that happens since head was, it is gonna be pointing to know would be at that point, will go to note, see and head will be assigned to point to node see right and so on and so forth. Um, so that's well, the set up we need right there with this wild. So now that we're all this code in place, I'm going to hit run once it compiles at a run. And there we go, right. And so we basically just iterating over the link list, printing out each letter that started each note until we get to the end, right, cause eventually head is gonna go to B and C and D and then to know and we have this loop saying while head is not know than do something once had becomes no or becomes nothing that while it brakes in the function is over. Right. So, um, I hope that all made sense. Just want to kind of walk you through this in code so you can see some or detail in terms of how this is all working. But, um, the core take away from this video is just understand, you know, conceptually what link lists are and how they work, and you know, the potential use cases for them. You know, using them for a Q is certainly a very common and useful thing to use them for. So, um, that's the end of this video here. And in the next one, we're gonna get into maps. 6. Maps: all right. Thanks for joining me again here in this next video and in this one working me, talking about maps and just like a res maps or another very common in popular data structure that could be used for a wide variety of different use cases and purposes. They often come up in interviews to so very important that you understand how these things work. And the good thing is, they're actually quite simple to understand. So, conceptually speaking, a map is just another container of sorts that holds pairs of things. And, you know, typically the way they work is you have key value associations. So you have your keys that you can use to go into the map and then pull out the values that are associated with them. And so the best way can really, uh, explain this is to just walk you through a very specific example. So you set up for our for our example is gonna be, Let's say we have a basket that's just gonna hold various kinds of fruits, right, apples, oranges, bananas, etcetera. And we want to create an inventory that allows us to track the quantities of each fruit that we have in our basket. So maybe we have three apples to oranges in one banana. Well, when you think about that for a second, we have two things that we can kind of pair together, right. We have our fruits and the quantities of each food that we have. Three apples to oranges, one banana, right. These things can be paired together, and, you know, without a mind, then using a map to create our inventory seems like a really logical thing. Do. And that's exactly what we're gonna do, right? And so, um, you know, getting into the code now, I'm just going to make a map variable at the top here. We're gonna put things into it, and then I'm gonna print what the contents are so you can see exactly how this is all working. So to create a map variable and java, it's very simple. Um, job offers a map interface, right? So, you know, doing this is again very simple and easy to dio. And so let me just write this out first, and then I can explain what's going on here. So, um, you know this syntax right here should seem familiar But now we have two things within these little brackets. Right? And all this means is you know, we're specifying the actual data types that are going to be used to, uh, map things together, right? We're essentially saying that we're gonna be pairing strings with integers, right? The strings are going to be the names of our fruits, apples, oranges, bananas, and they're gonna act as our keys and these keys, they're gonna be associated with integers, which we're gonna be the quantities of each fruit that we have. That's all this means. And so then we have our variable name. We're just gonna call it map, and now we're gonna actually in stand. She ate one, right? And again, just like you sell with queues. We can't just say new map, right? We couldn't just say new que, um And again, this is kind of getting into more job of syntax. So, um, you know, maps just like usar an interface. And you cannot actually in Stan Shaitan, the interface and java. Um, but hash maps are class and, you know, hash maps are just a very specific type of a map that Java offers. There's a few different flavors of maps that Java does offer. So hash maps for just one form of them. And that's what we're gonna be using in this example. So I don't know much about this in textile that I just wanted kind of briefly explain what was going on here. So then we have our map variable. That's now we're gonna start putting things into it. So we're just going to say map dot Put right. These map objects have methods on them that allow you to interact with them. So there's a put method that you can use to actually put things into it. Right. So we're gonna put in apples and three so this creates our pair of apples in the number three. We have three apples in our basket and then repeat this process for oranges. You know, we have two of those, and then lastly for, uh, bananas. We have one of those, right? So that's a simple is that we've now. We've now created three pairs, um, in our map that represent the the inventory of what we have in our basket. Three apples to oranges, one banana. Simple is that, and again, the names are fruits are gonna be our keys. And these are gonna be what we used to actually go into our map and then pull out the values that are associated with each one. So, um, to print these things out now, we're just going to say, um I'm just gonna basically print out the fruit names and the quantities that we have, right? So I'm gonna say apples, colon, and then plus s basically just gonna put these two things together when we actually put them out. But to now, go in and pull out the quantity of apples that we have, which is three. You want to use another method on this map variable called get. And this is where we can actually specify the key that we want to use to go into a map and pull out the value associated with it. So this this method call right here is going to use Apple's, as are key to pull out the number three. And so it's gonna print out apples colon three basically, and you'll see that in a second when I run this function something, just copy this really fast on, then paste it two more times just make things a bit faster. Um, it's nominated. Replaced this with oranges. And again, we're gonna, you know, swap out the apples key with our orange is key, right? And then same thing down here for bananas. We're going to swap out the apples key again for bananas, right? And so now when this runs, go ahead and run it, There we go. Weaken. See, Exactly. We have three apples to oranges. One banana. Very simple, right? And that's all maps do. And there, you know, a great thing to use if you have a use case where pairing, you know, two related things is something that you need to do right now, One thing to keep in mind is you know, there's always pros and cons with any data structure, right? And so one of the cons with maps is they don't actually guarantee any ordering. Right? So if I were to make, like, you know, for you, for example, that just loops over all the keys in my map, it was actually other method. You can call map dot key set, which returns a list of all the keys we have in our map. Um you know, if I were to do this. And in fact, I will just go and do right now. So for for each key in our key said I just wanted to print something out. Do you? Ah, print F actually here was going to say percent s and then percent D. This is just some formatting stuff. Don't worry about what that means necessarily. Um, but organs I'm doing here is the same thing as what this block of code is doing right. I'm simply iterating over each key anarchy set. So apples, oranges, bananas, right? That's what this fool it is doing. And then I'm going to print out each key and then also the value that's associate with each key with this map dot Get method again, right, and you'll see. Let me comment these out. So it's not confusing. You'll see that when I run this method again going to run it right? So we specified where we put things into our map in the order Apples, oranges, bananas and they came out as apples, bananas, oranges, right. That's a different ordering. So this demonstrates the fact that maps don't actually guarantee the order of the pairs. The associations within the map, right? So if maintaining the order off whatever is you have, then maps are not something to be wanting to use. A raise might be a better data structure to use if ordering is imperative to have, but that's not required then maps are certainly very advantageous. And there's two main reasons. One is the size of your map can grow and shrink, Um, dynamically, right? So the more things you put into it, the size of the map is just going to going to grow for you. You don't have to actually do anything to change the size of your map. You can just keep putting things into it. There's also a remove method you can call to remove things from Europe, and then the size of it will shrink right with a raise. If you were to make an array of size 10 you're stuck with that size. It's only ever going to be size 10 and if you wanted to expanded or shrink it, you'd have to basically create a whole new array with a different size than copy everything over maps. You don't worry about that. Another benefit is just like a raise. They run in constant time. So, for example, you know when I want to use a key to go into my map and pull out the value associated with it, it's a constant time procedure. So whether my map is of Size three here, there's only three things in it or of size 100 million. As long as I have a key on hand, then going into the map and pulling out the value associated with it, it's gonna take the same on time. Whether the map this small in size or massive, just like a raise, right? I mean, if you have a massive array going into any position in that array, to see what's there is a constant time procedure is gonna take a very, very small and consistent amount of time. So with that in mind, if ordering does not matter for you, then maps certainly offer a lot of benefits in terms of, um, you know, the size can change dynamically and they run. They run super efficiently and quickly when you want. Actually, you go in and pull the values out when not that our associate with different keys that you might have etcetera, etcetera. Right. So, um, I saw these maps a lot in my day to day programming at at work. And I imagine if, you know, programming is something you want to stick with. Um, you'll find many different use cases to use maps as well. So I hope that all made sense. And in the next video coming up, we're gonna be talking about trees. 7. Trees: all right. Thanks for joining me in the next video here. This one's gonna be all about trees. And you know, this video as well as the next one on graphs, is where things get a little bit more tricky, a little bit more nuanced. But also my opinion a little more interesting as well. So please do give this video as well as the next one your full attention. So conceptually speaking, a tree and I have a diagram here to show you is it sounds exactly how it's named right. These are tree like looking data structures, and there's a variety of different flavors. And, um, you know, variants of trees under this kind of data structure category, which you're looking at here is what's called a binary search tree. And these were one of the most commonly used types of trees in the industry. So this view is going to focus solely on these. There's also heaps red black trees, be trees. Plenty more beyond that. I'm not gonna go into all the different variants of what not. But, um, you know, if you can understand buying a research trees and how they work, then moving over to understand how heaps work or be trees, it's gonna be a very simple and straightforward really. The main things that separate these different variants apart is just a matter of how they organize their contents. But they're all still treat like structures. So the way of binary search tree works is you have what's called nodes, just like with a linked list, right? And these nodes basically represent packages, if you will, that hold data of some sort. Typically, the numbers with binary search trees or it could be any kind of data that can be compared toa one another in a very specific way. So and you'll see why this is important in a second here. So with, uh, any kind of tree, there's a little of nomenclature here. You have parent nodes and you have Children nodes you can see here seven is the parent of two and nine, and two and nine are the child nodes of seven, but also notes can be both Children and parents themselves, right? You can see here, too, is a child of seven, but also a parent of one and five. Same thing with 99 is a child of seven, but apparent of 14. And the nose down here at the bottom there, all Children themselves, right. But they're also called leaf nodes as well. All the notes at the bottom of a tree are also referred to as leaf nodes. Just some nomenclature that you wanna, uh, keep in your mind. And so the way these things are actually structured, though in terms of their data, is the parent node always has to be greater than the left child node, but smaller. And then the right child notes. You can see here seven is greater than two, but less than nine to is greater than one, but less than five nine. No, there is no left child note, and that's okay. Not every note has toe have two or even one Children, but you see nine is less than 14. So this is a valid by new research tree, and you also notice if you kind of look at this ATM or of a macro, Level seven is greater than yes to. But all the nodes on the left hand side of 77 scared of the two. It's greater than one has greater than five Same thing with the right hand side. Seven is less than all the nodes on the right hand side. It's less than nine less than 14 and this is another characteristic of binary search trees . Um, so, for example, if you wanted to put in a new number, let's see what we wanted to put in the number 10 in this binary search tree. The way you do this is you start at the top. The top note is also called the root node, and you would just do a quick comparison is seven less than or greater than 10. Most seven is less than 10. So 10 we know has to go on the right hand side of seven, and then we go to the node nine and we do. A comparison again. Is nine greater than or less than 10 old nine is less than 10 so we also go to the right hand side of nine. Now we get to 14. Is 14 greater or less than 10? Well, now 14 is greater than 10 so 10 would go to the left side of 14 and it would go right here and be connected to 14 as its left child node, right? It's a simple is that, um if you wanted to search four number in a binary search tree, and this is where these structures are extremely efficient, also very efficient with putting numbers in, um, let's say we want to look for the number five while you started the top again is five less than or greater than seven once less than said. So we go to the left is five. Greater than less than 25 is greater than toots. We go to the right and there you go. We found it. You'll notice that especially with huge tree searching for numbers or putting numbers in or taking numbers out as long as the tree is balanced like this. It's nice and bushy and kind of symmetrical. In this way, it is extremely, extremely efficient and fast. It's one of the fastest data structures available in terms of searching for whatever it is you you wanna see, if is in there, right. And the reason why is you know, let's say we had an array of just random numbers. Maybe the array had, you know, 10 million random numbers, and you want to see if you know five was in there. Well, since there's no structure to that array in terms of the ordering of its contents, you would have to search the entire array to see a five is in there. That's a pretty inefficient process, with a binding research tree coming in at the top of the route and doing a quick comparison . Okay, five is less than seven, so we go to the left just in that one comparison, we have now eliminated half of the entire tree. You can imagine if this tree had 10 million numbers in it and seven was the top root node and wanted to see if five was in there just by doing one comparison and going to the left. If the street was balanced, we would have eliminated five million numbers without even having to look at them, because we know that every number on the right side of seven is greater than seven. And since five is less than seven, it must be less than all the numbers on the right hand side of seven. That's five million knows that we could just automatically eliminate, and then when we go to two right now, we've got five million nodes left to look at. Um, we do another comparison. Five is greater than two. And so we go to the right. And just in that second move, we have now eliminated 2.5 million other nodes. And we didn't even need to look at them because all the numbers on the left side of two are gonna be smaller than it. And if that's the case, then there's no need to look on that side from the number five. So you can see how this works and how rapidly weaken get down to where, whatever it is we're looking for extremely, extremely efficient. So this is why buy new research trees are, ah, preferred structure in my use cases, whenever I need to have something that's sorted, Um, and they also do come up in interviews quite frequently as well. So definitely is. This is something that you want to understand. It's not going back into the code here we're gonna do is I'm going to recreate this exact tree, just kind of just like I did with the linked list example. You know, we had a diagram, and I basically created it in code I'm doing the same thing here. And also I'm gonna show you a quick little algorithm that will allow you to walk the tree, so to speak, and visit every node and basically print out the value that's at each note. Right. And this is a cool little algorithm because it will leverage both obviously a tree as well as a cue. So this is a great example to show you how you can combine the use of multiple data structures to achieve some goal. And so that's good. Started here. As you can see, her have already got some code laid out for you. Um, similar. Set up with the linked list video I got on the private class here that basically just represents a single node in the tree. Right again, this is a job, but just not a Java course. So if the sin taxes a little bit confusing, don't worry about it. I just know that this little private class here, this private static class represents a single note, and it holds an integer as the value and has a left child node. And it has a right child note. That's it. I have some getter methods that simply return, You know, the value, the left child, the right child. Very simple. And then I have some center methods that allow you to actually set the left child of a particular node to another node. Likewise set the right child of given no to, uh, another note, right. Become more clear as I start walking you through the example here. So, um, I've already created all six nodes in the tree, and I've named each node simply, uh, after the value that they store. So, you know, note seven holds the value. Seven No. Two holds the value to and so on and so forth. And so, just like with the linked list example, I've created my nodes, but they're not linked together in any way. It I have to go and do that. So that's obviously going to do that. Um, so seven is the root note. So we're going to start connecting from the top down to the bottom. It's the way we do. That is, say, seven dot set left child and left child of seven from the diagram is too right. So this statement here takes the seven note and the two note and links them up in a way that says seven is the parent of two. Very simple. And so now we do the same thing with the right child. Seven not set, right, child to nine. Very simple. So not to continue the process. At this point, we have this kind of tree right here. We have seven as the parent of two and nine. It's now we're going to link up to with one in five and the nine with 14. So we say to dot set left child, uh, one and we say to dot set bright child five. And then lastly, we say they believe it's just nine to say nine set, right, child, because there is no left child for nine. That's fine. 14. And there you go. We have essentially traded this exact tree data structure that you can see right here. Simple. Is that right? So now what we're gonna do is I'm gonna show you how to implement a very small, neat little algorithm. Just uses a while loop and a Q basically to walk this tree level by level. And there's you'll find if you do some research into trees and how toe Walk them in different ways. There's a multitude of different ways and paths you can use to actually traverse a tree data structure. Well, I'm gonna show you is simply one such way. And as I said, we're gonna do it level by level. So we're gonna print seven than two and nine and then won 5 14 just like that. And so we're gonna do here is we need a que To do this, I'm gonna make a Q. And you saw exactly how I did this in that queue video. So we're gonna take a cue that just holds nodes. We'll call it Q and it's gonna be implemented under the hood as a linked list. And that should hopefully make sense to you. Um, why we can do that at this point in the course. And so now that we have our Q, you can make our wild loop. You just say while a que is not empty, we're gonna do something annual. You'll notice right here. We made a Q, but there's nothing any yet. So if we were to jump right to this while loop, the Q is empty and nothing, what happened so we gotta fix that. So the way we fix that is we are going to put in to our cue the root note, which is seven right, started seven and then level by level worker way down the tree. So this while it is not going to execute And so what we're gonna do is we're going to get a little variable in here, and it's going to hold the value that we pull out of the queue. The first thing that's ready to come out of the queue, right? And so we just say, Q dot poll and this in this case, when the loop interest for the first time, it's gonna pull up the node with a value seven in it, right? And so we're gonna do now is just print out the value that's in there. So we say, no dot get vow, right? Print that out. And now we need to put something back into the Q because at this point, the key would be empty in this loop of end. But obviously we have much more of the tree to still work our way through. So what we do now is we say, if no dot get left child does not equal. No, you'll remember that. You know, not every node has to have Children. And in the case where we get to know that doesn't have a left child as I have a right shell doesn't have either right, the left child and the right child, whichever, whichever or both that are not present will just be set to Noll, which is basically nothing. And so, in this if statement here, we can see weaken. This is how we check that if the left child is not know right, so it's actually a node there. Then what we want to do is throw that into the queue. So it's a Q not ad, no dot get left child. Simple. Is that right? And then do the same thing for the right child node. So we said, No, Tiffin, the know dot get right child does not equal no same thing. Then we just throw that into the Q as well. Que dot ad, no dot get right, child. And that's it. That's the whole algorithm. Very simple, very clean. And you could see how this works if you walk yourself through it. This way. So we start with seven, right? We print out that number and then we check. Okay. Is the left child No, No, it's not. It's too. So we throw that into the queue. I mean, check the right child, OK? That's not know either. So we throw nine into the queue. At that point, the Q holds two and nine. That leaps, going to reiterate again. And then we put the number two print out the value there and then we check. Okay? Is the left child No, No, it's not. It's we throw one into the queue. Is the right child? No. Nope. Throw five into the queue and then the loop it rates again. Nine is not the first thing to be the head of the cuse. We pull that out, print out the number check the left child that doesn't exist. Check the right child. Hope 14. Throw that to the queue. So at that point we have 15 and 14 in the queue. Let me pull out one. No left child or student plot one print out the value. No left child. No right, child cape. Nothing there. Now we just have five and 14 In the cubes, we pull up five. Print that number out on the left child. No, right, child, find 14 is still in the queue. We pulled out, Out, Printed out. No left child. No right child. The Q is now empty, the loop breaks and we're done Very simple. So when I go ahead and run this function now, after compiles, you will see that Boom. There we go. It's prints out 7 to 915 14 right, 7 to 915 14 just like I said it would. So, um, I hope this example made sense, and I hope it really illustrated how you can now start combining the use of different data structures to achieve some desired outcome. This is where you know the sky is the limit, right? It's just a matter of your imagination and creativity. When it comes to solving a problem, you know which data structure by itself or a combination of multiple can I use to a solved the problem and then be solve it in the most efficient way possible? Each of the kinds of questions that you want to think about and definitely answer if you want to be a skilled, valuable software developer. Right? So, you know, whether you're doing this as a hobby or if you're pursuing a career, is a software engineer. Either way, this is something that you really want to learn, understand and master. And so, um, that point, this is the end of this video and the final one Commit next. We're going to start getting into graphs, so stay tuned for that. Thanks. 8. Graphs: All right, Welcome back to the final instructional video. This course this one's gonna be all about graphs, and you'll see here in a second that graphs and trees are quite similar. In many ways, there's just a few subtle little differences. And so I have a diagram here once again that depicts a pretty simple looking graph. And yeah, it should be pretty apparent that there's a lot of similarities here. You have nodes, right? Or typically in regards to graphs that refer to as vergis ease. So you have vortices that hold pieces of data in this case numbers, and you can connect verses to each other using edges. Right? Just another ah, graph specific vocabulary. Right. Um and that's it, Right? Conceptually speaking, this is all a graph is just a group of vergis ease with connections connecting them and really, anyway, that you want trees on their hand, on the other hand, are simply a very specific form of a graph. Trees are graphs there, just a very specific type. And, um, you know, specifically they they are required to have that hierarchical structure, right? You have parent nodes, and each parent can have zero arm or Children nodes. And those Children can have Children, notes of their own and so on and so forth. Right in regards to graphs, there is no required structure. You could have as many Vergis ease as you want, with connections going all over the place, connecting any vertex to another. As you desire right, there's a lot more latitude with graphs, and there's also a couple of different flavors in variance of graphs as well. What you're seeing here is it's a bidirectional graph in terms of its edges, because each edge represents two directions, right. Vertex zero is connected to Vertex four and Vertex Fours connected to Vertex zero right goes both ways. You can also have directional graphs, in which case the edges would be represented using arrows. So, for example, you might see in a graph like that you might see an aero coming out of Vertex zero and pointing towards Vertex four, which basically would mean there is a path. There's a connection between Vertex zero to Vertex four, but not the other way around. There would be no connection between Vertex four going to for Tech zero. So that's one other variant of graphs that you could get into for this video. I'm just gonna focus on bi directional graphs. Um, and example I'm gonna walk you through is give me very similar to the trees video and the linked list video. I'm going to create this exact diagram in code. You can see how that works, and then I'm gonna show you an algorithm that allows you to traverse or walk through the graph visiting each node or each vertex Exactly. Once, right. And with bi directional graphs, you'll see how that could be a little bit more tricky. You'll see why. Um, but because of that, it's certainly I think this is a good example, cause that added complexity can certainly be beneficial going forward in terms of, you know, interviews. Or which, in my experience on the job, etcetera, etcetera. So, um, before we get to the code, though, I just want to set up Seymour realistic example or more easy to understand example of you know, what might you want to use? A graph four. And really the sky's the limit when it comes to how are when it comes to how you might want to use a graph or what situations could be beneficial. Um, and using graphs and what not the example I'm gonna go with here is a social network, right? So, you know, with Facebook, for example, everyone has friends and your friends have friends and their friends have friends and so on and so forth. Right? And using a graph is one excellent way to represent that kind of structure. Right? So you could think of each Vertex here representing an individual person. And each person has friends, right? So, for example, with person four, this person's friends with person zero person, one and person, three. And you know, it's a bi directional kind of relationship, right? It goes vice versus. So, you know, if person fours friends with person zero, then person zero must be friends with person four. Same thing with person one and person. Three. Right? And, you know, obviously, like I said, your friends could have friends of their own that you may or may not know. So, you know, for person four. He's friends with person one but person one also knows and his friend and his friends with person to but clearly person to and person four are not friends, at least yet because there's no direct connection between these two. Vergis ease. So hope. It's pretty clear now that using a graph to represent a social network is a very straightforward and intuitive thing to do, right? So that's the example I want you to have in mind as I'm walking you through this code and apps going back to the code. Um, I already have a live it set up here for you just to make things a little more fast and what not? I got a class down here or private class that represents an individual vertex. So each for text holds a value. That's a number, right? And each Vertex also holds a map that represents all of its friends. Right. And, you know, it's kind of up to you. If you wanted to recreate this example for yourself, it's up to you how you might want to structure this code. I've I chose to use a map in this case simply because, you know, maybe if you were designing a social media platform, you might want to store, uh, relationships with some metadata associated with it. So, for example, you know, if you get a friend request from somebody. And you want to add that person to your friend group? You might want to at that time store cemented eight about that new connection. Right? And you can see down here in this add friend method, all it does is it puts this new Vertex here. Actually, I should call this friend. So when a friend request comes in, replace that. There we go. That's when a friend request comes in. We're basically we're gonna be adding this friend to our group, and so we're doing is we're putting this new friend in our friends map, right? And along with that, we're just storing Just I have a placeholder here. Just called metadata, right? It could be a string. It could be another object that you've created somewhere else that could hold just some data about that new connection. That new friend, right? Maybe it stores the time at which that connection was made. Maybe stores some, um, some data about your common interests and things like that. So just a complete example, but something that you might want to set up if you were creating a platform like this, um, also using maps you have the benefit of that constant time. Look up, meaning If I wanted to just see if so and so is in my friend group, and I have my friend stored as a list. You know, I would have to search that entire list to see if that friend is in my group. And that might be an inefficient procedure if you've got a lot of friends, right with a map, as you learned in the maps video. Looking to see if something is in the map is a constant time procedure. No matter how big it is, it's gonna be very, very fast and run in a constant amount of time. That's another benefit of using a map here. Teoh store. All of your friends and I also have just to get her methods. Basically one method that just returns the value that this verdict stores and then another method that just returns the map that has all of its friends So very simple little class. Don't worry too much again. If the syntax and went on is a bit confusing. If you're not from the job, just understand that the main concepts here and going back up here to the main method. I have already created the five vs Ease in our social network. You know, person zero person. 123 and so on. Right. Very straightforward. And I've already gone ahead and created all of the different connections between each person or each Vertex. Right? So an example. Looking at these two lines of code person zero dot Add friend person four and then person four dot add friend person zero. This simply sets up this connection, right? The first line of code sets up the friendship connection between person zero to person for and then a second line of code sets of the connection between person four two, person, zero. And that's all that does, right? Same thing with all these other little groups of of code. Right here. Um person zero not add, friend Person. One person, one dot add friend person to same thing. Says of the sets of the friendship connection between person zero in person one and person . 12 person, zero. Right. So we have 1234567 told edges each edges bi directional. So basically they needs 14 pieces of code that just sets up all those different connections , right? That's all these lines of code do. And at that point, there you go. Our graph is created. We have our network very simple and easy. Right. So now we're gonna do is I'm gonna show you a little algorithm in that you can actually tweak using either a stack or a que to traverse this graph in different ways. Right? So we're gonna start at Vertex zero. This is give your starting point, and we're going to traverse this graph in different ways, visiting each vertex exactly once and printing out the value that stored at each Vertex. That's it. Um, it's gonna be a very similar set up to in the previous video with trees, except for one little cell difference. Remember, we are only going to visit each vertex exactly once, and that's gonna require another little trick to ensure that we don't visit for Texas more than once. So, um, I'm gonna show you first using using a que And so you should know how to make a Q by now in Java. It's very simple. So Q called Q and then we'll use a linked list to you. Actually, implement it under the hood and we're gonna of a while loop again, saying while the queue is not empty right, we're going to do something. But just like before, right? The Q is has been made, but it's coming empty, so I gotta put something into it. So we're gonna put in our starting Vertex, which was Vertex zero So cute dot Ad person zero Boom. There you go. So now we're gonna do is just before with the trees were gonna pull something out of the queue, the first thing in the queue and then print out the value that stored there. So miss a Vertex protects equals Ah que dot poll writes that Paul's that first for takes out of the queue and then we're simply going to print out the value that store to never text. So for tex dot get vow, right? Simple. Is that right? And then, just like with the trees example, we have to now put things back into the Q because at this point, it would not be empty, right? And the the first difference here between this algorithm and the one in the trees video is , you know, with a graph we have. We clearly have emergencies that can have varying numbers of connections, right with the binary search tree, we know that we're either gonna have a left child, a right child, one of the other, or neither, right, But with a graph in this case, you know, overtake. Zero has two connections, but Vertex four has four connections, so these numbers are going to vary for text. Three has three connections, so we need to account for that. That's the reason why I used a map to store friends because maps the size of maps can change dynamically. Right? And it's very easy to reiterate over all the keys in a map you can see here the vergis ease in our friends map the verdict. These are the keys of this map, right? And as you saw in the maps video, there's a dot key set method. You can call it a map that just returns a list of all the keys that are contained in that map. So all the vergis ease, and that's what we're going to use in this in this loop right here. So we have another four loop within this wild that says four for text. The you know, explains in a second, um, vertex dot Get friends dot key set. There you go. So what this is doing here is right for the Vertex we just pulled out of our cue. We're calling the get friends method on it. So it returns the map of a level of all the friends and that Vertex And they were saying, Get the key. Sit of that map, which is just a list of all the friends of old overseas in this ver Texas fund group. Right? And this full it is just gonna iterating over each friend in its friend group. Simple is that And so within this four loop as we're iterating iterating over all the friends, we're just gonna add them to the queue. So we say, q dot add b Right, B in this case, right represents each vertex that is returned in this list of all the friends, right? Adding them to the Q. Now, you might think we're done at this point, but we're actually not If we were to leave this code as is, it would run forever because that's going back to our diagram Here We started Vertex zero. We pulled out of the queue, print out the value that it stores zero right, and then we looked through all of its friends. So four and one, we add them to the Q. Let's say one was add to the Q first, then for so then one would be the first thing that comes out of the queue next. So we pull up Vertex one print out the value, and then we loop through all of its friends, right, and you'll see that in its front group is Vertex zero again. So we don't want to add that back to the queue again, because if we did, we would pull out against some point and we would just loop. We go through the same exact procedure. Visit for Tech zero again. Look through all of its friends one and four at them to the Q. And then we pull out, protects one again. Hope it's friends with Vertex. Zero at that to the Q. And it would just continue on forever and ever. Never. It would never end right, so we gotta fix that in the way we could do. That is using what's called a set and this is another little data structure. You can consider it a bonus data structure in this course, and I didn't make a separate video on it because it is very, very similar to a map. The only major difference is you know, maps have a key value. Pairs with sets. It's basically just keys. That's it, right? So with set, it's a container that holds keys, if you will, where each key is unique, just like a map, right? And so, for example, if you had a set that holds numbers, you cannot You cannot have multiple threes or multiple fours or twelves or whatever. In that set, everything has to be unique. And the cool thing with sets is they're running constant time when you put something into it and take something out of it or you want to just see if something is in there, right, just like with a map, right, fever key. And you want to see if there is, ah, key Value Association. In that map, you would take that key that you have and, you know, call a method on the map to see if it's in there and it would basically return the value that's associated with it or not. If it's not in there and would do so in constant time, right? Very fast and efficient with a set. It's the same way you have a key on hand. You want to see if it's in the set so you can call method on it. You do that and it basically returns yes or no, except there's no value that's associated with it, because it's a set. Doesn't have that. But it's still constant time procedure. Gonna be very efficient and fast, regardless of how big the set is. So that's what we're gonna leverage in this example. Here, we're gonna use a set to store. All the vergis is that we've visited so far. And every time we pull something out of the queue a new verdicts out of the queue, we're going to check to see Have we already visited this Vertex before? So we're gonna do that by looking into our set, seeing if it's there. If it is, then we know we've already seen it before and we can just ignore it and move on. If not, then we will, you know, go through our procedure printing out the value, the store there and so on. And then we'll add it to our set saying we have now visited it. So to make our set, I'm gonna do it right underneath this Q variable. So we're gonna say, Set, Gonna hold Vergis ease. Well, let's call it set equals new hash set. And again, um, Java sets are interface can stand shayt interface. But hash sets our classes, which implement this set interface, and you can stand She ate classes, right? So hash sets or just one form of a set that job offers. And this is only that we're going to use It's the most common type. So that's why again, this is kind of different. So at this point, we now have our set. And now going back to our wild loop. When we pull something out of the queue, we're gonna check. We're going to see if be set. Um, contains this Vertex and actually, more specifically, more specifically, we're gonna check to see if this set does not contain the vertex. Um, just you could go either way. This is what I'm gonna write this code. So I'm gonna move some things around here. There we go. So if the set does not contain this Vertex we just pulled out of a que we're going to do something right. Otherwise, we're just going to ignore it, right? We've already seen it before. So in this if statement now, if we have not seen this Vertex before, we're going to market as now visited. So we say set dot ad Vertex. So now we're adding to our set, saying that we've already visited it. Now we're gonna print out the value that's stored in that Vertex and now we're gonna look through all of its friends again. And where else can add a statement here as well, saying if the set does not contain any of the friends of this for Texas, then we're gonna add them into the queue. So we're going to say if, um, the set contains V and rather with set does not contain V this for Texas friend, we're going to you add it to the Q and there you go. Now, this code will work in such a way that every time you visit over text, we market as visited every time we want to add something into the Q. We check first to see if we have already visited the friend previously. And if we do pull something out of the queue that has already been visited before, we simply ignore it and move on. So now when I run this code, time to go over here and hit Run! You see? There we go. We started protect zero, right? And then we went to Vertex 14 to 3 started Vertex zero. Then we hit one, then four and then two and then three. Boom! Visited every note exactly once. Now, the way we just traverse this graph is called Breadth First search. And what that means is we're kind of where were we have a starting point and then we're traversing our graph kind of fanning out from our starting point. We had zero and we found out to one and four. Then we hit two and threes or kind of moving to the right in a fan like manner, hitting all the vergis ease as we're going along from left to right. So that's called breadth. First search, and there's a couple ways you can implement the algorithm. But typically in this in this style with a while loop. You want to use a que Now, we could simply swap this out for a stack and you see how it changes. So for a stack, it also holds Virtus ease will call it stack new stack. There we go. And let me just swap out each que reference to stack. Now that we're using a stack, obviously change that. Change that and so else got to change a couple function names or method calls cause stocks still have the pull method So it's gonna be stacked dot top this time, right? And then one changes to stack dot Ah, push v And there we go. So why did there was swap out our cue for a stack, changed a few things in terms of the methods and what not? But that's all I did was just swap out this to data structures. So now wanna run this myth it again. It prints out a different order. 04321 04321 And this method of graft reversal is called depth First search. So giving your starting point, you're gonna go to you know, one of its connections and you're going to keep trying to go as far into the graph until you like it until you hit a dead end, for example, or you hit a situation where you've visited every node that you can possibly go to, and then you have to kind of retrace your steps and then go somewhere else. So that traverse ALS going to really dive into the graph initially and retrace and kind of keep diving into it as deep as possible. Where is the other version that I showed you first? With a Q. It's more gradual and how it traverse of the graph. It's kind of fans out looking at all the vergis ease in a specific slice of the graph, if you will, and moves out accordingly. Looking at the next slice of the graph, going out, looking at the next slice and moving that way. So you know, depending on your use case and that maybe the broader algorithm or not that you're using breadth. First search might be better than depth first search or vice versa. But I just want to show you both examples quickly just to illustrate that, with a simple swapping out of one day a structure for another, you can dramatically change how the hour with them actually performs. So with all that being said, that covers it for graphs. I hope this was very informative. And last video coming up next is just gonna be rapping, rapping Something's up. So I'll see you in that next video. Thanks. 9. Wrapping Up: all right. Congratulations. You have now completed the course. And so your next steps going forward should be simply to practice, practice, practice The best way you're really gonna understand and master all the different concepts and data structures taught in this course is simply to write applications that use them. And that way you're gonna be over time able to see how they work, what their behavior is like, which situations are best suited for different data structures, etcetera, etcetera, right. And that's what the course project is really all about. So what I recommend you do is to write an application or multiple applications that use as many of these different data structures as possible. And one way you can get yourself started with that is to simply recreate one of the various examples that I've walked you through in any of the videos of this course. The last video, for example, on graphs. That's a great place to start, because that example, if you were to just kind of walk yourself through the video again and recreated on your own example, uses graphs, uses stacks or cues, and it uses a raise or maps or link list if you want, depending on how you actually want to implement the algorithm that walks through the graph or how you want to actually implement the data structure itself, that is certainly a great place to start, and you find that you know them or applications. You right. Walk yourself through these examples and whatnot, the more comfortable you'll become with these different data structures. And before you know it, you'll be writing applications in your own that you use all of them or one or two of them, and you'll be very knowledgeable in that area now. So all that being said, I really hope you enjoyed this course. I do appreciate any feedback or views that you might have to take that very seriously so I can improve courses going forward. Um, I do try to publish one new course every two weeks, And if this is the first course of mine that you're watching, my material is going to be all about three main things, the first of which is material like this. So, you know, suffered development, technical, interviewing, that kind of thing. The other concept or concepts is gonna be all about investing, so stock market investing, options, trading, real estate, investing, that kind of thing. And in the last category is personal development, goal setting, habit, creation, that kind of thing. Right. So, um, I highly recommend you look at the courses I already have on skill show that I published. Um, I think you might find a lot of value in them. And, um, yeah, with all that being said, thank you for watching this course again and stay tuned for what? I have going forward.