JAVA FOR EVERYBODY: Data Structure

1. Introduction: Hello and welcome to a new class. We've already covered the basic concepts of Java and programming in general. And in this class we talk about data structure. So first of all, we define a data structure. What types of data structure we have in programming, how to create and use them. And he will focus on linear data structures such as stacks, queues, and LinkedList. And we already talked about arrays and use them in the previous classes. So we'd be mainly focusing on stack cuz LinkedList. So in the stack, going to learn how to create a stat ourselves and how to use the built-in Java stack, how to use the linked list based stack. Then we'll continue with a queue. We do the same thing with the queue. And then finally create our singly and doubly-linked list to see you in the next video. 2. Data Structure: In this video, we're going to talk about data structures. And data structure is a specialized format for organizing, processing, retrieving, and storing data, where there are several basic and advanced structural types. Any data structure is designed to arrange data to suit specific purpose so that they can be accessed and worked with an appropriate ways. As you can see here, we have two types of data structure. We have the linear and the non-linear. For example, array is a, is an example of a linear data structure, and we've used it so many times in the previous classes. We also have stack and linked lists. In the LinkedList we have singly and doubly-linked lists. And the non-linear type, we have graphs and trees. So in this class, we're going to learn how and when we should use each one of them. And how can they help us? And what are the advantages? To see you in the next video. 3. Array Based Stack: A stack is a linear data structure which follows a particular order in which the operations are performed. There are many real life examples of a stack. For example, the plays that are stacked over one another so that it update, which is at the top, is the first one to be removed. And the plate which has been placed at the bottom most position, remains in the stack for the longest period of time. Here, for example, we have our empty stack and we pushed, for example, the number one, and then we pushed it in number two and then three. So we have 123. Now, if we want to take out an element, will take three, which is the last element, the entered. So can be simply seen to follow the lifo order that is last in, first out. So here we have two main operations, the push and pop. Now we have a stack class in Java, but we not use it in this video. We'll just implement the methods by ourselves. And to implement the stack, we used an array. So let's go ahead and use array to implement our stack. Let's go ahead and create a new project. Let's name it. And this name of the package as a phase. And, and this package will create out. So this is our class array stack. And Let's create an interface and name it stack. So here we have interface, and here we'll have all the methods. So this is our interface. And so first of all, we have, as you said, the method push and pop. So there'll be public void push, and we'll be pushing an object. It might be integers, string, character, and so on. And another method that is and popping an object. And let's create some other methods. So instead of popping, popping an element, and when we pop an element, we move it from the stack. However, if we, we just wanna take a look at this element, we need to create another method and we'll name it. So we just have a look at this object using that top method. And let's go ahead and create some other method. For example, the size to check the size of the stack and the SMD. It is empty. And to check whether the stack is empty or not, it will return a Boolean true if it is empty and false otherwise. So here we have our methods. Now. We have some problem here. Because whenever we want to push and reusing array, so if we want to push, the array is full, we have a limit on the array. And for example, let's say the area is of size four. And we're already pushed for elements. And we tried to push the fifth one. Then we'll have an average here. Since the array is limited and we cannot push five elements into a four element at a. And of course, if you want to pop an element and the stack is empty, then will not have, will not going to have any element to pop to see from the top method. So to fix that, we need to create our own exception class. So let's go ahead and create our exception. Let's name it stack exception. And as usual, we'll just create our constructor public exception. And we'll take string message and pull the supper. And of course we go to throw extend, sorry, the exception class to use it in this class. So now we're done with this Stark exception. Let's go back and we need to throw this statics that exception. So throws exception. And the same thing. Other methods that exception. And now these are our method. So here we have an error throws. Now let's go back to array based stack class and implement this method created earlier here. So first of all, we need to extend or implement the stack interface. Because whenever we want to use an interface, we need to add here implements and we're going to implement the stack interface. And of course we have an error saying that we have inherited abstract methods and that we need to implement. So let's go and every method, and these are our methods. So let's start with the first of all, we need to create the constructor, of course. And So first of all, we have today, and it might be an integer string, character, double anything. So we'll give it the value of object and let's name it. And of course we have our integer less than m. And so this would be where we are going to move. Now, let's create our constructor. And the constructor of the base. So this is the constructor and it will take the capacity of the array or the stack if you want. And of course, we'll instantiate the object at a with the value of capacity. And we still have top. So at first, let's say that tau is equal to minus1, and we'll see why in a minute. So top is equal to minus1, and here we have public. So this is our constructor. Now let's go to our is empty method. So if for example, if top is equal to minus1, return true, that is empty, otherwise, return false. So if top is equal to minus one, it is at the initial condition or we don't have anything and the stack just return true, otherwise return false. Now, we have a shortcut to this. So instead of saying return, otherwise, return, we can simply say return is equal to minus one. So this statement, top is equal to minus one. It will check if top is equal to minus1 will automatically return a Boolean. And returning a Boolean here would result in returning a Boolean method. So if the top is equal to minus one, it will return true. Otherwise it will return false. Now, we still have the size that is easy. So year will simply return what we have here, a top plus one. So at first we have top is equal to minus one. So whenever we need to know the size, we just add one to the top. So here we have minus one plus one equal to 0. So the initial condition of the stack is of size 0. Now, let's go to our push method. So we have our bush. And here, first of all, we need to check if the stack is full, then we can't add another elements. So first of all, we need to set the size. Is equal to the array.length. So whenever we have the size that is top plus one is equal to array.length than we need to throw our exception here. Throw an exception. That exception with a method message. It says that SQL. Now, if this is not the case, then we'll continue normally. So what we're going to do is first increment up, since we added an element set up, not minus1 anymore, it is equal to plus one, which is equal to 0. So now if we want to use the size, we get top plus 10 plus 11. And this is how many elements we have in the stack at the moment if we use the push method. So now after incrementing top, we need to hear the array at the value of the object we entered here. And now we're done with our push method. Let's go to our dock. Here. First of all, we need to check if our stack is empty, then we don't have any element to show. If it's empty. Then throw that exception. Exception and saying that the stack is empty. Now, if this is not the case, then our element just add the index cup. Now let's go to our final method. And the method we need to check if it is empty. If the stack is empty, we need to throw exception, saying that. And otherwise, we need to return this object. Whatever we have at the top. Here. For example, if we use pop here, then we need to return this object and to move it from the stack. However, if you use stop, then we'll just have a look at this object which is equal to three without removing it from the stack. So let's go back. And here, first of all, let's create an object className and to return. So this is the object we're going to return, and it is. Now we start the object here and this variable to return. And we need to remove this element, so we simply give it a value of null. And now we don't, we removed an element, so we need to decrement that up. So for example, if we have three elements and we use the pop method, then will decrement our variable top from three to two to one. So we'll simply decrement by one top minus-minus and returned this object and this variable here. So what we get here is that we create our interface, our exception, and our class, that we have, all our methods. So in the next video, we'll create our driver class and use these methods in it. 4. Stack Application: So now that we have all our methods, let's create our driver class. So the, this is our driver. And I would main method. Of course you're going to throw a stack exception. Or we can say exceptions, since stack exception is a subclass of the exception class. And first of all, we need to create our at a base stack S name instead, a stack with a capacity of port, for example. Now, first thing we're going to do is to add an element to this that, so we use the stack, the Bush. Let's add another one and stack the push to stack the three. So we're going to do as this example. So first of all, we have an empty stack. Then we pushed three elements. Now, what? It's going to happen here, when we run this code, let's go to our array-based stack. We're going to use this method three times. So first of all, we have the top initially is equal to minus one. When we pushed the number one. What's happening here is, first of all, it should be checking the size of this size is equal to array.length. Now the array.length is the capacity here. So this capacity and the driver class here is the array.length. Now, the array.length here is equal to four. So it's a PE, since the size is equal to plus one and top is equal to minus1. And initially so size equal to 0 since we don't have any element and 0 is not equal to four. So we're not going to throw the stack exception. So now we're going to increment the top. Now DOB is equal to 0. And in this case we're going to add this element, which is one. We're going to add it to the at a, at the position 0, since we increment it here. Now, the same thing. We're going to do the same thing two more times for object 23, for integers 23. So, and we're going to check if size. Now the size is equal to one. Since the size is equal to plus one and top is equal to 0. So size is equal to 0 plus one. And of course it's not equal to four, is not equal to the length. So the stack is not full yet, and we increment it one more time and we'll store it at, at a position one, then you element and then at array position to the second, the third element. So here let me check the sides here. So we print stack size. And after adding, this element will go. We're going to check the size, size. And finally, we are going to check it after adding the third element. So let's go ahead and run this code. See what's going to happen. So first of all, we have this size equal to 123. And let me use the stack is empty method. So here the stack is empty, it should return true. So the stack is empty. Now, if we use it, for example, here, the stack is empty. It should return false. Since the stack is not empty, we have three elements in the stack. Now, we also have the stack, the top. Here. We have three elements. So if we use the stack the top, it will give us this value without removing it. So let's use it here. We say top element. Thus that data. And let's run the code that will give us the top element is equal to three. Now let's use the pop, pop, and it will also give us three. However, if we use the stack, the top method, again here, now that we remove the element three would not get three. We'll get two now, since we move this element, now, the new element at the top position is the element two. So these are all the methods that we implemented in the array-based stack class and the interface of course. So this is it for this video. See you in the next one. 5. Symbol Matching Problem: Lets demonstrate the use of stack. So we'll do an example. Let's consider this tag. So here we have our stack, and let's do an example on symbol matching. So our program should return either that the expression is valid or not. So for example, these are the opening symbols, and these are the closing symbols. Now, let me write this way. So here we have our three symbols. And let me write here some examples. For example, if we say etch. So our program should return true here, since this opening symbol has a closing one. However, if we, for example, let's say edge, and let me place one here. So this opening symbol does not have a closing one before opening a new one. So here we have this. And to be a valid expression, we should add one here and you moved this. Now, every opening symbol is followed by a closing one. And of course we can add whatever you want. And so this is a valid one sense. Every opening symbol is followed by a closing. So what we're going to do is to accept an expression and then store every opening, every opening symbol in the stack. So let's suppose we have this expression. Okay? So we have, for example, a, B, C, and D. Let me click at 20. And so this is our expression and will pass through this expression one by o. So a doesn't match any of these opening, opening symbols. So we'll ignore it and go to this curly brackets. And it matches this one. So we stored it in the stack. So here we have, now this curly brackets. Then we'll go to B. We don't have at B doesn't match any of these, any of these symbols, will ignore it and go to this one. This one also doesn't match any of these opening, but it matches the closing one. So here we have this matches best. And of course, we are going to pop this element in the stack, compare it with this one. If they are equal, then we will continue in our expression. Otherwise, we're going to return false. The expression is invalid. So we're going to do the same thing here. We have this fantasies and I'm going to compare them. This one. We're going to go put it in the stack and compare it with this one. And finally, we have the square brackets also. Now we might have also, for example, something like this. So what's going to happen here is let me, let me delete is. And so this is our expression. And first of all, going to look at this. It is an opening symbol, so will place it here. And then we're going to look at the second element. We have square brackets. So it is an opening symbol also, and we'll store it in the stack. So we're going to push it. So this fantasies will go down here and the square brackets here. Now, we're going to check the third element, this closing one, we're going to compare it with the top element in the stack. So here we have a closing square brackets and an opening square brackets, the match. So we're just going to pop this one from here. And we're going to continue here. And of course we're going to put the parentheses here. Now, after that, we're going to compare this opening symbol with the last element here. And of course the image, then our expression is valid, otherwise it would be invalid. So this is a quick idea about this problem, and let's start with writing R code. So here we have our array-based stack. Let's create a new class and name and symbol matching. And now class, of course, we have our main method and we'll create a method that returns a Boolean true if the expression is valid, otherwise it will return false. So it would be a private static boolean. Let's name it, validate, and it will accept an expression as a form of string. Now, first of all, we'll start with the Y loop. And we'll see what we are going to put as condition here. Now let's create our array-based stack and with the perimeter of expression that length. So the maximum number of elements that can be stored in the stack is the maximum number of elements in this string. So if all of them are opening, we can store all of them. But of course it will return an invalid, false since we didn't close them. Now, we have, our stack has created, for example, an index, the same index. It will be at 0. And a Boolean statement is valid. Well, first of all, to be equal to true and character, let us name the current. Now. While it's valid and why this expression is valid, then we'll continue running this code. And of course, while the index is less than the length, length of the expression. So these conditions are satisfied. Continue executing this code. Now, first of all, going to store it in this current, this character equal to the expression at the index. So let's suppose we have this example and first of all, we're going to store edge and current. Now we're going to check if this director matches any of the opening or closing symbols. So to do that, let me create some opening, some strings to create them outside. They will be private. Therapy. This opening will be equal to these opening symbols. And of course, private static. String closing b equal to is closing symbols. Now, what we're going to do is to check if this current matches any of the opening symbols. So if we remember correctly, we have the string class, the method index off. So let's use it here. So F up the name that index off. So what we're trying to do here is to check if the current is an opening. So if opening that index of current, so if current is one of the characters in the opening string, then it will return the index of it. So for example, if we have current is equal to this opening symbol, it returns 0, disciplining symbol one, and the last opening symbol it would return to. Otherwise, it will return minus one if it is not equal to any of these symbols. So f guess. Symbol is not equal to minus one. Then we'll simply push it to the status of stack that push. And we're going to push this sum, but now this is not the case. It might be a closing symbol. So what we're going to do is to check as closing that index off. This current is also not equal to minus one. If this current is one of the closing symbol, then it would return any value other than minus one. So this is the case and the current is a closing symbol. Then we, then we going to compare it with an opening one from the stack. So we're going to pop an opening symbol from the stack. And we can easily compare the symbols or recount compare the index. So for example, we have the curly brackets. Then if we compare the index of opening and closing, if they are equal, then the symbols are equal. So this is what we're going to do. So if opening that index of stack, that puck is not equal to the closing index of this current. And this is not the case, then we just return is valid to false. Now we have an error here saying that the method index of type String class does not accept object since the stack that pop is an object. And we also know that we are only storing in this stack character. So I can safely say that we know we need this to be a character. And now let's see unhandled exception, since we might have exception here and this type of push and stack the pop. So to be on the safe side, we're going to use a try and catch. So we're going to try this. Otherwise if stack exception occurred, just gadget and return false. We're going to increment the index to pass through all the expression of the elements in this expression. And we're going to return is valid. So it will return true if the expression is valid, otherwise it will return false. Now we still have one modification and we'll do it in the next video. Why running the code to see you in the next one. 6. Symbol Matching Problem 2: So let's see what our code would do till now. For example, if we have this expression, first of all, it will get the first element and compare it with one of the opening symbols. If this is not the case, it will compare it with the closing ones. And of course, if it didn't match any of these opening and closing, we'll continue without doing anything. So secondly, we'll get this opening symbol compared with one of the opening symbols in the string opening. And of course it will match the curly brackets and we're going to push it to the stack. Now, we'll do the same thing with this D and a character's. We're not going to do anything since the opening or ending closing symbols. Then we'd have this closing symbol and it will match one of the closing symbol and the closing strain. And if this is the case, then we don't do pop up anything. The first element, the top element in the stack, that is this, this symbol. And we're going to compare it with the closing one. We're going to compare the analysis of them and they're equal, then we're not going to do anything. If they're not, then we're going to, I'm going to say that as valid is now false. For example, if we have this symbol than the stack, we're going to have the curly brackets down and the parentheses up. And we're going to compare the parentheses with the curly brackets and the not equal. So it will return false. Now we still have one modification to make. For example, suppose we have, let's say we have this, this code would run correctly. However, let's suppose we have square brackets here. Now, I will quote, will start all these characters, all these symbols and the stag. And first of all, it will pop this parenthesis and compare it with this closing parentheses there equal, then it will continue. And the other one, that is this curly brackets and compare it with the curly brackets. Now, we'll end with b and we're not going to do anything. And our code we returned true since we don't have any problem with the opening and closing. However, we still have this square brackets and our stack. So it should, we should return false since. Not all symbols are matched with one another. So what we're going to do is to compare the stag, to use the f m is empty. So if stack is empty, if it is not empty, then is valid is going to be false. Since we still have one or more elements in the stack. And this should return false, not true. And of course we're going to return is valid. Now, let's see the last examples. For example, the 3.5. This code. We have a closing symbol. And of course we are going to pop from the stack and opening one. Now the stack is empty and we don't have any symbol in it. So this will generate an exception and we're going to catch it here and returned falls directly. So this is our code and let's use it here. So first of all, let me start with accepting an expression. We use scanner scan. When new Scanner, as usual. The expression equal to scan. The next line. We're going to use this validate method. So if validate, if it is true, then we'll print expression is valid brand expression. And let's run this code. Let's see it's going to happen. For example, let's enter the return expression is valid. Now, let's suppose we have these symbols. And of course, they are valid since every opening is followed by a closing symbol. And if we just have an opening that will be invited, just a closing symbol, of course it would be invalid. And finally, if, for example we have the values, the symbols. This way, it will not be valid even though every opening has a closing symbol, but they are not ordered in the right way. So it returned an invalid. So this is it for the group symbol matching. And see you in the next video. 7. Secret Message Problem: Now we already have a stack built in Java. So let's use it and work with the problem. That is a secret message. So the idea is that we are going to receive a secret message that reserve reversed message. So for example, instead of saying hello, Eddie will be o. So we're going to convert this to Hello heady using stuck. So first of all, let's create our main method. But this has a main method and another method that is to decode this message. But you'll be private static. String, name it, decode and string message. Let's create our stack here. So first of all, we have a stack, and the stack will be a stack of characters. And this name is equal to nu. And of course, we're going to need a string. And let's use the StringBuilder. So this is a string class. String. It is a class defined in Java as name at SBI and B equal to U StringBuilder. So in this StringBuilder, re going to upend our characters and eventually our words. So let's use a string tokenizer. So distinct tokenizer class allowed to break a string into token. So to instantiate the string tokenizer, we simply write string, the coloniser. And you can find it in the Java that you think class is named SD, instantiated with the string, the message itself. Now that we're ready, let's go ahead and were acquitted. So it says that star cannot result in too. So simply can put stack from Java Tutor. And here we should return, we return it later. So first of all, would read every word in the string tokenizer. So as long as the strict organizer has more tokens, will continue executing. First thing we're going to do is to create a straight outside list Emit word. And if this word The value that is in the string tokenizer to give it as G, the next token. Now, suppose we have this expression first, where it would be this one. And we're going to read it and push every character into the stack. So here we create a for loop. For i is equal to 0 till i is less than or is that length will simply push this character into the stack so that child. And we simply pushed all the characters in the stack in this word to this step. After pushing them, we need to extract them using the pop method and a plant them into the StringBuilder. So while this is not empty, we simply append characters that using the standard bulb. And after that, after finishing from the wild loop, we simply append this whitespace. So let's see what we did here and an example. So for example, as we said, if we have, let's write it. For example. Hello, instead of having a low will be happening. This. Now, first thing, we're going to store this comma and then O, L, L, E, and F. So our stack will look like and L, o. And, and let's separate this. So here we have, this is our stack. We have 123456 characters. Now, after sorting them into stack, we need to extract them using the statute book. So while popping down, the first step would be then E, then L, L O. So we'll get e l, l. So if we give this input, that will return us this one. And this is what we need. This is what we're going to do. We need to reverse the word from O allele edge to hello. So let's go back here. And simply after fetching from the wild loop, we simply return SB for two. Now, let us go back to our main method. And in this method, we need to have the message and the decoded message. First of all, we'll use a scanner to ask the user to enter a message. And we simply ask the user to enter a message. And we'll store it in the message. Then we go into the decoded using the method decode and sold it in the decode message. To decode our message. Then we'll print it out. Message decoded. And print out the decoded message. Let's go ahead and run this code. So we'd have entered a message. For example, as we said, hello. To get that message decoded, is hello, happy. So this is how we use the state-defined in Java and how to use it to reverse anything from message to numbers or anything. We want to see you in the next video. 8. Array Based Queue: Now let's talk about queues. A queue is a linear data structure which follows a particular order in which the operations are performed. The odour is first in, first out. A good example of a queue is a restaurant. The person who comes first will be served first. The difference between stacks and queues is in removing. And instead we remove the item most recently added, And the queue, we remove the item the least recently added. For example, here we have two position front and basically we have two main operations, enqueue and dequeue. They are equivalent to pushing and popping in stacks. So when we want to enqueue and q, the element at position. And when we want to dequeue, we just use the front position and remove the element from the first position or seconds, so on. So now lets demonstrate the use of a queue and an example. Let's go back to Eclipse. Close these classes of stocks and create a new package. And sname based. Q. So in this package, as we did in this example, we're going to create a basic q a q interface. Of course we are going to create an exception. Exception. Let's rename it. So these are our three main classes. And let's start with our interface. We're going to have the methods, as we did in this example. We have a blue, but the size boolean is empty. Public void will take public objects to return an object and you move it. And we'll name a black object, name it front. To just see the front. Here we have an energy capital. And as we did in the previous examples, in this example, we need to create our exception. Let's create a constructor message, coding message and extends exception. Now, we just need to throw these exceptions and these methods queue exception. And we do the same here and here. So this is it for Q and Q exception. And the next video we'll use will work with the array-based goo and create our methods. 9. Array Based Queue 2: Now let's start with the array based cube. As you can see here in this example, we have the index front entry. So first of all, we need to create an array of object naming. And of course we're going to create a front and size. Now let's go ahead and create our constructor. So as usual, the capacity, because we're working with an array and we need to give the, the size of the length and create our object with the capacity equal to the size, equal to 0, equal to 0 initially. Now, let's start with our size. Of course we're going to implement and we need to authorize it on two methods. So here we have all the methods and the interface aside with size will simply return the size, whatever it the size as we just return it. Now, empty is empty. We just return if size is equal to 0. So if science is equal to 0, then it is empty. Otherwise, it is not empty and it should return true. This expression is a Boolean expression and it returns true if the size is equal to 0, otherwise it will return false. Now, let's start with enqueue. First of all, we need to check if the size is equal to array.length. Then we don't have any space left in the skew and we need to throw the exception. So we need to throw the exception. And saying that Q S foot. This is the first condition. Now, if this is not the case, then we can add the element to the skew. So to add it, we'll just use the year. So we'll add it at the rear. And now we need to increment the read. So when we simply can say that, that v plus plus. However, when we get to a point where the rear is at position six, and we add an element here, then we need to increment the real U2 will be at position seven. Now, however, if we try to add one more time, that will give us an exception. But if One of the front elements here are deleted. For example, if we use the Q and we removed one, then we have an empty space here. And we didn't use it because that is just incrementing by one. So we need to solve it. We need to solve this issue by saying that whenever this sphere is equal to array.length, in this case is equal to seven. Then we need to modify it and give it a value of 0 to return p2 here. So to do that, we can simply say can use f statement. And if I needed length is equal to rear, then we'll just give that a value of 0. However, we can simply say that v is equal to beer plus one. We increment it and the remainder of the time. So what we're saying here is V is equal to d plus one. Every time real plus one is less than this IDed length, we don't have a problem. Everything will work correctly since j plus one remainder of array.length is the same. Since, for example, if we say for Commander of five, it is 43 remainder of five. It is. However, if five, remainder of five is 0, so whenever we have three plus one is equal to array.length rear will become 05 remainder of five-sixths, remainder of six is equal to 0. So this is it. And we'll just increment the size since we added one element. Now let's move to the queue. And this example here. First of all, we need to check if size is equal to 0 or we can use as empty method. For example, if it is empty, would just you queue exception saying that in that queue is empty. And then we can work. Now, first of all, we need to create an object to return. So what we're going to return is the element at front. So we simply return. And now we need to remove it from the queue. So to do that, we simply use the same a technique that we used for the year r1 plus one remainder of at a ninth on, we'll go into a decrement size since we removed an element and we just return to return for this is it for the dequeue? We still have one last method. And this method we're going just to have a look at what, what we have at the front. So first of all, we're going to check if it's empty. Row. Let me copy this. And basically tear. And of course, the returned array at front. We don't need to remove anything. We'll just turned to return. These are our methods. And returned still have a new method. That is a toString method. We didn't use it in the stack, but you can create one here and print the queue whenever we want. So let's go ahead and implemented. Now, if we want to create this method public, trying to string, and we can work with the for loop and pass through all the elements in the array. However, I prefer to to modify it every time we enqueue or dequeue. So let's first of all create a StringBuilder. It is like a string, but we can modify it. You can add to it whenever we want or delete from it. So we again create a string under this defined in the java.lang class. So StringBuilder sb, sb, and he will give it, will instantiate that new StringBuilder. And really good, we can use it. So every time we enqueue, we can append to distinguish the SP that append whatever we increment we added plus space. And every time we dequeue, we can dequeue the element q it from here to just sba dot delete from position 0 to the length of the object plus one to account for the whitespace. So till the object to return that length. To return the toString, first of all, we need to convert it to a string that's nine plus one. And this is how we delete from the StringBuilder. And of course here we simply return sba dot two. And we're good. So this is it for the array-based queue class. And in the next video, we'll create the driver class in which we'll test these methods. 10. Queue Application: Now that we have all our methods, let's create our transfer class. So this is a driver and discuss food. We have our main method. We need to know's queue exception. And let's create the enemy base, namely U equal to U array-based Q with the capacity of. For. Now, let's enqueue some elements. So for example, q dot q one. And let's copy it four times 234. Now if we use, if we print out Q or Q, the two strings are the same. We get 1234. Now for example, let's dequeue. So for example, if we say, let's print it out to see what we're going to remove. Q dot dq. It will dequeue the front element at position material. So in this case, we'll get one. So we dequeued pond and if we go ahead and print them one more time, we'll get 234. Now, if we add an element, for example, let's say we're going to add five. So what we're going to get if we print it out now is 2345. So this is it. Now. It doesn't look like this in the, since we are using the StringBuilder. However, this five is at position 0 Now in the array. But we see, we're seeing it as 2345, since we're just adding the element at derived position and you're moving it from the left position and the StringBuilder. Now for example, let's use some of the other methods. For example, the size of free, to use q-dot sides. Here, we'll get three since we have only three elements. So here we have three elements. However, if we use it here, print out the size u dot size, we get four since we added one more element. So here we can see it clearly is first of all, we have three. However, if we print it out after adding the element five, we get four. Now let's try Q that is empty. Let's print it out. Is empty and we'll get false since we added some elements here. However, it could split it out with that before enqueuing. Then we'll get this true and then false since we added some elements. This is a quick example of Q. And the next video we're going to talk about josephus problem and learned how to solve it. So see you in the next video. 11. Josephus Problem : Now let's solve the Joseph's problem. First of all, let's understand it. So for this problem, we're going to have players and a number. For example, let's say we have three players, John, Alfred, and trends. In this case, let's say we have the number and the number is equal to two. For, for example. The first of all, we need to store these names, NICU. The game ends when one person is left. For example, when we say k equal to four, First of all, we need to dequeue. We Dequeue from here. We need to dequeue John and added to here. Then. So this is one times we perform it four times. So we still have three times. So we need to Dequeue, Enqueue, Dequeue and AQ. And so this is the last time. So now we perform this operation for all times. And we ended up with Alfred at the first position. So we dequeue. Now we still have two names. So we'll perform the same operation also four times. So dQ, Cress, and same thing here. And finally, last time with a huge chunk and place it here. So we end up with crest at the first position. So we remove it by using the q method and we end up with John switch. John is the winner. So this is it. So this is the idea of the Georgia, this problem that we're going to solve. Let's now implemented and outgoing. First of all, let's create our method plus name it so that it will take a staying at a array of strings. And let's name them players and an integer k. Now, first of all, let's create a string and add a based two q equal nu at a base view with the capacity of players that length. So how many players we have would just give the cue display. Now, first of all, let's try. And if anything happens, we'll just catch this exception is a queue exception of course, and simply return that wild, identifying the winner. Now, let's work with our Try block. First of all, we need to enqueue all the players into the cube. So for all, we can say that for the for loop, there's that length and in queue every time however, we can use another form afford MOOC, which is let's name player. Four player in distinct layers, would just enqueue this layer. So this is another form of the for loop. We can use it when we have a stain or something that we can work with as, as a variable and we can include in this queue using this for loop. Now, let's go to our while loop. As long as our queue has more than one element, will just keep working in it. So y queue size is greater than one. This code would be executed. So first of all, let's print the queue without modifying it. So it would just print queue. And thus q. Now we use the phone loop from 0, del k. We'll just use the q-dot enqueue, Q, the Q. So what we're doing here is, first of all, we're going to dequeue, going to remove an element from the queue and then stored it one more time by using the enqueue. So we can say that we need object. For example, equal to Q dot dQ. We just dequeued the element and then store it. So this is the same thing, but you can simply add this into the parameter of the q-dot enqueued. Since due that Enqueue accepts an object and this du, the dq returns an object. So this is the same. Now we simply after working with in this for loop in queuing and dequeuing for k times. Now, we simply dequeued the last element, the first name of player. So we can simply view dequeue and you move it from the list and let's say it is out. Now, we're done with this. After performing this while loop, we still have one player and he's the winner. So when r equal to Q dot dq and we remove it from the list, of course we have an error because this is an object and this winner is changed. So, and you know for sure that this element is a string. So we can give it value of string. Now that we're done with our code would just lastly returned. So we simply here. So this is it for the josephus problem. Let's create our main method and executed. But let's first of all create a string of arrays, so, and a string of names. Let's name it layers. And this, we're going to create the names, for example, Chris and Fred and John. So this is our string and a string and we have an integer k that twill come to ask the user to enter. So we're going to use the scanner to scan it. And let's ask the user and gay and stored whatever the user entered and the variable k. Now, the winner is solve layers and K. So since this returns a string, we can store it in a string and simply print it out. Now, let's go ahead and run this code. So what we're going to get is enter k For example, let's foil. So first of all, we have Chris, Alfred Chuang. Now we perform k4 times. So we moved Chris and then Alfred, and then John, and then Chris, and we end up with Alfred at the first position. So we dequeue Alfred and Alfred is out. Now. We still have John and Chris. So we perform this operation four times. John, Chris, John and Chris, and we end up with John at the first position. And John is out. So we still have one element or one player, and he's the winner. So just print out that the winner is Chris. So this is it for the josephus problem. See you in the next video. 12. Singly Linked List part 1: Like arrays, linked list is a linear data structure. However, the elements in this list are linked using pointers. When we use arrays, we have some limitations. For example, the size of the arrays is fixed. And when we need to insert a new element in the array, it is expensive because we need to create room for this specific element. So this is an example of a LinkedList. Now, these are nodes, so we have four nodes in this example. And every node is data and address. So we have a box for data where we store our element object, integer, string, character, and so on. And we have another box to store the address of the next node. So we can think of this address of a pointer. We don't need to know the exact numerical number here, but it should point to the address of the next node. So the LinkedList is this list. And when we say singly, This means that the nodes are linked together using one direction. So we can't go back from 20 to ten, we can only go from ten to 2030 and so on. So this is the idea of a singly linked list. And let's go to our Eclipse workspace and create a new package. Name it singly linked list. And this package, as usual. Let's first of all create our exception class. Now, since this list is infinite, so we can add whatever we want in this list and we don't have a limit. So let's name this exception as empty list exception. Since we don't have to worry about whether we exceeded the elements is we don't have any limit. And in this exception, of course, we're going to extend the exception class. Extends exception as we did before, and create our constructor empty list, the message called a soup with parameter message. So this is our empty list exception. Let's go ahead and create another class. Now. Let's see, for example, let's create First of all, the position and this interface going to have only one method to get the element. Now, we need to specify that this is a generic type. So when we say d, Now, this is a generic data type. And we got with this class. We've seen how to use it at, let me just create another class that is node. So let's name it singly linked list node listening with S naught. And as we did in the position, which simply at D. And of course we go to implement the interface position. And, and the method debug get element. And simply, let's create some elements variables outside. We have the element d. We also have the S naught itself. Unless name and next. So we have to private values, variables outside. So to get the element, we simply return the element. So this is our data element method. Now we might also want to return the next node. So we simply say public snowed yet next. And we'll return next. Then next node two we have. Now we might also want to set the next node. For example, let's create another method to send to set it. So public void, it's name it and it will take it off, and it will take a node and payment next. Now, we'll set this to be equal to this one. So what we did here is setting the next node. We have here. It is named next and set it whatever we have here. So this is the subnet. And if we want to set the element, we have the element d can simply create another public void set element. And in this case we get an element, the element and say this dot element to element. When we use this, we are saying that we need the local variable d from here and set it to whatever we have, the parameter here. Now, let's create our next interface. This interface would be, let's say I'm a Teslas. So this S list is kinda interface, absolutely. And here we have all our methods. So the first method, and of course it is a generic type. The first method as usually it will be the size. Then public boolean is empty. Now we still, we also have to answer it. Now if we go to this example. So this is our head and this is our dale. So we might want to store a value in hand. So let's create a method that stored at head. So public void, insert at head and whatever the animal is. Also, we might want to sell it at tail. So answer. Now, since it is unlimited, so we don't have to worry about the empty list exception. Any exception. That time, we might want to remove an element using the remove from Pat. And in this case we need to throw the empty list exception since they list might be empty. And the same thing will occur if we use removed from tail, throws an exception. So now we're done with our S list position and will continue with this in the next video. 13. Singly Linked List part 2: So now that we have all our methods, let's go and create a new class and write them down. So this class will be a singly linked list class. And in this class we're going to first of all, extent or implement the S list we created earlier. But of course, first of all, it could be generic and implement. We can have the 0s and we need to inherit the methods. Now we have all the methods and let's work with them. So first of all, we have the size. And before that, let's create some variables outside. The first variable is the nodes. As we said, we have two nodes, the head, that will be the first element or the first node. So this is the head node and the tail is at the last node. So we have two nodes as not with E. And we also have signs as usual. And let's create the StringBuilder to use it for the toString method. Now we have also the constructor Republic singly-linked list. And here, let's instantiate the head and tail to be equal to. So the first time we create the singly linked list, we have the head and t equal to none. And size will be equal to 0. And we'll create the StringBuilder. Now we also have here. So this is it for liquid, the constructor. Let's start with the science. First of all, for the size, we simply return the size. For the empty is empty, we simply returned as usual. If size is equal to 0. Now let's move on to the other methods. They are much more complicated and we need to work them slowly. So the first method is insert at head. So let's go back to the picture. And here we can see four nodes. Suppose we need to add a node here. Suppose we need to add an audit with an element 0. So the first thing we need to do is to create the node and then link it to this node. After that, we need to move the head since they had was here. Now we need to move it to here. So we'll give the head. The new position, which is the new node. So let's go back here and implemented. So the first thing we need to do is to create this node. And let's name it knew as node. It will be equal to new node, this node by using e. And the next node is, as usual, we have this, this linked list. If we create a new node here, the next node will be the head. Now, we still have it and let's see what it is. So yeah, we need to create the constructor. And the snowed we forgot to created. So let's go back to S naught and create our constructor, which is public knowledge. And I'm serving as element. And it will take two parameters, a0 and a1. And element will be equal to E, max would be equal to. And now we can go back to our singly linked list. And we, okay, now after that, after creating this as node, we need to check if the list is empty. List is empty or we can simply say F is empty. If this is the case, then we don't have any element in this node. So the first element we're going to add will be the head and tail. So again, say that DE is equal to mu naught. In both cases, if it is empty or not, the head will be equal to this. So this f only execute this line. And they had in both cases would be equal to this new asymptote. After that, we need to increment the size since we added a new element and we need to insert it in the SPS StringBuilder so we can append. But when we use append, we appended to the end. However, we need to add it at the first as the first element. So we'll need to use insert, well, do we need to insert it at position 0? And what do we need to answer? We need to insert this new node and this new element which is E. And that's the whitespace here. And we'll talk. So this is it for insert at head. Now let's go and work with insert at tail. So the first thing we need to check, insert a tail is also if it is empty. Now let's create the new AST node. As node. The new node as node, the value of E. And so the next node, as you can see in this picture, is null. For example, if you want to add an element here, an ODE. So we need to point from here to the new node. And now the table would be the last node. And this last node will not point out anything. It will be not. So let's go back to here and work. So here we have inserted at the it. First of all, we need to check if it's empty. If it is empty, then It's also the could this new snowed. And in both cases, it will be equal to the astronaut. Otherwise, if it is not the case, if it's not empty and we already have an element. So this element, the last element, which is detail here, we'll point out to this node. So how do we do it? If it is not empty, then tail that sat next member, we created a method to set max and the delta setText will be the new node. Now, the tail would be this new node. As we said. We increment the size and appended at the end of the string builder or using either toString LAS spec, we still have removed from hat, removed from tail. And you might add, get ahead and get tail to have a look at what we have at head and tail. And of course, our last method, that toString method. So we work on them in the next video. 14. Singly Linked List part 3: We still have some methods here. So let's start with the removed from head method. First of all, let us delete this. And first thing we're going to do is to check if the list is empty. So if it is empty, then we need to throw the empty list exception. Type the exception and saying that the list is empty. If this is not the case, then we'll continue without throwing this exception. Now, the element that we're going to return that store it in a variable called to return. And it is the element that is at head that get element. So now we got this element and store it and to return. Now, if we need to check if the head is equal to tail other n, In other words, that we only have one element in this list, then both head and tail will be equal to null in this case. So f is equal to k, then will simply say that AD is equal to, is equal to nine. So we move this element to it. We only had one element and we remove that. So now head and tail will be equal to null. Otherwise. If this is not the case, then since we removed from the head, was we remove this element. Now, instead of pointing out to this element, now the head will be this node. So we need to remove the pointers from head from here to here. So to do that, we will simply say that head is equal to head that next. Next. So this is it. And of course, since we are removing an element, we need to decrement the size by one and delete from StringBuilder, such as lead from the StringBuilder. We need to start with 0 and, and with whatever we have here. And this object, it is to return to strength and the length of it plus one dot count foot whitespace. We're going to delete and finally, return to return. Now this is inferred, removed from headless. Continue with she move from Taylor. Now here. Same thing. First of all, we need to check if it is empty, is empty, then we throw an exception saying that list. And otherwise, we continue. We need to store the return equal to whatever we have in detail since removing from the tail that get element. Now, we also need to check if head is equal to k. In other words, is head and tails. The same node. So we have only one element. Then. The both head and tail will be equal to null and the list will be empty. So if head is equal to, we simply say that had to be equal to take to that. Otherwise, just gonna work with that since we're moving from today. So let's go back to our picture here. And let's see, for example, if we want to remove this node. So we remove that. Now, we need to say that the tail is this node. And to do that, remember, this is a singly-linked list. We can't go back from here to here. So what we need to do is create a loop and pass through all the nodes until we get to this node. So we don't want to the last node, we need the one before it. So to do that, let's go back to Eclipse and implement this code. So first of all, we need to create a new node other than the head and tail. So here we have the head and here we have detailed mid to create an atlas limit. And it will pass through all the nodes until reaching this node. So here we have a new node, D. Let's name a town at the first, at the first position. It is at head. While damp is not equal to detail, this code will be executed, so that will be equal to them, but get next. So every time we check if the next note is the tail, if it is not the tail, then we'll go to the next node. And reaching this one. We, when we reach this one, will check if the next node is the tail. Yes, then we go out from this while loop. Now we have our position, our new position which is here, and the damp is pointing out at this node. So we can simply say that they would be equal to time. And of course, since we are here and we don't want this Arab anymore, we simply give this value, a value of null. So we can simply say that that sat next to a value of null. We don't need to point at any node anymore after the tail. Now that we're finished with this gold, we can simply decrement the size and sweep, removed one element, and we need to delete it from here, from the StringBuilder. Now, let us see how can we deleted. For example, if now StringBuilder, we have 1234 and we need to remove from the tail. So what we're going to do is to know what is the length of this and minus the length of the final value. For example, it is 12 with the whitespace 34567. So it is seven minus one, which is six. So we'll start at this position and we'll end the length. So how do we do this? We simply right sba dot length minus whatever we have in this element to return the string, that ninth minus1. And we'll end with SBY, that length. Now we deleted from StringBuilder and will simply return it. So this is it for the removed from Dale. And let's go and continue with the other message. We send, get head and get tail. And of course the last method which is a string. So let's start with the get. And we simply force, we're going to throw the empty list exception. If it is empty. We're going to throw this exception. And this exception that the list is empty. Now, otherwise it is not the case. Then we simply return head that get element. Let's copy this code and create get tail. So instead of get head or tail and to check if it is empty, otherwise we have a tail that get element. Now, the last method is public string to string. And since we use the StringBuilder, can simply return, it, returns Sb to strength. So these are our methods and now we're all set. We can use them in a rhetoric class in the next video. 15. Singly Linked List Application: Now that we have all our methods, let's go ahead and use them in our driver class. So this is our driver class. And this class, as usual, is the main method. Let's create the singly linked list of integers. And the same it singly linked list SLL. You think LinkedList. And first of all, let's print the size of it. So as dot size, let's go ahead and run this code. Co2 count to happen. The size is 0. Now let's add some elements. So I said that insert at head one, SLL, that insert at to assist SLL dot insert at had three. Let's print out the singling list here. And we're now going to have 12. And after that we inserted at head the element three. So this is the head, so we have 312. Now, if we insert at Tate for example, insert date number one, and then print it out one more time. We'll get 3121. Now, let's check here. If it is empty, is empty, and let's check it one more time. Is empty. Run this code, we get true at first and then after adding some elements, we get false. Now, we still have some methods. For example, let's remove from head. So we can simply save that SLL dot remove from head. Print out SLL. We have here. So this error is unhandled exception, we need to throw this exception, knows Empty Exception. Now let's go ahead and run this code. Not have an earth anymore. And we get one-to-one sense, remove this element from head. Let's do the same thing at date. So as LL remove from tail and print out one last time. We'll get one to after removing the last element. And in all of our examples we used integer. However, we can choose any type you want. For example, the string double, anything. And it will work the same way. So this is it for this video. See you the next one. 16. SLL Based Stack: Now, one thing we can do this singly-linked list is to create a step. So here we have the classes, that's a 100 room for this tag. So let's create our stack interface. Name it. And the stack would be generic. Type. Goes as usual. The Boolean is empty. And the push. What we're going to push the element b. B also that bump. And of course we need to create the exception class, but this tag, so stack exception. And as usual extend exception with the constructor. But this message, but this message and we're done with this exception, would use it with Bob and top, so knows that exception. And here also knows exception. But the difference between using singly linked lists and at a is that when we need to push, we don't have a limit since the singly linked list is not limited. However, when we used array, remember we used to throw here also an exception since we might be exceeding the limit of the day. So this is it for the StatPlus. Now let's go ahead and create our singly-linked list based stack. So this is a singly linked list based. And this singly-linked list we have. So the methods we created in the interface. So we will simply implement the stack interface. And upper right, all the methods. Let's simply overwrite them from E by add implemented methods and the methods. Now, the first thing we're going to do is to create the singly linked list outside before the constructor, private singly linked list of D. Now let's create a constructor, public singly-linked list based that. And in this, in this constructor will simply. Give a saddle defined you new thing, the linked list. And of course, here we have like this. So this is it and that's separate them. So this is our constructor. Now let's move on to the science. While using the size. We can simply return the singly linked list using is empty. We can also use the isEmpty method available and the SLR. So we'll simply return ALL that is empty. Now, what we're doing here is that we've created as a linked list. And linked list. We have all the methods. We have inserted head, insert, remove, get, and of course size and empty, so we can use them simply. And our singly-linked list based stack, because size and is Empty are the same. Now when we go into Bush, I'm going to push ahead. So we use the push from head or insert at head and the singly LinkedList class. So to do that, we simply say SLL, but insert at what we have here. And this is basically now. First of all, let's use a try and catch block. So try if something happened, just catch it. And this should be the empty list. If it is empty. If the list is empty, then what we're going to do is to throw the new exception that we created, which is the stack exception. So in this, we create a new exception saying that the stack is empty. Now, this is the catch. Let's go back to try and write some code here. First thing we're going to do is to create the object. And we also need to remove from hat. So in this stack, as we said before, we add the first and last out. And we can say that N is first out. So we need to push ahead. And that's the same time if we want to pump, we need to pop from the head. So SLL dot, remove from hat. Now after removing this, we simply return. And we're done with pub. Let's just go to connect method which is top. So as we did and try and catch, catch the empty list exception. If we have an activist exception, then we throw a new stack exception. And we'll say that stack is empty. Now if this is not the case, then we just Be it an object to return and use the get method from SLL, but get help and return this object. So this is it for the top method. And now we're done with all the methods ahead and create a class to use them. We'll name it SLL based stack. So in this class, as usual, we have our main method and that's created SLL based dark integer and slim it SLL b equal to new stack integer. First thing we're going to do is to create a push, to push an element which is one, be the Bush and the Bush regime. Let's go ahead and print the size, size and this code. See what we get. So we got three. Now we forgot to create the toString method. We can simply create it after this method. And this method will simply be the SLM. Good. Now let's go back here and run this code one more time. We'll get three. Now if we go ahead and print SLM b will get three to one, since we're pushing in the stack. So first of all, we pushed one, then we push two, Then we push three. So putting them in D. Now if we pump from this, we'll get SLL B that we get the number three here saying that unhandled exception, we need to throw this exception here, throws the exception and run this code will get three. Now if we go ahead and print it out one more time, we'll get to one. Let's check if it is empty. That is empty, it should return false since we have two elements. And lastly, let's use the buttock method. So SLL v dot. And we should get the number 222 is the first position. So this is it for the singly linked list based stack. Now, we implemented stack using three methods. The first one is by using array, and the second one was by using the built in Java stack. And lastly, we use singly linked list to implement stack. So this is it for this video. See you the next one. 17. Doubly Linked List part 1: Let's move on to doubly linked list. And doubly linked list is a linked data structure that consists of a set link jackals called nodes. Each node contains three fields to link fields to the previous and the next node. And of course, one data field. So for example, this node contains one data field to store data. And for example, suppose we have variable called b and two nodes, two fields to point out to the previous node and to the next node. And of course we have in the first field, in the first node, none, and in the last field, the last node and also not. And here we have the head pointing to the first node and the trader pointing out to the last node. So let's go ahead and implement this program here. So let's create a new package and name it doubly LinkedList. And in this package, let's start with creating our position interface. As we did with a singly-linked list. We have our interface position. And in this position it will be generic, generic type. We have only one method, get element. So this is our position class. Let's create another class. I would note class is named D, since it is a doubly-linked list, the node. And in this class, let me just, yeah, okay, so here we're going to implement the position interface. So by simply writing implements position. And of course you don't have to override this method. Get element. So let's create a variable outside this name of the element. Nodes. We need two nodes here since we are working with previous and next. So let's name them, denote the previous. And next. Now, in this method, what we are going to return the element, we simply return the element here. In this case. Now, let's create some other methods. For example, we need to get the previous node. So it will be public forgetting and also to be of type d naught. And that previous. In this case, simply return radius, get next. So in this case, the node to the next node, and we simply return next. Now, we might want to setup the previous and the next node. So let's create a method to set them up. So it will be of type void since we're just setting up these nodes. So set previous. And we need to give it its name, its previous. And simply set this third previous total local variable previous IE to be equal to the pedometer to devalue entered by the user for the program. So it will be equal to previous. And we need to create another method, methods, method to set next. As we did in the previous two, would be this dot next equal to next. So now we're done with setting and getting previous and next. Now we still have only one method that is to set the element. So it will be a void element and element. And this element equal to elements. And now we're done with this class. Let's go ahead and create some exception class. So as usual, first of all, we have the empty list exception. So I would list might be empty. So let's create an exception. But that empty list exception. And it will just extend exception with creating the constructor and the list exception message and that message. So this is the first exception. Now let's create some other exceptions and we'll talk about them later. So we also have invalid position exception. And it will be the same. It extends exception. And so the last exception we're going to create is the boundary violation exception. So these exception will make it easier for us to detect and we'll put this doubly linked list data structure. So boundary violation exception. And of course I should extend the exception class. The constructor. The constructor. Now, with done with these exception classes. And we can go ahead and work on with our doubly-linked list. As we did with a singly-linked list, we created an interface to name it S list. So here we're going to create the D list since it is a doubly-linked list. So we're going to create this D list, and then we're going to override all the methods from this interface into our WMA list class. So we do that in the next video. 18. Doubly Linked List part 2: Now, before creating our delist class, let's understand these exceptions. So first of all, we have the empty list exception. And this class in this exception, who going to check if the list is empty? So we'll only throw this exception if the list might be empty. The other exception, the inverted position exception. So for example, if the user is entering a node, it is not in the list, then we're going to throw this invalid position exception saying that the node is not part of the list or we didn't and identify the snowed. And lastly, the boundary violation exception. So when passing through the list, for example, if we going to use a next method, we're going to pass through the node and we end up with the last node. And we used one more time, the next. Then we're going to throw this boundary violation exception, since we don't have any node after the last one. So these are our three exceptions, glasses. And let's go ahead and create the denote class. So in this case, this is the Denote, the list, sorry. And this class will be T. And this creates a method. First of all, we have, as usual, Boolean is empty, is empty. And we have the method to get the first element, the first node. So it will be of type denote T and it will be first. So here the list might be empty. So what we're going to do is to throw the empty list exception. Now, we can also create a method to get the last node in the list. And of course it also might be empty. So we throw this until succession one more time. Now, let me see what's going on here. The method body, I'm sorry, hidden. We need to create the interface and interface math class. And canceled that. Let's create the method next to get the next node. So here we have d naught e to get the next. Let's name it next. And it will accept a denote. Let's name it d. And after accept Him, accepting this node, we have two issues here. First of all, this node might not be one of the nodes in the list. So what we're going to throw it. The invalid position exception. Since this position we entered here might be invalid in this case we're going to throw this exception. Now. We also might encounter a boundary violation exception, since we're going to try to access the next node. Suppose this node is the last one, so we can't access the next node. So to fix that, we simply draw the boundary violation exception. Now we also have the previous. So we have the same DNA. The end throws, invalid and bounded variation exception. After that we have two methods to remove and replace. So first of all, let's create the move. So we're going to remove an element. So it is div. Let's name it, you've moved, and so we're going to remove it from the node. Let's name a deem and remove it. Maybe this node is not one of the nodes in the list. So what we're going to throw is the invalid position exception. And we're going to throw the same thing if we want to replace, for example. Note here might not be also one of the nodes in the list. So we're going to throw in violet position next. Now let's go to insert. We can insert at first, insert at last, and insert before a node, and insert after. So let's go back to our picture here. For example, we can insert here between a and b. So we can use either insert before b or insert after a. And you can also answered at first and insert last. So let's go back and create these methods. First of all, let's create the node and insert first. And we're going to accept and element d. Then the same thing at class, insert last E, and let's name it E. Then we have insert before a node and insert after a node. So now insert the node. And let's name it, insert before. Now we're going to accept them out. So we going to know what node to insert before. And we're going to accept it here. Let's name a d and of course, the animal that regarding to insert. So this is the element d. Now denote that is given to us, might be and valid. So of course you're going to throw the inviolate position exception. The same thing with inserting at a specific node, insert after the sname it D, D, E, and E will have the throw of the invalid position exception one more time. So this is it for the class. These all our methods for now. And in the next video, we're going to implement them in the doubly-linked list class. 19. Doubly Linked List part 3: So we have now onto method in the interface D list. Let's go and create the doubly LinkedList class. So doubly linked list. And in this class, we're going to implement this interface. And of course we're going to override all the methods to let me use this and add unimplemented methods. So we're going to have all the methods here. First of all, let's create our constructed and some variables outside. So as usual, we have the size and we have two nodes. Now, the D, let's name them header and trailer. Now we can create our constructor. And in this constructor going to setup our header and failure and suicide. So size. Then we have header and Taylor. So let's go back to this image. This is our header, and this is our data. First of all, we don't have any node in this doubly-linked list join creating the header and trader, the header should point out at the trailer and the tailor should point out at the header. So here we can say that this box point out at the tailor and the failure, the first box should point out at the head. So let's go back and see how can we implement this. First of all, our header will be equal to the new node E, node. E node. And first of all, we have, as we said, in the position class, let me see where our denote. We have element previous and next, but forgot to create our constructed. So that's created. And in this case, the constructor will be of three parameters. It will take d node, node D. Let's name it previous soapy and the element e. And lastly, the d naught, that is the next node. And of course, let's set them here. So the element will be equal to a, previous would be equal to b. And lastly, next. And of course he identified this. Now we can go back to our note, and here we need to create the previous next and element. So first of all, since we don't have any previous. Next, we set them to Null. And after that we're going to create our trailer. Now, I will taylor, As we said, it should point out to the header. So none, none. And we also said that the header should also point out to tailor. However, here when creating the header, we didn't have any tailored to. So instead we're going to point it out here. Header that sat next. And we're going to set next the trailer. Now, we're done with this method and the constructor, I mean, and we can work with our method. So first of all, we have the size will simply return size. Then we have the SMT and as usual determined size equal to 0. Now we can work with our more complicated methods. So first of all, we have the first method and as we said, when extracting a node, it might list, might be empty. So to be on the safe side, we throw this empty list exception. Now let's create this method. So here we have, we don't want to extract the first denote. So first of all, we're going to check if it is empty so that the list is empty, then we're going to throw a new empty exception. And in this case, we're going to say that list is empty. Now, this is not the case. Then we'll simply return the first mode. How do we access dispersed node? Let's go back to pin. And we can see that whenever we have some nodes in the list, the first, the header going to point out at the first node. And the trader who going to point out at this last node. So the axis, the first node, we simply, let's go back. And in Eclipse, we simply return whatever we have at the header that get next to the next node to the header is the first node in the list. And the same thing here. First of all, we're going to check, so let me copy this and pasted here. If this is not the case, then we'll simply return jailer that get the previous node. So after getting the previous, let's go back to this picture and check. So here we have our trailer. The last node in the list is the node before that later. So whatever the Taylor is pointing out to is the last node in this list. Now let's go back here and we'll work with the other methods later in the next videos. 20. Doubly Linked List part 4: Let's now move on to next, previous and remove, replace and so on. So here in the next method that might throw an invalid position exception and the boundary violation exception. So let us see what is an invalid position exception is to us. So for example, if the node entered is none, is event a is not a valid position. O, of course, if we enter the node header or trailer, there also not a valid position. And finally, if this node is pointing out at a next or previous node, as we can see here, all nodes in this list should point out at the next and the previous node. Only the header and trailer are allowed to point out at one node only. So the header is pointing out that the first and the Taylor at the last. And here we can have none. And the same thing here. Now let's go back here. So let's create another method that checks for us the invalid positions that we can work with. So it's created before this next method. That would be private since we're using it only in this class. So let's name it private void. And it will only check the position and the position of this t naught. And of course it should through the invalid position exception. First of all, we're going to check if D is none. Then we're going to throw the New Invalid position. Invalid position exception. Let position exception. And of course, let's write healed that null is not a valid position. And let me copy this and paste two times. And if D is equal to header, then we'll also go into throw the invalid position exception, but saying that header is not a valid position. And also the trailer going to throw jailer is not a valid position. So the last thing we're going to check is if this node D dot dot next is equal to null. Or the previous is also equal to null, then this is not part of the list. So we're going to throw you invalid position. Exception, saying that node is not part of a deal is. Now we're done with this method. We can use it in our methods here. So first of all, before doing anything, we need to check the position. So it calls this method. So if something occurred as if an invalid position exception of good will simply throw it using this chap position. So it will go in to check it. And if nothing happens, then you can work as usual. And let me see what what's the problem we must return. Of course, we're going to return it at the end. So first of all, since we're going to get the next node, first, we're going to check if the next is later. If the next door is a tail, then we can get the next node. Sends Taylor is not part of the list. So we're going to throw the new boundary violation exception, saying that cannot move as the last note. So when this condition is satisfied, then we are at the last node and we can't access after that. This is not the case. Then we simply return the next. Now, we're going to do the same thing with the get previous. But we're going to check if the previous node is the header. And this case, we can't access it since it's not part of the list. So first of all, we need to check the position. If everything is okay, then we can continue. If previous is equal to in this case, the boundary violation exception that we write it, a newline boundary violation exception saying that cannot move the first node. And here, this is not the case. Just return the previous studies, the next and previous methods. Let's continue with our remove method. Lets go back. And let's suppose we need to remove this node. In this case. First of all, we need to cut these pointers from here and here and create new pointers. So a is going to point at sea. And C is going to point at a. So let's implement this in our code. To remove, we simply create. First of all, we need to check the position of the node. If everything works correctly, then we can continue. So we need to return. Let's create an object return. And in this case it will be the dot-dot-dot element. Now, before setting these fields into non, we need to set these two fields in a and C to point at each other. So how do we access a? We can simply write that node d dot get previous. So when we saying didn't get previous, we're getting a and we need to set a to be pointing out at sea. So how do you do that? We can simply write d that gets previous. Now, using get previous, we got a. What we're going to do is to set this field to point out at sea. So that sat next. We're going to set next. And how do we access c by a, the saying that B, that get next. So what is, what should we should write here is speed or DDL GetMax, I'm sorry. Not get next. So let me repeat it. First of all, we accessed a using DDL get previous after accessing the previous. Here. After accidentally saying this a, we simply set this field to be pointing out at the node after B, and we access that using B either get next. Now we still have to set this field to be pointing out at a. So how do we do it with simply access the next element, the next node. And we should set the previous to the previous. So what we did here is we access the next element, the next node. So by using the dot get next, we got C. And what we should, what we should store it here at the previous. So we're going to set previous to be pointing out at a and what is a? A is d, D would get previous. Now, after doing this, we can simply set next of D equal to null and the previous equal to null, and simply decrementing size and deter name to return. So this is how we remove the node from the list. This a little bit complicated when it comes to setting and getting here. But if we work on it step-by-step, it will be simple. So we'll continue with replace in the next video. 21. Doubly Linked List part 5: Now let's continue with the replace method. First of all, we need to check if this node is valid. So we're going to use chat position. The position is valid. Then you can continue. First of all, we need to create an object, return an element to return, and return whatever we have at D. Then we're going to set the element at the two be equal to e. And here we have something missing in the replace method. So let's go back to our detest and fix it. When we need to replace, We need to enter a node and an element. Let's go back here and fix it. Now, we can add this element here and return whatever we have the object to return. Now, let's start with the insert method. First of all, we have the insert first. So let me create the node. We have the element here in the parameter. So all we need to do is to create ignored the and let's name it in your denote. In this case, the would be equal to the anode and the note. And it will take three parameters. Now let me go back to this picture. Suppose a need to create a new node here. This new node should point out at this node a, and a should also point out at this node that I need to create. And of course, header should point out at the newly added node. Instead of pointing out at this a naught. So let me go back here. First of all, when we need to create this node, it should point out at header. Then the element e, then point out whatever we have had a get. Next. After getting this node, we need to fix the arrows. Now. We have the arrow pointing out from here to the header. So let me fix this by simply typing head.next. Now I accessed the first node here, which is a And what do I need to do is to set previous to be equal to the new node. So by simply saying set previous. And in this case, either that or we can simply say that new V naught. Now, we also have to set the header the next. So instead of pointing out the a, it should point out at the new node. So how did that sat next and sat next to the new denote. Lastly, we need to increment the size. And of course return this new denote. This is it for the insert first. Let's continue with the insert last. Once you understand the idea is the same for last, before and after. So first of all, we need to create the node, the new denote to be equal to denote. And here, when we want to answer it at the last position, we need to set up our node pointing out at d from one that action and at the Taylor from the other direction. So we can simply access the node by simply accessing the trailer dot get previous element is e. And now let's modify the arrows. First of all, the previous. So in this case it is this node D. And when we need, when we access it, we can simply set the next to be equal to the new denote. Then we need to set the previous of the Taylor instead of being pointed out at d, it should point out at the new node. So the previous new denote. And finally, increment the size determines this new denote. Now let's continue with insert before. Here we accepting unknowns. So we should check the position of this knowledge. And then we can work. Let me go back to this example. Suppose we need to, let me take these. And suppose we need to insert node. Here is our new node. And we need to set it up between B and C. So here, C should point out at this field, and of course this field should also point out at sea. And the same thing with B. So when we create this new node, so this is the new d naught. Let me write it here. Mu. And with some new denote and minimize the front. So here we have our new denote, and this node is the node d. So here we are getting the node D And we need to insert the new node before this D. So suppose this node is C0 and we need to insert before. So first of all, we need to modify the arrows and create the new node. So let me click Create and new denote D. D, sorry. New denote will be equal to new V naught. And first of all, it should point out at the B and C. So from the first position, it should point out that d dot get previous. Then the element e, And then it should point out at D. Now, let's modify the arrows here. This node should point out at this field. So to access this node, we can simply say that e dot get previous. After getting the previous, we should set next and previous to be equal to the new, denote. The should. We should set the previous of D to be equal to new denote also. Lastly, increment the size and turn this new denote D. Now let's do the same thing with the insert after. So here, that position after that create the new denote, the new node equal to denote. And let us go back to this example. Suppose we need to modify this list by adding a new node between B and C. But we using the insert after, sorry, modifying it by using the insert after B. And this is, what we should do, is once we set up the new denote, it should point out at this node and then next one. So it should point out that the element is e and d, but get next. So now let's set the next of this node, which is in this case. And we can access it by saying d dot get next. Now, we accessed the second node and we need to set to be equal to new denote. Then the new denote, increment the size and return new node. So this is it for insert before and insert after. See you in the next video. 22. Doubly Linked List part 6: We still have the toString method, but it will be very complicated since we have insert before and insert after, Show and we need to create a StringBuilder mid to account for inserting before an element and after an animal. So to be a little bit complicated, so let us create our tribal class and work in this class name at DLL demo. And he as usual, our main method. Let's create our doubly-linked list, type integer, and naming DLL doubly-linked lists. And here let's add some values. So let's insert first and value one. Insert last. Let's insert after the first node. Insert after whatnot. It is the first. So DLL God first. And we need to store it forward. Dot insert after, before. So we want to store before the last. And now we have some errors. Let's see. We have unhandled exceptions to throw the exception class. And now let's print out, for example, let's remove an element. So to remove it, that's print. We remove, remove the element, a DLL, the one before the last element. So the previous of the last element. And in this case, let us printed. We get removed two. Now, as we can see here, first of all, we entered one than we entered five. Then after the first position, after the first node we entered for. So here we have four and then we have to. So when we need to remove the element before the last one, we're going to remove this one, and we still have 145. So let's print size DLL, but size, we get now three. As you can see, size if three, is it empty, it's not. Dlls dot is empty. You get folds. Now, if we want to print the elements in this list. So we can create a for loop starting with i equal to 0, equal to DLL dot size. But since DLL, that size is can change while removing, adding. So let's start with a variable outside listening mid size equal to the size. And in this case, the boundary will be the size. Now let's create a denote outside. So denote D equal to a to be equal to DLL. But first, and we print out the element. And before that it is on the same line. And then every time we enter this loop, we need to modify the B equal to the next two, b equal to d, that next. Now, while executing this code, something might happen. So let's put it in a try and catch block. And if an exception of any type, just throw it out from this for loop. Now, let's go ahead and run. This code will get 1425. So let me remove an element here. For example. As we did before. The LL remove yellow dot previous. Yet. So let's go ahead and run this code and see what's going to happen with the move to, and we'll end up with this list 145. Now, we can also use this method in the doubly linked list and create a toString method. But I found it easier when we use it in the main class since we are creating the list at the same time as printing it. So this is it for the doubly linked list. It is much more complicated than the singly linked list, but it is more powerful in terms of inserting and removing from whenever we want. 23. Insertion Sort: Consider you have a list of integers such as this list. And you want them to be sorted from lowest to highest. Hey, you can use salting. And there are actually multiple sorting algorithms and we'll talk about some of them. So inside by insertion sorting. Insertion sort is a simple sorting algorithm that works similar to the way you saw playing cards in your hands. The array is virtually split into a sorted and unsorted part. Values from the unsorted part are picked and placed at the current position in the sorted part. And here we can start with this example. Let's suppose we have this list, and this list will be divided into two parts, a sorted and unsorted part. So first of all, our sorted part will be the first element only. So this is our first list, and this is the second part. Now, four is already sorted since it is only one element, there is only one element in this list. And you don't have to do anything. There is no element to the left of that is greater than four, then we need to add three. So we have 43. We compare three with four. So four is greater than three. So we should swap them and we'll get 34. Now, the sorted part of the list is 34 and the unsorted part is whatever there is here. And we'll move on to the next element. We have to compare two to 44 is greater than two, then we swap them. And the same thing we compare two with 33 is greater than two also. So swap them one more time, we'll get 234. And now this is the sorted part and this is the unsorted part, and so on until reaching the last element of the list. And then we'll be done. So the general idea is to compare every element with all the elements to the left. Swap. Every time we find an element to the left greater than the element we are using. So let's go ahead and write the code. You go and create a class. And first of all, let's create our integer array, our list of integers. And for example, we have five elements in this array. Let me store them directly to 5110. So this is our array, and let's create our Method. But let's name it insertion. And to take parameter an array, let's name it at work here. So first of all, we have the for loop to pass through all the elements from 0 to listed length minus1. 0 is already sorted, so we don't have to start with 0. So we start with one. So our for loop result with one and ends a dot length minus one. Now we'll create an integer. Let's name ID key, and it will be our element in this list. So we'll be comparing a of i. So here it is three to 1012 and so on. And we sold it and an integer called game. And we'll have another integer will be j, i minus one to i minus one and go back until reaching 0. And what we're doing here is that we're starting this number, for example, that the state does case. The third line, third key in an integer. And we thought this number to an integer called key. And then we stored the position we're recovering to start, which is the position i minus one, j i minus one. So we're going to side with this position and going back until reaching 0. So we'll create a while loop. While j is greater than 0 and the key is less than a of J, we need to swap. So to saying here is that while j is less, is greater than 0. So here in this case j is equal to one. So good. And the second condition, while key, which is two, is less than a of J, in this case four. So we need to swap them. We swap. And then one more time, we check the conditions. We have j greater than or equal to 0. In this case, j is equal to 0. So that condition is valid. And two in this case, we have here two and here four, so 23, so three is greater than two. Then this also valid. We need to swap one more time. And then we finish with this for loop since j will be greater than 0. And in this case, so every time we execute this for loop, j will be decremented by one. And here we need to swap this, create an integer called tamp. And as usual, that swap them will take a of j and storage here, and ten and a of j. A of j plus one in this case. And finally, we'll take a j plus one and give it the value of w. So here we swap them. And now we said, let's go back and print out. First of all, let's print the array as it is before sorting. So print at a and some space. Then perform this method with an a. And then that's printed one more time. For let's print the light from the code and time and will get first of all, the unsalted added and then we get the sorted one, since we used the insertion method we created here. Now we can see how this changed every time. So let's print out the array to create another for loop after each change into wide, after executing the loop. And print out a J2, in this case, some space. And and then, and here we need to print an island. Before executing this loop and run the code will get this. So first of all, we have 32510. We start with i equal to one. So I equal to onRestart, t equal to a of i, j is equal to a of 12, and j is equal to 0 in this case, which is i minus1 0. Then we have a while loop that will run only one time since J is equal to 0 and then read recommended. So the condition here, it will not be valid for another execution. So we need to swap them since the two conditions are satisfied. The same thing with five. We compare five to now. Five with 25 is greater than two, then this condition is not satisfied. Will not enter the for loop with simply though and increment I by one. Now we have number one. The same thing here. We'll compare this one with every element and swap the two numbers. So for example, 15 will swap them. And then 13, we swapped them one more time. And lastly, 12 swap them. And lastly we'll have 1010 is greater than all the other elements. So it will not enter the loop, the while loop, and we'll be done with the two loops, the inner and outer loop. And we can print, print telling you look out at the new array out. So this is it for insertion sorting. We'll explore more sorting algorithms in the next videos. 24. Selection Sort : Let's move on now to another sorting algorithm is the selection. The selection sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning. Now we're considering ascending order. We also have the descending order in which we can find the maximum element and store it at the beginning. And as the insertion sort, we have two parts. The one that was already sorted and the unsorted part. And every iteration of selection sort, the minimum element from the unsorted sub-array is picked up and moved to the sorted sub-array. So let's use an example. We'll use the same list here. And let's delete this. We have this method, delete these. And we'll keep this method work here. But before, let's run this code and use this list. Now. But we're going to do in this sorting algorithm is to find the minimum every time and store it at the unsorted, the sorted part. So first of all, we will find the minimum and this list here we have one as the minimum, will take this 11 and swap it with this number. Whatever this number is, we'll swap it with one. So here we have one now. And so let me write it here. So we have 1253 and that the next step is to find the minimum and this list. So the minimum is true and we need to store it at this position. So we're okay since the minimum is two. So the next step would be the same as the first one. Sense, we don't need to change anything. Now, we will look at this list. We have 5310 and we find the minimum here. The minimum is three. We need to store it at the first element. So we need to swap three with five to the next. That is, to swap them. So we'll get 123510 and glass scheme compared these two numbers as usual, Find the minimum between them and store it at the first element in this list. And since ten is greater than five, then we don't need to do anything. And this is our final list. So now let's go ahead and write it as a code. So public static, void, selection, parameter of an array, integer. And in this case, for example, first of all, we need to store the length, the length, length to use it in the for loop. So here we have the length of this list. Beside our for loop, we can say array.length or both, the same. And now we need to find the minimum element in the unsorted part. So the unsorted part should be starting with i plus one. So every time we finish with I will compare and find the minimum and part of I plus one at the length. And here we have n minus one. Since we don't have to end at the last element, we can simply add and here. And the inner for loop would compare the two last element. So in this case, let's store the minimum as i equal to i. And now we should find the minimum and the unsorted part. So we start with i plus one and then with array, array.length or and the same Maxwell simplicity. And now we'll compare every element to find the minimum. So first of all, we considered that the minimum is at index i. The index and an integer called minimum. Firstly, I is equal to 0. So we considered that the minimum number in this list is at index 0 to go and look at index 00. So we'll find three and it's not the minimum. So we need to compare this number with all the others. And that's what we're going to do to compare a j. In this case, j is the list from i plus one from here to the end. So if i of j is less than array of men, then we need to swap the index and men, it will be actually the other annex. So what we're saying here is men would be equal to, and let's work with this example to understand it better. So first of all, we start with i equal to 0, i equal to 0. We store in minimum 0. Now we are looking at this number and j will be equal to 0 plus one is one who sat with one with 1234 and with four. We'll compare array of one. If any of one is less than array of men and men, remember, many xn equal to 0 and J, in this case it's equal to one, will go and compare T2, which is any off one with three, just at a minimum of 0. F two is less than three, then minimum now is not this one anymore. It's not at index 0 anymore. It is at index j, in this case at index one. So we'll give minimum and nu value of one. And the same thing as before. Now, J is equal to two. Would compare J, I, J and K of two. We have I2 here, five with any of the new minimum, which is one. So you should compare now, is five with 25 is greater than two, then nothing will happen. Then we go to here, we compared array of three, which is one with L2. So one is lower than T2. So we need to give the minimum a new value, the value of one. And finally, we have here at which index, the minimum value as after finding the minimum using this for loop, we need to swap this minimum with the element at the sorted list where we should solve them. So what you should do is as usual, we'll take, at a minimum, can store it in an integer called damped than. We change whatever there is minimum with our eye. And lastly, give this i index ID array at index i, the value of dam. So here we swap them and let's go back and use this method here. So selection and the arrays, array. And the same thing. We'll print them and we'll get 123510. So I think that selection sort is easier than the insertion. So in terms of understanding, it is basically just finding the minimum in the inner for loop and then swapping it with the first element here. But here. And this is it for selection, so it see you in the next video. 25. Bubble Sort : The third sorting algorithm we are going to talk about is bubblesort. Bubblesort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in groundwater. So consider this list of five elements. First of all, we compare the first two elements and swap them since five is greater than one. And then we do the same thing for number 235 is greater than four, then we should swap. So this is the nest now. And the same thing for element number. 345 is greater than two, she should swap. And lastly we have 58. And since they are in the correct order, eight is greater than five, then we don't swap. Now, we can see that this list is not sorted yet, since we have 1424 is greater than two. So what you should do is repeat the same steps over and over again until we reach the sorted list. The worst-case scenario, if we have the here an element, for example, that say 0. So this 0 should be swapped 12345 times. We have six elements in this list. And the worst case scenario is to swap this 05 times. So if we have a list of n elements, we should swap n minus one times. So we can perform this operation n minus one times, and eventually you will get this sorted list. So let's go ahead and write this code to create another method. Or it bubble with a parameter name ID array as usual and would work here. So first of all, we have a for loop. As we said, from 0 to n minus one, we can say array.length. And inside this for loop we have another for loop to swap every two elements. If the wrong code for we compare every two adjacent elements, a of j is a of j is greater than a of j plus one. Then we'll just swap them. Let's create an integer tamp. Now here, RAM spring, and the same thing here. And if we consider that temp equal to array dot j a j, whatever there is at j plus one. And then if j plus1, the value salt, and this is our method and I'm sorry, we will have n minus one and n minus one. Let's use this bubble and use it here, and print the last one more time. And we'll get 325110. This is before eating and after salting 123510. Now, our code can be improved by doing a simple task. So for example, here, we swapped out the elements here. First time. And then the second time, we only needed to swap 42. And this list is sorted now. But in our example, we're obliged to pass through all the list and minus1 times. So one thing we can improve is f. And we got to a point where our inner for loop do not perform any task, then we can equate because we have no elements to swap. So we can do this task using a Boolean. So let's name it swat. First of all, it is, should be and not give it the value here will give it the value inside our outer for loop. Swap two will be first the equal to false in this case. And if, if we only threw up at least one time, then after going out from this inner loop will check swap. If swapped equal to false. Then we did not perform any swapping here. So we can exit the for loop since our list is sorted now. So we can break. Otherwise will continuous swapping. And we run the code, we get the same result as before. But now it is much simpler and it will not take as much time as before. So this is it for bubblesort, the simplest sorting algorithm between all of them. And see you in the next video. 26. Merge Sort: Moving on to another sorting algorithm, merge sort. Merge sort is a divide and conquer algorithm. So let me go ahead and create a new class. Subclass, created insertion name it merged. And he will discuss merge sort. First of all, let's consider a small list of four elements and then discuss a bigger list. For, for example, let's consider a list with four elements, 2431. So what we're going to do is to divide this list into two list. The first one we'll have 24, will contain two elements, and the second one will have the last two elements, 31. Then we will sort each list alone. So 24 are already sorted, so we don't need to do anything, just type them. And here we have 31, we need to swap them. So this is our second sorted lists. And then after that we need to merge them. Since they are sorted. So the first element should be the smallest. So we'll compare the first element in the two lists. Here we have 21. So one is exploited and would write one. And then we'll compare two with 32 is smaller than two, and then three with four. Same thing, pride. And then still have the last element in the first list, just four, and then we're done. Now, let's use a bigger list. We have in this list seven elements. We divide this lesson to Troilus. And first list will be four elements and the second three elements. Then we do the same thing with this list divided to two lists, two, and to the same thing with the other one too. And we still have only one element, so we'll divide it to one and we'll do the same thing. And this list, we have two elements, would divide it to one element and every list. And then we'll have 1234567 list. Each list contains only one element. After that, we need to merge them. We start with the two elements here. We have twenty seven and thirty eight. Twenty seven is smaller than you'd write 2738. Same thing here, 343982. And then after that, we need to merge the two lists here, as we did in the previous example. So first of all, we have three, then we have twenty seven, thirty eight, forty three. The same thing here. And we finally have our finite list final salted. The idea of merge sort is quite simple. It requires to call the method would more than 1s, two until we reach. List of one element, then recreating sorted lists as shown here. Let's go ahead and write it now. So to complete the Merge Sort, need to write two methods. The first method could be thought, the main function that sorts the array using another method. So let's write it. Public void. Let's name it public static, void. And it will accept an integer and no index and high index. They represent where should we start? And then if low is less than the hard, then we can continue. Otherwise, we don't need to do anything. It means that low is greater or equal to high. In this case, we only have one element in the list and we don't need to cite it. So we're working on if low is less than high. So what we should do here is to the middle index equal to low divided by two. And then what we'll do is to sort and divide the list into two lists. And then, so the left part alone and then so the Right but so can do that will enter our At a, we have with low and then sort the right but at a middle plus one. And after that, we need to merge the sorted halves. So we'll call a method limit merge. And it will take as a parameters left, low and high. And let's go ahead and create our merge method. So we have here can make it private, private, static, void, merged and as usual method. And now we need to find the sizes of the two subarrays and to be merged. So the first type is limit n one equal to minus one. And the second one is N2 equal to hi minus. Now we have the two sizes. New lists. So we name it list one. Or we can emit left and right. So we have left, the size and right. This second side. After that, you need to copy the data from this original array to our two arrays. Now, to do that, we simply use a for loop with the boundary of un1 and copy all the data from right to left. So left i equal to i. And another for loop to copy the data of the right part of the array to our list called right. In this case, we'll start with an array of middle plus one and plus j. And now we copied the data here. Plus, I am sorry. And this is how we copy our data. Now, we need to merge them together. So what you should do is to create a while loop to copy all the data we stored and left and right copied back to our original update. So as we said in this example, after going to this phase, we need to store them back in the original list. So here we'll compare the two elements and then we'll start them and the original array and the same thing here. We compare these elements together and we'll get our sorted list. So let's go back to our code and write a while loop. And the condition of this while loop that we still have elements in both left and right. So here let's create integers i equal to 0, and the same thing for J, 0. And let's create an integer and name to name it, which is equal to o. Now, while i is less than n, one, which is the size of left and J is less than. And two will be working on this loop. Now first of all, we'll compare left with right of j, of i is less than j, then we store it. This component and the original list. So a would be equal to left. And then we increment i. Since we're done with this, for example, let's go back here. What we have done in this case is we compared left of i here, 27 with three. F, 27 is less than three. We should store it here. Now, in this case, 27 is greater than three, then we should store three in this case. So otherwise, we should store it. And at any k derived component and increment j by one. And in both cases, we should implement k Since it will be filled either way. Now, after finishing this while loop, we might have some elements left in any list. So to fill in the original one, we should complete whatever there is left in our two lists. So we create a while loop. While i is less than N1. The N1 if i is equal to N1. And we broke out of this while loop because of i equal to one, then this while loop will not work since it would be already equal line one. So if this is the case, we should only buy whatever there is in the left part and increment, increment k. And the same thing with n2 if j is less than and to do the same exact thing, to write increment j and k. So now we're done with our merge function. And let's go ahead and use it and our main method. So lets go back. But before let's check our boundaries. Here we have left and right and go. Here. We should start with a node. Since we are not sat with zeros, sat with whatever our index here is. And now let's go back and documented here. Our main method. This creates a delay equal to, in this case, four to 718 and use it now, use the sort with a 0 length minus one. And then use a for loop to print out our elements. And discord 12478. So this is it for merge. So it See you next video. 27. Quick Sort: Like merge sort, quicksort is a divide and conquer algorithm. It takes an element as Pivot and partitions the array around the pivot. There are many different versions of quicksort that big pivot and different ways. We can pick the pivot as the first element. First element, random element, or the media. I'd ask explained what pivot is in a moment. First, let's write a list. So consider we have a list contains 101819. And so this is our list. Now we choose element as a pivot. So let's go ahead and choose, for example, the last element and separate them to understand it. And it's going to have to the same thing here. So here we have this list and this is our pivot. So right down here. And here we have the first element. Now we need two arrows, 2.2 to two positions at this list. The first, we start with the first element from the left and the last element before the pivot. So here we have our first, lets say this is the first element and this is the last. Now, what will do is to compare the first element if it is greater than the pivot, than we need to swap it, we need to end up with a part that is lower than the pivot and the other part should be greater than the pivot. So to do that, first, ten is greater than the pivot. Now, then will move, will move to 80. Here we have 80. So now we're at 8050. So 80 is ready to be swapped. Now we'll look at 5050. Is 50 greater than the pivot? No, then we can swap it. So now we swap 50 with 80. Here will have 80, and here we have 15. Now we change the positions of these arrows. We have this arrow at 42nd 30. Now, the same thing will do the same thing here. We have 13, is 30 lower than the pivot? Yes. Then we don't need to swap. It will go to another go to 90. And now we'll compare 90 with 40. 90 greater than the pivot? Yes. Then we need to swap it. Is 40 lower than the pivot? Yes. Then we need to swap these two elements, will have 90 here. And the, now the two arrows, let's name them to be able to see what will happen. We have low and high. Now before swapping, these were the positions and low and high flow at position 0123 and high position for. Now, after swapping the two elements, we need to increment by one and decrement high by one. So I will be at position, at this position and low will be at this position. And whenever low is equal or higher than high, we can know that we're done here since low has passed high. Now, the last thing we should do is to swap this element with the pivot. So you will have 17 And at the pivot 90. Now we can see that all the elements here smaller than 70, and all the elements here are great and 70. So this is the idea of the QuickSort. We can perform this same exact algorithm to this list. We can choose 40 as the pivot and work accordingly. And the same thing goes here. And we let recursion do the work for us. This is the general idea and we'll use the recursion to be able to implement it more than once. Now has emerged. So we have two methods here. First method will be private, integer. Let's rename it partition. It will take the parameters and emit and low. And this method will take the last element as the pivot. The pivot element at its correct position in the sorted array. And cases all smaller, smaller elements than the pivot to the left and greater to the right. So let's go ahead and start with this method. First of all, we have our pivot is created. Now the vector is equal to the last element in this list. And we have the index of smaller element. It is a sname i, which is equal to minus1. And this case, we start with our for loop. We start by low. All the way to. Now, we need to check if the current element is smaller than the pivot. So if j is less in this case, and we need to increment i. One, swap and array j. So let's swap it. And equal to edit a. He then equal to, sorry, a equals i, equal to j. And finally, back to G. So now we swapped the two elements. After finishing with this word loop, we need to swap the pivot with at a i plus one. So in this case, create another time and swap the two elements. As we said. Here, we have the pivot is at location a. And then giving the tan two. Now we swapped the two metadata to elements and then we will simply return plus one. So this is our method, the partition method. This method took the last element as Pivot, place the pivot element at its correct position in the sorted at a, and places all smaller to the left and greater to derived. Now, the other method is the main function that implements that quicksort. And let's name it public static, void. So that it would take three parameters as usual, and low and high. First of all, we'll check if flow is not greater than high. We can work otherwise will not work because it will not make sense. And we'll have, we'll create an integer, let us name it by, by partitioning and depth. That will, where we'll use this method we created here. So pi would use partition at the low. Now, after getting the index, but now we should sort the two, abase the left part, Right? But so we'll use the same method one more time with no other way to Pi minus one. And the same thing by plus one other way to write. And then we're done with this method. You can use it. And our main method. So we create an array, for example, steam it, and with some values 426173. And we'll call the sort method 0. And at length minus1, then create a for loop and print out the elements of this list. So as usual, with some space here, and let's go ahead and run. The code will get 1234567. So this is the array is sorted array after performing this QuickSort. So this is it for Quicksort. See you in the next video. 28. Jump Search: Like binary search, jumps Search is a searching algorithm for sorting arrays. The basic idea is to check fewer elements than the linear search by jumping ahead by fixed tabs or skipping some elements instead of searching all the elements in the list. So for example, consider we have this list. We have 16 elements here. Let's suppose that we're searching for number 55. So the jump search will find the value of 55 using some steps. First, let's consider that the block size to be jumped as for since 16, square root of 164. So first of all, it will jump from index 0 to index four. So it will jump to 01234. Jump to this element compared to 5535 is still greater than three. Then we'll jump one more time to any one. Same thing here, 21 is less than 55, then we need to jump, will jump to 144. And then we can see that 144 is greater than 55. So we'll go back to 21 and perform a linear search from 21244 until we find our element to number 55. We usually use the square root of length as the block size to be jumped. Because in the worst case scenario, this is the best step size to take. So let's start with our code. Jump. The main ij's of integer and x that we are going to search in this list. And here, first of all, we need to store the length of the day. We need to choose our stack. And as we said, we'll take the square root of n using the mass. And this mass square root. For example, suppose we have 17 elements, give US 14 and so as a number. So after taking the square root of and formatted using Math.floor. And then since we assign an integer to converges to n, and if the element exists, then we need to find the block where the element is present. So let's go back to our example. And he 55 is between 2144. So we need to find these two elements. And we already have an integers, have recreate an another entity or let's call it, for example, previous liquid to 0. So at the beginning, previous is equal to 0, so it is at position 0 and step is at position four. And if the element is not found in this interval, then we should give previous the value of four. So previous is now at position four and we need to add four to the step. So step would be at position eight and continue until we find a work element and this interpret and our interval. So to do that, we need to create a while loop and set the wild loop as at a is less than x. Now, we might get to a point where if we keep adding four, the step, we might have step greater than n, then we cannot access at a half-step. So instead of accessing array of step that says a radar minimum between step and, and. So every time we execute this loop, we need to change previous to the new value. And the same for step three to add. Whatever we have here. So it added and then we'll get previous is greater than or equal to. And then we're finished. We didn't find the animal who simply turned minus1. And he we should change to integer. Now. So what we're saying here in this while loop, let's use it at this example. First of all, we have previous equal to 0 and step four position for now, we go through this while loop. First of all, we'll check array of minimum between step and then step is surely less than n. In this case, step is equal to four. So math at a of four, which is three. In this case, we'll check if three is less than x. Yes, then we'll continue executing this while loop will change the values. Now, reverse is equal to four and step is equal to eight. And then we'll check if we pass the boundaries. If previous is greater than or equal to n, Then we passed the boundaries and we done, we didn't find any number that matches acts. So now we're at position four. And position eight. The same thing. We compare this 21 with 5521 is less than 55 and we need to execute the while loop one more time previous is now at position eight. So this is position for, this is position aid. And step is at position 12. In this case, we have 144. So compared one hundred forty four, fifty five and fifty five years less than a 144, then will exit the loop. Having previous the value of eight and step the value of 12, then we have our interval and 55 is in this interval. Now, after exiting the while loop, we need to perform a linear search for x and a y and another while loop. So while array of result with the previous. Now since the previous is at position eight and step is at position a hundred and forty four and fifty five, which showed that receiver is in dissent first interval, then we'll start with 21 and continue. So wide carry at previous is less than x, then we'll increment by one. And if we got to a point where previous is equal to either step, equal to 12 over n, So equal to minimum between the two integers, either stamp. And then we need to break or return minus1 can simply return minus one. In this case, since we didn't find our number. And then we check if we found the element. So if array previous is equal to x, then we return this position and return minus one. If we die, we didn't find it. So this is a t we have added cannot converge from n Boolean, we have a missing. So this is it, this is our function. And let's go ahead and choose it here. So we'll print out chunk and we'll search for 55. So let's take this and put them in our, this is our array and it will return ten. So 55 is at position ten. So these first two lines were from the past functions now this hour than our position where 55 is at this list. So this is it for jumps. See you in the next video. 29. Interpolation Search: And other searching algorithm as interpolation search. Interpolation search works better than binary search. Because binary search always check on a middle element basis. But interpretation search may go to different locations according to the value of P to be searched. So for example, if we want to search for the number three and this list, if we use binary search, will go and check in the middle. So either 1321034, so this is the middle of the list. However, if we use interpolation search will go to the value that is closer to our number using a specific formula and we'll talk about it later. So he three is closer to 0 than it is closer to 610. So our formula will lead us to a number between these. So the same idea as binary search, but instead of having a middle element, we will having a position that will change according to our elements. So let's go ahead and create our method public. And let's name it interpolation. And as usually to take an array of elements and the size of the element, as well as the IV or let's say x. Now, we need to set our low and high and low equal to be 0 and will be and minus1 y loop. So while low is less than or equal to i, otherwise we don't need to work anymore because we didn't find our element. So it's the same as we did in binary search. And we need to add some conditions. While our element x is less than or equal to, our low is greater than or equal, I'm sorry, and is less than or equal to our element. So as long as these conditions are satisfied, we can work here. Now, whenever we get to a point where our low is equal to our high index, then this means that we have done so either we find the element or not. So we'll check if I know the same since they are equal, is equal to our x. And this is the case return low, otherwise, return minus1. And after checking this condition, now we can work, can create our formula that same position that will jump. As we did in our binary search, we created a position called metal element. Every time we go to the middle element now, we create another integer called position. And the formula is as follows. This is how we compute the interpolation. And a of high minus low. Then we multiply it with I would x minus a of load. And now we check if a ray at this position is equal to our element, then we just return our position. Otherwise, we'll check that a at this position is less than our element. Then we need to change our low from low to high position plus one. The same thing as we did and in binary search, but instead of position and we used method otherwise will be position minus one. So otherwise, if the we have at a position is greater than x, then du would be equal to position minus1. And after finishing this condition and everything, the while loop, we can return minus one if we don't find the integer. And now let's go back and use it here. So I print out interpolation. We have the a and B and x will be the number. So for example, let's suppose for a search for b. And let's go ahead and run our code. Will get for SO three is at position 401234. Let's change this number to 89 and we'll get position 11. So 89 is at position 11. And the last thing we come to check if we enter a number that's not in this lesson, 900, we get minus one. So this is it for interpolation search. See you in the next video. 30. Exponential Search: The last searching algorithm we're going to talk about is exponential search. Exponential search involves two steps. First, we need to find the range where the element is present. And then we'll do binary search in the strange. So let's consider this lesson. We have 16 elements and we need to find, for example, 89. So what we're going to do is, first of all, consider if our number is equal to the first element in this list. If this is the case, then we return 0, so it is at position 0. Otherwise, we check all the other elements. We start with i equal to one and with doublet I equal to two, then i equal 24816 and so on. And let's go ahead and implemented to better understand this. Go here and you have public static, and let's name it exponential. As usual, take an array of integers and, and, and the value that we're going to search, we'll name it x here. First of all, as we said, we need to check if at index 0, if the value is at index 0, then we simply return 0. Otherwise, we need to find the range for the binary search by repeated doubling. So we will define an integer with the value of one, and we enter the loop. While i is less than n, the length of the day. And at a, at i is less than our, less than or equal to our number. This loop will be executed. So we'll simply multiply i by two. So every time we enter this loop, we multiply i by two. So let's see here in this example, when we can exit this loop. For example, if we want to search for the number 13, first of all, we check if 0 is equal to 13. No, it's not. Then we define i equal to one and enter this loop. I is equal to one, will check. While I at a, at i is less than or equal to x, one is less than or equal to 13. Yes, then we multiply i by. So now we have I equal to two, and we'll go to our next element. Here we have also one, it's less than 13 and i is less than n. Then we multiply i by 21 more time. Now we have two times 24201234. Now we're here. We check the is less than 13. So we can multiply one more time to four times 28. So now we're 5678, we're at 21. Now. We'll check 21 is less than 13. No, it's not. Then. We exit the loop with i equal to eight. Now we have I equal to eight. And to get our interval, we have i equal to eight and i equal to four, which is eight divided by two. So after finding our interval here, we simply use binary search. And I work at a. And here we have i divided by two. This is our interval and minimum between i and one, i and n. Since it might be, it might be that i is greater than n and we cannot work outside our boundaries. And here we have our integer x. And since we need to return the type, so we simply turn binary search. And then we're done. Let's go ahead and use it here. So we'll go ahead and print out exponential at array.length and w. We're going to search for example, 13. And the code will get seven. So 13 is at position seven. So let's make it better, nicer. And exponential. Let's store it as exponential. And an integer result is equal to this exponential. If the result is greater than 0, then we print out the element is present at index. And we print out the index. Otherwise, we print out that element is not present. And Ray and clustering the code will get element is present and index seven. Now we have a shortcut in Java that you can use. So instead of writing all of these, we can simply print out one of the two lines. So we need to set here the condition if result is less than 0, this is the case. We can print out. Element is not present. And the other statement would be element is present, index. And we print out the index. So let's go ahead and see what would have been here. Let's run the code and we get element is present and index seven. So this shortcut, First of all, NDA System.out.print method. We set the condition your result is less than 0. Then automatically this method will print the first statement. Otherwise, it will print whatever there is after the two points here. So we asked them if there is asked is less than 0, yes, print this. Otherwise. Print this. This is very helpful if we don't want to complicate things and we need a very simple form of printing. So this is for searching algorithms. See you in the next video. 31. Project: Let's finally move on to the project is very easy and straightforward one, and this project will have two stacks and stack one and start to. Here you need to push some strengths to this tags. So for example, I pushed you are how had the low to get Hello had the, how're you. Now what you need to do is to create this method that is called merge. To merge stack one and start to new step and then store it in a new stack here outside in the main method. Then of course printed out I used and Java stack. But of course you can use the stack that we built ourselves before. You can also use any type of data here instead of strength. But I chose things to just see how it would look like when I print the message or the words. And of course, this is how your method should look like. It should. 32. Recap: Thank you and congrats on punching discourse. Here is a quick recap of what we have done. First of all, we talked about stack. We used arrays and singly-linked lists to implement these tags. Then we move to cues and singly and doubly-linked list. And of course, finally, we talked about sorting and searching algorithms. We've done so many of them, such as quick and bubblesort and linear and binary search. And we still have the non-linear data structure. And hopefully we'll cover them later in the next classes. So thank you for attending and see you in the next class.