Data Structures and Algorithms in Java

Data Structures and Algorithms in Java


Hi guys! Mosh here! Today, we’re gonna
talk about the basics of data structures and algorithms which is one of the
topics that come up in coding interviews all the time. In fact, more and
more companies ask questions about data structures and algorithms to see if you
can think like a programmer in this video we’re going to talk about the
basics of data structures on algorithms we’ll be talking about Big O notation
arrays and linked lists after watching this video if you want to learn more I
encourage you to enroll in my ultimate data structures and algorithms course
the link is below this video now to watch this video you don’t need any
prior knowledge of data structures on algorithms but you need to know the
basics of programming in this video I’ll be using Java but if you don’t know Java
that’s perfectly fine you can code in your favorite programming language if
you enjoyed this tutorial please support me by liking and sharing it with others
also be sure to subscribe as I regularly upload near videos all right now let’s
jump in and get started before we talk about data structures and
algorithms we need to talk about the Big O notation we use the Big O notation to
describe the performance of an algorithm a lot of people find Big O scary but
don’t worry I’m gonna make it super simple for you so let’s jump in and get
started so what is this Big O all about well let’s start with the classic
definition on Wikipedia Big O notation is a mathematical notation that
describes the limiting behavior of a function when the argument tends towards
a particular value or infinity huh that’s the reason why a lot of people
find Big O scary but as you will see in this section the underlying concepts are
actually not that hard we use Big O to describe the performance of an algorithm
and this helps us determine if a given algorithm is scalable or not which
basically means is this algorithm going to scale well as the input grows really
large so just because your code executes quickly on your computer doesn’t mean
it’s gonna perform well when you give it a large data set so that’s why we use
the big o notation to describe the performance of an algorithm now what
does this have to do with data structures well as you will learn in
this course certain operations can be more or less costly depending on what
data structure we use for example accessing an array element by its index
is super fast but arrays have a fixed length and if you want to constantly add
or remove items from them they have to get resized and this will get costly as
the size of our input grows very large so if that’s what we need to do then we
have to use another data structure called a linked list these data
structures can grow or shrink very quickly but accessing a linked list
element by its index is slow so that’s why you need to learn about the Big O
notation first before we can talk about various data structures also big
companies like Google Microsoft and Amazon always ask you about Big O they
want to know if you really understand how scalable an algorithm is and finally
knowing Big L will make you a better developer or software engineer so over
the next few videos we’re going to look at
code snippets and use the Big O notation to describe the performance of our
algorithms you here’s our first example this method
takes an array of integers and prints the first item on the console it doesn’t
matter how big the array is we can have an array with 1 or 1 million items all
you’re doing here is printing the first item so this methyl has a single
operation and takes a constant amount of time to run we don’t care about the
exact execution time in milliseconds because that can be different from one
machine to another or even on the same machine all we care about is that this
method runs in constant time and we represented using the Big O of one this
is the run time complexity of this method so in this example the size of
our input doesn’t matter this method will always run in constant time or Big
O of 1 now what if we duplicate this line here we have two operations both
these operations run in constant time so the runtime complexity of this method is
Big O of 2 now when talking about the runtime complexity we don’t really care
about the number of operations we just want to know how much on an algorithm
slows down as the input grows larger so in this example whether we have 1 or 1
million items our method runs in constant time so we can simplify this by
writing down o of 1 meaning constant time let’s look at another example next
you here we have a slightly more complex
example have a loop so we’re iterating over all the items in this array and
printing each item on the console this is where the size of the input matters
if you have a single item in this array we’re gonna have one print operation if
you have a million items obviously we’re gonna have a million print operations so
the cost of this algorithm grows linearly and in direct correlation to
the size of the input so we resent the runtime complexity of this method using
the Big O of n where n represents the size of the input so as n grows the cost
of this algorithm also grows linearly now it doesn’t matter what kind of loop
used to iterate over this array here we’re using a traditional for loop we
could also use a for each loop for example for int number in numbers we
could simply print the number we’re still iterating over all the items in
this array we could also use a while loop or a do-while loop now what if we
have a print statement before and after our loop what do you think is the
runtime complexity of this method well you saw that this single operations
running constant time so here we have the Big O of one our loop runs in Big O
of n and once again we have the Big O of 1 so the run time complexity of this
method is o of 1 plus n plus 1 which we can simplify to or of 2 plus n however
when using the Big O notation we drop this constants because they don’t really
matter here’s the reason if our array has 1 million inputs
adding two extra operations doesn’t really have a significant impact on the
cost of our algorithm the cost of our algorithm still increases linearly so we
can simplify this by dropping this constant what matters is that the cost
of this algorithm increases linearly and in direct proportion to the size of our
input if you have five items in the input we’re gonna have five operations
if you have a million we’re gonna have a million operations
now what if you had two loops here so let me delete these print statements and
duplicate this loop what do you think is the runtime complexity of this method
it’s gonna be big-oh of n plus n or Big O of 2n this is another example where we
drop the constant because all we need here is an approximation of the cost of
this algorithm relative to its input size so N or 2n still represents a
linear growth now what if this method had two parameters an array of numbers
and an array of names so first we iterate over the area of numbers and
then we iterate over the array of names like this what do you think is the
runtime complexity here well both these loops run in O of n but here’s a tricky
part what is n in this case we’re not dealing with one input we have two
inputs numbers and names so we need to distinguish between these two inputs we
could use n for the size of the first input and M for the size of the second
input so the runtime complexity of this method is going to be o of n plus M and
once again we can simplify this to O of n because the runtime of this method
increases linearly you in the last video you learn that simple
loops running linear time or Olaf n but here we have nested loops this is the
algorithm that we use for printing all combinations of items in an array so
what is the runtime complexity here well let’s find out in our outer loop we’re
iterating over our input array so here we have o of n now in each iteration
once again we’re iterating over all the items in this array another example of
oh of n so the runtime complexity of this method is o of n times N or N
squared we say this algorithm runs in quadratic time as you can see in this
diagram algorithms that run in O of N squared gets slower than algorithms that
run in O of n of course this depends on the size of the input if you’re dealing
with an array of let’s say 50 items we’re not gonna see any differences but
as our input grows larger and larger algorithms that run in O of N squared
get slower and slower now what if you had another loop before or after this
loop for example let’s add a for loop and once again iterate over all the
items in this array and print them on a console what is the runtime complexity
of this method well here we have o of n so the runtime complexity of this method
is gonna be o of n plus N squared now once again we can simplify this this
square of this number is always greater than the number itself right so in this
expression N squared always grows faster than n again use the Big O notation to
understand how much the cost of an algorithm increases all we need is an
approximation not as an exact value so here we can drop in and conclude that
this method runs in O of N squared let’s look at another example what if instead
of this loop we had another nested loop here so for end of third in numbers
there you go the run time complexity is now o of n
cubed you can imagine this algorithm gets far
slower than an algorithm with o of N squared
you another growth rate we’re gonna talk
about is the logarithmic growth which we show with the Big O of log n here’s the
logarithmic curve now compare this with a linear curve as you can see the linear
curve grows at the same rate but the logarithmic curve slows down at some
point so an algorithm that runs in logarithmic time is more efficient and
more scalable than an algorithm that runs in linear or quadratic time let’s
see a real example of this let’s say we have an array of sorted numbers from 1
to 10 and we want to find the number 10 one way to find the 10 is to iterate
over this array using a for loop going forward until we find the 10 this is
called a linear search because it runs in linear time in the worst case
scenario if the number we’re looking for is at the end of our array we have to
inspect every cell in this array to find the target number the more items we have
the longer this operation is gonna take so the run time of this algorithm
increases linearly and in direct proportion with the size of our array
right now we have another searching algorithm called binary search and this
algorithm runs in logarithmic time it’s much faster than the linear search
assuming that our array is sorted we start off by looking at the middle item
it’s this item smaller or greater than the value we’re looking for it’s smaller
so our target number in this case 10 must be in the right partition of this
array right so we don’t need to inspect any of the items in the left partition
and with this we can narrow down or search by half now in the right
partition again we look at the middle item is it smaller or greater than the
target value it’s smaller so again we ignore the items on the left and focus
on the items on the right so in every step we’re essentially narrowing down or
search by half with this algorithm if we have 1 million items in our array we can
find the target item with a maximum of 19 comparisons we don’t have to inspect
every item in our array this is logarithmic time in action we have
lovers meet growth in algorithms where we reduce our work by half in every step
you’re going to see this a lot in the second part of this series where we talk
about trees and graphs unfortunately I cannot show you an
example of this in code now because it’s a bit too complex there are a few things
we have to talk about before you are ready to see that in code but trust me
you’ll see that in the code in the future and it’ll become super easy for
now all I want you to take away is that an algorithm with logarithmic time is
more scalable than one with linear time you the last growth rate we’re going to talk
about in this section is the exponential growth which is the opposite of the
logarithmic growth so the logarithmic curve slows down as the input size grows
but exponential curve grows faster and faster obviously an algorithm that runs
in exponential time is not scalable at all it will become very slow very soon
again I cannot show you an example of this in code yet we’ll have to look at
it in the future for now all you need to understand is that the exponential
growth is the opposite of the logarithmic growth and by the way these
growth rates we have talked about so far are not the only growth rates but these
are the ones that you see most of the time there are some variations of these
that we look at in the future for now just remember these five cares
you you have seen how we can use the Big O
notation to describe the runtime complexity of our algorithms in an ideal
world we want our algorithms to be super fast and scalable and take minimum
amount of memory but unfortunately that hardly if ever happens it’s like asking
for a Ferrari for ten dollars it just doesn’t happen most of the time we have
to do a trade-off between saving time and saving space there are times where
we have more space so we can use that to optimize an algorithm and make it faster
and more scalable but there are also times where we have limited space like
when we build an app for a small mobile device in this situations we have to
optimize for this space because scalability is not a big factor only one
user is going to use our application at that moment not a million users so we
need a way to talk about how much space an algorithm requires and that’s where
use the Big O notation again let’s look at a few examples here we have this
greet method that takes an array of strings and prints a high message for
every name in this array now in this method we’re declaring and loop variable
and this is independent of the size of the input so whether our input array has
10 or 1 million items this method will only allocate some additional memory for
this loop variable so it takes all a one space now what if we declare is string
array like this we call it copying and initialize it like this
so the length of this array is equal to the length of our input array so if our
input array has a thousand items this array will also have a thousand items
what is the space complexity of this method it’s all of n the more items we
have in our input array the more space our method is gonna take and this is in
direct proportion to the size of our input array that’s why we have oh of n
here and by the way when we talk about space complexity we only look at the
additional space that we should allocate relative to the size of the input we
always have the input of size n so we don’t count it we just analyze how much
extra space we need to allocate for this algorithm so that’s all about space
complexity in this course we’ll only focus on runtime complexity because
that’s a bit more tricky but from now on think about the space complexity of your
algorithms especially in situations where you have limited space see if
there are ways to preserve the memory hey guys Marcia I wanted to let you know
that this video is actually part of my ultimate data structures and algorithms
course the complete course is 13 hours long and I’ve divided it into three
parts so you can take and complete each part easily if you’re serious about
learning data structures and algorithms I highly encourage you to take this
course and learn all the essential data structures and algorithms from scratch
it’s much easier and faster than jumping from one tutorial to another we’ll be
talking about various types of data structures such as linked lists stacks
queues hash tables binary trees AVL trees heaps tries graphs and various
types of sorting searching and string manipulation algorithms the course is
packed with almost 100 interview questions these are the interview
questions that get asked that companies like Google Microsoft and Amazon you can
watch the course online or offline anytime anywhere as many times as you
want and you would also get a certificate of completion and a 30-day
money-back guarantee it’s exactly like this tutorial it just has more content
if you’re interested click on the link below this video to enroll in the course
thank you and have a great day in this section we’re going to talk about our
very first data structure and one that you’re probably familiar with arrays
arrays are built into most programming languages and we use them to store a
list of items sequentially in a section first we’re going to look at various
strengths and weaknesses of our race then I’m gonna show you how to use
arrays in Java and finally we’re gonna build an array class from scratch this
is a fantastic exercise for you to get your hands dirty in the code and get
prepared for more complex data structures so do not skip this section
even if you know arrays well so let’s jump in and get started arrays are the simplest data structures
and we use them to store a list of items like a list of strings numbers objects
and literally anything these items get stored sequentially in memory for
example if we allocate an array of five integers these integers get stored in
memory like this let’s say the address of the first item in memory is 100 as
you probably know integers in Java take 4 bytes of memory so the second item
would be stored at the memory location 104 the third item would be stored at
the memory location 108 and so on for this very reason
looking up items in an array by their index is super fast we give our array an
index and it will figure out where exactly in memory it should access now
what do you think is the runtime complexity of this operation it’s all of
one because the calculation of the memory address is very simple it doesn’t
involve any loops or complex logic so if you need to store a list of items and
access them by their index arrays are the optimal data structures for you now
let’s look at the limitations or weaknesses of arrays in Java and many
other languages arrays are static which means when we allocate them we should
specify their size and this size cannot change later on so we need to know ahead
of time how many items we want to store in an array now what if we don’t know we
have to make a guess if our guess is too large will waste memory because we’ll
have cells that are never filled if our guess is too small our array gets filled
quickly then to add another item we’ll have to resize the array which means we
should allocate a larger array and then copy all the items in the old array into
the new array this operation can be costly can you guess the runtime
complexity of this operation pause the video and think about it for a second
here’s the answer let’s say our array has 5 items now we will add the sixth
item you have to allocate a new array and copy all these five items into that
new array so the runtime complexity of this operation is o of n which means the
cost of copying these items into the new array increases linearly and in direct
proportion to the size of the array now let’s talk about removing an eye
here we have a couple of different scenarios if you want to remove the last
item that’s pretty easy we can quickly look it up by its index and clear the
memory so here we have ol1 which is our best-case scenario but when doing Big O
analysis we should think about the worst case scenario what is the worst-case
scenario here this is when we want to remove an item from the beginning of the
array we have to shift all the items on the right one step to the left to fill
in the hole the more items we have the more this shifting operation is going to
cost so for the worst-case scenario deletion is an O of n operation so
because arrays have a fixed size in situations where we don’t know ahead of
time how many items we want to store in them or when we need to add or remove a
lot of items from them they don’t perform well in those cases we use
linked lists which we’re going to talk about later in the course now let’s see
a quick demo of arrays in Java you in this video we’re gonna look at arrays
in Java if you know arrays well feel free to escape this video so to declare
an array we’ll start with the type of the array let’s say we want to declare
an array of integers so we type int and then we add square brackets to indicate
that this is an array and not just a regular integer next we give our
variable a name like numbers and here we use the new operator to allocate memory
for this array here we repeat the type of the array one more time but this time
inside the square brackets we specify the size of this array let’s say 3 now
let’s print this on the console we get this weird string what is this
well this is a combination of the type of the array followed by an @ sign and
then this value that is generated based on the address of this object in memory
that is not useful you want to see the content of this array to do that we’re
gonna use the arrays class let me show you so here in sort of printing numbers
you’re gonna use the arrays class we type arrays as you can see in this class
is declared in this package Java dot util so we press ENTER and IntelliJ
imports this class on the top now we use the dot operator and call the two string
method a password array here and this method will convert it to a string and
then we’ll print that string on the console no let’s run the program one
more time there you go much much better so as we can see all items in a numeric
array are initialized to zero now let me show you how to change the value of
these items so after we declare our array let’s say we want to set the first
item we type numbers once again we use square brackets and here we specify an
index the index of the first item is 0 so here we are referring or referencing
the first item we set this to let’s say 10 similarly we can set the second item
to 20 and the third item to 30 now let’s run the program one more time so here’s
the content of our array beautiful now if you know the items that you’re gonna
store in your array ahead of time there is a shorter and cleaner way to
initialize your array instead of doing all this ceremony we can use curly
braces to declare and initialize this array so here we type 10 20 and 30 and
this will allocate an array of 3 items in memory and it will initialize each
item according to the values we have passed here take a look we get the exact
same result as before now this area objects have a field
called length and this returns the size of the array let’s print this on the
console and see what we get so print numbers dot lengths there you go the
size of this array is three and we cannot change it so if want to store
four items here you have to create another array copy all the existing
items and then add the fourth item this is the problem with arrays in Java so if
you want to work with lists that grow or shrink automatically you’ll have to use
linked lists you’re going to talk about them in the next section but before we
get there I’m gonna give you a fantastic exercise we’ll look at that next so as you learn arrays in Java or static
which means they have a fixed size and this size cannot be changed but now
we’re going to do something really cool I’ve created this array class which is
like a dynamic array as we add new items to it it will automatically grow and as
we remove items it will automatically shrink let me show you how that works so
we create a new array object we call it numbers and then initialize it like this
here we pass the initial size let’s say 3 now this numbers object has a method
for adding new items let’s add 10 and then 20 and then 30 we also have a
method for printing this array but technically this print method shouldn’t
be here because an array should not be concerned about printing its content on
the console it shouldn’t know anything about console it should only be
concerned about storing these values displaying these values is a completely
different concern and should not be implemented as part of this class but in
this course we want to keep things simple that’s why I’ve implemented the
print method inside the array class now let’s run this program and see what we
get so 10 20 30 beautiful so the initial size of our array is 3 but we can easily
add a new item and our array is going to automatically grow no problem we also
have a method for removing items that is remove at which gets an index let’s say
we want to remove the last item what is the index of this item
well the index of the first item is 0 then 1 2 3 so let’s remove the last item
here’s the result beautiful you also have one method for
finding the index of an item let me show you so I’m gonna do a print statement
here and call numbers dot index of this will return the index of the first
occurrence of this item let’s say 10 so because 10 is the first item in this
array this method is gonna return 0 take a look 0 if we pass a number that
doesn’t exist in the array let’s say 100 it’s gonna return negative 1
okay now here’s your exercise I want you to build an array class that works
exactly like what you saw in this video this is a fantastic exercise for you to
get your hands dirty in the code especially for working with data
structures and algorithms don’t say all mush
this is too easy I already know how to do this trust me as we talk about more
complex data structures our code is gonna get more complex so I want you to
treat this as a warm-up exercise so pause the video and spent 20 minutes on
this exercise when you’re done come back see my solution
you all right we’re gonna solve this problem
step by step and this is the approach I want you to follow whenever you want to
solve a complex problem don’t try to do too many things at once try to break
down that problem into smaller easier to understand easier to solve problems so
in this video we just want to focus on creating this array class and printing
its content on the console you’re not going to worry about adding new items or
removing existing items we’re gonna implement these features in the
following videos so let’s add a new class here we’re going to right click
this package and add a new Java class we call it array
now in this class first we need to add a constructor so we type public array here
we need a parameter to specify the initial size of the array so and length
now inside this class we’re gonna store our items in a regular Java array so
we’re going to declare a private field private int array called items now here
in the constructor we need to initialize this array based on the initial size so
we sell items to new interim a of length pretty straightforward now let’s
implement the print method so public void print here we need to iterate over
all the items in this array and print them on the console pretty easy so 4
into I we set it to 0 as long as I is less than items that length we increment
I and in each iteration we simply print items of I so in each iteration we get
one item from the array and print it on the terminal now let’s go back to our
main class we’re going to create a new array object we call it numbers and set
it to a new array of 3 now let’s print this object on a console so we get these
three zeros but technically we shouldn’t see anything because we haven’t inserted
any items in this array so let’s go back to our array class
we need another field to keep track of the number of items in this array we
cannot rely on items that length because this is the memory we are allocating
initially we might allocate memory for 50 items like you might only insert two
items in this array so every time we insert a new item we need to keep track
of the number of items in this array how can we do that we can declare another
private field private int let’s call it count now back to a print method we’re
gonna replace items that length with count
so initially count is zero and this loop is not gonna get executed in the future
every time we insert a new item in this array we’re gonna increment count by one
so now let’s run this program one more time because our array is empty we don’t
see anything beautiful we have completed the first step so next let’s implement
the insert method alright now let’s implement the insert
method so public void insert we give it a parameter int item now what should be
doing this method there are a couple of things we need to do if the array is
full we need to resize it and also we need to add this new item the new item
at the end of the current array let’s not worry about the first step yet
instead we’re gonna do the second step which is easier so we want to add this
new item at the end of this array how can we do this well we use the items
field we use square brackets now we need to pass an index
what is this index this index should represent the last item in this array
it’s not gonna be items that length it’s gonna be count so currently we don’t
have any items in this array so the index of the last item or the place
where we should insert the new item is index 0 next time we add a new item the
index is gonna be 1 and then 2 and 3 so we said items of count 2 this new item
and then we increment count by 1 or we can simplify this code get rid of this
line and increment count over here so with this expression first we said items
of count 2 item and then count is going to be incremented by 1 let’s test our
code up to this point so back to the main class we’re gonna call the insert
method and pass a couple of numbers 10 on 20 nanus run the program there you go
beautiful so let’s go back to the array class and implement this scenario
how can we tell if they are useful that’s very easy we can write an
expression like this if items that length equals count now in this case
what should we do first we need to create a new array that is larger and
let’s say twice the size then we need to copy all the existing items into this
new array and finally we’re gonna set the items field to this new array
because currently the array that the items field is referencing is four so
let’s implement each step first we need to create a new array this is pretty
easy we declare an int array let’s call it new items and set it to a new entry
of count times two so this new array is twice the size of the old array now we
need to copy all the existing items here we’re gonna use a for loop exactly like
the for loop we have here so we need to iterate over all the existing items and
reference them using their index so four and I we set it to zero as long as
I is less than count we incremented after each step now in each step we’re
gonna set new items of I two items I buy that is pretty straightforward finally
we need to set the items field to this new array
so we set items to new items now let’s test this so back to the main class I’m
gonna add a couple more items and run the program
look now we have a dynamic array that automatically grows as we add new items
to it so now that you understand how everything works I’m gonna go back to
the array class and get rid of these additional comments we don’t need this
comments because our code is clean and straightforward we don’t need to repeat
it we should only use comments for explaining wise and house not what the
code is doing that should be reflected in the code itself so delete delete and
delete next we’re going to implement the delete operation
you alright now let’s implement the remove
method so public void remove at we give it an index now what should we do here
first we want to validate the index and make sure it’s within the right range
for example if someone passes negative 1 it doesn’t make sense what doesn’t mean
to remove the item at index negative 1 or let’s say our array has 5 items as
you know the index of the last item in this case showed before what if someone
says remove the item at the index 5 or 6 or 7 okay it doesn’t make sense so first
we want to validate the index second we want to shift the items to the
left to fill the hole we’ll talk about what this means in a second let’s
implement each of these scenarios one by one so first we’re going to validate the
index this is pretty easy we can write an if statement like this if index is
less than zero or we use two vertical bars to indicate a logical or or index
is greater than or equal to count what does this mean well if count is four
that means the index of the last item is three so we cannot tell this array to
remove the item at index 4 or 5 and so on so that is why we have greater than
or equal to count here now what should we do in this case we don’t want to
print a message on the console because this class might be used in an
application with a graphical user interface there we don’t have a console
so instead we should throw an exception because this is a programming error if
someone passes an index that is out of range so by throwing an exception we
forced a program to crash and with this the programmer knows that they made a
mistake and they will solve this problem so we throw a new exception of type
illegal argument exception that was the first step now let’s work on the second
part let’s imagine we have an array like this
10 20 30 and 40 and then we want to remove the item at index 1 that is this
20 over here so in order to remove 20 we should copy 30 over here and then 40
over here so we’re shifting each item one step to the left in other words the
item at index one should be set to what we have at index 2 and what we have at
index 2 should be set to what we have at index 3 how can we implement this this
is very easy we need a for loop that starts from this index and it goes all
the way until it reaches the end of this array so for int I we set this to index
as long as I is less than count the increment I after each step now in each
iteration we want to set the item at this index to the item to its right side
that is pretty easy so we set items of I to items of I plus 1 ok so after we
execute this for loop our array is going to look like this 30 is gonna be copied
over here and then 40 is gonna be copied over here but we still have 4 items in
this array we want to shrink this array so it looks like this how can we do that
very easy after our loop with decrement count by 1 because count represents the
total number of items currently in there a not the size of the array right so
let’s test our code back to the main class we added four items here before
printing the array let’s call remove add and remove the first item so 10 is gonna
go away now we have 20 30 40 beautiful let’s test it with a different index
let’s say index 1 now 20 is gone beautiful let’s do another test and
remove the last item so it pass index 3 40 is gone what if you pass in X 4
we got an exception of type illegal argument exception this is a programming
mistake we don’t want to print a message on the console we want to stop the
execution of the program so now that we’re done with the implementation of
the remove method let’s get rid of these unnecessary comments and make our code
clean next we’re going to implement the search operation finally let’s implement the search
operation so public int because we want to return the index of the given item we
call this method index of and give it a parameter item now what should we do
here we want to loop over all the items in this array if we find the item you
want to return the index otherwise we’re gonna return negative one so once again
we’re gonna use a for loop that’s pretty easy for I we set this to zero as long
as I is less than count you’re gonna increment it by one now we
need to get the item at the given index and compare it with this item so we
write an if statement if items of I equals this item then we want to return
I as the index otherwise if you finish this loop and we’re still here we didn’t
return from this method that means we couldn’t find this item so we should
return negative one let’s test our new method back to the main class we added
these four items 10 20 30 40 let’s print numbers that index of 10 so that is 0
beautiful what about the index of a number that we don’t have let’s say 100
that is negative 1 so we’re done with this implementation but before I remove
the comment let me ask you a question what is the runtime complexity of this
method pause the video and think about it for a second ok here’s the answer we
need to analyze the best case on the worst case scenario the best case
scenario is where this item is the first item in this array so in that case the
runtime complexity is o of 1 but the worst case scenario is where this item
is at the end of the array so we have to loop over the entire array to find that
item if our array has 1 million items that means we’re gonna have 1 million
comparison operations so in the worst case scenario the runtime complexity of
this method is o of as I told you before when doing Big O
analysis we always consider the worst case scenario
so the runtime complexity of this method is o of N
you so you learn how to build a dynamic
array from scratch and that was a great exercise
however Java has two implementations of dynamic arrays let me show you we have
two classes vector and array list both these classes are declared in the Java
that util package but they’re slightly different the victor class would grow by
how to person of its size every time it gets full whereas the ArrayList will
only grow by 50% of its size also all the methods in the vector class are
synchronized this is an advanced topic and I’m gonna cover that in my upcoming
advanced Java course but basically when we say a method is synchronized that
means only a single thread can access that method in other words if you have a
multi-threaded application where multiple threads are gonna work with
this collection that you’re not gonna be able to use the victor class you should
use the ArrayList class because the methods of the ArrayList are not
synchronized again I’m gonna cover that in detail in my upcoming advanced Java
course now let’s have a quick tour of the ArrayList class so let’s type array
list then this angle brackets you see here these represent a generic parameter
with this generic parameter we specify the type of each element in this array
list for example if you want to have an array list of integers we type integer
this integer class is a wrapper around the native or primitive int type so for
every primitive time that we have like int short white boolean whatever we have
a wrapper class for example we have short we have white we have boolean and
so on we can also have an ArrayList of strings or students assuming that we
have a student class in this demo I’m gonna create an array list of integers
so integer n term now we need to import the ArrayList class because it’s
declared in a different package so we press Alt + Enter
there you go it’s important on the top now let’s create our ArrayList we call
this list and initialize it using the new operator like this new ArrayList and now we can call the add method we
can add a number here and duplicate this line a few times I have two more numbers
now we can print this list on the console so here is the content of our
array beautiful we can also remove items so remove we can remove a particular
object or remove an item at a given index for example we can remove the
first item and now ten is gone we only have 20 and 30 we can also find the
index of the first occurrence of an element so recall list that index of 20
because now after removing the first item 20 is going to be the first item
this method will return zero we also have last index of which will return the
index of the last occurrence of an item we also have contains which returns a
boolean value telling us if you have this item in our array or not and
finally we can use the size method to get the number of items in this array
and finally another useful method is the true array method this will convert this
list to a regular array object so there are times that you want to work with a
regular array object let’s say you have a method that only accepts an array and
you cannot pass an ArrayList class there in that case we can easily convert your
ArrayList to a regular array linked lists are probably the most
commonly used data structures after arrays they solve many of the problems
with arrays and are also used in building more complex data structures so
in this section we’re gonna look at linked lists we’ll talk about how
they’re structured in memory we’ll look at the time complexity of various
operations on them and finally we’re gonna build a linked list from scratch
again this is an incredible exercise for you to train your programming brain so
let’s jump in and get started we use linked lists to store a list of objects
in sequence but unlike arrays linked lists can grow and shrink automatically
as you can see here a linked list consists of a group of nodes in sequence
each node holds two pieces of data one is a value and the other is the address
of the next node in the list so we say each node points to or references the
next node that’s why we refer to these structures as linked lists because these
nodes are linked together we call the first node the head and the last node
the tail now let’s look at the time complexity of various operations let’s
say you want to find out if our list contains a given number we have to
traverse the list starting from the head all the way to the tail what is the
runtime complexity here it’s o of n because the value that we are looking
for may be stored in the last node that is our worst case scenario right what
about looking up by index well unlike arrays where items are stored
sequentially the notes of a linked list can be all over the place in memory they
may not be exactly next to each other that’s why each node needs to keep a
reference to the next node for this reason unlike arrays we cannot quickly
look up an item by its index we have to traverse the list until we find that
item in the worst case scenario that item can be at the end of the list so
once again here we have o of n what about insertions well it depends where
we want to insert an item if you want to insert a new item at the end we simply
need to create a new node and have the last node or the tail point to it we
should have a reference to the last node somewhere so we
have to traverse the list every time now we need to have the tail reference this
new node so inserting a new item at the end is an O of one operation
what about inserting at the beginning what do you think is the runtime
complexity here pause the video and think about it here’s the answer it’s an oil one
because again we should have a reference to the head or the first note so to
insert a new item at the beginning of the list we create a new note linked it
to the first note and then change the head to point to this new note again
this is very fast unlike a race we don’t have to copy or shift items around we
simply update the links or references now what if you want to insert an item
somewhere in the middle let’s say after the tenth note well first we have to
find that note that’s an O of n operation and then we have to update the
links which is an O of one operation so inserting an item in the middle is an O
of n operation now let’s talk about deletions I want you to pause the video
and think about three scenarios deleting an item from the beginning from the end
and from the middle draw on a piece of paper how the links should be updated
also calculate the runtime complexity for each scenario this is very important
make sure to do this little exercise because later on you’re going to code
all of this if you don’t understand these concepts you’re not going to be
able to code them so pause the video do the exercise when you’re done come back
continue watching all right here are the answers deleting
the first item is super fast we simply set the head to point to the second note
that’s an O of one operation now we should also remove the link from the
previous head so it doesn’t reference the second note anymore
why because if you don’t do this Java’s garbage collector thinks this objects
still used so it won’t remove it from the memory that’s why we should unlink
this object from the second object what about deleting the last item this
one is a bit tricky we can easily get the tail but we need to know the
previous node so we can have the tail point to that node how can we do that we
have to traverse the list from the head all the way to the tail as soon as we
get to the node before the last node we keep a reference to it as the previous
node then we’ll unlink this node from the last node and find in half the tail
point to the previous node so the runtime complexity here is o MN because
we have to traverse the list all the way to the end what about deleting from the
middle again we have to traverse the list to find out the node as well as its
previous node we should link the previous node to the node after this
node and then remove this link so this object gets removed from memory by
Java’s garbage collector again here we have an O of n operation next we’re
gonna work with linked lists in Java in this video we’re going to look at
linked lists in Java so if we type linked list we can see this class is
defined in Java that util package this angle brackets you see here these are
generics that means we can store any kind of objects in this list you can
store integers strings any type of objects so let’s press Enter
this class is imported on the top beautiful now let’s say we want to store
a bunch of integers in this linked list so we add angle brackets and type
integer with capital I because here we’re using the integer class that is
defined in Java that Lang package not the built in primitive type so we should
always reference a class here this integer class wraps a primitive integer
okay or we could have a linked list of strings or if we don’t specify anything
here we can store any kind of objects in this list one node can hold an integer
another node can hold a string so let’s create a list once again we have to use
the new operator to allocate memory for this object so a new linked list now we
have a bunch of methods for adding new items we can add at the beginning or at
the end let’s add 10 at the end and then 20 and 30 now let’s write a print line
statement and print this list there you go it looks like we have an array but
actually we’re dealing with a list so don’t let these square brackets fool you
okay now we can also add an item at the beginning so we call list that at first
let’s add 5 here there you go now we have 5 10 20 or 30 we have similar
methods for removing items so we can call lists that remove last term of the
last item we also have remove which takes an index as well as remove first
for removing the first item another useful method is the contains method we
can use this to see if our list contains the number 10 so let’s do a print line
statement and move this expression over here so our list certainly does include the
value 10 we have a similar method that is lists that index of which will return
the index of the first occurrence of this object so if you pass 10 here this
will return 0 because that is our first item there you go another useful method
is the size method so let’s print that list that size this will return the
number of items in this list which is three beautiful and finally the last
useful method I want to cover is list the to array
there are times you want to work with an array so you can convert a linked list
to a regular array let’s convert it to an array and store it here now we can
use the arrays class to convert this array to a string and then print it on
the console there you go so this is how linked lists work in Java you alright now just like the previous
section we’re gonna build a linked list from scratch this is a great exercise
for you to practice all the materials in this course but before we get started I
want to give you a couple of hints to do this exercise you need two classes a
note class like this here we have a couple of fields an integer called value
and a node called Nick’s so with this field we can keep a reference to the
next note we also need a linkless class with these two fields first and last we
could call them head and tail but to be consistent with the link list class in
java i decided to call this first and last I would recommend you to follow the
same names so as you will see my solution you don’t get confused about
these names you can simply compare your code with mine and here are the metals I
want you to implement in this exercise at first at last
delete first till at last contains and index off these are the essential
methods that we need in a linked list so spend 30 to 40 minutes on this exercise
do not skip this it’s super important because in the next section I’m going to
talk about stacks and queues and we’re gonna implement them using a linked list
so linked list is one of those essential fundamental data structures that you
need to master all right enough talking so grab a coffee and get started
you all right let’s start by implementing
the at last method so public void at last we give it an integer now what
should we do here the first step is to wrap this value of this integer inside a
node object so we create a node object like this
now as we can see we have repeated the name of the class twice and this is
unnecessary we can use the VAR keyword I let the Java compiler detect the type of
this variable so because we have new node on the right side the Java compiler
will know that this variable is a node object all right now we need to set node
that value to this item however this field is declared as
private and that’s why we cannot access it from outside of this node class we
can come here and create a setter like public void set value which takes a
value and here we type this that value equals value but I want to show you a
better way I argue that this node class is part of the implementation of the
linked list we don’t need to work with this node class directly so this should
not be declared as a public class here that can be accessed anywhere in our
program earlier when we worked with the linked list class in Java if we see a
node class we didn’t we simply called various methods on the linked list and
the linked list took care of everything under the hood so this node class is
something that the linked list class shall have internally it’s an
implementation detail so we can remove this setter and move this class inside
the linked list so we can add it here on the top
there you go now because this class is declared inside the link list we have
access to its private fields so we don’t need a setter also we should change this
to private so nowhere in our program we can access the note class that’s better
now another thing we need to improve here is this line with this
implementation we can have a note that doesn’t have a value this doesn’t make
sense whenever we create a note object it should always store a value so we can
create a custom constructor for the note class and pass this value there so here
in the note class we type public node in this constructor we add a value and we
set this dot value to value now we can get rid of line 18 and simply
pass the value here sorry I made them item so our code is shorter and our note
object will always be in a valid state you’re not gonna have a note without a
value that doesn’t make sense so we have a note what should we do next well that
depends on the state of the linkless if our linked list is empty we need to set
both the first and last note or head and tail to point to this new node otherwise
we need to append this node at the end of the list let me show you so here’s
the first scenario we should check to see if the list is empty or not how can
we do that we write an if statement like this if first equals no that means we
don’t have any nodes in this list because as soon as we add a node in this
list first should be initialized so if first is now we should set first to this
new node we should also set last to this new node or we can simplify these two
lines and initialize both these variables on the same line that is
better now we don’t need these ugly curly braces so let’s look at the other
scenario where our list has at least one node so else in this case we want to add
this node after the last node so we type last that next equals node we’re linking
the last node to this new node finally we should update last to point to this
new node because now we have one new node in this list so we type last equals
node we’re done with the implementation of this method so let’s use our new list
and see if it’s working properly so back to the main class I want to create a new
linked list or call it list now once again we can use the VAR
keyword to simplify this code here we’re gonna call list then at last 10 and then
20 and then 30 now currently we don’t have a method for printing this list and
I realize I forgot to tell you to implement this method but in this video
I don’t want to spend time implementing the print method instead I’m gonna show
you a different technique so we add a breakpoint on this line by clicking on
this area look now it’s red now we’re gonna run this code using the debugger
so on the top look run debug main is the shortcut that’s ctrl + D on Mac so here
we are all the previous lines are executed but this line is not so we can
click on this icon that is step over now all these lines are executed so let’s
inspect our list object and see if it’s structured properly so in this debug
window let me expand this good so here we have this list let’s look at the
first node so the value is 10 now next this is referencing another
node what is this node here we have 20 and this is also referencing another
node in this node we have 30 but next here is set to null because this is the
last node in our list so far so good what about our last node this is
pointing to the same object where we have the value of 30 beautiful so we’re
done with this step we’ll implement another method next all right let’s implement the ad first
method this is very similar to what we did in the previous video so public void
at first which takes an item now once again we need to wrap this item inside a
node object so far node equals new node of either now here we have two scenarios
if the list is empty we need to add the first node otherwise we need to prepend
this item to the list so we check if first is no then just like before we set
first and last to this new node otherwise we want this node to point to
our first node so your type node that next equals first and then we need to
set the first node to this new node so first
EKOS node we’re done with the implementation of this method but I want
to show you a technique for making this code more readable and more maintainable
this is something that unfortunately most data structures books and courses
don’t teach you most of the code samples I say in this book look disgusting
they look really ugly like old school the code we used to write in 1980s so
how can we improve this code and make it more readable well look at this logic
what is the point of this logic you’re trying to see if this list is empty or
not so we can extract this into a private method and call it is empty let
me show you so here we create a private method it’s private because this is
implementation detail we don’t want this to be accessible outside of this class
so public boolean is empty now here is simply return head equals sorry
first equals no now we can improve this code by
replacing this logic with a call to this new method isn’t the cleaner
let’s also modify the add last method is empty beautiful next we’re going to
implement the indexof method alright now let’s implement the index of
methods of public int index of this item what should we do here
we need to traverse this list starting from the beginning all the way to the
end as soon as we find an item with this value we’re gonna return the index of
that item but we don’t have indexes here so how
are we gonna implement that well we can declare a variable index and initially
set it to 0 then as we’re traversing this list we increment this index so we
need another variable let’s say current we set this to the first node now we
need a while loop as long as current is not no which means we haven’t reached
the end of the list we need to compare the value of the current node with this
item so if current that value equals this item we want to return the current
index silver return index otherwise you’re gonna set current to the next
node so we set current to current dot next and at the same time we should also
increment index now if we reach the end of the list and we can’t find a node
with this value we need to return negative 1 all right now let’s test our
code so back to the main class we added a few items here now let’s print list
that index of 10 so we get zero beautiful what about
index of 30 the last item I always look for this edge cases that is too perfect
and finally an item that doesn’t exist in the list so negative one beautiful
next we’re going to implement the contains method
you the contains method is pretty easy so
public boolean contains item now what should we do here once again we should
traverse the list starting from the beginning all the way to the end if you
find this item will return true otherwise we’ll return false however we
already built this logic in our index of method so we can reuse this there is no
need to repeat this logic so we type return index of item does not equal to
negative one so if this expression if value is to true that means we have this
item in our list let’s test this so back to the main class we’re gonna call list
that contains for D obviously we don’t have this item what about 10 we get true
beautiful that was very easy next we’re gonna implement the delete first method right now let’s work on removing the
first item so public void remove first we don’t need any parameters here this
one is a bit tricky imagine our list looks like this ten point into twenty
point into thirty now we want to remove the first item so we have this field
called first that is currently pointing to ten we should have this point to the
second node and this will bring our list forward it’s gonna look like this right
however we still have this object this first note that is referencing the
second node so the garbage collector in Java will not be able to remove this
object from the memory to solve this problem we need to remove this link now
here’s the tricky part if we remove this link we are not going
to be able to set first to point to the second node because the moment we remove
this link we lose track of the second point so to solve this problem we need
two different references first and second let me show you so I’m going to
bring this back let’s write some code so first we declare a variable called
second we said this to first dot next so ii is pointing to twenty now that we
have this we can go and remove this link without worrying about losing track of
the second point because we have the second variable as a backup here so we
go and set first up next to know this will remove this link and finally we
need to update first and set it to point three second node so we set first to
second let’s test this so back to the main class after adding these items
let’s call list dot remove first just like before we’re gonna run this program
using the debugger so ctrl + D okay what we have here in this list first is
pointing to the note that contains 20 and this is pointing to this other note
beautiful now what if our list is empty and we call the remove first method
let’s see what happens we got an exception of type null pointer
exception this is a programming error we shouldn’t let this happen so let’s see
how the built in LinkedIn class in Java works and we’ll implement the same
behavior in this class so temporarily I’m gonna create another linked list
this time we’re using the class that is declared and the Java that util package
so we’re gonna create a linked list of strings we call it X and instantiate it
like this now we call X EE move first let’s see what happens so we got an exception but look at the
type of this exception no such element exception this is different from a
nullpointerexception this is a deliberate error handling so
we should not be able to remove an item from an empty list
so we’re gonna go back to our linkless class and before this logic you want to
add an if statement like this if this list is empty look once again we’re
reusing this beautiful method so if the list is empty we’re gonna throw and you
know such element exception this is the proper way to implement this method
hey I just wanted to let you know that when I was reviewing my videos I noticed
I made a mistake here I didn’t count for the scenario where our linked list has a
single item because this logic would work for a list that has at least two
items first and second so here we need to add an if statement and check to see
if first equals last that means we have a single item or a single note in this
list in this situation if you want to remove this item we should set both
these fields to no and then return because we don’t wanna execute this
logic over here so see even I make mistakes so does everybody it doesn’t
matter what matters is that we should always review our code we should test it
with different inputs and think of various edge cases
you alright now let’s amend the remove last
method this is the trickiest part so pay close attention we’re gonna declare in
your method public void remove last so let’s imagine our list looks like this
10 pointing to 20 pointing to 30 and we have this last field that is pointing to
this node now to remove the last item we need to find the previous node this is
the tricky part so we need to traverse this list starting from the beginning
the moment we get here we need to keep a reference to this node so we can update
last and set it to point to the same node so let’s implement this
step-by-step first we want to find the previous node we start by declaring a
variable called current and we set it to the first node now as long as current is
not no we’re gonna go forward first we check to see if current that next equals
the last note if that’s the case we need to break out of this loop otherwise we
set current to point to the next node so at this point we have the previous
note now if we’re going forward I want to refactor this code and extract this
logic into a separate private method because at a first glance it might not
be clear what we’re trying to do here so let’s declare a private method that
returns a node object we can call this get previous and give it a node object
so whatever node we give it it will return the previous node so let’s move
this logic over here now instead of working with the last
node you want to work with the node that is passed here so let’s change that
beautiful also instead of breaking out of this loop we can simply return the
current node now what if we traverse the list all the way to the end but we
couldn’t find the node before this node we should return no now that we have all
this logic in a single place we can go back to the remove last method and call
get previous give it the last node and store the result in a variable called
previous so in this case previous is gonna point to this node what should we
do now well currently last is pointing to this node we should change last and
make it point to previous so this will shrink our list like this however
there’s still this object that is pointing to this other object we should
remove this link so the garbage collector in Java can also remove this
last node from the memory so we said last two previous this will shrink our
list and then to remove the link we said last that next to nan let’s test our
code after this point so back to the main class after adding these items
let’s remove the last item now let’s start the debugger there you
go so here’s our list let’s see what we
have here we have first that is referencing its node this is referencing
this other node and here we don’t have anything after so we successfully
removed the last node beautiful let’s also make sure that this last field is
referencing the same node beautiful so we’re gonna stop the debugger now we
need to think of the edge cases what if the list is empty just like before we
should throw an exception so I’m going to remove these comments and check to
see if the list is empty we want to throw and you know such element
exception what if our list has only a single item
this logic is not gonna work because there is no node before the last node we
only have a single node so this logic is assuming that our list has at least two
nodes so we need another if statement if first equals last that means we have a
single node in this list in this situation
should set both these fields to know and then return so this other logic is not
executed so this is how we implement the remove last method
hey guys Marsha I wanted to let you know that this video is actually part of my
ultimate data structures and algorithms course the complete course is 13 hours
long and I’ve divided it into three parts so you can take and complete each
part easily if you’re serious about learning data structures and algorithms
I highly encourage you to take this course and learn all the essential data
structures and algorithms from scratch it’s much easier and faster than jumping
from one tutorial to another we’ll be talking about various types of data
structures such as linked lists stacks queues hash tables binary trees AVL
trees heaps tryes graphs and various types of sorting searching and string
manipulation algorithms the course is packed with almost 100 interview
questions these are the interview questions that get asked that companies
like Google Microsoft and Amazon you can watch the course online or offline
anytime anywhere as many times as you want and you would also get a
certificate of completion and a 30-day money-back guarantee it’s exactly like
this tutorial it just has more content if you’re interested click on the link
below this video to enroll in the course thank you and have a great day

16 thoughts on “Data Structures and Algorithms in Java”

  1. Well, that moment when you ask your parents for Christmas, a SUBSCRIPTION to watch Mosh courses. As soon as I saw you had a video about this topic. Instantly bought a subscription to your courses and told my parents it would be my christmas gift. 😀 Thanks this would be much appreciated since I am having troubles with how my teacher explain this at the university. Lots of variables with a,b,c,s,kmnnakfwofkvms and no real examples.

  2. For Mobile Users

    0:00:00 Intro

    0:01:04 What is Big O?

    0:03:03 O(1)

    0:04:32 O(n)

    0:08:17 O(n^2)

    0:10:41 O(log n)

    0:13:20 O(2^n)

    0:14:10 Space Complexity

    0:17:53 Understanding Arrays

    0:21:03 Working with Arrays

    0:24:32 Exercise: Building an Array

    0:27:24 Solution: Creating the Array Class

    0:30:43 Solution: insert()

    0:35:03 Solution: remove()

    0:39:54 Solution: indexOf()

    0:42:23 Dynamic Arrays

    0:46:11 Linked Lists Introduction

    0:46:41 What are Linked Lists?

    0:51:16 Working with Linked Lists

    0:54:40 Exercise: Building a Linked List

    0:56:05 Solution: addLast()

    1:02:15 Solution: addFirst()

    1:04:28 Solution: indexOf()

    1:06:23 Solution: contains()

    1:07:28 Solution: removeFirst()

    1:11:52 Solution: removeLast()

Leave a Reply

Your email address will not be published. Required fields are marked *