Learn Data Structures and Algorithms for free 📈

Hey y'all what's going on everybody it's you bro hope you're doing well and in this video we're going to discuss data structures and algorithms so sit back relax and enjoy the show if you wouldn't mind please like comment and subscribe one like equals one prayer for the youtube algorithm here's a few of the topics that we're going to cover in the series first we will learn about basic data structures followed by big o Notation then searching algorithms sorting algorithms graphs and trees be sure to look for the timestamps in this video's description well what's a

data structure simply put a data structure is a named location that can be used to store and organize data here's a real life example think of a family tree it's a hierarchy of family relationships we need some way to organize all of this data a tree is a data structure what about arrays we have A little bit of experience with those an array is a collection of elements stored at contiguous memory locations that's another example of a data structure it's basically a named location that can be used to store and organize data different data structures

store and organize data in different ways each of them has their own pros and cons well what's an algorithm an algorithm is a collection of steps to solve a problem it's the steps to a solution here's an Example i'm hungry and i need a pizza that's my problem an algorithm to bake a pizza could be one heat the oven two knead the dough three add the toppings and then eventually you'll solve your problem of not being hungry anymore so that's a real life example of an algorithm one algorithm that you're probably familiar with is a

linear search suppose we have an array of elements and i need to find a value using a linear search we would one by One examine the elements of an array to find a value a linear search is an example of a searching algorithm i know what you're probably thinking why do i need to learn data structures and algorithms what's the point well let me tell you you'll write code that is both time and memory efficient and two commonly asked questions involve data structures and algorithms and coding job interviews do you know how to reverse a

doubly linked list no no you don't do You so you should probably watch this series so without further ado ladies and gentlemen let's begin hey what's going on everybody it's you bro hope you're doing well in this video i'm going to explain the stack data structure so sit back relax and enjoy the show all right everybody stacks a stack is a lifo data structure lifo is an acronym for last in first out this allows us to store objects into a sort of vertical Tower like a stack of books or a stack of cds we use

the push method to add objects to the top of the stack and the pop method to remove objects from the top so here's a real-life example of us creating a stack data structure after declaring our stack we can add objects to our stack the objects that we'll be adding are various video games to add an object to our stack we use the push method like we're pushing something onto our stack so let's push minecraft onto The bottom of our stack and then next we'll add skyrim then maybe some doom then borderlands and then final fantasy

vii so this is a lifo data structure last in first out to access objects on the bottom of our stack we first need to pop or remove objects from the top of our stack if i need to access minecraft on the bottom i don't want to pull this from the bottom because everything on the top is going to fall right so that's kind of the concept so in order to Access minecraft on the bottom i need to pop or remove objects from the top in order to access objects on the bottom so in order to

access minecraft i need to remove all the games on the top of my stack so that's kind of the point of a stack data structure now let's create a stack the language you use really doesn't matter for the most part you can implement a stack in java python c plus plus c is sharp the language really doesn't matter however The syntax might be slightly different i just so happen to be using java so i'll stick with that now to push objects onto our stack we first need to declare our stack and instantiate it so let's

do that stack then we will list the data type of the objects that we will be adding to our stack luckily strings are a type of object and they're fairly simple so we will create a stack that can store strings the names of video games and i will name the stack step to Keep it simple stack stack equals new stack and i will list the data type and then add a constructor okay so we now have a stack data structure now with stacks they have five unique methods let's take a look now with stacks we

can push an item onto the top of our stack we can pop an item from the top of the stack we can peek at the item at the top of the stack we can check to see if our stack is empty and we can search our stack for an item So those are five unique methods available to stacks let's first check to see if our stack is empty so let's use system.out.printline stack dot empty method and currently our stack is empty that is true but that'll change soon so let's push some games onto the top

of our stack so we type the name of our stack stack and use the push method then pass in our object so we will pass in a string the name of a video game let's Add minecraft first then let's add skyrim then doom you can pick your own games if you want i don't care then borderlands and then final fantasy vii ffv iii okay let's check to see if our stack is empty now so let's move this line of code to the bottom and run it So our stack is no longer empty this returns false

so with the stack we can at least take a look at the items within the stack without removing them so let's use system.out.printline and i will print my stack so this will print all of the objects within my stack beginning with minecraft then skyrim doom borderlands and final fantasy vii however by printing our stack we're not removing items from the Stack so that's completely fine so this time let's pop the topmost item from our stack by using the pop method stack dot pop and we don't need to list an object because pop will always remove

the top most object from our stack so now final fantasy will be missing from the top of our stack so if i was to repeat this again well then this will remove borderlands and then doom Then skyrim and then lastly minecraft then if you pop again this is what happens an exception empty stack exception so that's something to keep in mind now when you pop the topmost object from a stack this will actually return that object if you need the object from the top of the stack you can pop it and then assign it to

something so let's say string My fav game equals stack dot pop and then i will print my fave game and this will print final fantasy 7 and it should be missing from the top of my stack if i was to print my stack so final fantasy vii is no longer in my stack because i popped it then assigned it to the string variable of my favorite game so in order to take the top most object from a stack you use pop and then assign it to something if you ever need To take a look at

what the top most object is within your stack you do not want to use pop because that will remove it you can instead use the peak method of stacks so what i'll do is system.out.printline stack.peak and then immediately follow this with printing my stack so let's run this so the topmost item within my stack after using the peak method is final fantasy 7 then after printing my stack final fantasy 7 is still at the top of My stack so if you ever need to take a look at the object that is at the top of

the stack without removing it you can simply use the peak method if you need to search for an object within the stack you can use the search method let's print stack dot search and we pass in our object as an argument so the very first item in a stack will have a position of one you would think it's zero but it's actually one now let's find borderlands that will be in Position two from the top then doom would be of course three skyrim is four then minecraft is five so if you search for an item

that is not within the stack like fallout 76 well then this will return negative one if search does not find this object within your stack it will return negative one so with stacks we can actually run out of memory so let's add like a billion copies of fallout 76 we find bethesda's warehouse of unsold Fallout 76 games so we'll create a stack of a billion copies of fallout 76 we can do this using a for loop didn't i equals zero as long as i is less than like 1 billion that's probably close enough increment i

then we will push a copy of fallout 76 to our stack so stack dot push fallout 76 and this is what happens a few moments later so we will run into An out of memory error due to the java heap space so it is possible to run out of memory when adding objects to our stack now this is an interesting feature that may or may not happen to you if you add a billion copies of skyrim onto a stack [Music] [Music] damn it todd howard you did it again now what are some uses of stacks

here's a few examples one we can use them in Undo redo features in text editors like when we go to edit then undo typing or redo typing we can move back or forward through browser history by hitting the back or forward button in the top left corner of most web browsers we can implement them in back tracking algorithms if we need to navigate a maze or search through file directories and another is that we use them when calling functions whenever we call a function we add what is known as a frame to the call Stack

but i'll probably save this topic for another video so in conclusion everybody a stack is a lifo data structure last in first out it stores objects into a sort of vertical tower a stack of objects you use the push method to add objects to the top and the pop method to remove objects from the top so those are stacked data structures in the next video we'll be covering cues which work a little bit different so if you can give this video a thumbs up and drop A random comment down below but yeah that is a

stack data structure and well computer science what's going on everybody it's bro hope you're doing well in this video i'm going to explain cues in computer science so sit back relax and enjoy the show if you find this video helpful please remember to like comment and subscribe your support will help keep this channel running whoa hey we're talking about Cues today so cues are a fifo data structure not to be confused with fifa fifo as in first in first out an example would be a line of people it's first come first serve whoever's there first

gets helped first so this is a collection designed for holding elements prior to processing it's a linear data structure here's an example imagine that we're a cashier and we're selling tickets to a concert we will help whoever approaches our register first It's first come first serve in other words it's fifo first in first out unfortunately a wild karen appears and she would like to talk to the manager now karen is going to waste everybody's time so it's going to be a while in the meantime chad enters the line he will enter in at the back

and wait his turn followed by steve and then harold so karen is at the head of our queue our line and harold is all the way at the back our tail as you can see harold is Very anxious right now once karen has been defeated chad will move to the head of our queue so chad will now be helped next and harold will still be at the tail until somebody else enters the line once chad has been helped he will move out of our queue and steve is at the head now and the tail will

move as well and then once steve has been held harold is the only one currently waiting in line for his tickets he will be at Both the head and the tail of our queue so that's kind of how a queue works it's first come first serve fifo first in first out if you were here first then you will be helped first now the concepts of adding and removing objects from a queue are known as both enqueuing and dequeuing enqueuing is the concept of adding an object to the end of our cue our tail and dequeueing

is when we remove an object from the head of our queue now what methods do you need to Enqueue and dequeue from a queue well it really depends on the programming language that you're working with a lot of you voted for data structures and algorithms using java so i'll probably stick with java then here's an example now to enqueue and dq we need well a queue so let's create one q then we need to list the data type of the objects that we're going to add to this queue Let's work with strings because strings are

objects and they're fairly simple and i will name this queue q equals new now check this out i will attempt to create a queue object and instantiate it and the data type is string and i will add a constructor now we cannot instantiate the type q here's the reason why so if we take a look at the queue class right here q is actually an interface and not a class and based on our lesson On interfaces we cannot create an instance of an interface an interface is meant to be more of like a template that

we can apply to another class so to utilize q technology we need a class that implements q now taking a look at our java collections hierarchy there are two classes that implement cues one of which is the linked list and the other is the priority queue now priority queues they will rearrange their elements based on a certain priority so They wouldn't be a good example so to utilize the features of a queue we are going to create a linked list because we cannot instantiate a queue itself because it's an interface with that being said let's

change equals new queue to equals new linked list we won't be focusing on any of the features of linked lists we'll save that for another video maybe the next one i haven't decided yet so we will only cover the features that linked lists Will utilize via the q interface now with the q interface there are three methods that we inherit from the collection's parent class add remove and element these will do approximately the same thing as enqueuing dequeuing and peaking at the top most element however they throw exceptions and according to the documentation it's actually

better to use this column of methods instead these will return a special value we have offer which will enqueue or add an Element to the tail of our queue poll will dequeue it will remove the head of our current queue and then there is also peak it will not remove the head but it will examine it and return it so those are the three dedicated methods that we implement via the queue interface there are some additional methods too which we'll cover later which we inherit from the collections class so let's begin by offering a bunch

of people to our queue this is how we enqueue or add elements To our queue so first in our line we have karen so to add her to the queue we would type the name of our queue q dot offer and we will offer karen to the front of our queue and she would like to complain to the manager next we have chad q dot offer chad then we have steve and lastly harold Okay now if we were to display our cue we'll place it within a print line statement we will pass in q as

an argument and this should display our queue in order first we have karen at the head then chad steve then harold at the tail one method that we implement from the q interface is the peak method we can use the peak method to examine and take a look at the object at the head of our cue we're not actually going to remove The object at the head of the cube but take a look at it so within a print line statement i will use q dot peak method and after peaking over our cash register unfortunately

karen is at the front of the line now to dq we can use the pull method so type q dot poll and this will dq your q So karen is no longer at the head of our queue so let's pull a couple more times for practice so after pulling twice karen and chad are now gone using pull a third time will remove steve and lastly harold now the nice thing about the pull method is that it will not cause an exception according to the java documentation you can use element to peak but it will Throw

an exception so if i was to use element at the end this would cause an exception then so usually it's preferable to use this column of methods even though they're similar these will not throw exceptions offer pull and peek now with cues there are some additional methods that you might be interested in the q class will extend the collection class so the q class inherits everything that the collection class has and there's some Pretty useful methods within here i'll show you a few so the first is that we can check to see if our queue

is empty so within a print line statement i will type q dot is empty and if our queue is empty this will return true so if i move this line of code after we offer a bunch of strings a bunch of people to our queue if we check to see if our queue is empty That will be false there are people currently within our line so that is the is md method we can also check to see the size of our queue how long is our line system.out.printline q dot size and the size of our

line our q is four four objects we have four people waiting in line to be helped so that is the size method and another is the contains method we can check to see if Our queue has a certain object that we're looking for so within a print line statement i will type q dot contains and then pass in an object let's check to see if harold is at the back of the line he's been waiting here patiently q dot contains herald and according to the contains method harold is in fact within our line that is

true however this method does not give the index the position in which harold is in imagine that we yell out Hey harold are you there and he yells back yeah or true that's kind of how the contains method works so these are three useful methods that cues inherit from the collection class now where could cues be useful they're actually used in quite a number of things but here's a few examples that came to mind so one that can be used in keyboard buffers have you ever typed so fast that the computer couldn't render all the

characters onto the screen and all of Those characters were added to a buffer they were all displayed in sequence and they were waiting for their turn to be displayed so with a keyboard buffer letters should appear on the screen in the order that they're pressed right first in first out they're also used in printer cues print jobs should be completed in order so we would start with page one then page two and just follow that pattern and as we discussed before they're used in linked lists Priority queues as well as breadth first search algorithms well

everybody in conclusion a queue is a fifo data structure first in first out it's a collection designed for holding elements prior to some sort of processing it's a linear data structure imagine a bunch of people waiting in line to enqueue that means to add an element to the tail of our queue to the end we can use the offer method in java to dequeue we would use the polled method in java that will Remove the element at the head of our queue so that is the queue data structure in the comments down below let me

know what you would tell karen if she asked to speak with your manager and that ladies and gentlemen is the q data structure in the field of computer science hey yeah everybody it's you bro hope you're doing well and in this video we're going to discuss priority queues in computer science so sit back relax And enjoy the show hey y'all what's going on everybody so priority queues a priority queue is a fifo data structure first in first out however a major difference with priority queues is that before we start pulling and serving elements we put

them in some sort of order higher priority elements are served first before elements with lower priority so here's an example let's say that we have some student gpas and we'll place them all within a queue And then a priority queue and take a look at the differences so let's create a queue the data type is q and we are going to insert some doubles some gpas i'll name this queue equals new now queues are actually interfaces and we can't implement them directly so we need to use a class that utilizes the queue interface one that

i know of is a linked list then finish instantiating it Now to add data to a queue we use the offer method q dot offer and then pass in a gpa let's make sure that these are not in order uh how about a 3.0 then the next student has a let's say 2.5 then a 4.0 1.5 and 2.0 okay now let's display the elements of our queue One easy way in which we can do that is to use a while loop and this is our condition we'll continue this while not logical operator q dot is

empty method while our q is not empty pull each element and display it so within a print line statement let's use queue dot poll to display and remove each element beginning with the first One and then working our way to the end so this will display the elements within my queue so these are in first come first serve order whatever element we were offered first we are serving that element first if an element was added last well then it's served last so that's a standard queue now with a priority queue we're going to arrange them

in some sort of order before we actually pull these elements so let's change our linked list to a priority Queue and run this again and let's take a look at the differences okay these are all in order now so if we're working with numbers like doubles these are arranged in ascending order beginning with the smallest element let's pretend that these are grade point averages gpas why might we want to put these in order let's say whatever student performed the worst gets two hours of free tutoring whichever student Performed second worst gets one hour of free

tutoring and third gets half an hour free tutoring now if you need these in descending order well there's one change that we're going to make within the constructor we can pass in a comparator but that's a little advanced for us and we haven't discussed that yet so there is a default comparator that we can use found within collections collections dot reverse Order method so these elements will be in reverse order then in this example let's say that whichever student has the best gpa will receive i don't know a gold medal like the olympics and the

second best student will receive a silver medal then a bronze medal and then every student after that i guess will receive nothing but that's okay though they got some free tutoring in the last example okay now let's change the data type let's say That these are now strings and let's put these in standard order so let's change these two strings maybe this student has a b this one has a c a f and what are we missing d if we have a priority queue of strings well then these elements will be in alphabetical order so

if we need these In reverse alphabetical order again we can pass in a comparator and then one that we can use is from collections collections dot reverse order and these elements within our priority queue are now within reverse alphabetical order so yeah that's a priority queue think of it like a queue however we first sort these elements based on a certain priority we will pull and serve the elements with the highest Priorities first and work our way to elements with lower priority so yeah that's a priority queue if you would like a copy of this

code i'll post this to the comment section down below and well yeah those are priority queues in computer science hey what's going on everybody it's you bro hope you're doing well in this video we're going to discuss linked lists and computer science so sit back relax and enjoy the show Now before we dive straight into linked lists we're going to take a closer examination of arrays and array lists we will see what disadvantages that these data structures have where linked lists excel at so we'll compare and contrast the differences between the two with what we

understand with arrays and array lists these data structures store elements in contiguous memory locations in this demonstration i'm storing letters of the alphabet suppose that the First element of my array has a memory address of one two three fake street obviously these are not real memory addresses but this is how i like to think about things if this was a memory address then the next element in my array may have an address of one two five fig street then one two seven fake street one two nine fake street and then you just continue on in

that pattern now arrays are fantastic at randomly accessing elements because they have an Index but they're not so great at inserting or deleting elements especially when those elements are closer to the beginning of the array here's an example suppose i need to insert a new element at index three since this element is already occupied with a value i would need to shift my elements to the right in order to accommodate room for this new element so the process of shifting is cumbersome but once this element is empty then i Can insert a new value so

it's not that big of a deal if i have a small data set but imagine if i had one million elements i would need to shift my data up to that many times depending on the location of the insertion and the same concept applies with deletion as well we would shift our elements to the left to close the gap you're probably thinking dude why are you talking about arrays in a video about linked lists well where arrays Have difficulty inserting and deleting linked lists actually have the advantage here is a representation of a linked list

a linked list is made up of a long chain of nodes each node contains two parts some data that we need to store and an address to the next node in line also referred to as a pointer linked lists do not have an index the same way that arrays do but each node contains an address to where the next node is located so these nodes are Non-contiguous they can really be anywhere within your computer's memory if our initial node has a memory address of one two three fake street like our array example then the next

node in our linked list could have a memory address of maybe 101 help boulevard and another could be 404 nowhere lane then 666 crime circle each node knows where the next node resides i imagine this as if we're following a scavenger hunt or a series of clues to find the end of the linked List the tale each node has an address a clue as to where the next note is we begin at the head and work our way towards the tail following each clue each memory address found in each node then we know when we

reach the end of our linked list when we check that address our pointer and it has a value of null that means we're at the tail we're at the end of our linked list inserting a node is easy in a linked list there's no shifting of elements Involved wherever we need to place a new node we take the address stored in the previous node and assign the address of our new node with the address from the previous node so that our new node is pointing to the next node in line then we can take and

replace the address in the previous node with an address that points to our new node it's as simple as that and we're completing our chain simply by inserting a node at a given location there's only a few steps Involved no shifting of elements required deleting nodes are easy too wherever we need to delete a node we have the previous node point instead to the next node in line again no shifting of elements is necessary now this is where linked lists tend to be inferior to arrays they are bad at searching we can randomly access an

element of an array because we have an index with a linked list that is not the case to locate an element we need to begin at The head and work our way towards the tail until we find the element that we are looking for this itself takes time in fact it would take linear time but making the insertion or deletion of a node is constant this variation of a linked list is a singly linked list there are single links to each node however there's another variation called a doubly linked list a doubly linked list requires

even more memory to store two addresses in each node not just one Which is the case with a singly linked list one address for the next node and another for the previous node in our chain the benefit of a doubly linked list is that we can traverse our doubly linked list from head to tail or from tail to head in reverse each node knows where the next and previous note is but the downside is that a doubly linked list uses even more memory than a singly linked list so how about we create a linked list

in real life now let's do it Alright ladies and gentlemen with all that out of the way let's create a linked list linked list list the data type of the objects we'll be storing within this linked list just strings because they're easy and i will name this linked list linked list linked list equals new linked list and list the data type again we are storing strings add a constructor boom you got yourself a linked list now if i was to take my cursor and hover over my linked list Declaration there's a note here that says

this is a doubly linked list each node knows where the previous and next nodes are now if we head to the linked list class itself there's a few things i need to mention here our linked list stores the memory location of our first and last nodes these are effectively the head and the tail of our linked list and there's also an inner class named node each node knows the memory address of the next and previous nodes within this Linked list now taking a look at our linked list class definition our linked list class implements the

dac interface and a deck is more or less a double-ended queue so with the deck interface we implement 12 additional methods so here's just a few of them so we can add to the head add to the tail remove the head remove the tail peek at the head peek at the tail some will throw exceptions some will return a special value so you can use any Combination of these really and not only do we have these 12 methods but we can treat our linked list as either a stack or a queue we can push we

can pop we can pull then we can offer so just to demonstrate let's first treat our linked list as a stack so linked lists do have a push method as well if we need to push an element onto our linked list as if it were a stack so let's push the letter a and then i will display my linked list with a print line statement System.out.printline linked list and of course we have the letter a so let's push another letter onto our stack what about b so at the bottom of our linked list we have

a and then on top we have b let's add a couple more letters let's represent a typical grading scale we have c d and f a b c d f notice that i'm intentionally leaving out e we're going to insert that later so within our linked list that's Behaving as a stack we have f on top then d c b and a so we also have access to a pop method as well linked list dot pop and this will pop the top of my linked list so f should no longer be here it's d c

b and a so we can treat a linked list as a stack we can also treat it as a queue as well and just to save some time i'm going to copy these lines of code to add an element to a queue we do not use push we use offer so linkedlist.offer And we will keep the order so i'm not going to pop it quite yet so we have a b c d f a is at the head f is at the tail and to remove the head of our q we do not use pop

we use pole and a is no longer in here we have bcdf so you can use a linked list to mimic a stack or a queue before we move on to the next section i'm going to get rid of this pull method so we have a typical grading scale a b c d f where linked lists are really good is the insertion And deletion of nodes let's say for this example i need to add a node between d and f that contains the letter e so that's really easy to do with the linked list we

would type the name of our linked list dot add list and index like for and our object e and then to remove a node we would type the name of our linked list dot remove then list the object e so e should no longer be within my Linked list so where linked lists tend to have an advantage over arrays and array lists is the insertion and deletion of nodes however there's one catch to this with a linked list we still need to traverse the entire linked list to find where we need to go unlike with

arrays and array lists there's no random access to a linked list searching for an element is fairly straightforward too so within a print line statement i'm going to use the index of method of a Linked list index of let's look for f so that would be at index four and before we wrap things up here here's a few methods related to linked lists that you might be interested in we can peek at the head or the tail node of our linked list so within a print line statement i'm going to print linked list dot and

then use the peak first method so the first node within my linked list contains the Letter a so we can peek last as well linkedlist.peak last and the last node of my linked list contains the letter f we can add new nodes at the head or the tail of our linked list by using the add first method for the head so maybe i need to add maybe zero because i don't really know what comes before a and the alphabet so zero would be a good bet i guess or we could add to the tail by

using add Last and after f comes g and we now have g at the tail of our linked list we can remove first and remove last you can also store them within a variable two let's say string first equals linked list dot remove first then to remove the last node we could just use remove last then and let's store this within a different Variable remove last so yeah those are a few useful methods related to linked lists in conclusion everybody a linked list is a data structure that stores a series of nodes each node contains

two parts some data and an address nodes are stored in non-consecutive memory locations each node can be really anywhere within your computer's memory and elements are linked via these pointers they contain an address for where the next node is We've discussed two varieties of linked lists a singly linked list as well as a doubly linked list with a singly linked list each node is made up of two parts some data and an address to traverse a singly linked list we would begin at the head node and use the address as a sort of clue to

find where the next node is located within our computer's memory with a doubly linked list each node is made up of three parts some data and two addresses one address for the next node And another address for the previous node and it behaves the same way and to traverse a doubly linked list we could begin at the head and work our way towards the tail or we could begin at the tail and work our way towards the head depending on which way is closer to where we need to be within our linked list what are

some of the advantages of a linked list one they're a dynamic data structure they can allocate needed memory while their program is currently Running two insertion and deletion of nodes is really easy if you're familiar with big-o notation this would be in constant time there's only a few steps regardless of the size of our data set and three there is no to low memory waste what are some disadvantages one there is greater memory usage because we have to store an additional pointer each node also stores the address for where the next node is located and

even more so with a doubly linked list this will Use a lot more memory because we need two addresses for each node now two there's no random axis of elements within a linked list to find an element we need to begin at one end and work our way towards the other end and three accessing and searching of elements is more time consuming this is done in linear time this is where arrays and array lists have an advantage since they use indexing they can randomly access an element of an array or an Array list with a

linked list we have to manually traverse the entire linked list to get to a particular index since we don't have random access now what are some uses of linked lists one they could implement stacks or queues if you need a stack or queue for anything you could also use a linked list two maybe gps navigation so let's say you have a starting position and a final destination each step or stop along the way is kind of like a node and if you Need to take a detour you can easily change insert or delete a node

and recalculate how to get to your final destination three what about a music playlist so each song within a playlist might not necessarily be next to each other within your computer's memory you want your playlist to follow a certain order of songs so that could be another use of a linked list so those are linked lists if you would like a copy of all my notes here and my code i will post this To the comments section down below if you can give this video a thumbs up drop a random comment down below and well

yeah those are linked lists what the heck is a dynamic array a dynamic array is an array with a resizable capacity if we need extra room for elements we can increase the capacity which we cannot normally do with a standard typical fixed size array dynamic arrays are also known as arraylist in java vectors in c plus plus Arrays in javascript and lists in python here's an example of a static array and then we'll take a look at a dynamic array a static array has a fixed capacity we determine that capacity at compile time and we

can't change it later normally in this example i have a static array with a capacity of six elements and a size of five elements that are currently occupied the last element is open so it's null each element has a memory address obviously These are not real memory addresses but this is how i like to think about things imagine that all of these memory addresses are houses and they're all next to each other now accessing an element is easy because we have index numbers to work with we can randomly access an element in o of one

constant time the size of our data set doesn't matter however searching for a stored value still takes time because we need to begin at index zero and iterate over Our array until we reach our value or the end in case we don't find it this is done in ofn linear time the larger the data set the time to finish will increase linearly and in the case of inserting or deleting that takes a linear time unless done at the end no shifting of elements is required however the closer we need to insert or delete to index

zero we need to shift all elements that follow in order to make room for insertion or close any gaps in The case of deletion so if i need to insert a value at let's say index zero i have to shift all elements to the right by one to make room for this insertion and then we can insert a value now currently with our static array we're at capacity our array is full our size is equal to our capacity then in the case of deleting an element we need to shift all elements that follow after this

index where we're making the deletion and shift everything once to the left so That would look like this and our size is back to five so there is one element that is open a major disadvantage of static arrays is that they have a fixed capacity we can't increase the capacity once the size of the elements reaches capacity in this separate example i have an array with a capacity of five elements and a size of five elements and it's completely full i can't decrease the capacity because the next memory block contains i don't know Pictures of

cats or something you do you i guess a dynamic array has its own inner static array with a fixed size once the inner static array of our dynamic array reaches capacity our dynamic array will declare and instantiate a new array with an increased capacity usually the amount that we increase the capacity by really varies depending on the programming language it's usually between 1.5 and 2. i just picked capacity times 2 for extra Emphasis so what we'll do now is copy the elements over to our new array and these have different memory addresses than our original

array so that would look something like this we now have a new array with double the capacity but like i said it really depends on the language that you're working with it's usually between 1.5 and 2. this array has a size of 5 elements that are full and a total Capacity of 10 then if you need to shrink the capacity like if you're not using a lot of elements you can always just do the reverse process of what we did to increase it now with this new inner array the insertion and deletion of elements is

really the same as a static array so you just shift all the elements to the right by one to insert a new element or shift all the elements to the left to delete an element what are some of the advantages of dynamic arrays One there is random axis of elements that is done in o of one constant time we can randomly access an element by an index number and retrieve the value 2. there is good locality of reference and data cache utilization because all of these memory addresses are contiguous they're right next to each other

unlike with linked lists you have to jump around a lot because all of the memory addresses are kind of random and three it's easy to insert and delete elements At the end because there's no shifting of elements required and for the disadvantages a dynamic array wastes more memory than a linked list because we need to increase the capacity to accommodate more elements if we need the extra room and we may not necessarily need all of this extra room so a dynamic array wastes more memory than a linked list two shifting of elements is time consuming

the closer we need to insert Or delete closer to index zero we have to shift all elements that follow afterwards to the right in case of an insertion or to the left in case of a deletion and three expanding or shrinking the array is time consuming because we have to copy all the elements over to a new array with a different capacity and that's the basics of a dynamic arrays let's create our own dynamic array for practice all right welcome back we're going to create our Own dynamic array using java in the future if you

ever do need a dynamic array you might as well just use an array list according to the description it's a resizable array implementation of the list interface and it's pre-built so you might as well use it i thought we would create our own dynamic array just for learning purposes in practice but let's take a look at the arraylist class within this class there are a few defined members there's a default Capacity set to 10. there are overloaded constructors within this arraylist class we can set our own initial capacity or we can use the default by

not passing in an initial capacity there is a size to keep track of how many elements are filled within our array list and our arraylist does have its own inner static fixed size array and if we ever need to expand the size of this array we just copy the elements over to a new inner array so let's begin let's create a new Class named dynamic array and i'll get rid of this so file new class and this will be named dynamic array then finish okay let's declare a few members let's create int size int capacity

this will be the initial capacity i'll set this to 10 but feel free to pick whatever value that you want as well as an array of objects named array i will declare this but not Yet instantiate it so you can make these private however i think that'll make our code a little more complex and difficult to understand although it'd be more secure i'm just going to use the default visibility for these members here all right let's create some overloaded constructors so public dynamic array and within here we will instantiate a new fixed size array This

dot array equals new array of objects with a capacity of whatever capacity the default is so it's going to be 10 by default and we'll create an overloaded constructor just in case the user passes in their own capacity that they would like to set so int capacity this dot capacity equals whatever capacity that we pass in Okay let's instantiate a new dynamic ray dynamic make sure to spell it right dynamic array i'll call this dynamic array with a lowercase d equals new dynamic array so i'm not going to pass in an initial capacity and let's

print whatever the capacity is of our dynamic array dynamic array dot capacity And this should be 10. okay now let's pass in maybe a capacity of five and this should be five yep cool so it seems like that works all right let's head back to our dynamic array and declare all of the methods that we'll need let's create an add method public void add and there will be one parameter of object data next method insert Public void insert the two parameters are int index object data okay next method we have delete public void delete there

is one parameter of object data then we have search Public and we're going to return it index search and we will need object data and let's return negative 1 for now then we have private void grow to expand the size of our array private void shrink Then we'll need an is empty method public we will return a boolean value is empty and we might as well fill this in right away because there's only one line return size is equal to zero if our size is anything but zero we will return false and lastly tostring public

String to string and i need to type in something i'm just going to return null for the time being until we return something okay let's begin by filling in the add method first we'll want to check to see if we're at capacity if our size is greater than or equal to our capacity then we better call the grow method to expand the size of our array So if there is room we will take our array at index of size that should be the end of our array equals data then we will increase our size by

one now let's head all the way down to the tostring method to display the elements of this array and we just need to iterate over these let's declare a local variable of string string string and i will set this equal to an empty String and we will fill in the elements when we iterate over it so let's iterate over the elements of our array so let's create a for loop for int i equals zero and then i will continue this for loop as long as i is less than our size you can do capacity too

if you want to see the entire array but let's begin with size i is less than size and i will increment our index i by one so i'm going to take our string and Append it string plus equals our array at index of i that's one i plus maybe i'll add a comma then a space then we should return our string string okay this isn't perfect yet but let's at least test it let's head back to our main java file and add a few elements to our array using the add method so let's use the

default capacity of 10 so we don't necessarily need to pass in anything so to add to our array we can Use dynamic array dot and we declared an add method at the top so let's add maybe some letters i will add the letter a then b then c that should be good so a b and c and then let's call the tostring method system.out.printline and with the tostring method we only have to type in The name of what we would like to display the elements of so dynamic array and we don't necessarily need to type

tostring so this should display a b and c now let's format this and clean it up a little bit like i would like to get rid of the last comma here and maybe enclose all of these elements within a set of square brackets so this is what we can do within the tostring method so after the for loop let's check to see If our string does not equal an empty string if that is the case if there are elements to display let's take our string then i'm going to create a substring and get rid of

these last two characters the comma and the space so string equals string dot substring and the length is going to be beginning At index 0 and i will continue this until string dot length method minus two then after running this one more time the common space at the end should no longer be there because we created a substring to end at the last element then let's enclose all of these elements within a set of square brackets so i'll use some string concatenation so i'll add a Left square bracket and then at the end add a

right square bracket and then these should be within square brackets now and that looks a lot better now what if our string is empty let's return it just a set of square brackets using an else statement else we will set our string equal to a set of square brackets and that's it so let's head back to our main java file And comment these lines of code out where we add elements to our dynamic array so let's run this and we should have an empty set of square brackets actually this would be a good opportunity to

test our is empty method so let's check that so within a print line statement system.out.printline i will take my dynamic array and use the is empty method then i'm just going to use some string Concatenation empty colon space plus dynamic array is empty method and our dynamic array is currently empty that is true then let's fill this with elements a b and c so this should iterate and display the elements of our array and let us know if our array is empty which is false since we're here let's display the size and the capacity of

our array too so system.out.printline dynamic array Dot size and i'll use some string concatenation here too so size colon space plus dynamic array dot size and the capacity as well so capacity plus dynamic array dot capacity so this dynamic array has a size of three three elements are filled in and a capacity of ten for fun just to see the entire array let's go to the tostring method and change size to Capacity so we can see all of the elements that are filled in and not filled in so after running this we can see our

entire array at its full capacity so we have a size of three three elements are filled in but we have a total capacity of 10. the rest of the elements are null so if we were to count all of these they should be 10 so we have one two three four five six seven eight nine ten nice so you can change that back to size or You can keep it as capacity i'll just keep it as capacity for teaching purposes now let's fill in the insert method there's not a whole lot left to do first

let's check to see if our size is greater than or equal to our capacity if so then we'll need to grow our array so size is greater than or equal to our capacity if that is the case call the grow method what we're going to do at this point is shift all of the elements That are filled in to the right in order to make room for the insertion so let's use a for loop and iterate over our filled elements in reverse order i will set into i art index equal to our size and then

i will continue this as long as i is less than our index then decrement i by one so i'm going to take our array at i and set this equal to array at index of i minus one this will shift all of the elements over to the right to Make room for the insertion so we will take our array at index equals whatever data we want to set then increase our size by one so then if we head back to our main java file we can insert a value at a given index so let's take

our dynamic array dot use the insert method let's say at index 0 i would like to insert an x so let's try it Cool we have x a b c the size is now 4 and the capacity is still 10. now let's work on the delete method within here we're going to iterate over the elements of our array beginning from left to right so this is fairly easy int i equals zero we will continue this as long as i is less than our size and increment i by one after each iteration so during each iteration

we will check to see if our array at index of i is equal to the data that we pass in as An argument so if that is the case we need to shift all of the elements to the left then so we'll need a nested for loop for that then we will need an index of j because i is already taken we're within a nested for loop int j equals zero and i will continue this nested for loop as long as j is less than our size minus i minus one and then we are going

to increment our index j by one during each iteration so Basically wherever we make the deletion we're going to shift all of the elements afterwards one spot to the left so we will take our array at index of i plus j and set the sequel to our array at index of i plus j the same as before but add plus one so that will target the next element that comes afterwards so after we escape this for loop we will take our array at index of size -1 And set the sequel to null and then we

will decrement our size by one and actually here would be a good place to shrink our array so let's write an if statement and check to see if our size falls below a certain criteria so let's say that if our size is less than or equal to a third of the capacity so capacity divided by three we don't want to shrink too often just because that's time consuming and then you may want to cast This as an int because it may not divide evenly so if our size is underneath a third of the capacity let's

call the shrink method and we will shrink our array by maybe half but we'll get to that later so then we want to break to escape this for loop then okay let's try this then so after making the insertion let's delete what about a so dynamic array dot delete and i do not need to pass in an index Just the data that i'm looking for all right so a is no longer in here we have x b and c the size is three and the capacity is still ten all right i promise we're almost finished

let's fill in the search method next and this one is fairly short so we just need to iterate over the elements of our array beginning at index zero four and i equals zero i will continue this as long as i is less than the size of our array Increment i by one if our array at index of i is equal to the data that we're looking for the data that we pass in as an argument then we will return whatever i is our index if we do not find it we return negative one that's kind

of like a sentinel value that means we did not find the value that we're looking for okay so let's search for maybe c dynamic Array dot search and i will pass in the data that i'm looking for i am looking for c so that should be 0 1 2 assuming we insert and delete some values later and then i'm going to place this within a print line statement so dynamic ray dot search and i am searching for c and our result is that c is at index two zero one two all right we're near the

end let's grow and shrink our ray and i'll turn these lines into comments Now for the grow method we're going to instantiate a new array but we'll increase the capacity first int new capacity equals our old capacity which is just named capacity and let's say we want to increase the capacity by two and then i will just cast this as an end okay so after we create a new capacity we will instantiate a new array then we need to copy the elements over so we'll Have an array of objects named new array equals new array

of objects with a capacity of our new capacity and then we need to copy the elements over to our new array and that's kind of time consuming but necessary so we begin at index zero for int i equals zero we will continue this as long as i is less than our size And i will increment this by one after each iteration so we will take our new array at index of i and set this to our old array just named array at index of i and then we will change the capacity to whatever new capacity

is then lastly we will set our array to equal our new array then let's test it so i'm going to maybe add a bunch of elements i'll keep that as a comment So let's change the capacity of our array to five i'll pass in five into the constructor so we have less elements to work with so the size is three and the capacity is five i'm going to add another element let's try d so size four capacity five let's add e okay so currently our array is full now let's try to increase the size past

the capacity so i will add f And this should increase and grow the size of our array so we have a capacity of 10 now and we have a bunch of empty elements and lastly we just need to shrink this array and this next part is super simple for the shrink method copy everything from the grill method and paste it within the shrink method but change capacity at times to to capacity divided by two now we will call the shrink method automatically when the size falls below a third of the capacity That means we have

a lot of wasted memory now let's begin deleting elements so i will type dynamic ray dot delete a then maybe b so when the size is a third of the capacity that's when it should shrink so we're not there yet let's delete maybe one or two more times so let's delete c and there we go so the size is three and the capacity is now five well all right that's a very basic Dynamic array if you're using java instead of just building your own dynamic array you might as well just use an array list because

it's more efficient and well it's already coded for you but i think this was good practice for us just to understand how dynamic arrays work so if you would like a copy of all this code of course i will post this to the comment section down below if you made it all the way to the end please give this video a thumbs up a Random comment down below and well yeah those are dynamic arrays and well computer science hey what's going on everybody it's bro hope you're doing well and in this video we're going to

run some tests on both array lists and linked lists in java so sit back relax and enjoy the show all right let's begin we'll need both a linked list and an array list so linked list the data type will be integers and i will name this linked List equals new linked list again the data type is integer add a constructor boom we got ourselves a linked list and now we'll need an arraylist change linked to array this will be named arraylist make sure to pay attention the capitalization equals new arraylist and we'll need to keep

track of the time we'll need a start time and time and elapsed time and these will be of the long data type we'll be working with Nanoseconds so a long is preferable to an end a long is really just a really long integer think of it that way so we have start time end time and elapsed time okay and now we'll need to populate both our linked list and our array list and we can do that with a for loop we'll need a large sample size maybe one million elements that'll be good so int i

equals zero we'll continue this as Long as i is less than a million and i believe that's about a million yeah we're good okay then increment i by one during each iteration so i'm going to add i to both my linked list and my arraylist so we can add primitives because java has an autoboxing feature so even though these are integer objects we can still add primitives and be sure to add to our arraylist as well so arraylist.ad i okay let's move on now we'll keep track of The time we'll need to assign the start

time of value and end time of value before and after our operation so let's say that start time equals and we can get the current time of our jvm by using system dot nano time method and let's take a look so this returns the current value of the running java virtual machine's time source in nanoseconds so we will get the start time after we do something i'll just add a note here do Something then we will get the end time so end time equals system dot nano time method and to calculate the elapsed time that

will be elapsed time equals end time minus start time and then we'll probably want to display this so let's do that system.out.printline and let's say linked list I'll add a tab too plus elapsed time plus ns4 nanoseconds and let's just run this to test it so this portion of code really took right between here took 400 nanoseconds okay let's actually do something now so let's get the first element within our linked list linked list dot get zero And let's see how long this takes okay thirteen thousand two hundred nanoseconds now with an arraylist let's copy

everything that we have for our linked list and change linkedlist to arraylist and be sure to do that here as well array list and let's compare these so we are getting the index of zero for both our linked list and arraylist and we will compare them And it appears that our arraylist is slightly faster our linked list took 11 800 nanoseconds and our arraylist took 6700 so it looks like getting the first element of our linked list is going to be a little bit slower than our arraylist this time let's get something right in the

middle of our linked list and arraylist so i'm going to turn this line to a comment and we will get the index of 500 000 so that's right in the Middle and do the same thing with arraylist as well so arraylist dot get 500 000. and let's see how long this takes okay so our linked list took way longer than our array list our linked list took 7.5 million nanoseconds compared to our arraylists 6900 nanoseconds okay so that's still way longer with a linked list now let's try something near the End of our linked list

and array list what about the last element linked list die get nine hundred ninety nine thousand nine hundred ninety nine so that is the last index in our linked list and array list we have one million elements and this is exclusive and the first element has an index of zero so let's do the same thing with arraylist arraylist die get 999 99999 and here are the results our linked list took 63 000 nanoseconds compared to our arraylist 17 000. now the reason that our linked list took less time to retrieve and index at the end

is because this linked list is a doubly linked list so we can begin at the head and work our way towards the tail or begin at the tail and work our way backwards to the hud so since this index is right at the end it's actually going to be very easy to retrieve this index whereas in the middle is actually going to be the worst possible spot for a linked list because we can start at Either end but it's still going to take the same amount of time to get to the middle so it appears

that accessing an element from an arraylist is always faster than a linked list and that's to be expected because with an arraylist we have a random access of elements unlike with a linked list we have to begin at one end of our linked list and traverse our linked list until we get to the index that we're looking for now let's add or remove an element from our linked List and array list maybe just remove because it's going to take really the same amount of time so linked list dot remove and let's remove the first element

so index zero and do the same thing with arraylist array list dot remove index zero and let's take a look again okay so it appears that our linked list was actually faster this time 17 000 nanoseconds compared to 2.2 million nanoseconds of an arraylist And the reason that our arraylist took longer is because we need to shift all elements to the left after removing an element so we had to shift one million elements after removing the first element now let's remove something near the middle so let's remove index number five hundred thousand so linked list

dot remove five hundred thousand and do the same thing with the arraylist be sure to comment this line out Arraylist dot remove 500 000. and here are the results so looks like our linked list took a lot longer this time 7 million nanoseconds compared to 1.6 million nanoseconds for an arraylist so with our arraylist there were less elements to shift this time because we were right in the middle but with our linked list we still had to navigate to the middle to remove one of These elements and then let's remove the element at the end

of both our linked list and our array list linked list that remove 999 999 and do the same thing with arraylist arraylist dot remove 999 99999 and this time our linked list is just slightly slower than our arraylist adding or removing elements near the end of an array list is actually fairly easy The closer that we insert or delete near the end the less time it's going to take because we have to shift less elements and with a linked list well this is a doubly linked list so accessing the last element doesn't really take too

long if it's near the middle it's going to take forever actually so it seems that in most situations an arraylist is going to be better than a linked list however if you have to do a lot of inserting or deleting especially if it's a large set A linked list might be better but it seems that an arraylist is going to be more flexible for most applications so that is linked lists versus arraylists if you would like a copy of all this code i will post this to the comments section down below and well yeah that's

linked lists versus arraylists and computer science hey what's going on everybody it's you bro hope you're doing well and in this video i'm going to describe the very Basics of big o notation in well computer science so sit back relax and enjoy the show oh yeah big o notation so a common phrase used with big o notation is how code slows as data grows it describes the performance of an algorithm as the amount of data increases and really this notation is machine independent what we're really focusing on is the number of steps to complete an

algorithm because some machines are going to run Certain algorithms faster than others and three we tend to ignore smaller operations if we had some task that took n plus one we would just reduce it to just n because that plus one really isn't going to make a difference so here's a few examples of big-o notation we have o of 1 o of n o of log n and o of n squared and n is really just the amount of data that we're passing in it's a variable like x what we're focusing on is the performance

of an Algorithm as the amount of data increases and n is a representation of the amount of data that we're passing in here's a more concrete example i have a function named add up we will add up to a certain number depending on what we pass in as an argument the for loop within here will iterate once up to whatever number that m is add i to sum then return it what if n was a large number like a million well it's going to take just above a million steps to Complete this function this function

is said to have a runtime complexity of oh then linear time as the amount of data increases it's going to increase the amount of steps linearly or proportionally now another way in which we could write the same function is to take sum equals n times n plus one divided by two we will get the exact same sum so if n was let's say a million this is still only going to take a couple steps three steps not a million Steps so this function is going to have a runtime complexity of o of one the input

size doesn't matter the amount of data that we have really doesn't matter it's going to be completed in the same amount of steps so this function is way better than this previous one three steps is better than a million steps and the reason that this isn't o of three because this takes three steps is that we really don't care about smaller operations in the grand scheme of things They really won't make much of a difference so we would just shorten this and say that this is o of one constant time the input size doesn't matter

here's a graph that i made to represent the different runtime complexities we have data on the x-axis represented by n so data will increase as we go more to the right and we have time on the y axis i did add an asterisk next to time because some of these times can vary depending on what machine you're using So these can vary another way to look at this is number of steps so as we increase on the y-axis these algorithms are going to perform with increasingly more time they're going to get slower so let's begin

with o of one constant time anything that has a runtime complexity of o of 1 will take the same amount of time regardless of the data size a few examples would include the random access of an element within an array and inserting at the beginning of a linked List so o of 1 is extremely fast next we have o of log n also known as logarithmic time one example is binary search we haven't talked about this yet we'll talk about a few of these algorithms in future videos but anything that has a runtime complexity of

o of log n will actually take i don't want to say less and less time but increasingly less time to complete so as the data size increases this algorithm is going to be more and more efficient compared To the early stages with a small data set of n is also known as linear time as the amount of data increases the time it takes to complete something will increase proportionally linearly that would include looping through the elements in an array and searching through a linked list next we have o of n log n also known as

quasi-linear time this would include a quick sort merge sort and heap sort we'll talk about these concepts in future videos so for The most part this is very similar to linear time unless we're working with a large data set then anything using o of n log n is going to start to slow down when we work with larger data sets hence this curve here then we have o of n squared also known as quadratic time a few examples would include insertion sort selection sort and bubble sort as the amount of data increases it's going to

take increasingly more and more time to complete anything that has a runtime Complexity of o of n squared so just to compare linear time and quadratic time with linear time if our data set was a thousand if n equals a thousand it's going to take a thousand steps they're proportional they're linear but if we were using quadratic time if n was a thousand then a thousand squared would be a million so if our data set was a thousand if we're using quadratic time it's going to take a million steps then way more than linear time

so quadratic Time is extremely slow with large data sets but in the case of a small data set it could actually be faster as you can see by the graph here and lastly we have o of n factorial also known as factorial time and one place where this is used is with the traveling salesman problem which i might discuss in a future video so this is extremely slow so if i had to give a letter grade to each of these runtime complexities when working with large data sets with constant time this Would be an a

like an a plus logarithmic time would be a b it's pretty good linear time is c it's okay quasi-linear time is a d it's just barely passing quadratic time would be an f and factorial time well you get expelled from school although some of these runtime complexities are actually faster when working with a smaller data set so keep that in mind well that's the very basics of big o notation it's notation used to describe the performance of an Algorithm as the amount of data increases so if you can give this video a thumbs up drop

a random comment down below and well that's big o notation in computer science all right everybody linear searches we need to talk about linear searches because this wouldn't be a complete course without them with a linear search we iterate through a collection one element at a time the runtime complexity of a linear search is big o of n the Larger the data set the number of steps to complete that search will increase proportionately the disadvantages of a linear search is that they are slow for large data sets but with the advantages they are fast for

searches of small to medium sized data sets and they don't need to be sorted that's a huge benefit over binary searches and interpolation searches and they are useful for data structures that do not have random access such as linked lists so let's Begin let's create a basic array of integers int array and to make up some numbers they don't necessarily need to be in order all right then let's find an index int index equals and we will invoke a linear search function which we still need to declare we will pass in our array and some

value we would like to search for uh let's search for the number one okay so then let's declare this function Create method linear search private static and linear search so we have two parameters an integer array and an integer i'm going to rename i as value so it's more descriptive okay with a linear search all we need to do is loop through our array one element at a time so we can do that with the for loop so let's set into i our index equal to zero we will continue this as long as i is

less than Our arrays length then increment i by one what we're checking with an if statement is to see if our array at index of i is equal to the value that we're searching for this parameter if it is then let's return whatever our index is i if we do not find it after iterating through our entire array let's return it negative 1 as a sentinel value and that's all there is to it to our linear Search function so back within our main function let's check to see if the value returned does not equal negative

one that means that we found our value so with an if else statement let's check to see if index does not equal negative one that means that we have found our element so let's print element found at index plus index else let's print element not found System.out.printline element not found so if we're searching for the number one we would find that at index one zero one if we search for five that is found at index eight zero one 2 3 4 5 6 7 8. if there's some number that's not in here like 10 then

this will print element not found so yeah that's the idea behind a linear search we iterate through some collection one element at a time it's Slow for large data sets but it's fast for small to medium data sets this would be a small data set and they do not need to be sorted that's a huge advantage so yeah everybody that is a linear search if you would like a copy of this code i'll post this to the comment section down below and well yeah that is a basic linear search in computer science i guess hey

everyone it's you bro hope you're doing well and in this video i'm going To explain the binary search algorithm in computer science so sit back relax and enjoy the show all right binary search it's a search algorithm that finds the position of a target value within a sorted array or other collection in order for a binary search to work whatever we're searching through it needs to be sorted and basically what we do is we take half of the array and eliminate it during each step and we will whittle down our Collection until there is only

one element remaining in this example i have an array of 11 elements each element contains a letter and they're all sorted alphabetically let's say we are looking for the letter h and i need the index what we would do with a binary search is that we always begin in the middle we first check to see if our target value is equal to this middle value if these are equal then we can return this index but odds are They're probably not going to be equal on the very first turn the very first step so these are

not equal then we will check to see if our target value is greater than or less than this middle value since h is greater than f we can disregard this entire first half of our array because since this is sorted our target value could not possibly be within this first portion and then we begin step two or phase two it's the same process as before so again we begin In the middle check to see if our target value is equal to the middle value they're not check to see if our target value is greater than

or less than the middle value this time h is less than i we would delete the second half of this portion we're not actually deleting these values we're disregarding them and then we can move on to step three we're repeating the same process as before and this time these elements divide evenly so we would just round down and begin And say that this is the middle so h is greater than g we would disregard this element and we only have h remaining so we would return this index because these values are equal and that's a

binary search now a binary search isn't too efficient when working with small data sets however if you're working with a large data set like 1 million elements well then a binary search is actually fantastic because we're eliminating half of the elements we are searching through During each phase or turn so if we had a million elements after the first phase we can already disregard like half a million elements and then we just repeat the process until there's only one left so if this was an iterative approach we would need to search through these linearly beginning

with you know index zero and going all the way to a million so a binary search is fantastic with large data sets the runtime complexity of a binary search is o of log n the Larger the data set a binary search becomes more and more efficient compared to other search algorithms alright let's perform a binary search in real life now we'll use the built-in binary search method of arrays to begin with and then later on we'll build our own binary search function so we'll need an array to work with let's say we have an array

of integers named array int array and the size of this array will be 100 we'll increase The size later for demonstration purposes and we'll need a target value that we're searching for i'll just name this target and target equals what about 42 we'll search for the number 42 and we'll need to populate our array so we can do so using a for loop int i equals zero we will continue this for loop as long as i is less than array dot length and increment i by one during each iteration then we will fill array at

index i with whatever i is our index Okay so the cheap way of using a binary search is to use the built-in binary search method of arrays let's say int index equals arrays dot binary search and taking a look at this binary search method there's two arguments that we Have to pass in an array and whatever we're searching for so we will pass in our array and our target then return the index and let's display that so let's check to see if our index is equal to negative one if our target is not found then

that means negative one will be returned from our binary search method so let's print something system.out.printline uh what about element not found Actually better yet target not found let me change that target plus not found okay then else else we will display system.out.printline element found at colon space plus index all right let's try it Okay element found at 42. cool now let's create our own binary search function for practice i'll turn this line into a comment copy it paste it and get rid of this erase portion okay then i'm just going to use a shortcut

to generate this function okay so private static int binary search there are two parameters an array of integers named array and int target so We'll return negative one that acts as a sentinel value negative one means that the value is not found now what we'll need at this point is the beginning and ending index of our array so let's say int low will be the beginning and int high is the end array dot length minus one so we have a low index and high index and we'll create a while loop while Low is less than

or equal to high we'll continue this while loop and keep on searching through our array so first we need the middle index int middle and here's the formula for that low plus high minus low divided by two so we have our middle index we will take Int value equals our array at index of middle so this will extract that value found within this element okay so this portion is optional i'm just going to display whatever this value is so we can count the amount of steps it's going to take to find a value so let's

say middle colon space whatever this value is This line of code is optional i'm just doing this for educational purposes okay now we need to check to see if our value is less than or greater than our target or equal to if value is less than our target low equals middle plus one and actually i'm going to get rid of These curly braces if you have an if statement and you only have like one line of code you don't really need the curly braces i'm just doing this so it's easier to read okay else if

value is greater than target we will set our high index high equals middle minus one Else that means we have found our target else return middle so this means that target is found and by returning negative one that means target not found and that is our binary search function let's try it okay element found at 42 so it took us let's see one two three four four steps to find the number 42 within this array of 100 elements now let's increase the Size because binary searches do extremely well with large data sets so let's say

we have 1 million elements and let's change this target what about seven hundred seventy seven thousands whatever that number is okay so let's search for it and let's count the steps uh so there's quite a number of steps here but let's count them 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 steps now imagine if we took a linear Approach where we began at index 0 and looped through this entire array looking for this index and in that case looping through an array would

have a runtime complexity of of n to find this number it's going to take over 700 000 steps because we're iterating once for each element within this array compared to a binary search where it only took 20 steps well then in conclusion a binary search is a search algorithm that finds the position of a target value within a Sorted array half of the array is eliminated during each step or phase so that's a binary search algorithm if you would like a copy of all this code of course i will post this to the comment section

down below and that is the binary search algorithm in computer science all right what's going on everybody interpolation searches these are an improvement over binary searches that are best used for uniformly distributed Data basically speaking we're going to make a guess and i'm saying that within quotes we're guessing where a value might be based on calculated probe results if our probe is incorrect our search area is narrowed and a new probe is calculated basically we're guessing where a value is going to be and return the index so using an interpolation search this has an average

runtime complexity of big o of log log n and in a worst case Scenario where our values within our collection increase exponentially this can have a runtime complexity of big o of n so to demonstrate this let's create an array of integers int array we'll name this array equals and assign this some numbers all uniformly distributed let's say the numbers one through nine all in order this would be i would say a best case scenario then let's find an index int index Equals and we will invoke an interpolation search function so interpolation search we will

pass in our ray and a value we would like to search for let's search for the number maybe eight okay then let's declare this function private static and interpolation search there are two parameters an array of integers and our value we are searching for i'm going to rename this parameter as value So it's more descriptive the first thing that we're going to do is calculate the upper bound and the lower bound of our searchable area so int high will be the higher bound of our searchable area and this will be our arrays length minus one

and the lower bound is well the first index and low and i will set this equal to zero using a while loop we will continue probing the condition within our while loop is while our value is Greater than or equal to our array at index of low the lower bound and our value is less than or equal to our array at index of higher bound and our sizable search area is going to shrink after each iteration so while our value is within the new searchable area keep on probing keep on searching i'm going to add

another Condition too low is less than or equal to high after each iteration our searchable area is going to shrink once our searchable area is zero elements well we can't search anymore so we might as well exit now here's the formula to calculate where our value is probably going to be and our guess will be referred to as our probe int probe equals and here's the formula high minus low Times our value minus array at index of low our lower bound divided by array at index of high minus array at index of low just going

to add low to the front of this and i'm just going to make this a little bit more readable for us here's the formula to calculate where our value is likely going to be it's a little complex to read this a few of the Contributing factors are the size of our current searchable area high minus low so to begin with we have nine elements times the value we're searching for minus the value at the lower bound so 8 minus 1 divided by the value at the higher bound minus the array at the lower bound then

at the end we're just tacking on whatever our lower bound currently is so it's a complex formula all you have to do is just copy this so during each Iteration i'm going to display our probe this is going to be essentially our guess and let's check to see if our probe is equal to our value so using an if statement let's check to see if array at index of probe is equal to our value that we're searching for if it is let's return our probe this is the correct index else if our guess our Probe

is incorrect we'll need to narrow down our search area so using an else if statement let's check to see if array at index of probe is less than our value if that's the case we will need to set the new lower bound low equals probe plus one else high equals probe minus one now here's the deal with these Statements we're currently searching for the number eight if we guess our probe is at let's say five and our value is greater than this probe we can disregard this portion of the searchable area so we're moving the

new lower limit the new lower bound to just after where our probe was six so this is the new searchable area and then we'll calculate a new probe based on this data if we're looking for let's say Two and our probe says it's likely here at five well then since two is less than our probe we can disregard all of this data and this would be our new searchable area we would move the higher bound of our data down to just below our probe so that's kind of the idea so at the end if we

do not find our value let's return negative 1 as a sentinel value so back within our main function let's check to see if the value returned does Not equal negative one using if else statements if index does not equal negative one then let's print a message system.out.printline element found at index plus index else element not found okay so this should work let's run it so we are searching for eight so this formula calculated that this value is Likely at probe seven index seven zero one two three four five six seven and this was the first

iteration of our while loop we were able to find our value 8 on the first iteration so let's find a different value how about one element found at index 0 that's the first element so interpolation searches work very well with uniformly distributed data these numbers are all increasing by one so this is a little too easy for our interpolation search It's guessing the likely index on the first try so let's create a more difficult data set so with our new data set let's say that we will start with one and then double the number of

the previous element so 1 2 4 8 16 32 64 128 256 512 and 1024 and let's search for the number what about 256 let's see how many probes this is gonna take all right so here's the results we iterated our while loop five times we had five different guesses after the first guess this was not correct so we narrowed down our search area then we probed again this still wasn't the Correct answer so we probed again add again and again until we got the right value so that's an interpolation search it's an improvement over

a binary search that is best used for uniformly distributed data it guesses where a value might be based on a calculated probe result if the probe is incorrect the search area is narrowed and a new probe is calculated the interpolation search has an average runtime complexity of big o of log log n and a worst case Runtime complexity of big o of n this would be if our values increase exponentially so yeah that is the interpolation search if you would like a copy of this code i'll post this to the comment section down below and

well yeah that is the interpolation search in computer science oh yeah all right bubble sort bubble sort is a sorting algorithm that compares adjacent elements and checks to see if they're in Order if not these elements are switched then the next pair of adjacent elements is compared and we continue on in that pattern until all elements are in order while using bubble sword i like to imagine that our collection is filled with water heavy things like rocks sediment will sink to the bottom anything light such as air wood bubbles anything light will flow to the

top here's an array of nine unordered elements we will use bubble sort to Manually sort these elements in ascending numeric order alright so i reset this array we're going to perform a total of nine laps but don't worry i'll fast forward through this footage so let's just walk through the first few steps we will compare these first two adjacent elements we'll check to see if the first element is greater than the second element if it is we will move this element to a variable which will probably be named temp short for Temporary check the video

in the java playlist on how to swap variables i think it's a pretty good video but i might be biased with my opinion we'll take the next element and place it where the first element was then move this variable within temp into the spot that one was in the previous element okay so then we will check these next two adjacent elements this first element is greater than the second element so we will move our first element Into temp move the second element to where element one was and then move temp to where element two is

and then we would just repeat this process so we will lap through this array once for each element that is available so let's just speed up the footage here and i will show you manually a bubble sort [Music] as you may have noticed the bubble sort algorithm really isn't that efficient Even when working with smaller data sets in most real world applications you'll probably use a different sorting algorithm but this is still a good thing to learn so the bubble sort algorithm has a runtime complexity of o of n squared it runs in quadratic time

so the larger the data set the more and more inefficient that this sorting algorithm is going to be with a small data set it's not horrible but there's definitely better algorithms out there so for Practice let's create our own bubble sort algorithm all right let's create an array of integers and assign some random numbers make sure that they're not in order because well then that would defeat the purpose of this program so at the end we'll just display all the elements of this array using an enhanced for loop for i in array we will display

with a print statement not print line Whatever i is during each iteration so let's just test this so i have all the elements in my array printed and they're currently not in order so we'll need to declare a bubble sort method bubble sort and then we will need to define this outside of our main method so public static void we're not returning anything Bubble sort and then we will need to pass in an array so that will be the argument array and we will accept int array okay so this is actually really easy to write

even though the bubble sort algorithm really isn't too efficient so i guess that's one benefit so we'll Need nested for loops and then the outer for loop will be int i equals zero i is less than array dot length minus one i plus plus and let's do the same thing with the inner for loop but we can copy what we have Change i to j and this is going to be array length minus i minus 1. so we're going to check to see if array at index of j is greater than that will be for

ascending order is greater than array at index of j plus one so that would be the next adjacent element so if this number is Greater than this one we should switch these two elements around and we'll need the assistance of a temporary variable so let's declare int temp equals array at index of j then we will take array at index of j set this equal to array at index of j plus one and then lastly we have array at index of j Plus one equals whatever is stored within temp and honestly that's all there is

to it so this should sort our array and it's in ascending order so if you need this in descending order we would just swap this greater than sign with a less than sign and now this is in descending order so even though the bubble sort algorithm really isn't too efficient it's actually extraordinarily easy to write if you Just need something really simple so i guess that's one benefit all right everybody that is the bubble sort algorithm it compares pairs of adjacent elements and checks to see if they're in order if they're not they're swapped and

this process will repeat once for each element in an array or other collection so this algorithm has a runtime complexity of o of n squared so it's okayish for small data sets and please do not use this for any large data sets So if you would like a copy of this code i will post this to the comment section down below and well that's the bubble sort algorithm in computer science hey everyone it's me again and in this video i'm going to explain the selection sort algorithm and computer science as always sit back relax and

enjoy the show okay everybody selection sort selection sword is an in-place comparison sorting algorithm that keeps track of the minimum value during each iteration and At the end of each iteration all we do is swap variables how i like to imagine this is that let's say that our array is a bunch of different closed boxes and each box contains a number and they're all out of order so what we'll do is we have a flashlight too because we're in the attic and it's really dark so we have a flashlight we will open each box beginning

with the beginning of our array and we'll take a look at the value inside okay nine is a fairly small Number i guess right so we will move this value to some temporary storage we'll keep track of the index of the minimum value nine is the new minimum let's open the next box and holy crap it's a one one is a really small number so that will be the new minimum then we'll open the next box which is an eight one is still less than eight let's move on the next box is two seven three

six four and five one was the minimum value during this iteration and we need To move this value to the place that we started during this iteration index 0 so we'll have to do some good all variable swapping so we will take 9 place it within some temporary storage then take one and place it where nine was then take nine and place it where one was and that is the first iteration let's move on to iteration two and we'll clear min and temp okay so this portion is Done now we're not worried about it this

is the new beginning of the next iteration and well nine is a low number i guess we'll move that to min but eight is even lower than nine so we'll move that to min holy crap it's a two two is the new min for sure and then we just repeat this process over and over again two is the current minimum of this iteration one was the minimum of the first iteration but we're Not concerned with that it's already sorted so we need to move two to where we began this iteration at index one and currently

there's a nine in there so we're going to evict this nine place it within some temporary shelter take two place it within where we started at index one then take nine place it where two was and that is the second iteration now that we kind of know how this process works i'll speed Up the rest of the video for this demonstration so let's begin at index 2. [Music] [Music] [Music] [Music] [Music] [Music] [Music] and that is the selection sort algorithm the selection sort algorithm has a runtime complexity of big o of n squared The larger

the data set the more and more inefficient that using the selection sort algorithm is going to be although it's okay with smaller data sets now let's create our own selection sort algorithm okay let's implement a selection sort we'll need an array or other collection to work with let's create an array of integers because i want to make this as easy as possible so integer array and make up some random numbers make sure that they're not in Order what about eight seven nine two three one five four six i guess then let's use a for each

loop to iterate over the elements of this array four and i in array we will display each element with a print statement system.out.print I and let's run this once just to be sure that everything is working fine so 879 five four six everything is working as it should so before we display the elements of our array let's invoke a selection sort function which we still need to declare so selection sort and we will pass our array as an argument because well that's what we want to sort right so selection sort and we'll need to create

this Method i will cheat and use the shortcut so outside of our main method let's declare private static void selection sort there is one parameter an array of integers we'll need a pair of nested loops to iterate over our array so let's work on the outer loop for int i equals zero we will continue this as long as i is less than array's length property minus 1 then increment i by 1 during each iteration then there is a nested loop within here Change i to j so j equals i plus one j is less than

array length and j plus plus so we'll need to keep track of the minimum so we'll do that outside of our nested loop int min equals i so that is the current minimum and within the nested for loop we will check to see If our array at index of min is greater than array at index of j if it is we will change our min to equal j then outside of our nested loop but within the outer loop we will do some good old variable swapping so int temp equals array at index of i to

store this element array at index of i equals array At index of min then lastly array at index of min equals temp and that's all there is to it so after running this program our array is now sorted via the selection sort algorithm then of course if you need your array or collection sorted in descending order currently It's in ascending order all we do is swap this greater than sign with a less than sign and this will now be sorted in descending order depending on what you need well okay then everybody that is the selection

sort algorithm it will search through an array and keep track of the minimum value during each iteration at the end of each iteration we swap variables and that's all there is to it it runs in quadratic time big o of n Squared it's okay with small data sets even more so than bubble sort and it's pretty terrible with large data sets the larger the data set the more and more inefficient that this selection sort algorithm is gonna be so that is the selection sort algorithm if you learn something new give this video a big fat

thumbs up drop a random comment down below and well that is the selection sort algorithm and i guess computer science What's going on people it's bro hope you're doing well and in this video we're going to discuss the insertion sword algorithm in computer science as always sit back relax and well enjoy the show all right everybody insertion sword now what we do with insertion sort is that we begin at index one we take the value found within move it to some temporary storage like a variable named temp to temporarily hold it we examine elements To

the left if any elements are larger than what's within temp we shift those elements to the right so six is larger than one we shift it to the right if it's less than whatever's within temp we stop or until we run out of elements so we have run out of elements we take this value found within temp and place it at this opening here that was the first iteration let's move on to iteration two take this value place it within temp examine the elements to the left if this Element is greater than temp then we

shift it to the right it's not so we stop here and place this value back where it came from so that was the second iteration iteration three take this value place it within temp examine the elements to the left if they're greater than four we shift them to the right seven is larger than four shift it to the right six is larger than four shift it to the right one is not larger than four so we stop here take Whatever's within temp this value four and insert it here into this opening so that was the

first three iterations we repeat this process until we run out of elements so i'll speed up the footage so we are currently on index four [Music] [Music] do [Music] and that is your visual representation of the insertion sword algorithm i like To think of it like a jigsaw puzzle we have some pieces that are connected they fit together and we will move whole sections of pieces together to make room for a piece that fits so let's create our own insertion sort algorithm in java now we'll need to create an array let's create an array of

integers int array and make up some numbers put whatever numbers you want within here uh maybe nine how about a one and an eight and a two and a seven three six five four that Sounds good to me okay then let's display the elements of this array we'll use a for each loop four and i in array we will display each element within this array with a print statement so let me get rid of that print ln and just have print so i will print i i think i'm going to add a space afterwards i

didn't do that in the previous two videos so i think i better do that okay let's just run this just to test it Nine one eight two seven three six five four and before we display the elements of our array let's invoke a function which we still need to declare called insertion sort so insertion sort then we will pass in our array as an argument and we'll need to declare this so i'm going to cheat and create this automatically so outside of our main Method create a method named insertion sort private static void insertion sort

there is one parameter an array of integers okay now the first thing we'll do is create a for loop to iterate over each element of our ray but it begins at one not zero so that would be four then we will set int i to equal one not zero pay attention to that we will continue this as long as i Is less than array dot link and we will increment i by one during each iteration now we need to take our value found within i and place it within temp so let's declare a temporary variable

named temp int temp equals array at index of i and now we'll create a variable named j int j equals i minus 1. so this will keep track of what value we're comparing to the left of whatever I is so then we need to create a while loop we will continue comparing values to the left of i and our condition is going to be while j is greater than or equal to zero and array at index of j is greater than temp so if we need to shift an element to the right we would say

array At index of j plus one equals array at index of j so that will shift an element to the right then we will decrement j by one j minus minus and the last thing to do is to insert the value found within temp into that opening so that would be array at index of j Plus one equals temp and that's all there is to it so let's run this boo yeah one two three four five six seven eight nine well people in conclusion the insertion sort algorithm compares elements to the left and it will

shift elements to the right to make room to insert a value the insertion sort algorithm has a runtime complexity of big o of n squared runs in Quadratic time it's decent with small data sets but bad with large data sets and using insertion sort tends to be preferable to both bubble sort and selection sort it uses less steps than bubble sort and in the best case scenario insertion sort can run in o of n linear time compared to selection sort which the best case scenario is of n squared all right people so that is the

insertion sword algorithm if you can destroy that like button leave a random Comment down below and well yeah that's the insertion sword algorithm in computer science well howdy y'all we're talking about recursion now recursion is when a thing is defined in terms of itself i stole that definition from wikipedia really doesn't make too much sense a thing is defined in terms of itself so basically with recursion we apply the result of a procedure to a procedure a recursive method is one that calls itself and this Can be a substitute for iteration there's a lot of

overlap where you could use either recursion or iteration with recursion we divide a problem into sub-problems of the same type as the original and recursion tends to be used within advanced sorting algorithms and navigating trees some of the benefits of recursive code is that it's easier to read and write and it's easier to debug but the disadvantages is that it's sometimes slower and uses more memory Let's begin with a very simple example let's create a method to simulate walking we'll do this both iteratively and recursively then take a look at the differences between the two

so let's write an iterative walk method so we will need to invoke this method and then we will pass in the amount of steps that we would like to walk like five steps and then we'll need to declare this method private static void walk and i'll change i to maybe steps just so that It's more descriptive now let's use an iterative approach so iteration is the repetition of an internal process so we can use a for loop that will repeat a process and let's say that int i equals zero we will continue this as long

as i is less than steps and then let's increment i by one during each iteration and then during each iteration i will print You take a step and really that's it and after running this code we have walked five steps now let's write the same method recursively recursion is the repetition of a procedure iteration is the repetition of a process so with recursion we need a base case that's what we do when we would like to stop and a recursive case what do we do when we would like to continue so our base case is

going to be If steps is less than one then we will return and if you only have one statement within your if statement you don't really need these curly braces so i'm just going to omit those all right then we will print you take a step so this is our base case this is what we do when we would like to stop then our recursive case is what We're going to do when we would like to continue we will invoke the walk method within itself but we will pass in steps minus one and this is

our recursive case and this will do the same thing however it's just written a little bit different now one thing that you should know is that programs have a data structure called a call stack a call stack keeps track of the order in which our program needs to function so with the main Method we call the main method first and that's added to the bottom of our call stack so in order to complete our program we have to complete the main method and get to the end of it however when we took an iterative approach

we invoked the walk method and that was added to the top of our stack remember that video on stacks it's a lifo data structure last in first out we have to take care of anything at the top of our stack first and then work our way down With a recursive approach we're adding multiple frames onto our call stack because one we're calling the main method then we're calling the walk method passing in five as an argument then we're calling the walk method again passing in four as an argument then three then two then one then

zero then we return and we have to solve this in a lifo order last in first out we begin at the top and remove frames from the top until we reach the end so that's why Using recursion is sometimes slower and uses more memory we're adding more frames to the call stack there's more methods that we have to keep track of now check this out what if we take 1 million recursive steps we're going to call this walk method a million times and that's going to be a problem and we ran into an exception let's

take a look at this so we encountered an exception a stack overflow error it's kind of like that One website when working with recursion it is possible to run out of memory although this is sometimes slower and uses more memory recursive code tends to be easier to read and write and easier to debug for a small method like this i would probably stick with an iterative approach just because it already is fairly simple but it's going to really come in handy when we get two topics on advanced sorting algorithms so let's try something a little

more complex let's Create a program to find the factorial of a number so let's create a factorial method and we'll write this recursively so let's find factorial what about 7 and then we'll need to define this method and we no longer need our walk method so if we're taking a recursive approach finding the factorial of a number let's say that i is num so we'll need a base case if num Is less than one we will return one this is our base case then we need a recursive case we will return num times factorial then

pass in num minus one and then eventually we'll hit our base case because num is going to be zero and this is our recursive case Oh then change void to end because i forgot okay then let's display factorial seven within a print line statement factorial seven and the factorial of seven is five thousand forty so you can see that this was fairly easy to write it only took two lines of code by the way i found a great example of recursion on its wikipedia page and that's by the process of creating refreshed sourdough so the

recipe calls for some sourdough Left over from the last time the same recipe was made i thought that was a fairly descriptive example of recursion let's move on to level three let's create a recursive method to find a base raised to a given power let's create a power method and we need a base and an exponent let's find it two to the power of eight and then we'll need to define this method private static let's change void to int i to base and j to exponent We need a base case and a recursive case the

base case will be if exponent is less than one we will return one this is our base case our recursive case will be return base times invoke the power method pass in base and exponent Minus one and this is our recursive case and then we will need to display the result system.out.printline two to the power of 8 which is 256. all right everybody so that's recursion it's when a thing is defined in terms of itself we apply the result of a procedure to a procedure and a recursive method is one that calls itself and this

can be a substitute for iteration we Divide a problem into subproblems of the same type as the original and recursion is commonly used within advanced sorting algorithms and navigating trees some of the advantages is that recursive code is easier to read and write and easier to debug however it's sometimes slower and uses more memory so yeah that is recursion if you learn something new be sure to smash that like button leave a random comment down below and well yeah that's recursion in computer science Hey what's going on everybody it's you bro hope you're doing well

and in this video we're going to discuss the merge sort algorithm in computer science so sit back relax and enjoy the show all right what's going on people merge sword merge sword is a divide and conquer algorithm basically what we do is that we will pass an array as an argument to a merge sort function this function is going to divide our array in two we have a left array and a right Array these will be sub arrays and we will copy the elements over from our original array to our two new subarrays and merge

sort is a recursive function so at the end of merge sort we will call merge sort again and pass in our subarrays that we create and again the merge sort function is going to divide our arrays in two by creating a two new subarrays and then copy the elements over and we will stop when our arrays only have a size of one and that's where Sorting then merging come in and with the process of merging and sorting we will create a second helper function named merge merge will accept a total of three arguments our left

subarray our right subarray and the original subarray in which these elements came from merge is going to take these elements and put them back into their original array which they came from in order and we will do the same thing with the next grouping of arrays until all of these Elements are merged back into their original array in which they came from all in order now in practice when we do execute this merge sort function instead of tackling all of these sub-arrays like one layer at a time we will tackle them by one branch at

a time so it's going to look a little something like this where we will start with the leftmost branch and then work our way towards the right so i'll speed up the footage and just give you a rundown of how this works in Practice [Music] [Music] so [Music] [Music] [Music] [Music] and that ladies and gentlemen is the merge sort algorithm the merge sort algorithm has a runtime complexity of big o of n log n it runs in quasi-linear Time along with quick sort and heap sort which we still need to talk about so when working

with large data sets merge sort is faster than insertion sort selection sort and bubble sort but on the other hand the emerge sword algorithm uses more space than a bubble sword selection sword and insertion sort because we need to create new sub-arrays to store elements whereas bubble sort selection sword and insertion sort can sort in place so they use a constant Amount of space to do their sorting unlike with merge sort now let's move on to the hands-on portion of this video and create a merge sort function in code now all right well let's get

started we'll need an array to work with make up some numbers make sure that they're not in order as well as a for loop to iterate over the elements of our array so currently our array is not in order but that's going to change soon let's invoke a merge sword method that we Still need to declare this is going to be a recursive method and we will pass in an array and each time that we invoke this method we will split our array in half create two subarrays and then copy the elements over so let's

create and declare this method private static void merge sort and we'll need a helper method too and we'll name this merge a helper method is just a method that helps another method basically so private Static void merge and there's going to be three parameters within our merge method int left array int right array and int array remember that these are arrays of integers the first thing that we're going to do within our merge sort method is that we need to get the length of our Array so let's cache that within a local variable named length

int length equals array dot length and we'll need a base case too when do we stop recursion if length is less than or equal to one then we shall return and this is our base case basically with this merge sort method we're dividing Our ray in two each time if the length is one there's no longer a need to divide our array further and we'll need to find the middle position of our array int middle equals length divided by two and we'll create two new sub arrays int array left array equals new integer array and

the size is middle and we'll create a write array Integer array right array the size is length minus middle okay now we need to copy the elements of our original array to our left and right arrays so we'll need two indices int i equals zero this will be for our left array and int j equals zero And this is for our right array then let's create a for loop we don't necessarily need to declare a new index here we can just use i so i'm going to add a semicolon our condition is i is less

than length then increment i by one during each iteration so our condition is with an if statement if i is less than middle then we will copy an element from our original array to our left array Left array at index of i equals array at index of i else we will copy that element to our right array else right array at index of j remember that this index is for the right array equals array at index of i Then let's increment j by one okay this is where recursion comes in so outside of this for

loop we will call merge sword again and pass in our left array so we'll consistently divide our array in half we'll begin by dividing the left array then the right array with a separate recursive call so select array then right array and then call merge so with merge we have to pass in our Left array right array and our original array because we'll put the elements back in order left array right array and our original array that we received as an argument so that is it for the merge sort function let's work on merge next

first thing that we're going to do within the merge method is cache the size of our left array and right array within some local variables int left size Equals array dot length divided by two and right size equals array dot length minus left size and then we'll need three indices int i equals zero this is for our original array to keep track of the position L will be in charge of our left array and r will be in charge of our right array and these will be the indices that we're using okay the next part

we're going to check the conditions for merging and we can do this with a while loop so our condition is going to be while l is less than left size And r is less than right size so basically while there's elements within both our left array and right array we will continue adding elements to our original array and we'll need to check to see which element is smaller if left array at index of l is less than right array at index of r Then we will copy the element from our left array to our original

array so we're basically comparing the number on the left to the right and adding whatever number is smaller back to our original array so array at index of i equals left array at index of l then we can increment i Increment l so if the number on the left is not smaller than the number on the right we have to copy the element in our right array to our original array and we can use an else statement else array at index of i equals right array at index of our increment i increment r So there's

probably going to be one element remaining that we cannot compare to another element because there's only one left so let's write a while loop for that condition while l is less than left size then we will take array at index of i equals left array at index of l increment i increment l then we'll need another while loop If r is less than right size we will copy the last right element over array at index of i equals right array at index of r increment i increment r and that should be it let's run this

and our array is now sorted In conclusion everybody the merge sort algorithm recursively divides an array in two sorts them and then recombines them the merge sort algorithm has a runtime complexity of big o of n log n and a space complexity of big o of n so that is the merge sort algorithm if you would like a copy of this code i will post this to the comments section down below and well yeah that is the merge sword algorithm in computer Science hey uh it's you bro hope you're doing well and in this video

i'm going to explain the quick sword algorithm make computer science yep so uh sit back relax and enjoy the show all right quick sort here's how quick sort is going to work we need an array or some other type of collection i have a simple unordered array what we do is that we'll pass our array as an argument into a quick sort function after passing Our array as an argument to the quick sort function we need to pick a pivot there's different variations of quick sort we can either pick a pivot at the beginning the

middle or at the end but with most standard quick sort algorithms we will set the pivot to be at the end of our array what we're trying to accomplish is that we need to find the final resting place of our pivot where is this value going to be and taking a look at this That would be right about here but we don't know that yet so to find the final resting place of this value our pivot here's what we can do we will declare and use two indices j and i j will begin at the

start of our array i will be one less than the beginning of our array and that's going to be important later and we'll need the help of a temporary variable so we can swap some values all we're doing is checking to see if the value at j is less than our pivot if It's greater than our pivot or equal to our pivot we ignore it eight is greater than five we ignore this value and then increment j by one so during that last iteration i did not come into play yet but it will this round

again we check to see if this value is less than our pivot which it is what we do now is increment i then what comes next is that we swap these two values i and j and we'll need the help of a temporary variable so take The value at i assign it to temp take the value at j assign it to i take the value within temp assign it to j then we can move on to the next iteration increment j we check to see if the value at j is less than our pivot which

it is if that is the case we increment i swap these two values We'll repeat this process until j reaches our pivot then we can move on to the next step here's the next step after our index j reaches our pivot we now know where the final resting place of our pivot is gonna be it's i incremented by one so we will increment i then swap the value at index of i with the value at our pivot our pivot is now within the correct place an easy way to tell is that all Elements to the

left of our pivot should be at less than our pivot but they're not necessarily going to be in order and that's fine they'll be organized later all elements to the right of our pivot should be greater than or equal to our pivot and like i said before they probably will not be in order the important thing is that elements to the left should be less than our pivot elements to the right should be greater than that's how we know the pivot's in The correct place now the next step we're going to create two sections two

partitions the first partition will be all the elements from the beginning of our array up until our pivot but not including the pivot and our second partition will be all the elements after our pivot until the end of our array quicksort is a recursive algorithm we need to pass these partitions as arguments into the quick sort function remember that the Quick sort algorithm is a recursive divide and conquer algorithm but unlike with merge sort with merge sort we create new sub arrays with quick sort we will be sorting these arrays in place but we need

to keep track of the beginning and ending indices of these partitions and then it's just a matter of repeating the same steps over again but we're going to instead use these partitions sections of our array i'll give you a Quick demonstration of what the quicksort algorithm is going to look like to completion [Music] do [Music] and that ladies and gentlemen was your visual representation of the quicksort algorithm let's code our own quicksort algorithm just to solidify our understanding of this topic all right people let's create a quick sort Function you'll need an array to work

with place some random numbers within that array and then some way to iterate and display the elements of your array i'm just using a symbol for each loop so after running this of course our array is not yet sorted so before we display the elements of our array let's invoke a quick sort function which we still need to declare defined there will be three arguments our array And the beginning and ending indices of our array so that would be zero for the beginning then to find the ending you can just say array dot length minus

one let's declare this function private static void quick sort and let's rename some of these parameters we have our array of integers named array and this will be the starting index and this parameter will be the ending index so we have indices start and end now the Base case this will use recursion will be if end is less than or equal to start then we will return and this is our base case eventually we won't be able to divide our array any further so that's when we stop and return with our quick sort function we'll

need the assistance of a helper function that we will name partition Let's copy our function declaration paste it and make a few changes so this will return an int the location of our pivot and the function name will be partition and the parameters are the same at the end of our partition helper function we'll return i i will be the location of our pivot but we'll get to that later okay so within our quick sort function we'll need to find the location of where to pivot int pivot and the partition function Will be in charge

of that partition is going to sort our array and find the pivot so all elements to the left will be smaller than our pivot all elements to the right will be larger so pass in our array we're sorting our array in place there's no need to create any sub-arrays we'll just pass in our original array as well as the start and end after we figure out where our pivot's going to be we can pass in each partition recursively back Into the quick sort function so again we will invoke quick sort pass in our array the

start of our left partition and the ending of our left partition and that is where pivot is minus one we do not want to include our pivot and then we will need to use quick sort on the right partition change start to pivot plus one because the pivot is already in place and then the end of our array in this Variation of the quick sort function we will say that pivot is at the end it will always be at the end to begin with int pivot equals array at index of n we'll need two indices

i and j we'll create index i equals start minus one and then we will iterate through our array and this is where we will declare int j our second index int j equals start and we will continue this for loop as long as j is less than or equal to The end of our array minus one then increment j by one what we're going to check is if array at index of j is less than our pivot if one of these elements is less than our pivot we want it on the left hand side of

our pivot any numbers larger than our pivot should be on the right hand side so we will increment i by 1 and do a basic variable swap and we'll need the Help of a temporary variable int temp equals array at index of i array at index of i equals array at index of j lastly array at index of j equals temp this is just a basic variable swap once all elements that are less than our pivot are on the left hand side and all elements that are larger than our pivot are on the right hand

side what we will do now is increment i by one and then insert our pivot into its final Resting place with another basic variable swap so let's copy this code then paste it and make a few changes int temp equals array at index of i that's the same array at index of i equals array at index of end array at index event equals temp and that's it and then make sure you return i at the end that is the location of our pivot then after running this Our array is now sorted via the quick sort

algorithm in conclusion the quicksort algorithm moves smaller elements to the left of a pivot we recursively divide our array into two partitions and pass those partitions as arguments recursively into the quick sort function the runtime complexity of the quicksort algorithm actually varies in its best and average cases it runs in big o of n log n however in its worst case it can run in big o of n squared This is rare and it occurs if the array is already sorted or close to being sorted but most of the time it will run in big

o of n log n and the space complexity of the quicksort algorithm is big o of log n this is due to recursion it uses more space than bubble sort selection sort and insertion sort even though it sorts in place that's because the quicksort algorithm uses recursion we're adding frames to the call stack which takes memory so yeah that is the Quick sort algorithm if you found this video helpful please be sure to smash that like button leave a random comment down below and subscribe if you'd like to become a fellow bro all right what's

going on everybody hash tables a hash table is a collection of key value pairs each key value pair is known as an entry we have two pieces of data the first is the key and the second is the value in this example let's pretend That we're a teacher and we need to create a hash table of all of our students each student has a name and a unique student id number but these can be of any data type that you would like in this example the key will be an integer and the value will be

a string so how do we know at which index to place each of these entries well what we could do is take each key and insert it into a hashcode method the hashcode method will take a key as input plug it Into a formula and spit out an integer this integer is known as a hash now if we're finding the hashcode of an integer in java that's actually really easy the formula is the number itself so the hash of 100 is 100 123 is 123. so on and so forth with the other keys so after

finding the hash of your key now what can we do these numbers are way too large and the size of our hash table is only 10 elements what we'll do next is take each of these hashes and divide Each of them by the capacity the size of our hash table we have 10 elements so take each hash divided by the capacity of our hash table whatever the remainder is we will use the remainder as an index and to find that we will use the modulus operator so 100 divides by 10 evenly the remainder is zero

so 100 modulus 10 gives us a remainder of zero so spongebob's entry we will place at index 0 within our hash table so the hash of patrick's key is 123. 123 modulus 10 Gives us a remainder of 3. patrick's entry will be inserted at index 3 of our hash table so here's a little shortcut if you have a number modulus 10 you could find the remainder and that is the last digit 321 modulus 10 will give us a remainder of 1. sandy's entry will be placed at index one then squidward's entry will be placed at

index five 555 modulus 10 is five and gary's will be at index seven following the same pattern now here's one situation what if Two hashes are calculated to be the same value that is known as a collision and i can best demonstrate that with a separate example in this next example let's say that each key is now a string each entry is a pair of strings we will first need to find the hash of each of these keys so the hash code of a string uses a different formula basically speaking we're going to take the

ascii value of each character within The string and plug it into this formula i went ahead and calculated the hash of each of these strings using this formula of the string hash code method and the next steps are the same as before take each hash divided by the capacity of our hash table and find the remainder so beginning with the first hash 48625 modulus 10 gives us a remainder of 5. spongebob's entry is now at index five within our hash table now patrick's will be at index zero now Here's sandy's sandy's will also be zero

we have a collision both of these entries will be located at the same index so what do we do each of these storage locations is also known as a bucket and the most common resolution for a collision in a hash table is that we will turn each bucket into a linked list if this bucket already has an entry within the first entry we will also add an address to the location of the next entry and keep on adding more if there's More entries within this bucket so in this way this becomes a linked list if

we're looking up a key we first go to the index in which it's located if there's more than one entry we will search linearly through this bucket as if it were a linked list until we find the key that we're looking for so that's the most common resolution when there is a collision but ideally you would want each of these entries to be within their own bucket based on the Hash of squidward's key squidward's entry has an index of nine and gary gary has an index of five and there's another collision we will add the

address of gary's location to the first entry and this bucket becomes a separate linked list this process is known as chaining the less collisions that there are the more efficient that this hash table is going to look up a value ideally you would want each entry to have their own bucket but collisions are possible to Reduce the number of collisions you can increase the size of the hash table but then again the hash table is going to use up more memory then so people usually find a balance between the two so yeah those are hash

tables in theory let's create our own now alright everybody so let's implement a hash table in java so we will need to declare this hash table and list the data types of our key value pairs if we need to store primitive data types we can use The appropriate wrapper class so let's store integers and strings integer and string the integers will be the key is the strings will be the values we'll map student id numbers and student names and i'll name this hash table just simply table equals new hash table there we go so in

java when we create a hash table these have an initial capacity of 11 elements and a load Factor of 0.75 so once 75 of our elements are filled this hash table will dynamically expand to accommodate more elements now you can set a different capacity for your hash table instead of 11 let's say 10 to be consistent with our example in the previous part of this lesson and if you would like to change the load factor you can add that as well instead of 75 let's say 50 so we would pass in a floating point number

So 0.5 then add an f at the end for floating point numbers but in this example let's just keep the load factor consistent so let's start adding some key value pairs to add an element to your hash table use the put method so table dot put and then we will pass in an integer as the key and a string as the value so our first student is spongebob he has a student id of let's say 100 and let's pass in a string for the value Spongebob okay that is our first student so let's add a

couple more from the previous example so we have spongebob patrick with an id of one two three sandy with an idea of three two one squidward with an id of 555 and gary with an id of 777 now to access one of these values you can use the get method of tables so i'll display this within a print line Statement table dot get and i will pass in a key let's get the value at key number 100 so this student is spongebob how can we display all of the key value pairs of a table well

we could use a for loop so i'm going to create a for loop and place this within it so to iterate over the keys of our table this is what we can write we can use an enhanced for loop so we are iterating over integers So the data type is integer key colon so to make our hash table iterable we can get all of the keys from our table and put them within a set a set is iterable so we will iterate over table dot key set method this will take all of our keys and

return a set and a set is something we can iterate over and within our print line statement let's print each key key Plus then maybe i'll add a tab to separate these plus table dot get then pass in whatever our key is okay so after running this this will display all of our key value pairs and if you need to remove an entry well there's a remove method table dot remove then pass in a key let's remove gary So remove the entry with this key 777 and gary is no longer within our table but we'll

keep them in i'll turn this line into a comment now just to get a better understanding of where these key value pairs are being placed let's also display each hash code for each of these elements so preceding our key let's display each hash code i'll precede our key with a tab and let's display each key's hash code Key dot hashcode method if we're using the hashcode of integers this will return the primitive integer value represented by the key that we're passing in if we're using the hashcode method of integers well the hash is going to

end up being the same integer so you can see that these numbers are the same to calculate an index we can follow the hash with modulus operator then the size of our table We set this to originally be 10. so we have gary at index 7 squidward at index 5 patrick at 3 sandy at 1 spongebob at 0. now if our data type was strings we would use a different hashing formula so let's change the data type to string and all of these keys are now strings then let's remove modulus 10 and change the data

type of our for loop to strings string key Okay these are the new hashes for each of our keys this key has this hash number this key has this hash number so on and so forth so different data types will have different hash code formulas now let's calculate the element in which each of these entries is going to be placed by adding modulus the size of our hash table 10. so here are the elements and we actually have two collisions we have a collision With these two keys they're both within bucket five as well as

these two entries so both of these will be placed into bucket zero since there's more than one entry within the same element we will treat this bucket as a linked list and just iterate over it linearly until we reach the key that we're looking for now one way in which we can avoid collisions is to increase the size of our hash table if we set this to the default of 11 and change this to modulus 11 well Then these will be placed within different buckets and you can see that they have changed however we still

have a collision with spongebob and squidward so what if we increase this to 21. do we have any collisions then nope we do not these keys are within their own buckets all right everybody so in conclusion a hash table is a data structure that stores unique keys to values when you declare a hash table you state the data Types of what you're storing and these are reference data types each key value pair is known as an entry and a benefit of hash tables is that they have a fast insertion lookup and deletion of key value

pairs but they're not ideal for small data sets since there's a lot of overhead but they're great with large data sets hashing in the context of a hash table takes a key and computes an integer it utilizes a formula which will vary based on the key as input and its Data type then to calculate an index we follow this formula we take a hash modulus the capacity of our table to calculate an index each index is also known as a bucket it's an indexed storage location for one or more entries they can store more than

one entry in the case of a collision and in case that happens we treat each bucket as a linked list each entry knows where the next entry is located and as we discussed a collision is when a hash function Generates the same index for more than one key less collisions equals more efficiency and the runtime complexity of a hash table varies if there are no collisions the best case would be a runtime complexity of big o of one it runs in constant time in case there are exclusively collisions as in we place all of our

entries within the same bucket it's going to be one giant linked list and the runtime complexity of a linked list is big o of n it runs in Linear time on average the runtime complexity of a hash table will be somewhere within this range so yeah everybody those are hash tables if you would like a copy of all my notes here i'll post them in the comments section down below and well yeah those are hash tables in computer science all right what's going on everybody graphs a graph is a non-linear aggregation of nodes and edges

a node also known as a vertex may contain some Piece of data and an edge is a connection between two nodes there are two types of graphs we're going to discuss undirected and directed an example of an undirected graph could be a social network like facebook each node could represent a user and if one user is friends with another user well we could establish a friendship and edge a connection between these two nodes if two nodes are connected they have what is known as adjacency in this example Larry is friends with patrick and sandy so

larry has adjacency to patrick and sandy patrick is friends with larry sandy spongebob and spongebob is friends with sandy patrick and squidward and squidward is adjacent to only one neighbor spongebob so a social network could be an example of an undirected graph the other type of graph is a directed graph a director graph contains edges that will link one node to another however these are one-way connections in This example node a would have adjacency to node b but not the other way around however it is valid to have one node pointing to another node and

that node could point back to the previous node an example of a directed graph could be a street map let's say you're working on a travel app and each node is a possible destination these single edges could be one-way streets and these double edges could be two-way streets you can move back and Forth between these two destinations there are two popular ways to represent a graph an adjacency matrix and an adjacency list with an adjacency matrix we could create a 2d array or 2d array list one row and one column for each node if we

need to check to see if there is adjacency between two nodes we would first find the index of the node we're beginning at let's say a so we would go to node a and then find the index of the node we're trying to travel to so b so Row a column b if there are no edges this would be zero if there is an edge this would be one so since there's one here within row a column b well there's adjacency from node a to node b but if we take a look at row a

column c this is zero so there's no adjacency between a to c but if there was well we would replace the zero with one then now there are pros and cons with the matrix one of the benefits is that the runtime complexity to locate an edge is big o of One it's constant all we have to do is find two indices so we have to find the row and the column however the space complexity to store a matrix is big o of v squared v as in the number of vertices that we have but you

could also think of that as n and for the number of nodes big o of n squared so since we have five nodes and five columns we would have a total of 25 spaces so the benefits of a matrix is that it's very quick to look up an edge however a matrix uses a lot Of room so it tends to suit graphs that have a lot of edges on the other hand we have an adjacency list an adjacency list is an array or array list of linked lists each element is a separate linked list and

each header within the linked list would contain the address of a node if there's adjacency between one node and another we would add the adjacent node to our linked list so to find adjacency between two nodes we would find the node that We're starting at let's see if b is adjacent to e so we would locate index b and travel this linked list until we find the node that we're looking for that means there's adjacency between nodes b and e even if there's a node that is not adjacent to any neighbors we would still want

to add it to our adjacency list just in case we do update it here are the pros and cons of an adjacency list the time complexity to locate an element is big o of v v as in The number of vertices you can also think of this as n so this would be big o of n to locate an edge we would first access the node that we're beginning at by an index so let's begin at b and we are looking for adjacency between b and e since each element is a linked list we need

to traverse this linked list linearly until we find the node that we're looking for so in that way it's linear however a benefit of a list over a matrix Is that they use less space the space complexity of an adjacency list is big o of v plus e v for the number of vertices aka nodes and e for the number of edges so yeah everybody those are graphs a graph can be used to model a network each node is a piece of data within our network and an edge connects nodes so like i said it's

a popular way to model networks which don't necessarily have any sort of order so yeah that's an intro to graphs and in the next two Topics we'll create our own adjacency matrix and adjacency list hey if you enjoyed this video give it a thumbs up if you have any ideas of where else you could implement a graph let me know in the comment section and of course subscribe if you'd like to become a fellow bro hey yeah everybody it's you bro hope you're doing well and in this video i'm going to show you one way

in which we can create an adjacency matrix and Computer science so sit back relax and enjoy the show alright people so an adjacency matrix an adjacency matrix is a 2d array to store ones and zeros to represent edges between nodes there are different variations you could use booleans so you could say true or false depending if there's an edge or not and basically the number of rows and columns in an adjacency matrix is equal to the number of unique nodes the runtime complexity To check an edge is big o of one it's constant and the

space complexity is big o of v squared so it uses up a lot of space now let's create our own adjacency matrix they're actually fairly simple so i'm going to create two classes graph and node so file new class i will name this graph finish file new class and i will name this class node so let's say that each node has some Data maybe a single character char data and i'll create a constructor node we'll pass in some data when we create a node char data this dot data equals data within the graph class i'm

going to declare a 2d array of integers so integer 2d array and i will name this matrix and within the graph constructor We will instantiate our matrix matrix equals new int now we need to declare a size of this matrix when we construct a graph object let's set up a parameter so int size size will be the amount of notes that we have and the size of this 2d array will be size and size that's why the space complexity is big o of v squared it's the number of vertices squared if we have five nodes

well then the size is Going to be a total of 25 elements now let's declare a few methods public void add node and then we will pass in a node node node and add edge public void add edge then we need two indices a source and a destination and source int destination dst for short we'll need a method to check an edge public and this will return a boolean Value boolean check edge and we'll need a source and destination for parameters and let's create a print method void print okay we'll fill in add a node

a little bit later so let's fill in add edge we will pass in a source and a destination two indices so source will be the row destination Will be the column so what we're gonna do is take our matrix at index of source and destination and set whatever value is in here which will be zero equal to one that means there's an edge between two nodes and that's really it within the check edge method we're going to check within our matrix if a given value is equal to one if it is return true if not

return false so using an if statement let's check to see if matrix at index of source and Destination is equal to one that means there's an edge if there is an edge let's return true else we will return false and that's it okay now before we actually print our graph let's actually create a graph so let's get rid of this graph graph equals new graph and we can add some nodes although this method doesn't do anything quite yet but it will in the future And we need to pass in a size uh so let's pass

in five we'll create five nodes so to add a node type graph dot add node and this is a method that we created and i will pass in an anonymous node or you can use a named one so we have new node and then to create a node we need to pass in some data because that's what we decided on so let's pass in the letter a so this will be node a And we'll create a few more nodes b c d and e and we also can add edges between these nodes to represent adjacency

so to add an edge type graph dot add edge so what we're doing in this example think of each node as having an index number to create an edge between two nodes we will pass in the index number of each node if i need an edge between nodes a and b while each of these has an Index number within our matrix so this first node would have an index of zero and the second node would have an index of one if i need an edge between these two i will add edge between zero and one

and let's create a few others so how about b and c so c would have an index of two and c will have two edges based on the previous video so c will be connected to d so two to three As well as e so two and four d won't have any edges this is a directed graph in this example and e has two edges we have e to a that would be four two zero and e to c four and two now let's print our graph graph dot print and we need to fill in

this method within the print method of the graph class we just have to print our 2d array and we can use for loops for that So this will be the outer for loop and i equals zero we will continue this as long as i is less than the length of our matrix matrix dot length then increments i by one so this will iterate over all of the rows in our matrix and then we need a nested for loop so change i to j within the nested loop whatever index we're on we will take matrix at

index of i dot length this time as the stopping condition And during each iteration of the inner for loop i will use a print statement and i will print matrix at indices of i and j then i'll add a space between each of these oh then when you exit the inner for loop let's print a new line okay and here's our adjacency matrix each row corresponds to a node as well as each column if there's adjacency between two nodes well then there will Be a one at that row and column this next part really isn't

necessary this is kind of the general idea of an adjacency matrix but let's add some headers to the rows and columns within the graph class at the top let's create an arraylist array list and the data type will be node and i will name this nodes when we construct a graph object let's instantiate our nodes arraylist nodes equals new array List and when we add a node we just take our nodes arraylist dot add node and within the print method let's make a few changes so preceding our nested for loops let's print the data found

within each node so it serves as a header and i can use it for each loop for this for every node node in Nodes then let's print the node's data then maybe i'll add a space oh then add a new line okay there we go each column has the data found within each node and let's also do the same thing with each of these rows i think it would look cool before the inner for loop let's do the same thing let's copy this line But this would be it nodes dot get index of i dot

data and let's see how that looks so far okay not too bad but let's add a few spaces so system.out.print and i'll just print two spaces all right there's our adjacency matrix if you're working with more complex data let's say city names i would consider using printf statements instead because you can align Things properly and if you do want to check an edge we did create a check edge method so within a print line statement let's invoke the graph dot check edge method and then pass in two indices so let's see if there's an edge

between nodes a and b so a has an index of zero b has an index of one there is an edge between these two so this will return true there is an edge this time let's check to see if there's an edge between D and c so d has an index of zero one two three and c has an index of two and this returns false there is no edge all right people so that's an adjacency matrix it's an array to store ones and zeros to represent edges the number of rows and number of columns

is equal to the number of unique nodes the runtime complexity to check an edge is big o of one all we need are two indices however The space complexity for an adjacency matrix is big o of v squared take the number of nodes you have and square it so if i have five nodes five squared is 25 we have 25 elements alright so that's an adjacency matrix if you would like a copy of this code i'll post this to the comment section down below and well yeah that's an adjacency matrix in computer science hey what's

going on everybody it's you bro hope you're doing well and in this Video i'm going to explain adjacency lists in computer science so sit back relax and enjoy the show all right what's going on everybody adjacency list an adjacency list is an array or an array list made up of linked lists each element is a separate linked list and each linked list can contain nodes and each linked list has a unique node at the head and basically speaking to represent a graph all adjacent neighbors to a node are added to that Node's linked list if

we add an edge we just add the address of that node to the tail so let's begin let's create two classes graph and node file new class this will be graph finish then file new class node let's say we have some data maybe just a single character char data and we'll create a constructor and then pass in some data Char data this dot data equals data within our graph class we need to create an array list of linked lists array list and the data type of what's going to be stored are linked now we need

a data type for our linked lists what are the linked lists going to store well they're going to store nodes let's name this array list just a list for adjacency list And let's create a graph constructor and we will instantiate our adjacency list a list equals new array list okay let's declare some methods we'll need an add node method so public void add node and there is one parameter a node of the node data type we'll need to add an edge public void add edge We'll need two indices a source and a destination into source

int destination we'll be able to check an edge public void check edge again we'll need a source and destination indices and let's print our graph public void print all right now let's head to our main Class and instantiate our graph graph graph equals new graph we're going to reuse a lot of the same code from the previous topic on adjacency matrices so let's add some nodes graph dot add node and i will pass in an anonymous node new node and we need some data so let's pass in the letter a let's copy this and create

four additional nodes So b c d and e and we need to create some edges again i'm using the edges from the previous topic so graph dot add edge each of these nodes has an index number the first will be zero the second will be one then two three four if i need an edge between Nodes a and b the index in node a is zero that's the source and the destination is b that has an index of one so zero one and let's fill in a few others how about one and two one and

four two three two four Four zero and four two okay so then at the end let's print our graph but we have not yet filled in the methods so graph dot print okay so let's head to our graph class and fill in some of these methods let's begin with add node so in order to add a node we first need to create a new linked list So linked list the data type of this linked list is nodes and let's name this current list equals new linked list after we create this new linked list we can

add a node to the linked list current list dot add node whenever we create a new node we will also create a new linked list and the new node will be at the head of the Linked list and lastly we just need to add this linked list to our array list alist dot add current list okay then let's fill in the add edge method i will declare a linked list and i'll just copy this linked list current list equals to add an edge to our adjacency list we first need to get a linked list from

the arraylist So let's store that within currentlist currentlist equals to access our adjacency list we will type dot get and then an index and that will be source this will return a linked list it's kind of like it's in two layers we'll also need to know our destination node so let's say node destination node equals then we'll need to find the array list That this node is located at the head adjacency list dot get our destination index then follow this with get zero that is the head of our linked list so this is the address

of the node we would like to link to and now we just need to add this node to the tail of our current list current list dot add destination node and that's it we're taking a node and adding it to the tail of a linked list you can shorten this code if you would Like to do so in less steps you would just take this portion and replace current list with alist.getsource then you technically don't need this line but it's a little more difficult to read so you do you okay this time let's check an

edge so we can copy these two lines of code paste it what we're going to do is iterate over our current linked list and see if there's a match between a node and our destination node so let's use a For each loop and we will iterate over all of the nodes within our current linked list so the data type is node node in our current list with an if statement let's check to see if the current node that we're looking at is equal to our destination node are these addresses the same if so then return

true if we escape the for loop that means we did not find the Node we were looking for so let's return false and the return type of this method is going to be boolean okay we have one more method we just need to print our adjacency list we'll use nested for each loops so we need to iterate over all of the linked lists within our array list so for linked list the data type is node and let's name this current List iterate over every linked list in our array list and then we'll need another for

each loop for every node node in current list then let's use a print statement print the node's data then maybe i'll add an arrow for flavor to represent a linked list then outside of our inner for loop let's print a new line and that should be Everything that we need so let's run this all right so there is our adjacency list basically an adjacency list is an array or an array list made up of linked lists each linked list has unique node at the head and all adjacent neighbors to that node are added to the

nodes linked list at the tail the runtime complexity to check an edge is big o of the v for the number of vertices it's because we need to traverse a linked list linearly to Find a matching node and the space complexity for an adjacency list is big o of v plus e v as in the number of vertices e as in the number of edges so yeah that's an adjacency list it's an array or an array list made up of linked lists it's used to represent a graph if you would like a copy of this

code i'll post this to the comment section down below and well yeah those are adjacency lists and computer science alright everybody depth first search Depth first search is a search algorithm for traversing a tree or graph data structure we can break this down into three steps when navigating a graph we will pick a route and we will keep on going until we reach a dead end or a previously visited node if we do then we will move on to step three we will backtrack to the last node that has unvisited adjacent neighbors let's navigate this

maze using a depth first search approach here's the entrance and Here's the exit so the general concept of a death first search is that when we reach more than one adjacent neighbor we're just going to pick a route let's say we prefer right turns over left turns but you can really set any rule that you want when faced with more than one adjacent neighbor i'm just going to pick her out and keep on going and if we reach a dead end then we're just going to backtrack to a node that has some unvisited adjacent neighbors

So there's no more place we can go so we're going to backtrack all the way back to this intersection right here this route is unvisited so we will continue going not backtracking yet there's no dead ends but now there is so we backtrack and keep on going so this is what this looks like sped up and we have reached the end let's use a depth first search approach to navigate this graph maybe we're at Node a and we need to travel to i but we don't know where i is one way in which we can

keep track of our position is to use a stack or in the case of recursion we can use a call stack whenever we visit a node we will push it onto the stack we can either travel to nodes b or d so we will mark d as visited and push this node onto the stack then we can either go to e or g let's go to g we'll push that onto the stack then h E and now we circle the round back to d but d is already marked as visited so we're going to backtrack

to a node that has unvisited adjacent neighbors which is a so we will pop all of these nodes off of the stack all the way back to a which has unvisited adjacent neighbors and this time we will go down this route and push all of these nodes onto our stack And we have reached the end using a depth first search approach when simplified you pick a route you keep going when you reach a dead end or a node you already visited you backtrack to a node that has unvisited adjacent neighbors and you repeat steps one

through two all right well let's implement this in code now and here we are people so i'm going to be using a graph that utilizes an adjacency matrix if you're using an Adjacency list the code's just going to be a little bit different but the concept is really still the same i'm using code from the previous few videos we have a node class a graph class and in the previous videos we've already populated this graph with nodes and edges and then i'm just going to print this this is my adjacency matrix now within the graph

class we're going to create a depth first search method and a helper method so this will be public Void and we will name this depth first search and there will be one parameter an index of where we would like to begin to keep track of the nodes that we've already visited what some people like to do is that they will create a boolean within their node class such as boolean visited and they'll just mark it as false or true however it's very easy to forget to change these back to false When you exit the depth

first search so what i'm going to do instead is create an array of booleans and the size will be equal to the length of the matrix so let's create a boolean array and i will name this visited equals new boolean and the size of our array is the length of our matrix then lastly we will implement a helper function so let's name this dfs helper And we will pass in our source and our boolean array visited then we just need to create this method private void dfs helper and there are two parameters int source and

an array of booleans named visited you can either implement a depth first search iteratively using a stack or you can utilize the call stack if you use recursion in this example we're going to use recursion when we invoke this helper function we're going to check to see if The current node that we're on is visited or not and we can use an if statement if our visited array at index of source is equal to true or you could write the shorthand and just say if visited at index of source since this returns a boolean value

if we've already visited this node we're going to return else we will mark this node as visited else Visited at index of source equals true if you would like although this part's not necessary within my console i'm just going to print that we visited this node so within a print line statement i do have my nodes within an arraylist i'm just going to access the data of one of these nodes dot get source dot data Plus equals visited this part technically isn't necessary but it's going to help with my demonstration in this example maybe we

start at node a we need to find any adjacent neighbors if we're using an adjacency matrix we need to iterate over this row we can use a for loop for that so into i equals zero we will continue this as long as i is less than our matrix At index of source dot length this equals the length of a row and then increment i by one we're checking to see if one of these elements is a one that means that's an adjacent neighbor that we can travel to using an if statement if matrix at indices

of source and i source is the row that we're working with i is the column if this is equal to 1 then we will invoke the dfs helper method again so this is recursive we will pass in i as well as our boolean array named visited if we successfully search through an entire row outside of the for loop let's return and that's it so let's run this within my main class i will call the graphs depth first search method and pass in an index of a starting node so let's begin At zero we visit a

first then b c d e let's try b which has an index of one b c d e a c which has an index of two c d e a b okay now pay attention to this this is a directed graph and we're beginning at d there's no place that we can go so we're stuck at d we only visit d and lastly we have e which has an index of four E a b c d alright everybody that is the depth first search algorithm you pick a route you keep going if you reach a

dead end or an already visited node you backtrack to a previous node with unvisited adjacent neighbors if you would like a copy of this code i'll post this to the comment section down below don't forget to give this video a thumbs up leave a random comment down below and subscribe if you'd like to become a fellow bro All right what's going on people breath first search breadth first search is a search algorithm for traversing a tree or graph data structure this is done one level at a time rather than one branch at a time like

what you see with depth first search here's an example in the previous topic on depth first search we would navigate a graph one branch at a time but in a breadth-first search approach we would navigate this graph one level at a time so let's begin at Node a and we are attempting to travel to node i instead of a stack we'll use a queue all unvisited nodes we will add to the queue so we're currently at a we'll add that to the queue then add any unvisited adjacent neighbors to the queue as well we have

both b and d as neighbors so we will add these to the q then add any unvisited adjacent neighbors of nodes b and d that means we will add c E and g and for the next level we have f and h and lastly i so that is a breadth first search approach we will navigate a graph one level at a time using a queue rather than one a branch at a time using a stack like with depth first search let's implement this in code now okay everyone so in my graph i'm utilizing an adjacency

matrix we're Reusing the same code from the previous few videos and we have a node class that contains some data and i went ahead and populated this graph already it's the same data from the previous few topics heading to our graph class let's create a breadth first search method public void breadth first search and we will take an integer name source This will be the index of the node we would like to begin searching at and with a breadth first search we can utilize a q so q we will store integers these will be indices

and i will name this q equals new now queues are actually interfaces we need to use a data structure that utilizes the queue interface one of Which is a linked list okay so we have our queue and we're going to create an array of booleans to mark if a node has been visited or not so let's create a boolean array named visited equals new boolean and the size will be matrix dot length with the node that will begin at let's add that to the queue q dot you can use add or offer And then pass

in the index of the starting node then within the boolean array of visited we will mark this as true at index of source equals true and now we'll need a while loop our condition is that we'll continue this while loop while the q's size method does not equal zero we'll assign our Source equal to whatever is at the front of the queue q dot pull to remove an element with this code that i've written i've already went ahead and created an array list of the nodes to access the data whenever we pull a node i'm

going to display the data so this part technically isn't necessary nodes dot get source dot data plus Equals visited let's say that we're at node a we're going to iterate over this row and look for any adjacent neighbors so let's use a for loop for that four and i equals zero we will continue this as long as i is less than our matrix at index of source dot length this means the length of the row then i plus plus during each iteration let's check to see If this value is 1 and the node that we're

trying to visit has not already been visited if then matrix at indices of source and i is equal to one and visited at index of i is not true so we can use the not Logical operator if we have an adjacent neighbor that's not been visited then we will add the index to the queue and that node is going to wait in line q dot offer i and i is an index and then mark this note as visited so take our boolean array visited at index of i set the sequel to true and there we

go let's invoke the breadth first search of Our graph class then pass in an index of a node we would like to begin at in this example node a has an index of zero b is one c is two so on and so forth so let's perform a breath first search beginning at node a we will cover these nodes in this order a b c e d let's change this to 1 that would be node b b c e d a 2 is c c d e a b 3 is d we can't go anywhere

from node d so only d is visited and e e a c b d now before we wrap things up here are the differences between breadth and depth-first searches breadth traverses a graph level by level depth traverses a graph branch by branch breadth utilizes aq depth utilizes a stack breadth tends to be better if the Destination is on average close to the start and depth tends to be better if the destination is on average far from the start in a breath first search siblings are visited before children in a depth first search children are visited

before siblings and if you ever plan on creating video games depth first searches tend to be more popular than breadth first searches alright everybody that is the breadth first search if you would like a copy of this code i'll post This to the comment section down below don't be afraid to give this video a thumbs up drop a random comment down below and subscribe if you'd like to become a fellow bro all right everybody here's a quick introduction to trees in this video we're only going to cover some of the terminology a tree is a

non-linear data structure where nodes are organized in a hierarchy this could be one example of a tree it's made up of nodes and edges Nodes could be some piece of data and edges represent a relationship between two nodes a real-life example of a tree could be a family tree maybe we're at no d that's us or me or you b is a parent e is your brother or sister a is a grandparent c could be an aunt or uncle and f is your cousin a few examples of where a tree data structure would be used

in programming or technology would be file explorers databases domain name servers And the html document object model the top of the tree is known as the root node the root node doesn't have any incoming edges only outgoing edges any nodes at the bottom of a tree are known as leaf nodes they do not have any outgoing edges but they do have incoming edges and branch nodes are in the middle they have incoming and outgoing edges here's a few other terms any nodes with outgoing edges are also known as parents any node with an incoming edge

is known As a child node and nodes can be both parents and children if they have both incoming and outgoing nodes any two children that share the same parent are known as siblings nodes d and e both share the same parent of b so d and e are both siblings the same thing goes with b and c nodes b and c share a as a parent so these two nodes are siblings it's just like a family tree a sub tree is a smaller tree held within a larger tree you could say that this portion is

A sub-tree the size of a tree is equal to the number of nodes so what's the size of this tree we have one node two three four five six the size of this tree is six six nodes the depth of a node is the number of edges below the root node our root node would have a depth of zero then as we move down levels b and c have a depth of one D e and f have a depth of two and lastly the height of a node is the number of edges above the furthest

leaf node all of these leaf nodes are the same distance away from the root node these would all have a height of zero b and c have a height of one and a has a height of two well all right then everybody that is a quick introduction to some of the terminology around trees it's a non-linear data structure where nodes Are organized in a hierarchy and in the next few topics we'll get a little more in depth with trees if you found this video helpful please help me out by smashing that like button leave random

comments down below and subscribe if you'd like to become a fellow bro all right what's going on everybody in this video we're going to discuss binary search trees but first we'll need to know what a binary tree is a binary tree is a tree where each node has no more Than two children that's why it's binary in this example node one has two children two and three and each of these children have their own children they have no more than two children nodes four and five are the children of two and nodes six and seven

are the children of three in the similar example this would also be a binary tree node 3 only has one child node 6 but with a binary tree no node has more than 2 children since node 3 has one child that's fine But if node 3 had three children well that would no longer be a binary tree now what makes a binary search tree different from a binary tree is that the values are arranged in a certain order here's the order the root node should be greater than the left child but less than the right

child four is greater than two and four is less than six that's the pattern that this data structure is built around if we take a look at some of the sub trees let's say This one two is greater than one but less than three and in this subtree six is greater than five but less than seven if done correctly starting at the root node the left most child should be the least value and again starting from the root node the rightmost child should be the greatest value the reason that these nodes are arranged this way

is for quick lookup let's say we're looking for five What we'll do is compare five to the root node if 5 is equal to the root node well then we found our answer if 5 is greater than our root node we will move down to the right branch and do the same thing again is 5 equal to 6 no it's not however it's less than 6 so we know to go down at this branch the runtime complexity to find a value within a binary search tree is big o of log n in its best case

so let's code a binary search tree now Okay let's begin let's create a node class file new class i will name this node and finish nodes will have some data maybe an integer this time int data and the node class should contain at most two nodes node left for the left child and node right for the right child if a node is a leaf node well then these will be null but we would still like to allocate space to hold children And within the constructor we will pass in some data int data and assign it

this dot data equals data now let's create a binary search tree class file new class binary search tree and within our main class let's instantiate a binary search tree object binary search tree i'll name this tree Equals new binary search tree and within the binary search tree class each binary search tree should have a root node node root here are some methods we'll need an insert method to insert nodes public void insert and there is a parameter of a node node Node now let's create a second method this next method will be a helper method

of the insert method so the insert method is going to call its helper method and this will be private the return type is node insert helper we need a root node node root and a node Node node in order for a program to compile we do need to return something so just as a placeholder i'm going to return null okay for the next method we need a display method public void display and helper method private Void display helper and this has one parameter a root node node root next method is a search method public boolean

we're returning a boolean search and the parameter is int data and we will need a helper method Private boolean search helper there are two parameters node root and int data again we do need to return something i'm going to return false just as a placeholder okay next method is a remove method Public void remove and the parameter is int data and we'll need a helper method the return type is node remove helper the two parameters are node root and int data we do have to return something so as a placeholder i'm going to return null

our remove helper method is also going To rely on two separate methods one to find a successor and another to find a predecessor this is in case we're deleting nodes we have to shift nodes around so this will be private int successor and we will pass in node root and we need to return something let's return 0 as a placeholder and let's copy This paste it and this will be method predecessor and that will be it so let's close these for now and begin with the insert method so with the insert method we will assign

our root node equal to insert helper method pass in our root node and node so the reason that we're using helper methods is that we'll be using recursion So it's a lot easier to use recursion if you have a helper method within the insert helper method let's declare int data equals our nodes data node is the node that we're passing in to insert so let's check to see if our root node is assigned or not so if our root is equal to null then we should probably assign this node To the root node because well

this is the first node root equals node return root if root is not null we have to compare the data to see if it's less than our root or greater than our root else if our data is less than the data of the root node then we are going to assign this node as the left child of our root node Are roots left child root dot left equals and we will use recursion insert helper method pass in our roots left node and our node the root node is going to change with recursion at first it's

going to be the root node of the entire tree after recursion we're examining the root node of a subtree So if we're passing in the left child of the original root node well then that left child is now the root node of a subtree that we're currently working with so else if the data is less than the current root node we go left if it's greater than the root node then we will go right else root dot right that's the right child equals insert Helper method pass in root dot write and our node and it's

the same process all over again and at the end we will return the current root node okay that is it for the insert method and the insert helper method so let's insert a few nodes although we can't yet display them Let's insert some anonymous nodes tree dot insert and we can pass in a node either a node name or an anonymous node so let's pass in some anonymous nodes uh let's pass in the number five or some other number of your choosing and let's pass in a bunch of numbers how about one and nine make

sure these are not in order seven and three six four and maybe one more Eight if you run and compile this there is nothing obvious that really happens so let's work on a display method next so with the display method we will invoke our helper method display helper pass in the root node within the display helper method we're going to check to see if the root node of our subtree does not equal no so if root does not equal no if you would like to display these in Order we can use in order traversal and

that uses recursion so invoke the display helper method pass in the root child's left node root.left if we're using recursion the first piece of data that's displayed is the least value and these values will be displayed in increasing order technically the term is non-decreasing but think of it as ascending order so the very first value is going to be the least one followed by the root node of This subtree system.out.printline root.data in our first subtree the data all the way to the left is one and the root node of that subtree is two then we

need the right child which should theoretically be three so again we'll invoke the display helper method and pass in the right child so this is in order traverso all of the nodes will be displayed in non-decreasing order so let's try this at the end of our main class let's Invoke tree dot display and see what happens yeah there we go all of the nodes within our binary search tree are now in order if you would like this in reverse order you can just change these methods around replace left with right and right with left and

these are now in decreasing order but let's change that back okay up next we have the search methods Okay search will return then invoke the search helper method pass in our root node as well as some data within the search helper class we'll check to see if root is equal to null that means our tree is empty so of course we can't search for anything return false Then add else if our root dot data is equal to data that means we found the data that we're looking for there's a match then we're going to return

true we found what we're looking for else if our roots data is greater than our current data that we're looking for that means we need to go left So return then invoke the search helper method pass in the left child root dot left and the left child is now the root node of the subtree and then you need to pass in data as well else we go right so copy this paste it return search helper root dot write and data and we can get rid of this return statement at the bottom Okay let's try this

so at the end of my main class let's use a print line statement and i will type tree dot search and let's search for xero none of my nodes have zero as a piece of data so this should return false let's search for one now that returns true there's a one within one of my nodes what about nine that is also true And let's try ten and that is false okay so those are the search methods and lastly we have the remove methods as well as successor and predecessor now these methods are going to be

a little bit tough but i'll try my best to explain it so within an if statement let's check to see if this data even exists first so let's invoke the search method and pass in our data so this returns a boolean true or false if we do Find the data that we're looking for then let's invoke the remove helper method pass in our root node as well as our data then within an else statement and this part's optional let's let the user know that we can't find that data data plus could not be found so

just to test things real quick i'm Going to remove some data that doesn't exist tree dot remove zero zero cannot be found now let's move on to the remove helper method the first thing that we'll do is check to see if our root node is equal to null if our root node is equal to null then let's return the root node then within an else if statement let's Check to see if the data that we're trying to remove is less than the data of our root node if it is we need to go left down

the binary tree root dot left equals then invoke the remove helper method pass in the left child of the root node root.left as well as our data so we're going to go as far left as we can then add an else if statement Else if data is greater than the data of the root node then we will go right so let's copy this paste it root dot write equals remove helper pass in root dot right as well as our data then add an else statement if we reach the else statement that means that we have

found our node and i'll just add a note to explain that if the node we're trying to remove has children that kind of complicates things Then we have to shift the nodes around but first let's check to see if it's a leaf node then that's really easy within an if statement we will check to see if the left child is equal to null and the right child is also equal to null that means that the node that we're trying to remove is a leaf node and that's really simple we don't need to Shift any nodes

around we can just set this current root node equal to null however if the node we're attempting to delete has a right child will have to shift those nodes around and find a successor else if root dot right does not equal no that means there's a right child and we need to find a successor to replace this node So we will assign root dot data is equal to the successor method which will find a successor for us and pass in the current root node then take root dot right equals and invoke the remove helper method

pass in the right child root.right as well as root dot data so when we delete a node that will Create a gap and if there's a child well we don't want that child to be lost we don't want that child to become an orphan so we will link a child to that spot where we deleted a node now if there's a left child we have a slightly similar procedure so we can use an else statement take root.data and invoke the predecessor method take this line of code paste it root dot left equals remove helper method

pass in The left child of the root node this else statement will find a predecessor to replace this node and at the end we will return root so we can close out of these two methods and we can open up the successor and predecessor methods what we're doing with the successor method is that we're attempting to find the least value Below the right child of this root node we will assign the current root node equal to root dot right then within a while loop we will take root dot left and check to see if it

is not equal to null while this condition is true take root set the sql to root dot left And at the end return root dot data so what's happening here within the remove helper method if the node we're trying to delete has a right child we need to find a successor to fill in that gap and that successor should have the least value so we will go right and look as far left as we can because values on the left are less than the root numbers on the right are greater than our root after going

Right we will go as far left as we can to get the lowest value then return it so that's what we're doing when we're assigning a successor to fill in that gap when we delete a node that has children and then the predecessor method is going to be very similar we will find the greatest value below the left child of this root node so we can copy all of this paste it this time we will go left Then go as far right as we can go i do apologize this is a lot to take in

recursion can be very confusing but yeah that's everything let's attempt to remove a node so before we display our tree let's take tree dot remove then pass in the data of a node you would like to remove let's remove one and here are the remaining nodes we have two through nine all in order let's remove five okay one two three Four six seven eight nine let's remove nine nine is no longer there and let's remove a node that is not within here like zero zero cannot be found alright then everybody that is a binary search

tree just so you're aware the order in which you insert nodes into a binary search tree does matter if it's unbalanced technically my tree follows all the rules however it's fairly lopsided there is a way to balance Binary trees but that's a topic for avl trees that's why the runtime complexity has a best case scenario of big-o of log n but a worst case scenario of big o of n depending on how balanced it is but basically a binary search tree is a tree data structure where each node is greater than its left child but

less than its right the benefit of a binary search tree is that it's easy to locate a node when they are in order so yeah those are binary search trees if you Would like a copy of this code i'll post this to the comment section down below don't be afraid to smash that like button leave random comments down below and subscribe if you'd like to become a fellow bro hey y'all everybody so let's talk about tree traversal tree traversal is the process of visiting all the nodes of a tree we don't have random access so

we begin at the root node and follow a certain procedure to visit all of the Nodes of a tree and there's three that we're going to talk about in order post order and pre-order traversal in this example we will be working with a binary tree not a binary search tree because these values are not in binary search tree order so each node has at most two children a left node and a right node let's begin with an in-order traversal here's a recursive method that will navigate a tree in order using recursion we visit as many

left nodes as we can Followed by the root node and then any right nodes the entry point is always the root and using recursion we will go as far left as we can so we go from a to b to d so we will mark this node as visited then visit the root node next and then the right node since we can't go left anymore we're going to visit the root node a all that's left is to go right so we will go to c However we can go left so we will visit f first

then c then g so this is in order traversal when used in the context of a binary search tree we will visit all of these nodes in non-decreasing order so again that was d b e a F c g we go left root right and here's that method again and here's post order traversal it's used to delete a tree from leaf to root and we follow this pattern left right root we will use recursion to visit the left children then the right children then the root so a is our entry point we are going as

far left as we can go from a to b to d Mark d is visited then we go right using recursion go from d to e then root left right root so we go back up go as far right as we can unless we encounter a left child which we did so we will mark f as visited then g right root left right root and all that's left is the root node So that is post order traversal it's used to delete a tree from leaf to root and lastly we have pre-order traversal pre-order traversal is

used to create a copy of a tree we visit any root nodes first then left then right so we will mark a as visited our entry point then visit the left child and we will continue to go left then go right so we can't go left anymore we're going To go right mark the root as visited then left then right this is used to create a copy of a tree but in order to create a copy of a tree you need to create a root node and a branch node to hold the leaves so again

that's root left we're still going left right root left Right a b d e c f g that is pre-order traversal it's used to create a copy of a tree well okay then everybody that is a few ways in which we can traverse a tree like i said normally we don't have random access so the entry point is the root node and you can either follow an in order in-order post-order or pre-order traversal Depending on what you need to do with this tree so that's tree traversal and computer science if you liked this video please

be sure to give it a thumbs up leave a random comment down below and subscribe if you'd like to become a fellow bro hey everybody in this video i thought i would show you all how you can get the runtime of a program i thought it might be useful now that we know how data structures and algorithms work for the Most part so within the entry point of your program you'll need the start time and we'll store this within a long data type i'll name the start equals then type system dot nano time a nano

second is a billionth of a second and then we have our program whatever it is and then at the end of our program we will get the duration this will be of the long data type Duration equals and then we need the current time system dot nano time minus our start time this returns a time in nanoseconds if you need milliseconds you can divide this number by 1 million okay then let's print the duration system.out.print line duration plus milliseconds or some other unit to Measure time okay so with our program let's just have the main

thread sleep for maybe three seconds whatever it is you want to do and we will sleep for three thousand milliseconds and here we go so we will wait for three seconds and we are done this program took 3014 milliseconds to complete when you enter your program get the start time at the end of your program Get the current time minus the start time then depending on the units you're using you may need to divide this number by a million or if you need this in seconds you would divide this by 1 billion so yeah that's

how to calculate the run time of a program if you found this video helpful please be sure to smash that like button leave a random comment down below and subscribe if you'd like to become a fellow bro hey you yeah i'm talking to you if you Learned something new then help me help you in three easy steps by smashing that like button drop a comment down below and subscribe if you'd like to become a fellow bro [Music] you