hi guys March here today we're gonna
talk about the basics of data structure
as on algorithms which is one of the
topics that comes 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
[Music]
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
[Music]
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
[Music]