Data Structures and Algorithms for Beginners

Data Structures and Algorithms for Beginners

Data Structures and Algorithms for Beginners

Data Structures and algorithms for beginners. Ace your coding interview. Watch this tutorial to learn all about Big O, arrays and linked lists!
đź‘Ť Subscribe for more Data Structure tutorials like this: https://goo.gl/6PYaGF
đź’Ą Get the full course: https://bit.ly/2OwNTxx

Java Tutorial for Beginners:
   • Java Tutorial for Beginners  

TABLE OF CONTENT

0:00:00 Intro
0:01:04 What is Big O?
0:03:03 O(1)
0:04:32 O(n)
0:08:17 O(n^2)
0:10:41 O(log n)
0:13:20 O(2^n)
0:14:10 Space Complexity
0:17:53 Understanding Arrays
0:21:03 Working with Arrays
0:24:32 Exercise: Building an Array
0:27:24 Solution: Creating the Array Class
0:30:43 Solution: insert()
0:35:03 Solution: remove()
0:39:54 Solution: indexOf()
0:42:23 Dynamic Arrays
0:46:11 Linked Lists Introduction
0:46:41 What are Linked Lists?
0:51:16 Working with Linked Lists
0:54:40 Exercise: Building a Linked List
0:56:05 Solution: addLast()
1:02:15 Solution: addFirst()
1:04:28 Solution: indexOf()
1:06:23 Solution: contains()
1:07:28 Solution: removeFirst()
1:11:52 Solution: removeLast()

#Programming #ComputerScience

CONNECT WITH ME

My Courses: http://codewithmosh.com
My Blog: http://programmingwithmosh.com
My Facebook: https://www.facebook.com/programmingw…
My Twitter: https://twitter.com/moshhamedani

Data structures and algorithms are one of the topics taught to computer science and software engineering students. It often comes up in coding interviews especially in big companies like Microsoft, Amazon, Google and Amazon. If you’re pursuing a career in software engineering, the knowledge of data structures and algorithms is a must. While you may not use these algorithms in your day-to-day job, studying these algorithms improve your problem solving and programming skills.


Content

0.62 -> Hi guys! Mosh here! Today, we're gonna talk about the basics of data structures
5.37 -> and algorithms which is one of the topics that come up in coding
8.67 -> interviews all the time. In fact, more and more companies ask questions about data
13.41 -> structures and algorithms to see if you can think like a programmer in this
17.279 -> video we're going to talk about the basics of data structures on algorithms
20.82 -> we'll be talking about Big O notation arrays and linked lists after watching
25.98 -> this video if you want to learn more I encourage you to enroll in my ultimate
29.73 -> data structures and algorithms course the link is below this video now to
33.899 -> watch this video you don't need any prior knowledge of data structures on
37.35 -> algorithms but you need to know the basics of programming in this video I'll
41.07 -> be using Java but if you don't know Java that's perfectly fine you can code in
45.09 -> your favorite programming language if you enjoyed this tutorial please support
48.69 -> me by liking and sharing it with others also be sure to subscribe as I regularly
53.219 -> upload near videos all right now let's jump in and get started
66.97 -> before we talk about data structures and algorithms we need to talk about the Big
71.39 -> O notation we use the Big O notation to describe the performance of an algorithm
75.89 -> a lot of people find Big O scary but don't worry I'm gonna make it super
80.09 -> simple for you so let's jump in and get started so what is this Big O all about
89.36 -> well let's start with the classic definition on Wikipedia Big O notation
93.86 -> is a mathematical notation that describes the limiting behavior of a
98.06 -> function when the argument tends towards a particular value or infinity huh
102.26 -> that's the reason why a lot of people find Big O scary but as you will see in
106.7 -> this section the underlying concepts are actually not that hard we use Big O to
110.99 -> describe the performance of an algorithm and this helps us determine if a given
115.19 -> algorithm is scalable or not which basically means is this algorithm going
119.21 -> to scale well as the input grows really large so just because your code executes
124.31 -> quickly on your computer doesn't mean it's gonna perform well when you give it
127.85 -> a large data set so that's why we use the big o notation to describe the
132.89 -> performance of an algorithm now what does this have to do with data
136.61 -> structures well as you will learn in this course certain operations can be
140.9 -> more or less costly depending on what data structure we use for example
145.64 -> accessing an array element by its index is super fast but arrays have a fixed
150.47 -> length and if you want to constantly add or remove items from them they have to
154.7 -> get resized and this will get costly as the size of our input grows very large
159.44 -> so if that's what we need to do then we have to use another data structure
163.64 -> called a linked list these data structures can grow or shrink very
167.75 -> quickly but accessing a linked list element by its index is slow so that's
173.33 -> why you need to learn about the Big O notation first before we can talk about
176.959 -> various data structures also big companies like Google Microsoft and
181.22 -> Amazon always ask you about Big O they want to know if you really understand
185.269 -> how scalable an algorithm is and finally knowing Big L will make you a better
190.4 -> developer or software engineer so over the next few videos we're going to look
194.75 -> at code snippets and use the Big O notation
197.39 -> to describe the performance of our algorithms
201.7 -> you
205.59 -> here's our first example this method takes an array of integers and prints
210.15 -> the first item on the console it doesn't matter how big the array is we can have
214.08 -> an array with 1 or 1 million items all you're doing here is printing the first
219.209 -> item so this methyl has a single operation and takes a constant amount of
225.12 -> time to run we don't care about the exact execution time in milliseconds
229.11 -> because that can be different from one machine to another or even on the same
232.95 -> machine all we care about is that this method runs in constant time and we
238.079 -> represented using the Big O of one this is the run time complexity of this
244.29 -> method so in this example the size of our input doesn't matter this method
249.15 -> will always run in constant time or Big O of 1 now what if we duplicate this
255.269 -> line here we have two operations both these operations run in constant time so
260.07 -> the runtime complexity of this method is Big O of 2 now when talking about the
266.13 -> runtime complexity we don't really care about the number of operations we just
270 -> want to know how much on an algorithm slows down as the input grows larger so
275.25 -> in this example whether we have 1 or 1 million items our method runs in
279.6 -> constant time so we can simplify this by writing down o of 1 meaning constant
286.53 -> time let's look at another example next you
294.87 -> here we have a slightly more complex example have a loop so we're iterating
299.88 -> over all the items in this array and printing each item on the console this
304.74 -> is where the size of the input matters if you have a single item in this array
308.67 -> we're gonna have one print operation if you have a million items obviously we're
313.62 -> gonna have a million print operations so the cost of this algorithm grows
318.27 -> linearly and in direct correlation to the size of the input so we resent the
324.21 -> runtime complexity of this method using the Big O of n where n represents the
330.63 -> size of the input so as n grows the cost of this algorithm also grows linearly
335.94 -> now it doesn't matter what kind of loop used to iterate over this array here
340.23 -> we're using a traditional for loop we could also use a for each loop for
344.31 -> example for int number in numbers we could simply print the number we're
352.89 -> still iterating over all the items in this array we could also use a while
356.88 -> loop or a do-while loop now what if we have a print statement before and after
364.68 -> our loop what do you think is the runtime complexity of this method well
368.94 -> you saw that this single operations running constant time so here we have
374.31 -> the Big O of one our loop runs in Big O of n and once again we have the Big O of
382.11 -> 1 so the run time complexity of this method is o of 1 plus n plus 1 which we
388.89 -> can simplify to or of 2 plus n however when using the Big O notation we drop
396.69 -> this constants because they don't really matter here's the reason if our array
401.19 -> has 1 million inputs adding two extra operations doesn't
405.36 -> really have a significant impact on the cost of our algorithm the cost of our
410.01 -> algorithm still increases linearly so we can simplify this by dropping this
415.32 -> constant what matters is that the cost of this algorithm increases linearly and
421.11 -> in direct proportion to the size of our input if you have five items in the
425.46 -> input we're gonna have five operations if you have a million
428.67 -> we're gonna have a million operations now what if you had two loops here so
433.38 -> let me delete these print statements and duplicate this loop what do you think is
440.55 -> the runtime complexity of this method it's gonna be big-oh of n plus n or Big
447.09 -> O of 2n this is another example where we drop the constant because all we need
453.3 -> here is an approximation of the cost of this algorithm relative to its input
458.16 -> size so N or 2n still represents a linear growth now what if this method
463.89 -> had two parameters an array of numbers and an array of names so first we
470.49 -> iterate over the area of numbers and then we iterate over the array of names
476.28 -> like this what do you think is the runtime complexity here well both these
483.48 -> loops run in O of n but here's a tricky part what is n in this case we're not
489.99 -> dealing with one input we have two inputs numbers and names so we need to
495.12 -> distinguish between these two inputs we could use n for the size of the first
499.17 -> input and M for the size of the second input so the runtime complexity of this
504.6 -> method is going to be o of n plus M and once again we can simplify this to O of
510.75 -> n because the runtime of this method increases linearly
515.49 -> you
519.55 -> in the last video you learn that simple loops running linear time or Olaf n but
525.52 -> here we have nested loops this is the algorithm that we use for printing all
529.15 -> combinations of items in an array so what is the runtime complexity here well
534.46 -> let's find out in our outer loop we're iterating over our input array so here
539.83 -> we have o of n now in each iteration once again we're iterating over all the
547.57 -> items in this array another example of oh of n so the runtime complexity of
552.7 -> this method is o of n times N or N squared we say this algorithm runs in
560.02 -> quadratic time as you can see in this diagram algorithms that run in O of N
564.91 -> squared gets slower than algorithms that run in O of n of course this depends on
570.34 -> the size of the input if you're dealing with an array of let's say 50 items
574.39 -> we're not gonna see any differences but as our input grows larger and larger
579.09 -> algorithms that run in O of N squared get slower and slower now what if you
585.04 -> had another loop before or after this loop for example let's add a for loop
590.8 -> and once again iterate over all the items in this array and print them on a
596.29 -> console what is the runtime complexity of this method well here we have o of n
602.31 -> so the runtime complexity of this method is gonna be o of n plus N squared now
609.49 -> once again we can simplify this this square of this number is always greater
614.41 -> than the number itself right so in this expression N squared always grows faster
620.11 -> than n again use the Big O notation to understand how much the cost of an
626.08 -> algorithm increases all we need is an approximation not as an exact value so
631.6 -> here we can drop in and conclude that this method runs in O of N squared let's
637.48 -> look at another example what if instead of this loop we had another nested loop
642.88 -> here so for end of third in numbers there you go
648.13 -> the run time complexity is now o of n cubed
653.32 -> you can imagine this algorithm gets far slower than an algorithm with o of N
658.03 -> squared you
664.08 -> another growth rate we're gonna talk about is the logarithmic growth which we
668.35 -> show with the Big O of log n here's the logarithmic curve now compare this with
674.38 -> a linear curve as you can see the linear curve grows at the same rate but the
679.06 -> logarithmic curve slows down at some point so an algorithm that runs in
683.38 -> logarithmic time is more efficient and more scalable than an algorithm that
687.61 -> runs in linear or quadratic time let's see a real example of this let's say we
692.8 -> have an array of sorted numbers from 1 to 10 and we want to find the number 10
697.45 -> one way to find the 10 is to iterate over this array using a for loop going
702.7 -> forward until we find the 10 this is called a linear search because it runs
707.38 -> in linear time in the worst case scenario if the number we're looking for
711.16 -> is at the end of our array we have to inspect every cell in this array to find
715.72 -> the target number the more items we have the longer this operation is gonna take
719.83 -> so the run time of this algorithm increases linearly and in direct
724.3 -> proportion with the size of our array right now we have another searching
728.65 -> algorithm called binary search and this algorithm runs in logarithmic time it's
733.78 -> much faster than the linear search assuming that our array is sorted we
738.16 -> start off by looking at the middle item it's this item smaller or greater than
742.78 -> the value we're looking for it's smaller so our target number in this case 10
747.1 -> must be in the right partition of this array right so we don't need to inspect
751.3 -> any of the items in the left partition and with this we can narrow down or
755.44 -> search by half now in the right partition again we look at the middle
759.7 -> item is it smaller or greater than the target value it's smaller so again we
765.22 -> ignore the items on the left and focus on the items on the right so in every
769.63 -> step we're essentially narrowing down or search by half with this algorithm if we
774.61 -> have 1 million items in our array we can find the target item with a maximum of
779.26 -> 19 comparisons we don't have to inspect every item in our array this is
784 -> logarithmic time in action we have lovers meet growth in algorithms where
788.53 -> we reduce our work by half in every step you're going to see this a lot in the
793.33 -> second part of this series where we talk about trees and graphs
797.06 -> unfortunately I cannot show you an example of this in code now because it's
800.84 -> a bit too complex there are a few things we have to talk about before you are
804.65 -> ready to see that in code but trust me you'll see that in the code in the
807.77 -> future and it'll become super easy for now all I want you to take away is that
812.6 -> an algorithm with logarithmic time is more scalable than one with linear time
819.089 -> you
823.12 -> the last growth rate we're going to talk about in this section is the exponential
827.29 -> growth which is the opposite of the logarithmic growth so the logarithmic
831.759 -> curve slows down as the input size grows but exponential curve grows faster and
836.74 -> faster obviously an algorithm that runs in exponential time is not scalable at
841.449 -> all it will become very slow very soon again I cannot show you an example of
846.16 -> this in code yet we'll have to look at it in the future for now all you need to
850.3 -> understand is that the exponential growth is the opposite of the
854.11 -> logarithmic growth and by the way these growth rates we have talked about so far
857.889 -> are not the only growth rates but these are the ones that you see most of the
861.85 -> time there are some variations of these that we look at in the future
865.059 -> for now just remember these five cares you
871.59 -> you have seen how we can use the Big O notation to describe the runtime
875.52 -> complexity of our algorithms in an ideal world we want our algorithms to be super
880.41 -> fast and scalable and take minimum amount of memory but unfortunately that
884.79 -> hardly if ever happens it's like asking for a Ferrari for ten dollars it just
889.02 -> doesn't happen most of the time we have to do a trade-off between saving time
893.4 -> and saving space there are times where we have more space so we can use that to
897.93 -> optimize an algorithm and make it faster and more scalable but there are also
902.07 -> times where we have limited space like when we build an app for a small mobile
906.66 -> device in this situations we have to optimize for this space because
910.62 -> scalability is not a big factor only one user is going to use our application at
915.48 -> that moment not a million users so we need a way to talk about how much space
920.16 -> an algorithm requires and that's where use the Big O notation again let's look
925.5 -> at a few examples here we have this greet method that takes an array of
929.58 -> strings and prints a high message for every name in this array now in this
934.38 -> method we're declaring and loop variable and this is independent of the size of
939.39 -> the input so whether our input array has 10 or 1 million items this method will
944.94 -> only allocate some additional memory for this loop variable so it takes all a one
951.69 -> space now what if we declare is string array like this we call it copying and
958.31 -> initialize it like this so the length of this array is equal to
964.81 -> the length of our input array so if our input array has a thousand items this
969.61 -> array will also have a thousand items what is the space complexity of this
973.81 -> method it's all of n the more items we have in our input array the more space
979.75 -> our method is gonna take and this is in direct proportion to the size of our
984.52 -> input array that's why we have oh of n here and by the way when we talk about
988.6 -> space complexity we only look at the additional space that we should allocate
992.88 -> relative to the size of the input we always have the input of size n so we
998.98 -> don't count it we just analyze how much extra space we need to allocate for this
1003.3 -> algorithm so that's all about space complexity in this course we'll only
1008.01 -> focus on runtime complexity because that's a bit more tricky but from now on
1012.18 -> think about the space complexity of your algorithms especially in situations
1015.69 -> where you have limited space see if there are ways to preserve the memory
1022.089 -> hey guys Marcia I wanted to let you know that this video is actually part of my
1026.75 -> ultimate data structures and algorithms course the complete course is 13 hours
1031.4 -> long and I've divided it into three parts so you can take and complete each
1035.329 -> part easily if you're serious about learning data structures and algorithms
1038.809 -> I highly encourage you to take this course and learn all the essential data
1042.679 -> structures and algorithms from scratch it's much easier and faster than jumping
1047.059 -> from one tutorial to another we'll be talking about various types of data
1050.57 -> structures such as linked lists stacks queues hash tables binary trees AVL
1056.84 -> trees heaps tries graphs and various types of sorting searching and string
1062.539 -> manipulation algorithms the course is packed with almost 100 interview
1066.2 -> questions these are the interview questions that get asked that companies
1069.35 -> like Google Microsoft and Amazon you can watch the course online or offline
1073.549 -> anytime anywhere as many times as you want and you would also get a
1077.39 -> certificate of completion and a 30-day money-back guarantee it's exactly like
1081.38 -> this tutorial it just has more content if you're interested click on the link
1085.49 -> below this video to enroll in the course thank you and have a great day in this
1093.47 -> section we're going to talk about our very first data structure and one that
1096.679 -> you're probably familiar with arrays arrays are built into most programming
1101.03 -> languages and we use them to store a list of items sequentially in a section
1106.19 -> first we're going to look at various strengths and weaknesses of our race
1109.37 -> then I'm gonna show you how to use arrays in Java and finally we're gonna
1113.24 -> build an array class from scratch this is a fantastic exercise for you to get
1118.01 -> your hands dirty in the code and get prepared for more complex data
1121.549 -> structures so do not skip this section even if you know arrays well so let's
1126.71 -> jump in and get started
1131.47 -> arrays are the simplest data structures and we use them to store a list of items
1135.95 -> like a list of strings numbers objects and literally anything these items get
1141.5 -> stored sequentially in memory for example if we allocate an array of five
1146.33 -> integers these integers get stored in memory like this let's say the address
1150.8 -> of the first item in memory is 100 as you probably know integers in Java take
1155.69 -> 4 bytes of memory so the second item would be stored at the memory location
1160.16 -> 104 the third item would be stored at the memory location 108 and so on for
1165.53 -> this very reason looking up items in an array by their
1168.17 -> index is super fast we give our array an index and it will figure out where
1172.88 -> exactly in memory it should access now what do you think is the runtime
1176.75 -> complexity of this operation it's all of one because the calculation of the
1181.73 -> memory address is very simple it doesn't involve any loops or complex logic so if
1186.8 -> you need to store a list of items and access them by their index arrays are
1190.91 -> the optimal data structures for you now let's look at the limitations or
1194.84 -> weaknesses of arrays in Java and many other languages arrays are static which
1200 -> means when we allocate them we should specify their size and this size cannot
1204.23 -> change later on so we need to know ahead of time how many items we want to store
1208.37 -> in an array now what if we don't know we have to make a guess if our guess is too
1213.44 -> large will waste memory because we'll have cells that are never filled if our
1218.24 -> guess is too small our array gets filled quickly then to add another item we'll
1223.4 -> have to resize the array which means we should allocate a larger array and then
1228.17 -> copy all the items in the old array into the new array this operation can be
1232.85 -> costly can you guess the runtime complexity of this operation pause the
1237.17 -> video and think about it for a second here's the answer let's say our array
1242.18 -> has 5 items now we will add the sixth item you have to allocate a new array
1246.74 -> and copy all these five items into that new array so the runtime complexity of
1252.2 -> this operation is o of n which means the cost of copying these items into the new
1257.09 -> array increases linearly and in direct proportion to the size of the array now
1262.82 -> let's talk about removing an eye here we have a couple of different
1265.929 -> scenarios if you want to remove the last item that's pretty easy we can quickly
1269.74 -> look it up by its index and clear the memory so here we have ol1 which is our
1274.779 -> best-case scenario but when doing Big O analysis we should think about the worst
1278.83 -> case scenario what is the worst-case scenario here this is when we want to
1282.46 -> remove an item from the beginning of the array we have to shift all the items on
1286.509 -> the right one step to the left to fill in the hole the more items we have the
1290.59 -> more this shifting operation is going to cost so for the worst-case scenario
1294.46 -> deletion is an O of n operation so because arrays have a fixed size in
1300.159 -> situations where we don't know ahead of time how many items we want to store in
1304.149 -> them or when we need to add or remove a lot of items from them they don't
1308.289 -> perform well in those cases we use linked lists which we're going to talk
1312.039 -> about later in the course now let's see a quick demo of arrays in Java
1318.15 -> you
1322.01 -> in this video we're gonna look at arrays in Java if you know arrays well feel
1326.63 -> free to escape this video so to declare an array we'll start with the type of
1330.65 -> the array let's say we want to declare an array of integers so we type int and
1335.42 -> then we add square brackets to indicate that this is an array and not just a
1339.86 -> regular integer next we give our variable a name like numbers and here we
1346.04 -> use the new operator to allocate memory for this array here we repeat the type
1351.08 -> of the array one more time but this time inside the square brackets we specify
1355.88 -> the size of this array let's say 3 now let's print this on the console
1364.62 -> we get this weird string what is this well this is a combination of the type
1368.879 -> of the array followed by an @ sign and then this value that is generated based
1373.559 -> on the address of this object in memory that is not useful you want to see the
1377.669 -> content of this array to do that we're gonna use the arrays class let me show
1382.35 -> you so here in sort of printing numbers you're gonna use the arrays class we
1389.039 -> type arrays as you can see in this class is declared in this package Java dot
1394.169 -> util so we press ENTER and IntelliJ imports this class on the top now we use
1400.259 -> the dot operator and call the two string method a password array here and this
1406.71 -> method will convert it to a string and then we'll print that string on the
1410.309 -> console no let's run the program one more time there you go much much better
1416.49 -> so as we can see all items in a numeric array are initialized to zero now let me
1422.34 -> show you how to change the value of these items so after we declare our
1426.779 -> array let's say we want to set the first item we type numbers once again we use
1432.45 -> square brackets and here we specify an index the index of the first item is 0
1438.659 -> so here we are referring or referencing the first item we set this to let's say
1444.21 -> 10 similarly we can set the second item to 20 and the third item to 30 now let's
1453.749 -> run the program one more time so here's the content of our array beautiful now
1459.149 -> if you know the items that you're gonna store in your array ahead of time there
1462.869 -> is a shorter and cleaner way to initialize your array instead of doing
1466.259 -> all this ceremony we can use curly braces to declare and initialize this
1470.61 -> array so here we type 10 20 and 30 and this will allocate an array of 3 items
1477.45 -> in memory and it will initialize each item according to the values we have
1481.019 -> passed here take a look we get the exact same result as before
1486.89 -> now this area objects have a field called length and this returns the size
1491.299 -> of the array let's print this on the console and see what we get so print
1496.179 -> numbers dot lengths there you go the size of this array is three and we
1503.72 -> cannot change it so if want to store four items here you have to create
1507.26 -> another array copy all the existing items and then add the fourth item this
1512.45 -> is the problem with arrays in Java so if you want to work with lists that grow or
1516.92 -> shrink automatically you'll have to use linked lists you're going to talk about
1520.88 -> them in the next section but before we get there I'm gonna give you a fantastic
1524.63 -> exercise we'll look at that next
1531.6 -> so as you learn arrays in Java or static which means they have a fixed size and
1536.64 -> this size cannot be changed but now we're going to do something really cool
1540.03 -> I've created this array class which is like a dynamic array as we add new items
1545.19 -> to it it will automatically grow and as we remove items it will automatically
1548.789 -> shrink let me show you how that works so we create a new array object we call it
1554.73 -> numbers and then initialize it like this here we pass the initial size let's say
1561.809 -> 3 now this numbers object has a method for adding new items let's add 10 and
1568.38 -> then 20 and then 30 we also have a method for printing this array but
1575.789 -> technically this print method shouldn't be here because an array should not be
1579.12 -> concerned about printing its content on the console it shouldn't know anything
1583.14 -> about console it should only be concerned about storing these values
1586.98 -> displaying these values is a completely different concern and should not be
1590.549 -> implemented as part of this class but in this course we want to keep things
1593.789 -> simple that's why I've implemented the print method inside the array class now
1598.77 -> let's run this program and see what we get so 10 20 30 beautiful so the initial
1604.289 -> size of our array is 3 but we can easily add a new item and our array is going to
1610.74 -> automatically grow no problem we also have a method for removing items that is
1617.94 -> remove at which gets an index let's say we want to remove the last item what is
1622.83 -> the index of this item well the index of the first item is 0
1626.34 -> then 1 2 3 so let's remove the last item here's the result
1633.929 -> beautiful you also have one method for finding the index of an item let me show
1638.28 -> you so I'm gonna do a print statement here and call numbers dot index of this
1646.26 -> will return the index of the first occurrence of this item let's say 10 so
1651.179 -> because 10 is the first item in this array this method is gonna return 0 take
1655.559 -> a look 0 if we pass a number that doesn't exist in the array let's say 100
1662.24 -> it's gonna return negative 1 okay now here's your exercise I want you
1669.3 -> to build an array class that works exactly like what you saw in this video
1672.6 -> this is a fantastic exercise for you to get your hands dirty in the code
1676.62 -> especially for working with data structures and algorithms don't say all
1680.85 -> mush this is too easy I already know how to
1682.98 -> do this trust me as we talk about more complex data structures our code is
1687.57 -> gonna get more complex so I want you to treat this as a warm-up exercise so
1692.19 -> pause the video and spent 20 minutes on this exercise when you're done come back
1696.84 -> see my solution you
1703.5 -> all right we're gonna solve this problem step by step and this is the approach I
1707.61 -> want you to follow whenever you want to solve a complex problem don't try to do
1711.39 -> too many things at once try to break down that problem into smaller easier to
1716.429 -> understand easier to solve problems so in this video we just want to focus on
1720.51 -> creating this array class and printing its content on the console you're not
1724.83 -> going to worry about adding new items or removing existing items we're gonna
1728.97 -> implement these features in the following videos so let's add a new
1733.74 -> class here we're going to right click this package and add a new Java class
1740.35 -> we call it array now in this class first we need to add a
1745.27 -> constructor so we type public array here we need a parameter to specify the
1751.42 -> initial size of the array so and length now inside this class we're gonna store
1757.48 -> our items in a regular Java array so we're going to declare a private field
1763.08 -> private int array called items now here in the constructor we need to initialize
1770.08 -> this array based on the initial size so we sell items to new interim a of length
1778.8 -> pretty straightforward now let's implement the print method so public
1783.69 -> void print here we need to iterate over all the items in this array and print
1791.02 -> them on the console pretty easy so 4 into I we set it to 0 as long as I is
1798.01 -> less than items that length we increment I and in each iteration we simply print
1806.14 -> items of I so in each iteration we get one item from the array and print it on
1813.46 -> the terminal now let's go back to our main class we're going to create a new
1818.95 -> array object we call it numbers and set it to a new array of 3 now let's print
1826.81 -> this object on a console so we get these three zeros but technically we shouldn't
1834.19 -> see anything because we haven't inserted any items in this array so let's go back
1839.26 -> to our array class we need another field to keep track of
1844.21 -> the number of items in this array we cannot rely on items that length because
1849.19 -> this is the memory we are allocating initially we might allocate memory for
1852.55 -> 50 items like you might only insert two items in this array so every time we
1857.47 -> insert a new item we need to keep track of the number of items in this array how
1861.7 -> can we do that we can declare another private field private int let's call it
1868 -> count now back to a print method we're gonna replace items that length with
1874.54 -> count so initially count is zero and this loop
1878.56 -> is not gonna get executed in the future every time we insert a new item in this
1882.67 -> array we're gonna increment count by one so now let's run this program one more
1887.44 -> time because our array is empty we don't see anything beautiful we have completed
1893.89 -> the first step so next let's implement the insert method
1902.899 -> alright now let's implement the insert method so public void insert we give it
1911.029 -> a parameter int item now what should be doing this method there are a couple of
1916.639 -> things we need to do if the array is full we need to resize it and also we
1923.479 -> need to add this new item the new item at the end of the current array let's
1929.69 -> not worry about the first step yet instead we're gonna do the second step
1933.049 -> which is easier so we want to add this new item at the end of this array how
1937.429 -> can we do this well we use the items field we use square brackets now we need
1944.059 -> to pass an index what is this index this index should
1947.21 -> represent the last item in this array it's not gonna be items that length it's
1952.789 -> gonna be count so currently we don't have any items in this array so the
1957.529 -> index of the last item or the place where we should insert the new item is
1961.759 -> index 0 next time we add a new item the index is gonna be 1 and then 2 and 3 so
1968.389 -> we said items of count 2 this new item and then we increment count by 1 or we
1976.46 -> can simplify this code get rid of this line and increment count over here so
1983.119 -> with this expression first we said items of count 2 item and then count is going
1988.249 -> to be incremented by 1 let's test our code up to this point so back to the
1992.96 -> main class we're gonna call the insert method and pass a couple of numbers 10
2001.359 -> on 20 nanus run the program there you go beautiful so let's go back to the array
2008.32 -> class and implement this scenario how can we tell if they are useful
2015.45 -> that's very easy we can write an expression like this if items that
2021.3 -> length equals count now in this case what should we do first we need to
2027.81 -> create a new array that is larger and let's say twice the size then we need to
2034.95 -> copy all the existing items into this new array and finally we're gonna set
2041.1 -> the items field to this new array because currently the array that the
2047.1 -> items field is referencing is four so let's implement each step first we need
2052.08 -> to create a new array this is pretty easy we declare an int array let's call
2057.6 -> it new items and set it to a new entry of count times two so this new array is
2066.57 -> twice the size of the old array now we need to copy all the existing items here
2071.82 -> we're gonna use a for loop exactly like the for loop we have here so we need to
2077.88 -> iterate over all the existing items and reference them using their index so
2084.379 -> four and I we set it to zero as long as I is less than count we incremented
2091.8 -> after each step now in each step we're gonna set new items of I two items I buy
2102.65 -> that is pretty straightforward finally we need to set the items field to this
2108.12 -> new array so we set items to new items now let's
2114.48 -> test this so back to the main class I'm gonna add a couple more items and run
2121.29 -> the program look now we have a dynamic array that
2124.77 -> automatically grows as we add new items to it so now that you understand how
2129.63 -> everything works I'm gonna go back to the array class and get rid of these
2133.98 -> additional comments we don't need this comments because our code is clean and
2138.18 -> straightforward we don't need to repeat it we should only use comments for
2141.84 -> explaining wise and house not what the code is doing that should be reflected
2146.73 -> in the code itself so delete delete and delete next we're going to implement the
2156.15 -> delete operation you
2162.619 -> alright now let's implement the remove method so public void remove at we give
2171.079 -> it an index now what should we do here first we want to validate the index and
2177.47 -> make sure it's within the right range for example if someone passes negative 1
2181.999 -> it doesn't make sense what doesn't mean to remove the item at index negative 1
2186.14 -> or let's say our array has 5 items as you know the index of the last item in
2192.17 -> this case showed before what if someone says remove the item at the index 5 or 6
2198.079 -> or 7 okay it doesn't make sense so first we want to validate the index
2204.84 -> second we want to shift the items to the left to fill the hole we'll talk about
2211.68 -> what this means in a second let's implement each of these scenarios one by
2215.37 -> one so first we're going to validate the index this is pretty easy we can write
2221.19 -> an if statement like this if index is less than zero or we use two vertical
2228.21 -> bars to indicate a logical or or index is greater than or equal to count what
2238.14 -> does this mean well if count is four that means the index of the last item is
2244.38 -> three so we cannot tell this array to remove the item at index 4 or 5 and so
2250.14 -> on so that is why we have greater than or equal to count here now what should
2257.04 -> we do in this case we don't want to print a message on the console because
2260.76 -> this class might be used in an application with a graphical user
2263.85 -> interface there we don't have a console so instead we should throw an exception
2268.11 -> because this is a programming error if someone passes an index that is out of
2272.52 -> range so by throwing an exception we forced a program to crash and with this
2277.11 -> the programmer knows that they made a mistake and they will solve this problem
2280.5 -> so we throw a new exception of type illegal argument exception that was the
2289.14 -> first step now let's work on the second part
2293.08 -> let's imagine we have an array like this 10 20 30 and 40 and then we want to
2299.11 -> remove the item at index 1 that is this 20 over here so in order to remove 20 we
2306.52 -> should copy 30 over here and then 40 over here so we're shifting each item
2313.18 -> one step to the left in other words the item at index one should be set to what
2319.18 -> we have at index 2 and what we have at index 2 should be set to what we have at
2323.98 -> index 3 how can we implement this this is very easy we need a for loop that
2329.23 -> starts from this index and it goes all the way until it reaches the end of this
2334.66 -> array so for int I we set this to index as long as I is less than count the
2344.35 -> increment I after each step now in each iteration we want to set the item at
2349.12 -> this index to the item to its right side that is pretty easy so we set items of I
2355.12 -> to items of I plus 1 ok so after we execute this for loop our array is going
2363.94 -> to look like this 30 is gonna be copied over here and then 40 is gonna be copied
2368.8 -> over here but we still have 4 items in this array we want to shrink this array
2374.17 -> so it looks like this how can we do that very easy after our loop with decrement
2382.84 -> count by 1 because count represents the total number of items currently in there
2388.93 -> a not the size of the array right so let's test our code back to the main
2393.31 -> class we added four items here before printing the array let's call remove add
2399.88 -> and remove the first item so 10 is gonna go away now we have 20 30 40 beautiful
2405.94 -> let's test it with a different index let's say index 1 now 20 is gone
2413.32 -> beautiful let's do another test and remove the last item so it pass index 3
2419.79 -> 40 is gone what if you pass in X 4 we got an exception of type illegal
2428.31 -> argument exception this is a programming mistake we don't want to print a message
2432.36 -> on the console we want to stop the execution of the program so now that
2436.86 -> we're done with the implementation of the remove method let's get rid of these
2440.97 -> unnecessary comments and make our code clean next we're going to implement the
2447.03 -> search operation
2453.78 -> finally let's implement the search operation so public int because we want
2459.55 -> to return the index of the given item we call this method index of and give it a
2464.53 -> parameter item now what should we do here we want to loop over all the items
2470.59 -> in this array if we find the item you want to return the index otherwise we're
2478 -> gonna return negative one so once again we're gonna use a for loop that's pretty
2482.71 -> easy for I we set this to zero as long as I is less than count
2488.05 -> you're gonna increment it by one now we need to get the item at the given index
2493.06 -> and compare it with this item so we write an if statement if items of I
2501.06 -> equals this item then we want to return I as the index otherwise if you finish
2508.93 -> this loop and we're still here we didn't return from this method that means we
2512.62 -> couldn't find this item so we should return negative one let's test our new
2517.66 -> method back to the main class we added these four items 10 20 30 40 let's print
2524.13 -> numbers that index of 10 so that is 0 beautiful what about the index of a
2534.7 -> number that we don't have let's say 100 that is negative 1 so we're done with
2543.16 -> this implementation but before I remove the comment let me ask you a question
2547.24 -> what is the runtime complexity of this method pause the video and think about
2551.83 -> it for a second ok here's the answer we need to analyze the best case on the
2558.25 -> worst case scenario the best case scenario is where this item is the first
2562.63 -> item in this array so in that case the runtime complexity is o of 1 but the
2569.02 -> worst case scenario is where this item is at the end of the array so we have to
2573.1 -> loop over the entire array to find that item if our array has 1 million items
2578.38 -> that means we're gonna have 1 million comparison operations so in the worst
2583.27 -> case scenario the runtime complexity of this method is o of
2587.5 -> as I told you before when doing Big O analysis we always consider the worst
2592.48 -> case scenario so the runtime complexity of this method
2595.51 -> is o of N you
2602.34 -> so you learn how to build a dynamic array from scratch and that was a great
2606.27 -> exercise however Java has two implementations of
2609.63 -> dynamic arrays let me show you we have two classes vector and array list both
2616.5 -> these classes are declared in the Java that util package but they're slightly
2620.82 -> different the victor class would grow by how to person of its size every time it
2626.67 -> gets full whereas the ArrayList will only grow by 50% of its size also all
2632.88 -> the methods in the vector class are synchronized this is an advanced topic
2637.29 -> and I'm gonna cover that in my upcoming advanced Java course but basically when
2642.24 -> we say a method is synchronized that means only a single thread can access
2647.28 -> that method in other words if you have a multi-threaded application where
2652.02 -> multiple threads are gonna work with this collection that you're not gonna be
2655.47 -> able to use the victor class you should use the ArrayList class because the
2659.37 -> methods of the ArrayList are not synchronized again I'm gonna cover that
2662.97 -> in detail in my upcoming advanced Java course now let's have a quick tour of
2667.41 -> the ArrayList class so let's type array list then this angle brackets you see
2672.75 -> here these represent a generic parameter with this generic parameter we specify
2678.06 -> the type of each element in this array list for example if you want to have an
2683.16 -> array list of integers we type integer this integer class is a wrapper around
2689.67 -> the native or primitive int type so for every primitive time that we have like
2696.06 -> int short white boolean whatever we have a wrapper class for example we have
2701.4 -> short we have white we have boolean and so on we can also have an ArrayList of
2706.74 -> strings or students assuming that we have a student class in this demo I'm
2711.9 -> gonna create an array list of integers so integer n term now we need to import
2717.45 -> the ArrayList class because it's declared in a different package so we
2721.08 -> press Alt + Enter there you go it's important on the top
2725.66 -> now let's create our ArrayList we call this list and initialize it using the
2731.34 -> new operator like this new ArrayList
2735.83 -> and now we can call the add method we can add a number here and duplicate this
2742.56 -> line a few times I have two more numbers now we can print this list on the
2748.77 -> console so here is the content of our array beautiful we can also remove items
2754.77 -> so remove we can remove a particular object or remove an item at a given
2760.23 -> index for example we can remove the first item and now ten is gone we only
2767.16 -> have 20 and 30 we can also find the index of the first occurrence of an
2773.04 -> element so recall list that index of 20 because now after removing the first
2780.78 -> item 20 is going to be the first item this method will return zero we also
2785.64 -> have last index of which will return the index of the last occurrence of an item
2792.45 -> we also have contains which returns a boolean value telling us if you have
2798.54 -> this item in our array or not and finally we can use the size method to
2803.64 -> get the number of items in this array and finally another useful method is the
2808.8 -> true array method this will convert this list to a regular array object so there
2814.26 -> are times that you want to work with a regular array object let's say you have
2817.26 -> a method that only accepts an array and you cannot pass an ArrayList class there
2821.16 -> in that case we can easily convert your ArrayList to a regular array
2828.02 -> linked lists are probably the most commonly used data structures after
2832.349 -> arrays they solve many of the problems with arrays and are also used in
2836.67 -> building more complex data structures so in this section we're gonna look at
2840.75 -> linked lists we'll talk about how they're structured in memory we'll look
2844.59 -> at the time complexity of various operations on them and finally we're
2848.7 -> gonna build a linked list from scratch again this is an incredible exercise for
2852.81 -> you to train your programming brain so let's jump in and get started we use
2861.39 -> linked lists to store a list of objects in sequence but unlike arrays linked
2866.099 -> lists can grow and shrink automatically as you can see here a linked list
2870.56 -> consists of a group of nodes in sequence each node holds two pieces of data one
2876.24 -> is a value and the other is the address of the next node in the list so we say
2881.16 -> each node points to or references the next node that's why we refer to these
2885.66 -> structures as linked lists because these nodes are linked together we call the
2890.82 -> first node the head and the last node the tail now let's look at the time
2895.14 -> complexity of various operations let's say you want to find out if our list
2899.49 -> contains a given number we have to traverse the list starting from the head
2903.78 -> all the way to the tail what is the runtime complexity here it's o of n
2908.97 -> because the value that we are looking for may be stored in the last node that
2913.38 -> is our worst case scenario right what about looking up by index well unlike
2918.63 -> arrays where items are stored sequentially the notes of a linked list
2922.74 -> can be all over the place in memory they may not be exactly next to each other
2926.64 -> that's why each node needs to keep a reference to the next node for this
2931.23 -> reason unlike arrays we cannot quickly look up an item by its index we have to
2936.089 -> traverse the list until we find that item in the worst case scenario that
2940.53 -> item can be at the end of the list so once again here we have o of n what
2945.75 -> about insertions well it depends where we want to insert an item if you want to
2950.43 -> insert a new item at the end we simply need to create a new node and have the
2955.109 -> last node or the tail point to it we should have a reference to the last node
2959.31 -> somewhere so we have to traverse the list every time now
2962.75 -> we need to have the tail reference this new node so inserting a new item at the
2967.28 -> end is an O of one operation what about inserting at the beginning
2971.9 -> what do you think is the runtime complexity here pause the video and
2975.56 -> think about it
2978.32 -> here's the answer it's an oil one because again we should have a reference
2983.09 -> to the head or the first note so to insert a new item at the beginning of
2986.9 -> the list we create a new note linked it to the first note and then change the
2990.98 -> head to point to this new note again this is very fast unlike a race we don't
2995.69 -> have to copy or shift items around we simply update the links or references
3000.07 -> now what if you want to insert an item somewhere in the middle let's say after
3004.48 -> the tenth note well first we have to find that note that's an O of n
3008.74 -> operation and then we have to update the links which is an O of one operation so
3013.69 -> inserting an item in the middle is an O of n operation now let's talk about
3018.34 -> deletions I want you to pause the video and think about three scenarios deleting
3023.59 -> an item from the beginning from the end and from the middle draw on a piece of
3027.85 -> paper how the links should be updated also calculate the runtime complexity
3032.44 -> for each scenario this is very important make sure to do this little exercise
3036.24 -> because later on you're going to code all of this if you don't understand
3040.84 -> these concepts you're not going to be able to code them so pause the video do
3044.71 -> the exercise when you're done come back continue watching
3050.92 -> all right here are the answers deleting the first item is super fast we simply
3056.14 -> set the head to point to the second note that's an O of one operation now we
3060.789 -> should also remove the link from the previous head so it doesn't reference
3064.15 -> the second note anymore why because if you don't do this Java's
3068.23 -> garbage collector thinks this objects still used so it won't remove it from
3072.279 -> the memory that's why we should unlink this object from the second object
3076.24 -> what about deleting the last item this one is a bit tricky we can easily get
3081.46 -> the tail but we need to know the previous node so we can have the tail
3085.63 -> point to that node how can we do that we have to traverse the list from the head
3090.4 -> all the way to the tail as soon as we get to the node before the last node we
3095.17 -> keep a reference to it as the previous node then we'll unlink this node from
3099.43 -> the last node and find in half the tail point to the previous node so the
3103.9 -> runtime complexity here is o MN because we have to traverse the list all the way
3108.519 -> to the end what about deleting from the middle again we have to traverse the
3112.869 -> list to find out the node as well as its previous node we should link the
3116.859 -> previous node to the node after this node and then remove this link so this
3121.059 -> object gets removed from memory by Java's garbage collector again here we
3125.319 -> have an O of n operation next we're gonna work with linked lists in Java
3135.35 -> in this video we're going to look at linked lists in Java so if we type
3139.79 -> linked list we can see this class is defined in Java that util package this
3145.01 -> angle brackets you see here these are generics that means we can store any
3149.06 -> kind of objects in this list you can store integers strings any type of
3153.56 -> objects so let's press Enter this class is imported on the top
3158 -> beautiful now let's say we want to store a bunch of integers in this linked list
3162.29 -> so we add angle brackets and type integer with capital I because here
3167.84 -> we're using the integer class that is defined in Java that Lang package not
3172.34 -> the built in primitive type so we should always reference a class here this
3177.5 -> integer class wraps a primitive integer okay or we could have a linked list of
3183.02 -> strings or if we don't specify anything here we can store any kind of objects in
3188.06 -> this list one node can hold an integer another node can hold a string so let's
3193.19 -> create a list once again we have to use the new operator to allocate memory for
3197.81 -> this object so a new linked list now we have a bunch of methods for adding new
3204.35 -> items we can add at the beginning or at the end let's add 10 at the end and then
3211.22 -> 20 and 30 now let's write a print line statement and print this list there you
3222.53 -> go it looks like we have an array but actually we're dealing with a list so
3226.25 -> don't let these square brackets fool you okay now we can also add an item at the
3231.14 -> beginning so we call list that at first let's add 5 here there you go now we
3239.51 -> have 5 10 20 or 30 we have similar methods for removing items so we can
3245.9 -> call lists that remove last term of the last item we also have remove which
3251.6 -> takes an index as well as remove first for removing the first item another
3256.4 -> useful method is the contains method we can use this to see if our list contains
3261.47 -> the number 10 so let's do a print line statement and move this expression over
3267.47 -> here
3270.52 -> so our list certainly does include the value 10 we have a similar method that
3277.82 -> is lists that index of which will return the index of the first occurrence of
3283.1 -> this object so if you pass 10 here this will return 0 because that is our first
3288.92 -> item there you go another useful method is the size method so let's print that
3294.83 -> list that size this will return the number of items in this list which is
3302.63 -> three beautiful and finally the last useful method I want to cover is list
3308.72 -> the to array there are times you want to work with an
3311.57 -> array so you can convert a linked list to a regular array let's convert it to
3316.19 -> an array and store it here now we can use the arrays class to convert this
3323.78 -> array to a string and then print it on the console there you go so this is how
3331.97 -> linked lists work in Java
3335.65 -> you
3339.75 -> alright now just like the previous section we're gonna build a linked list
3343.62 -> from scratch this is a great exercise for you to practice all the materials in
3347.52 -> this course but before we get started I want to give you a couple of hints to do
3351.45 -> this exercise you need two classes a note class like this here we have a
3356.34 -> couple of fields an integer called value and a node called Nick's so with this
3362.22 -> field we can keep a reference to the next note we also need a linkless class
3367.05 -> with these two fields first and last we could call them head and tail but to be
3372.96 -> consistent with the link list class in java i decided to call this first and
3376.89 -> last I would recommend you to follow the same names so as you will see my
3380.64 -> solution you don't get confused about these names you can simply compare your
3384.24 -> code with mine and here are the metals I want you to implement in this exercise
3388.5 -> at first at last delete first till at last contains and
3393.39 -> index off these are the essential methods that we need in a linked list so
3397.71 -> spend 30 to 40 minutes on this exercise do not skip this it's super important
3404.01 -> because in the next section I'm going to talk about stacks and queues and we're
3407.85 -> gonna implement them using a linked list so linked list is one of those essential
3412.17 -> fundamental data structures that you need to master all right enough talking
3416.67 -> so grab a coffee and get started you
3424.81 -> all right let's start by implementing the at last method so public void at
3430.45 -> last we give it an integer now what should we do here the first step is to
3437.2 -> wrap this value of this integer inside a node object so we create a node object
3443.01 -> like this now as we can see we have repeated the
3447.62 -> name of the class twice and this is unnecessary we can use the VAR keyword I
3452.83 -> let the Java compiler detect the type of this variable so because we have new
3458.72 -> node on the right side the Java compiler will know that this variable is a node
3463.04 -> object all right now we need to set node that value to this item
3467.48 -> however this field is declared as private and that's why we cannot access
3472.43 -> it from outside of this node class we can come here and create a setter like
3477.62 -> public void set value which takes a value and here we type this that value
3483.32 -> equals value but I want to show you a better way I argue that this node class
3489.32 -> is part of the implementation of the linked list we don't need to work with
3493.94 -> this node class directly so this should not be declared as a public class here
3499.19 -> that can be accessed anywhere in our program earlier when we worked with the
3503.63 -> linked list class in Java if we see a node class we didn't we simply called
3507.44 -> various methods on the linked list and the linked list took care of everything
3511.22 -> under the hood so this node class is something that the linked list class
3515.39 -> shall have internally it's an implementation detail so we can remove
3521.03 -> this setter and move this class inside the linked list so we can add it here on
3529.19 -> the top there you go now because this class is
3533.519 -> declared inside the link list we have access to its private fields so we don't
3538.92 -> need a setter also we should change this to private so nowhere in our program we
3544.74 -> can access the note class that's better now another thing we need to improve
3549.269 -> here is this line with this implementation we can have a note that
3554.73 -> doesn't have a value this doesn't make sense whenever we create a note object
3558.9 -> it should always store a value so we can create a custom constructor for the note
3564.24 -> class and pass this value there so here in the note class we type public node in
3570.829 -> this constructor we add a value and we set this dot value to value now
3579.92 -> we can get rid of line 18 and simply pass the value here sorry I made them
3585.89 -> item so our code is shorter and our note object will always be in a valid state
3590.96 -> you're not gonna have a note without a value that doesn't make sense so we have
3595.099 -> a note what should we do next well that depends on the state of the linkless if
3600.289 -> our linked list is empty we need to set both the first and last note or head and
3605.539 -> tail to point to this new node otherwise we need to append this node at the end
3610.73 -> of the list let me show you so here's the first scenario we should check to
3617.45 -> see if the list is empty or not how can we do that we write an if statement like
3621.799 -> this if first equals no that means we don't have any nodes in this list
3627.259 -> because as soon as we add a node in this list first should be initialized so if
3631.88 -> first is now we should set first to this new node we should also set last to this
3638.329 -> new node or we can simplify these two lines and initialize both these
3643.519 -> variables on the same line that is better now we don't need these ugly
3648.17 -> curly braces so let's look at the other scenario where our list has at least one
3654.23 -> node so else in this case we want to add this node after the last node so we type
3662.059 -> last that next equals node we're linking the last node to this new node finally
3670.489 -> we should update last to point to this new node because now we have one new
3675.98 -> node in this list so we type last equals node we're done with the implementation
3683.269 -> of this method so let's use our new list and see if it's working properly so back
3687.47 -> to the main class I want to create a new linked list or call it list
3695.32 -> now once again we can use the VAR keyword to simplify this code here we're
3699.97 -> gonna call list then at last 10 and then 20 and then 30 now currently we don't
3707.5 -> have a method for printing this list and I realize I forgot to tell you to
3711.04 -> implement this method but in this video I don't want to spend time implementing
3714.79 -> the print method instead I'm gonna show you a different technique so we add a
3719.23 -> breakpoint on this line by clicking on this area look now it's red now we're
3724.42 -> gonna run this code using the debugger so on the top look run debug main is the
3730 -> shortcut that's ctrl + D on Mac so here we are all the previous lines are
3737.89 -> executed but this line is not so we can click on this icon that is step over now
3744.1 -> all these lines are executed so let's inspect our list object and see if it's
3748.3 -> structured properly so in this debug window let me expand this good so here
3754.87 -> we have this list let's look at the first node so the value is 10
3761.35 -> now next this is referencing another node what is this node here we have 20
3766.39 -> and this is also referencing another node in this node we have 30 but next
3773.23 -> here is set to null because this is the last node in our list so far so good
3778.51 -> what about our last node this is pointing to the same object where we
3783.31 -> have the value of 30 beautiful so we're done with this step we'll implement
3787.45 -> another method next
3793.97 -> all right let's implement the ad first method this is very similar to what we
3798.15 -> did in the previous video so public void at first which takes an item now once
3805.35 -> again we need to wrap this item inside a node object so far node equals new node
3811.7 -> of either now here we have two scenarios if the list is empty we need to add the
3817.47 -> first node otherwise we need to prepend this item to the list so we check if
3823.29 -> first is no then just like before we set first and last to this new node
3830.21 -> otherwise we want this node to point to our first node so your type node that
3839.01 -> next equals first and then we need to set the first node to this new node so
3845.37 -> first EKOS node we're done with the
3848.67 -> implementation of this method but I want to show you a technique for making this
3852.54 -> code more readable and more maintainable this is something that unfortunately
3856.02 -> most data structures books and courses don't teach you most of the code samples
3861.06 -> I say in this book look disgusting they look really ugly like old school
3864.99 -> the code we used to write in 1980s so how can we improve this code and make it
3869.94 -> more readable well look at this logic what is the point of this logic you're
3874.83 -> trying to see if this list is empty or not so we can extract this into a
3879.39 -> private method and call it is empty let me show you so here we create a private
3885.09 -> method it's private because this is implementation detail we don't want this
3889.53 -> to be accessible outside of this class so public boolean is empty now here is
3897.51 -> simply return head equals sorry first equals no
3903.94 -> now we can improve this code by replacing this logic with a call to this
3909.849 -> new method isn't the cleaner let's also modify the add last method is
3917.4 -> empty beautiful next we're going to implement the indexof method
3927.64 -> alright now let's implement the index of methods of public int index of this item
3936.12 -> what should we do here we need to traverse this list starting
3940.36 -> from the beginning all the way to the end as soon as we find an item with this
3944.71 -> value we're gonna return the index of that item
3947.56 -> but we don't have indexes here so how are we gonna implement that well we can
3951.67 -> declare a variable index and initially set it to 0 then as we're traversing
3957.13 -> this list we increment this index so we need another variable let's say current
3963.73 -> we set this to the first node now we need a while loop as long as current is
3968.56 -> not no which means we haven't reached the end of the list we need to compare
3973.27 -> the value of the current node with this item so if current that value equals
3980.26 -> this item we want to return the current index silver return index otherwise
3987.01 -> you're gonna set current to the next node so we set current to current dot
3991.99 -> next and at the same time we should also increment index now if we reach the end
3998.56 -> of the list and we can't find a node with this value we need to return
4002.73 -> negative 1 all right now let's test our code so back to the main class we added
4008.85 -> a few items here now let's print list that index of 10
4017.05 -> so we get zero beautiful what about index of 30 the last item I always look
4023.66 -> for this edge cases that is too perfect and finally an item that doesn't exist
4028.58 -> in the list so negative one beautiful next we're going to implement the
4036.11 -> contains method you
4042.43 -> the contains method is pretty easy so public boolean contains item now what
4051.4 -> should we do here once again we should traverse the list starting from the
4055.059 -> beginning all the way to the end if you find this item will return true
4058.359 -> otherwise we'll return false however we already built this logic in our index of
4063.46 -> method so we can reuse this there is no need to repeat this logic so we type
4068.17 -> return index of item does not equal to negative one so if this expression if
4076.66 -> value is to true that means we have this item in our list let's test this so back
4081.64 -> to the main class we're gonna call list that contains for D obviously we don't
4091 -> have this item what about 10 we get true beautiful that was very easy next we're
4100.06 -> gonna implement the delete first method
4107.5 -> right now let's work on removing the first item so public void remove first
4113.38 -> we don't need any parameters here this one is a bit tricky imagine our list
4119.5 -> looks like this ten point into twenty point into thirty now we want to remove
4124.81 -> the first item so we have this field called first that is currently pointing
4129.97 -> to ten we should have this point to the second node and this will bring our list
4134.799 -> forward it's gonna look like this right however we still have this object this
4140.41 -> first note that is referencing the second node so the garbage collector in
4144.549 -> Java will not be able to remove this object from the memory to solve this
4148.509 -> problem we need to remove this link now here's the tricky part
4151.99 -> if we remove this link we are not going to be able to set first to point to the
4156.819 -> second node because the moment we remove this link we lose track of the second
4161.109 -> point so to solve this problem we need two different references first and
4165.819 -> second let me show you so I'm going to bring this back let's write some code so
4172.93 -> first we declare a variable called second we said this to first dot next so
4178.299 -> ii is pointing to twenty now that we have this we can go and remove this link
4183.52 -> without worrying about losing track of the second point because we have the
4187.63 -> second variable as a backup here so we go and set first up next to know this
4194.95 -> will remove this link and finally we need to update first and set it to point
4200.46 -> three second node so we set first to second let's test this so back to the
4208.09 -> main class after adding these items let's call list dot remove first just
4215.08 -> like before we're gonna run this program using the debugger so ctrl + D okay what
4221.56 -> we have here in this list first is pointing to the note that contains 20
4227.47 -> and this is pointing to this other note beautiful now what if our list is empty
4232.6 -> and we call the remove first method let's see what happens
4239.139 -> we got an exception of type null pointer exception this is a programming error we
4244.75 -> shouldn't let this happen so let's see how the built in LinkedIn class in Java
4248.86 -> works and we'll implement the same behavior in this class so temporarily
4253.54 -> I'm gonna create another linked list this time we're using the class that is
4258.219 -> declared and the Java that util package so we're gonna create a linked list of
4263.56 -> strings we call it X and instantiate it like this now we call X EE move first
4274.139 -> let's see what happens
4278.159 -> so we got an exception but look at the type of this exception no such element
4283.8 -> exception this is different from a nullpointerexception
4286.77 -> this is a deliberate error handling so we should not be able to remove an item
4291 -> from an empty list so we're gonna go back to our linkless
4296.07 -> class and before this logic you want to add an if statement like this if this
4302.04 -> list is empty look once again we're reusing this beautiful method so if the
4308.07 -> list is empty we're gonna throw and you know such element exception this is the
4314.4 -> proper way to implement this method hey I just wanted to let you know that
4319.34 -> when I was reviewing my videos I noticed I made a mistake here I didn't count for
4323.989 -> the scenario where our linked list has a single item because this logic would
4328.55 -> work for a list that has at least two items first and second so here we need
4334.699 -> to add an if statement and check to see if first equals last that means we have
4340.58 -> a single item or a single note in this list in this situation if you want to
4344.9 -> remove this item we should set both these fields to no and then return
4351.469 -> because we don't wanna execute this logic over here so see even I make
4356.389 -> mistakes so does everybody it doesn't matter what matters is that we should
4360.71 -> always review our code we should test it with different inputs and think of
4364.52 -> various edge cases you
4371.239 -> alright now let's amend the remove last method this is the trickiest part so pay
4376.02 -> close attention we're gonna declare in your method public void remove last so
4382.82 -> let's imagine our list looks like this 10 pointing to 20 pointing to 30 and we
4390.36 -> have this last field that is pointing to this node now to remove the last item we
4396.09 -> need to find the previous node this is the tricky part so we need to traverse
4400.83 -> this list starting from the beginning the moment we get here we need to keep a
4405.239 -> reference to this node so we can update last and set it to point to the same
4410.4 -> node so let's implement this step-by-step first we want to find the
4415.739 -> previous node we start by declaring a variable called current and we set it to
4420.96 -> the first node now as long as current is not no we're gonna go forward first we
4428.489 -> check to see if current that next equals the last note if that's the case we need
4435.78 -> to break out of this loop otherwise we set current to point to the next node
4442.899 -> so at this point we have the previous note now if we're going forward I want
4448.119 -> to refactor this code and extract this logic into a separate private method
4453.129 -> because at a first glance it might not be clear what we're trying to do here so
4458.409 -> let's declare a private method that returns a node object we can call this
4464.079 -> get previous and give it a node object so whatever node we give it it will
4469.57 -> return the previous node so let's move this logic over here
4475.19 -> now instead of working with the last node you want to work with the node that
4479.9 -> is passed here so let's change that beautiful also instead of breaking out
4485.66 -> of this loop we can simply return the current node now what if we traverse the
4491.48 -> list all the way to the end but we couldn't find the node before this node
4495.49 -> we should return no now that we have all this logic in a single place we can go
4501.95 -> back to the remove last method and call get previous give it the last node and
4509.08 -> store the result in a variable called previous so in this case previous is
4516.74 -> gonna point to this node what should we do now well currently last is pointing
4523.82 -> to this node we should change last and make it point to previous so this will
4530.09 -> shrink our list like this however there's still this object that is
4534.44 -> pointing to this other object we should remove this link so the garbage
4538.64 -> collector in Java can also remove this last node from the memory so we said
4545.6 -> last two previous this will shrink our list and then to remove the link we said
4551.3 -> last that next to nan let's test our code after this point so back to the
4557.75 -> main class after adding these items let's remove the last item
4563.689 -> now let's start the debugger there you go
4568.369 -> so here's our list let's see what we have here we have first that is
4572.659 -> referencing its node this is referencing this other node and here we don't have
4578.929 -> anything after so we successfully removed the last node beautiful let's
4583.369 -> also make sure that this last field is referencing the same node beautiful so
4590.059 -> we're gonna stop the debugger now we need to think of the edge cases what if
4595.519 -> the list is empty just like before we should throw an exception so I'm going
4599.959 -> to remove these comments and check to see if the list is empty we want to
4606.26 -> throw and you know such element exception
4610.479 -> what if our list has only a single item this logic is not gonna work because
4615.559 -> there is no node before the last node we only have a single node so this logic is
4620.689 -> assuming that our list has at least two nodes so we need another if statement if
4628.07 -> first equals last that means we have a single node in this list in this
4634.939 -> situation should set both these fields to know and
4638.98 -> then return so this other logic is not executed so this is how we implement the
4645.44 -> remove last method hey guys Marsha I wanted to let you know
4651.22 -> that this video is actually part of my ultimate data structures and algorithms
4655.21 -> course the complete course is 13 hours long and I've divided it into three
4659.71 -> parts so you can take and complete each part easily if you're serious about
4663.43 -> learning data structures and algorithms I highly encourage you to take this
4666.94 -> course and learn all the essential data structures and algorithms from scratch
4670.93 -> it's much easier and faster than jumping from one tutorial to another we'll be
4675.4 -> talking about various types of data structures such as linked lists stacks
4679.36 -> queues hash tables binary trees AVL trees heaps tryes graphs and various
4686.5 -> types of sorting searching and string manipulation algorithms the course is
4690.91 -> packed with almost 100 interview questions these are the interview
4693.97 -> questions that get asked that companies like Google Microsoft and Amazon you can
4698.23 -> watch the course online or offline anytime anywhere as many times as you
4702.46 -> want and you would also get a certificate of completion and a 30-day
4705.76 -> money-back guarantee it's exactly like this tutorial it just has more content
4709.69 -> if you're interested click on the link below this video to enroll in the course
4713.23 -> thank you and have a great day

Source: https://www.youtube.com/watch?v=BBpAmxU_NQo