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