- 00:00:01 hi welcome to this course
- 00:00:03 my name is maximilian schwarzmuller and
- 00:00:05 i will be your instructor in this course
- 00:00:07 now in this course we're going to
- 00:00:09 explore javascript data structures
- 00:00:11 and we're going to do this step by step
- 00:00:14 and in great detail we're going to start
- 00:00:16 with all the built-in data structures
- 00:00:18 sets maps arrays objects but then we're
- 00:00:21 also going to dive into a lot of
- 00:00:23 custom data structures which we can
- 00:00:25 build on our own things like stacks and
- 00:00:27 queues and
- 00:00:28 trees and binary search trees and
- 00:00:30 priority queues and heaps and graphs and
- 00:00:33 there's a lot of content in this course
- 00:00:36 we're going to get there step by step
- 00:00:37 and i will explain
- 00:00:39 what problems which kind of problems
- 00:00:41 these data structures
- 00:00:42 solve and of course you will learn how
- 00:00:44 to build those data structures
- 00:00:46 and how to work with those data
- 00:00:47 structures on your own
- 00:00:49 now this course does have one
- 00:00:51 prerequisite you need to know about
- 00:00:53 javascript algorithms you need to know
- 00:00:55 about time complexity
- 00:00:57 so for example if you took my javascript
- 00:01:00 algorithms course before this course
- 00:01:02 you will be well prepared to get the
- 00:01:04 most out of this course as well
- 00:01:06 and with that i'm super excited to get
- 00:01:08 started i hope you are too
- 00:01:10 let's dive in
- 00:01:19 so let's dive into the obviously most
- 00:01:22 important question
- 00:01:24 what exactly are data structures in
- 00:01:26 programming
- 00:01:28 and why do we need them data structures
- 00:01:32 simply allow you to manage data so data
- 00:01:35 structures are the
- 00:01:36 things in your code that allow you to
- 00:01:39 store and retrieve and delete
- 00:01:41 and in general manage data examples
- 00:01:45 in the case of javascript but actually
- 00:01:47 for most programming languages
- 00:01:49 would be arrays objects maps
- 00:01:52 sets something like this now just to
- 00:01:55 make it clear what i'm talking about
- 00:01:57 again referring to javascript here so
- 00:02:00 this
- 00:02:00 is the javascript syntax arrays where
- 00:02:03 you store a list of data like a couple
- 00:02:05 of numbers or a couple of strings that's
- 00:02:08 a data structure
- 00:02:09 objects where you group data together
- 00:02:12 into one object
- 00:02:13 and where you for example have a string
- 00:02:15 the name of a person
- 00:02:16 and the number the age of a person
- 00:02:18 grouped together in one object
- 00:02:20 and then lesser known i would argue you
- 00:02:23 also have
- 00:02:24 maps in javascript i'll come back to
- 00:02:26 those and you have sets
- 00:02:29 these are the four big data structures
- 00:02:32 the four main data structures
- 00:02:34 you have in javascript and no matter at
- 00:02:36 which
- 00:02:37 programming language you're looking you
- 00:02:39 will typically find
- 00:02:40 data structures like that in other
- 00:02:43 programming languages as well
- 00:02:45 maps sets arrays and or lists
- 00:02:48 that is what you work with in pretty
- 00:02:49 much all programming languages
- 00:02:52 now why do we need such different data
- 00:02:54 structures
- 00:02:56 well first of all of course programs so
- 00:02:58 the code you write
- 00:03:00 are all about doing something and for
- 00:03:02 that
- 00:03:03 something you pretty much always work
- 00:03:05 with data
- 00:03:06 and that data needs to be managed for
- 00:03:08 example also intermediate results which
- 00:03:11 you might be deriving in your code
- 00:03:13 and typically you have tasks that
- 00:03:15 require different kinds of data or
- 00:03:18 different ways of managing data here are
- 00:03:20 a couple of common use cases
- 00:03:23 you might have tasks where you need
- 00:03:24 ordered lists of data
- 00:03:26 and where duplicate data is wanted or
- 00:03:29 allowed
- 00:03:30 in other tasks you might not care
- 00:03:33 whether the order of the data is kept
- 00:03:35 and you might not want or need duplicate
- 00:03:38 data
- 00:03:38 so you might be fine with working with
- 00:03:40 unique values or you might actually want
- 00:03:43 unique values
- 00:03:44 then you might have cases where you
- 00:03:46 don't just care about the values and
- 00:03:48 whether they are
- 00:03:49 ordered or not you might actually want
- 00:03:51 to map them
- 00:03:52 to an identifier you might want key
- 00:03:55 value pairs
- 00:03:56 of unordered or ordered data
- 00:04:00 now for these different use cases you
- 00:04:02 would have arrays in the case of
- 00:04:03 ordered lists of data arrays in
- 00:04:06 javascript look like this
- 00:04:07 and as a side note ordered does not mean
- 00:04:10 that the elements themselves must have a
- 00:04:13 order
- 00:04:14 in the sense of being sorted in an
- 00:04:16 ascending or descending way
- 00:04:17 as you see in the example this array is
- 00:04:19 not sorted it just means
- 00:04:22 that the insertion order is memorized
- 00:04:25 is kept so that the element five in this
- 00:04:28 example
- 00:04:28 always is the third element in the array
- 00:04:31 and that it doesn't magically change
- 00:04:33 behind the scenes
- 00:04:34 that is what ordered means here and
- 00:04:36 that's important
- 00:04:38 now if the order does not matter and if
- 00:04:40 you don't want duplicates
- 00:04:42 a set might be the right choice a set in
- 00:04:44 javascript can be created with the new
- 00:04:46 set constructor
- 00:04:48 and then with the add method you can add
- 00:04:49 elements to a set
- 00:04:51 and we'll see how we can work with sets
- 00:04:53 over the next lectures
- 00:04:55 sometimes you need the key value pairs
- 00:04:58 and for that and javascript you of
- 00:04:59 course have the object
- 00:05:01 that allows you to map data together
- 00:05:03 into one object
- 00:05:04 to group it into one object and you can
- 00:05:07 assign
- 00:05:07 keys identifiers of your choice and
- 00:05:10 retrieve the values
- 00:05:11 with help of those keys and you also
- 00:05:14 have the map which does
- 00:05:15 almost the same thing but i'll come back
- 00:05:18 to the differences between maps
- 00:05:19 and objects later in this course
- 00:05:23 now one quick important note this course
- 00:05:26 will mainly be about custom data
- 00:05:29 structures
- 00:05:29 so data structures which you as a
- 00:05:31 developer build on your own
- 00:05:34 always in the end based on what's built
- 00:05:36 into the language so based on arrays and
- 00:05:39 objects and so on
- 00:05:40 but then simply enhanced with certain
- 00:05:42 functionalities
- 00:05:43 that's what this course is about but in
- 00:05:45 order to make sure
- 00:05:47 that we can dive into all those custom
- 00:05:49 data structures
- 00:05:50 i start with the built-in ones first so
- 00:05:53 that it's very clear what a data
- 00:05:55 structure
- 00:05:56 is and how the built-in ones work
- 00:05:58 because if that knowledge is missing
- 00:06:00 it will be hard to derive custom data
- 00:06:02 structures
- 00:06:03 and with that let's take a closer look
- 00:06:05 at those built-in data structures
- 00:06:07 so that we fully understand them and
- 00:06:09 thereafter i will also give you an
- 00:06:11 example for a custom data structure
- 00:06:18 so let's start with arrays and let's
- 00:06:20 take a closer look
- 00:06:21 this is an array it's a list of comma
- 00:06:25 separated data
- 00:06:26 in the case of javascript you can create
- 00:06:28 it by using these
- 00:06:29 square brackets this square bracket
- 00:06:31 notation
- 00:06:32 now there are a couple of important
- 00:06:34 characteristics about arrays
- 00:06:36 for example the insertion order is kept
- 00:06:39 it's memorized
- 00:06:40 by javascript so the element three will
- 00:06:43 always be the second element in this
- 00:06:46 array and you can
- 00:06:47 retrieve it by index therefore you have
- 00:06:50 an index
- 00:06:50 which clearly identifies the position of
- 00:06:53 an element
- 00:06:53 and that's why the order is important so
- 00:06:56 that the same index
- 00:06:57 always gives you the same element unless
- 00:06:59 the element of course was replaced or
- 00:07:01 removed
- 00:07:03 arrays in javascript also are iterable
- 00:07:06 which simply means that you can use them
- 00:07:07 with the for
- 00:07:08 off loop to loop through all the values
- 00:07:10 in there
- 00:07:12 in addition arrays and javascript are
- 00:07:14 dynamic which means
- 00:07:16 that the size of the array the length of
- 00:07:18 it adjusts
- 00:07:19 dynamically and automatically that's not
- 00:07:22 the case for
- 00:07:23 all programming languages there are
- 00:07:25 programming languages out there
- 00:07:27 where you clearly have to define how
- 00:07:30 long an array should be
- 00:07:31 before you can use it not with
- 00:07:33 javascript
- 00:07:34 in the case of javascript an array grows
- 00:07:37 with the number of elements
- 00:07:38 and also shrinks with it that is
- 00:07:40 important for
- 00:07:41 you as a developer because it makes
- 00:07:43 using it easier
- 00:07:44 but it's also important for memory
- 00:07:47 management and
- 00:07:48 performance optimizations javascript
- 00:07:51 takes care
- 00:07:51 that it doesn't occupy too much memory
- 00:07:54 which is why that automatic growing and
- 00:07:56 shrinking off the array is really
- 00:07:58 important and it's all baked into the
- 00:08:00 javascript array which is awesome
- 00:08:02 in addition in the array duplicate
- 00:08:05 values are allowed
- 00:08:07 in the above example we only have unique
- 00:08:09 values but you would be allowed to have
- 00:08:11 two ones two threes two twos whatever
- 00:08:13 you want in there and of course also
- 00:08:15 more than two
- 00:08:16 also noteworthy in javascript you can
- 00:08:19 also mix
- 00:08:20 types in an array so you can have an
- 00:08:22 array of just
- 00:08:23 numbers like in the example above but
- 00:08:26 you could also mix
- 00:08:27 numbers with strings with objects even
- 00:08:29 with nested arrays
- 00:08:31 all in one at the same array that's all
- 00:08:33 allowed in javascript arrays
- 00:08:36 now there is one downside about arrays
- 00:08:38 and about
- 00:08:39 lists of data in general and that is
- 00:08:42 that the deletion of elements and
- 00:08:44 finding elements can require extra work
- 00:08:47 and that simply means that it can be a
- 00:08:49 bit more performance intensive
- 00:08:51 and a bit more difficult now let's play
- 00:08:53 around with arrays in code a little bit
- 00:08:55 so that we get a feeling for all those
- 00:08:57 points and you understand what i mean
- 00:09:00 i have a very simple starting setup here
- 00:09:03 essentially just
- 00:09:04 two files it's the index.html file which
- 00:09:06 is an empty html
- 00:09:08 file the only thing i have in there is
- 00:09:10 this script import to app.js
- 00:09:12 and that's the file where we're now
- 00:09:14 going to play around with code
- 00:09:16 we're only going to evaluate some
- 00:09:18 results here in the browser javascript
- 00:09:20 console
- 00:09:21 because this is a obviously very
- 00:09:23 theoretic course
- 00:09:25 so let's play around with arrays and for
- 00:09:27 that i'll have a couple of
- 00:09:29 names here and as you learned you can
- 00:09:32 create an array in javascript with just
- 00:09:34 square brackets and in there we can have
- 00:09:36 max manu
- 00:09:38 and let's say julie so we have three
- 00:09:41 strings in here
- 00:09:42 now as i mentioned you are allowed to
- 00:09:44 also mix
- 00:09:45 types so we could easily also add a
- 00:09:47 number in here or even add a nested
- 00:09:49 array if we wanted to
- 00:09:51 in addition we are allowed to have
- 00:09:53 duplicate values so i can have max in
- 00:09:55 there twice
- 00:09:56 or three times or how often i want
- 00:09:59 now what we can also do is we can access
- 00:10:03 elements by index
- 00:10:04 so we can access manu with index one
- 00:10:07 because
- 00:10:07 the index for arrays starts at zero
- 00:10:11 now that's basically all knowledge you
- 00:10:13 should already have but just to make it
- 00:10:15 really clear
- 00:10:15 this is important the index starts at 0
- 00:10:18 so if we access the element at index 1
- 00:10:20 with this notation
- 00:10:21 we access manual and that's why we can
- 00:10:24 reload here
- 00:10:25 and see menu now in addition
- 00:10:28 arrays are iterable that means we can
- 00:10:30 use the for
- 00:10:31 off loop to go through all the names
- 00:10:34 here like this
- 00:10:36 and then for example to simply console
- 00:10:38 lock them or do whatever you want to do
- 00:10:40 with them
- 00:10:41 this code works because arrays are
- 00:10:44 iterable if we do that we see all the
- 00:10:46 names being printed out
- 00:10:48 now the size and length adjusts
- 00:10:50 dynamically
- 00:10:52 and we can kind of see this if i
- 00:10:54 console.log names.length here
- 00:10:56 and then maybe after the loop we
- 00:10:58 actually add a new element
- 00:11:00 with the push method which is a built-in
- 00:11:02 method we can call on array objects
- 00:11:04 and here we add let's say julie again to
- 00:11:07 really prove that
- 00:11:08 duplicates allowed concept if we then
- 00:11:12 console log the length again we of
- 00:11:14 course see that initially we have
- 00:11:15 four and then we have five now that does
- 00:11:18 not necessarily mean
- 00:11:19 that now more space is occupied in
- 00:11:22 memory than before
- 00:11:23 because we don't really see how much
- 00:11:24 space was allocated
- 00:11:26 and maybe javascript allocated more
- 00:11:28 space than it needed initially
- 00:11:30 to make it easier to add new elements
- 00:11:32 but nonetheless
- 00:11:33 the size also in memory grows
- 00:11:35 dynamically
- 00:11:36 with the number of values
- 00:11:40 now about the deletion and finding
- 00:11:42 elements
- 00:11:43 of course if we know the index of an
- 00:11:45 element which we want to retrieve
- 00:11:47 retrieving it is easy and very fast but
- 00:11:49 we don't always know that
- 00:11:51 and sometimes we just know the value and
- 00:11:53 we want to know the index
- 00:11:55 of that element then let's say we want
- 00:11:57 to find
- 00:11:58 julie in there in that case we can use
- 00:12:01 names and the build in find method
- 00:12:04 find executes a function on every
- 00:12:07 element in the array
- 00:12:08 and that function should return true if
- 00:12:10 it's the element we're looking for
- 00:12:12 and falls otherwise so this runs on
- 00:12:14 every element and should return true if
- 00:12:16 it's the right element
- 00:12:17 so here we could check if the element is
- 00:12:19 equal to julie
- 00:12:20 of course this doesn't make too much
- 00:12:22 sense because this will just return
- 00:12:23 julie
- 00:12:24 so here maybe find index is the better
- 00:12:26 example because that allows us to find
- 00:12:28 the index for a value we know in case we
- 00:12:31 guess what don't know the index yet so
- 00:12:33 that would be
- 00:12:34 julie index the find method on the other
- 00:12:36 hand can be very useful
- 00:12:38 if you have an array full of objects and
- 00:12:40 you want to find an
- 00:12:41 entire object by one value of one
- 00:12:44 property
- 00:12:44 of the object now what's the problem
- 00:12:47 about find index and find and all other
- 00:12:49 find methods you have in javascript
- 00:12:52 well this has to go through all the
- 00:12:54 elements up to the element
- 00:12:56 where this then returns true so in this
- 00:12:58 case this function which we passed to
- 00:13:00 find index
- 00:13:01 does not just run once for julie no it
- 00:13:04 starts at the beginning of the array
- 00:13:06 and it runs it for max and finds out
- 00:13:08 that this does not return true
- 00:13:10 therefore it runs it for menu and still
- 00:13:12 doesn't return true
- 00:13:13 and then it runs it for julie and that
- 00:13:16 means that if julie would be the last
- 00:13:17 element we would go through
- 00:13:19 all the elements in the array just to
- 00:13:22 then find
- 00:13:22 that final element now there is nothing
- 00:13:25 you can do about that
- 00:13:26 but obviously this is a downside not one
- 00:13:29 you can get rid of but something you
- 00:13:30 should be aware of
- 00:13:32 finding elements can be very performance
- 00:13:34 intensive
- 00:13:35 if you have long arrays especially of
- 00:13:37 course
- 00:13:39 and for deleting elements it's pretty
- 00:13:41 much the same there are various
- 00:13:43 techniques for getting rid of elements
- 00:13:45 in arrays
- 00:13:45 for example we can use the splice method
- 00:13:49 splice allows us to modify an array and
- 00:13:52 remove elements
- 00:13:53 for example i could splice the element
- 00:13:55 at index 2
- 00:13:57 or starting at index 2 and then splice
- 00:14:00 one element from that index on
- 00:14:02 i could also splice two elements but i
- 00:14:04 just splice one and that would simply
- 00:14:05 remove
- 00:14:06 one element after index two so for now
- 00:14:10 console.log
- 00:14:11 names you will see that our new array
- 00:14:14 has to be at the end because we added
- 00:14:17 here
- 00:14:18 but it does not have the original julie
- 00:14:20 at third position anymore
- 00:14:22 instead there we have max and the reason
- 00:14:24 for that is that we removed the
- 00:14:26 element at index 2 which was julie and
- 00:14:29 just that element
- 00:14:30 because we removed one element here with
- 00:14:32 splice now the problem with that is
- 00:14:34 this also can be quite performance
- 00:14:36 intensive because whilst we don't have
- 00:14:38 to look for the element
- 00:14:40 we have to move all the elements after
- 00:14:42 the elemented was removed because if we
- 00:14:44 remove julie
- 00:14:45 of course max has to be moved to the new
- 00:14:48 position
- 00:14:49 3 which is now empty and any element
- 00:14:51 after max
- 00:14:52 like julie which we added here also then
- 00:14:55 has to move one place ahead
- 00:14:57 so all the elements after the element
- 00:14:59 that was deleted
- 00:15:00 have to move and that again is a lot of
- 00:15:02 work on a lot of elements in the array
- 00:15:04 potentially
- 00:15:05 that's what i mean with extra work
- 00:15:08 that's being required for deletion
- 00:15:10 and for finding elements
- 00:15:16 so now with arrays out of the way a very
- 00:15:18 useful construct for managing lists of
- 00:15:20 data
- 00:15:21 let's have a look at sets because sets
- 00:15:24 are also about
- 00:15:25 lists of data but they work a bit
- 00:15:27 differently we can create and
- 00:15:29 work with sets like this in javascript
- 00:15:32 we don't have such a shortcut
- 00:15:34 syntax like with the square brackets for
- 00:15:36 arrays instead we have to use the set
- 00:15:38 constructor function and then
- 00:15:40 on the created object we can use the add
- 00:15:43 method to add items to the set
- 00:15:45 now you already see in this example
- 00:15:47 there is one important thing about sets
- 00:15:49 duplicate items are not allowed you
- 00:15:52 won't get an
- 00:15:52 error if you try to add one but it also
- 00:15:54 won't be added a second time or a third
- 00:15:57 time it's just added once
- 00:15:59 now what else is interesting about sets
- 00:16:02 the insertion order
- 00:16:03 unlike for arrays is not stored so
- 00:16:06 you can't rely on the order being kept
- 00:16:09 therefore of course
- 00:16:10 you can't access elements with index but
- 00:16:13 instead you'll have a method
- 00:16:14 for getting access to an element sets
- 00:16:17 like arrays are iterable though so you
- 00:16:20 can use the for off loop there
- 00:16:22 but the order of course could be
- 00:16:24 different for different loops so
- 00:16:26 the order is not guaranteed that's
- 00:16:28 something to keep in mind
- 00:16:29 and the size and length is also adjusted
- 00:16:32 dynamically so just like with
- 00:16:33 arrays you don't have to worry about
- 00:16:35 that now
- 00:16:37 as i mentioned duplicate values are not
- 00:16:39 allowed so in a set
- 00:16:41 you'll always only have unique values
- 00:16:45 and there's one other big difference
- 00:16:47 compared to arrays
- 00:16:49 deletion and finding elements is
- 00:16:52 more trivial and faster than with arrays
- 00:16:57 the simple reason for that is that the
- 00:16:59 order does not matter
- 00:17:01 sets can internally be managed
- 00:17:03 differently
- 00:17:04 for arrays you always have to go through
- 00:17:07 all elements
- 00:17:08 and so on now sets can simply store the
- 00:17:10 data more efficiently internally because
- 00:17:12 the position
- 00:17:14 of a value does not matter so there is
- 00:17:16 no need to go through all
- 00:17:18 values it can instead use different
- 00:17:20 techniques for quickly finding a value
- 00:17:22 the same for deleting if you delete an
- 00:17:24 element from a set
- 00:17:25 it doesn't have to move all other
- 00:17:27 elements
- 00:17:28 because elements didn't have a position
- 00:17:30 in the first place
- 00:17:31 so there is no need to move anything
- 00:17:34 just because something was deleted
- 00:17:36 now let's have a look at sets in code as
- 00:17:38 well
- 00:17:40 for that i emptied the app.js file and
- 00:17:43 in there let's create a new set
- 00:17:45 let's say a set of ids and every id is
- 00:17:48 only allowed once
- 00:17:50 as i said we create a set with the new
- 00:17:52 set constructor here
- 00:17:53 and to that constructor you actually can
- 00:17:56 pass an array of values
- 00:17:57 and then these values would be your
- 00:17:59 initial values in the set
- 00:18:02 if this array would contain duplicate
- 00:18:04 values only one
- 00:18:05 occurrence of the value would be added
- 00:18:07 to the set sidenote
- 00:18:09 just as with arrays you can have any
- 00:18:11 kind of data in sets though
- 00:18:13 and you can also have mixed types of
- 00:18:15 data in one and the same set
- 00:18:17 so here we can for example add an id
- 00:18:20 a b c we can add the id 1
- 00:18:24 and we could add other types of data as
- 00:18:26 well so maybe also bb2
- 00:18:29 and then let's say we also try to add
- 00:18:32 one
- 00:18:32 again now if we loop through the
- 00:18:36 elements here
- 00:18:37 because sets are iterable as you learned
- 00:18:40 we'll see that there's only one one in
- 00:18:43 there and not
- 00:18:44 two once so if we save this code and
- 00:18:47 run it you see abc 1 and bb2
- 00:18:51 you don't see a second one now here the
- 00:18:54 order
- 00:18:54 also looks like the insertion order but
- 00:18:56 again it is not guaranteed
- 00:18:59 so don't rely on the order the order
- 00:19:02 however
- 00:19:02 also shouldn't matter too much because
- 00:19:04 you'll not be able
- 00:19:06 to do ids one anyways that's not a
- 00:19:09 syntax that works
- 00:19:10 if you try that you get undefined
- 00:19:14 instead if you want to get a value you
- 00:19:17 simply call
- 00:19:18 has because you have to think about sets
- 00:19:21 differently you don't retrieve a value
- 00:19:23 from there
- 00:19:24 because it only stores those values
- 00:19:27 anyways
- 00:19:27 instead you only need one piece of
- 00:19:29 information you only need to know
- 00:19:31 does this set have a value or not
- 00:19:35 and if it has it well then you can use
- 00:19:37 it
- 00:19:38 right that's the same as retrieving it
- 00:19:39 in the end if you know it's part of the
- 00:19:41 set you got the value
- 00:19:42 so here we could check if it has abc and
- 00:19:46 this will of course return
- 00:19:47 true and then in the code thereafter we
- 00:19:49 could work with abc for example because
- 00:19:51 we know that is part of the set
- 00:19:54 this is how you have to think about it
- 00:19:56 now you can always add
- 00:19:58 new values here with the add method and
- 00:20:01 you can also delete
- 00:20:02 values with the delete method if i then
- 00:20:05 console log
- 00:20:06 my ids set thereafter you will see
- 00:20:10 this is how it's being printed looks a
- 00:20:12 bit like an object
- 00:20:13 it is an object but not a normal object
- 00:20:16 a different kind of object behind the
- 00:20:17 scenes
- 00:20:18 and what we can see here is that the bb2
- 00:20:21 value is missing
- 00:20:22 side note console log makes it look like
- 00:20:25 there is a position assigned to every
- 00:20:27 element again
- 00:20:29 that is not guaranteed the order is not
- 00:20:31 guaranteed
- 00:20:32 at all now that's how sets work and sets
- 00:20:37 are there for a great
- 00:20:39 choice if you need lists of data but you
- 00:20:42 don't want duplicate values
- 00:20:44 and you don't care so much about the
- 00:20:45 order and the position
- 00:20:47 instead if you manage something like
- 00:20:49 let's say ids
- 00:20:50 where you only care about whether an id
- 00:20:53 is already stored or not for example
- 00:20:55 then sets might be a great choice
- 00:21:02 so time for the official comparison we
- 00:21:04 got arrays
- 00:21:05 and we got sets now in javascript the
- 00:21:08 great thing is you can always use
- 00:21:10 arrays you can really always use arrays
- 00:21:12 it's a highly flexible data structure
- 00:21:15 and you can use arrays for any kinds of
- 00:21:17 data and that's why
- 00:21:18 in probably 99 of all scripts you
- 00:21:22 only see arrays if you have lists of
- 00:21:25 data
- 00:21:26 you especially have to use arrays if the
- 00:21:29 order matters
- 00:21:30 and or you want duplicates now it could
- 00:21:33 be worth a thought
- 00:21:34 to use a set though if you do not care
- 00:21:38 about duplicates if you want unique
- 00:21:41 values and if the order does not matter
- 00:21:43 and sets can especially actually provide
- 00:21:46 an advantage over arrays
- 00:21:48 if you delete a lot of values and if you
- 00:21:51 often
- 00:21:51 look for a certain values so if you
- 00:21:53 would often
- 00:21:54 go through the entire array to find a
- 00:21:56 value and to validate
- 00:21:58 if that value exists in such cases sets
- 00:22:00 can be awesome because they
- 00:22:02 actually provide better performance for
- 00:22:04 that
- 00:22:05 now of course for short lists of data
- 00:22:07 that won't matter
- 00:22:08 but if you have long lists with a lot of
- 00:22:11 data this
- 00:22:12 performance difference might make a real
- 00:22:14 difference
- 00:22:15 and that combined with the uniqueness
- 00:22:17 which also could be an advantage in some
- 00:22:18 cases
- 00:22:19 that might be a reason to use a set over
- 00:22:22 an array arrays however as i mentioned
- 00:22:26 at the beginning are your go-to default
- 00:22:29 list which you'll use in javascript all
- 00:22:31 the time
- 00:22:37 so with arrays and sets we had a
- 00:22:39 detailed look at our
- 00:22:40 list data structures in javascript so
- 00:22:43 data structures that simply help us
- 00:22:45 with managing lists of data now it's
- 00:22:48 time for objects
- 00:22:50 and an object can look like this we can
- 00:22:52 create it with this
- 00:22:54 shortcut here with this shorthand
- 00:22:55 notation in javascript with the curly
- 00:22:58 braces
- 00:22:59 and objects can have key value pairs
- 00:23:01 like name and h
- 00:23:02 which store a string and a number but
- 00:23:05 objects also
- 00:23:06 and that is important to keep in mind
- 00:23:08 can have methods
- 00:23:09 attached to them they can have
- 00:23:11 functionality that's part of the object
- 00:23:14 like discrete method which then in turn
- 00:23:16 is actually able to interact with the
- 00:23:19 key value pairs
- 00:23:20 with the so-called properties of the
- 00:23:22 object
- 00:23:23 now objects in general are unordered key
- 00:23:26 value pairs of data
- 00:23:28 the element axis is done with help of
- 00:23:31 the key name
- 00:23:32 so of the property name for example to
- 00:23:34 get the h
- 00:23:35 value you use age as an identifier
- 00:23:39 objects are not really iterable there is
- 00:23:42 the for
- 00:23:42 in loop which is built for objects but
- 00:23:44 you won't be able to use the for off
- 00:23:46 loop
- 00:23:47 you won't be able to access the values
- 00:23:49 with help of some index or anything like
- 00:23:51 that
- 00:23:53 keys are unique values are not so
- 00:23:56 every key name must only appear once
- 00:23:59 you can't have two h properties in the
- 00:24:02 same object
- 00:24:02 if you do the second property would
- 00:24:04 simply overwrite the first one
- 00:24:06 but you can absolutely have the same
- 00:24:08 value multiple times
- 00:24:10 if you store the number 31 for age and
- 00:24:13 also for
- 00:24:14 old age or some other property name that
- 00:24:17 would be perfectly fine
- 00:24:19 now one other important thing is that
- 00:24:21 the keys
- 00:24:22 for your properties actually have to be
- 00:24:24 strings numbers or
- 00:24:26 symbols in javascript most of the time
- 00:24:29 this is all what you want
- 00:24:31 but it is worth noting that your keys
- 00:24:33 for example
- 00:24:34 may not be objects themselves so it has
- 00:24:37 to be something like
- 00:24:37 name or one or a symbol but it's not
- 00:24:41 allowed to be an
- 00:24:42 object or an array now
- 00:24:45 objects in general therefore can be
- 00:24:47 summarized as
- 00:24:48 data structures or as constructs
- 00:24:51 that can store data but that also can
- 00:24:54 contain
- 00:24:55 extra functionalities namely the methods
- 00:24:58 you can add
- 00:24:58 in addition of course it's also worth
- 00:25:00 noting that objects in javascript have
- 00:25:03 this prototypes thing
- 00:25:05 that you can use constructor functions
- 00:25:06 to create objects
- 00:25:08 and that you got all these extra
- 00:25:10 features on top of objects
- 00:25:12 so to say so it's really more than just
- 00:25:15 a data structure
- 00:25:16 nonetheless objects in javascript are
- 00:25:19 the main
- 00:25:19 key value story you use whenever you
- 00:25:22 don't need a list but
- 00:25:23 well a key data store so whenever you
- 00:25:25 want to group data together
- 00:25:27 let's also see objects in code therefore
- 00:25:30 again back in an empty app.js file we
- 00:25:33 can create our person object
- 00:25:36 where we have the first name let's say
- 00:25:38 which is max
- 00:25:39 and the age which is 31 and hobbies
- 00:25:42 which is an array let's say
- 00:25:44 with sports and cooking
- 00:25:48 now as i mentioned you won't be able to
- 00:25:50 use
- 00:25:51 the for off loop here and console
- 00:25:54 log the element if you do that
- 00:25:57 you will get an error that person is not
- 00:26:00 iterable
- 00:26:01 so that you can't use it and you also
- 00:26:04 can't access
- 00:26:06 elements by index this will not give you
- 00:26:09 an
- 00:26:09 error but instead now this would simply
- 00:26:11 look for a key
- 00:26:12 named zero and we have no zero key in
- 00:26:15 here
- 00:26:16 we only have the keys first name age and
- 00:26:18 hobbies
- 00:26:19 so therefore this would give us
- 00:26:20 undefined now we can absolutely access
- 00:26:24 by key name so we could enter first name
- 00:26:26 here like this
- 00:26:28 this is a string key name we don't have
- 00:26:30 the quotes here but this is actually the
- 00:26:32 same as adding quotes
- 00:26:34 you just can omit it that's simply extra
- 00:26:36 convenience you have built into
- 00:26:38 javascript
- 00:26:39 but this is a string property name so
- 00:26:41 here we can access it like this as a
- 00:26:43 string
- 00:26:44 and now we get access to the max value
- 00:26:47 but you also certainly know the dot
- 00:26:49 notation which you can use instead
- 00:26:52 this also is possible now as i mentioned
- 00:26:55 you
- 00:26:55 are for example not allowed to use an
- 00:26:57 array as
- 00:26:58 a key name here you see i get an error
- 00:27:01 in the ide
- 00:27:02 and i get an error in the browser as
- 00:27:04 well so this does
- 00:27:05 not work here and you also may not have
- 00:27:09 duplicate key names
- 00:27:11 you are allowed to do that actually you
- 00:27:13 see i won't get an error here
- 00:27:16 but what you'll notice is of course that
- 00:27:18 if i now access the age property like
- 00:27:20 this
- 00:27:20 we won't print 31 but simply 32
- 00:27:23 so age is overwritten and i guess that
- 00:27:26 makes sense if you think about the fact
- 00:27:28 that we simply have a group of data here
- 00:27:30 of course every identifier may only be
- 00:27:32 used once
- 00:27:34 now you can always add new properties to
- 00:27:36 an object with the dot notation
- 00:27:38 because you are allowed in javascript to
- 00:27:40 access property names that don't exist
- 00:27:42 yet
- 00:27:43 for example last name that is allowed
- 00:27:46 and thereafter i can console.log person
- 00:27:49 and i'll see that new
- 00:27:51 last name here it is so this is
- 00:27:54 something you are allowed to do
- 00:27:56 and you can delete properties with the
- 00:27:58 delete operator
- 00:28:00 you can delete person.lastname for
- 00:28:04 example or
- 00:28:05 person.h here for example to get rid of
- 00:28:08 that
- 00:28:08 and thereafter you'll see that person
- 00:28:10 does no longer have
- 00:28:11 an age here we only got first name
- 00:28:14 hobbies and last name
- 00:28:15 so the delete operator can be used to
- 00:28:17 get rid of a property
- 00:28:19 there are other ways for adding and
- 00:28:22 configuring and deleting properties as
- 00:28:24 well
- 00:28:24 but you can learn things like that in my
- 00:28:26 complete guide or in the mdn docs
- 00:28:29 this here is just a quick wrap up and
- 00:28:31 summary about objects
- 00:28:32 so that we are all on the same page
- 00:28:34 regarding objects
- 00:28:36 now one very important feature of course
- 00:28:38 is the feature which i already mentioned
- 00:28:40 on the slide
- 00:28:41 your objects can have methods inside of
- 00:28:44 them
- 00:28:45 so you can add functions as values for
- 00:28:47 your properties
- 00:28:48 and you can use this shorthand syntax
- 00:28:50 here for adding such a method
- 00:28:54 there for example i could console.log hi
- 00:28:57 i am
- 00:29:00 this first name and this would print
- 00:29:04 high imax if we execute person.greet
- 00:29:08 like this so with this we execute this
- 00:29:11 function and therefore we see high immax
- 00:29:14 here
- 00:29:15 this is really special because this
- 00:29:17 shows us that the object
- 00:29:19 is not just a data storage but that we
- 00:29:21 can actually also add functionality to
- 00:29:24 it
- 00:29:24 because this here clearly is extra
- 00:29:26 functionality
- 00:29:27 that interacts with the rest of the data
- 00:29:29 that's in there so this is more than
- 00:29:31 just a dump
- 00:29:32 data storage and that's all we need to
- 00:29:34 know about
- 00:29:35 objects for now now let's have a look at
- 00:29:38 maps
- 00:29:43 now that we explored objects let's
- 00:29:45 explore maps
- 00:29:46 the syntax for using maps in javascript
- 00:29:49 looks like this
- 00:29:50 just like with sets we create a map with
- 00:29:52 a constructor function and then we got
- 00:29:54 certain methods for interacting with the
- 00:29:56 map
- 00:29:56 specifically for adding new key value
- 00:29:59 pairs we use the set method
- 00:30:01 and there we can use different kinds of
- 00:30:04 keys
- 00:30:05 including booleans but also objects and
- 00:30:08 arrays and i'll come back to that later
- 00:30:10 and we can store any kind of value for
- 00:30:12 any key
- 00:30:13 now the interesting thing about maps is
- 00:30:15 that the key value pairs are actually
- 00:30:17 ordered
- 00:30:17 so that's a difference to the object
- 00:30:20 just like with the object though
- 00:30:22 we access elements by key one important
- 00:30:25 difference again compared to objects
- 00:30:28 is that maps are iterable so you can use
- 00:30:31 the for
- 00:30:31 off loop there but again similar to
- 00:30:35 objects is that
- 00:30:36 keys are unique the values are not so
- 00:30:38 that's the same as with objects you
- 00:30:40 must not have the same key multiple
- 00:30:42 times if you do
- 00:30:43 you simply overwrite the value that was
- 00:30:45 stored for that key before
- 00:30:48 now keys and that's also an important
- 00:30:50 difference to
- 00:30:51 objects can be anything so you can
- 00:30:54 also use reference values like arrays
- 00:30:56 for keys and that is a difference
- 00:30:59 now also another difference is that maps
- 00:31:02 are really meant to be pure data
- 00:31:04 storages
- 00:31:05 now behind the scenes the interesting
- 00:31:07 thing is that of course
- 00:31:08 maps are actually objects because
- 00:31:11 everything in javascript
- 00:31:12 in the end is an object but they're
- 00:31:14 implemented such that the map
- 00:31:16 object when you use that really is just
- 00:31:19 a data store
- 00:31:20 so you can't add extra functionality to
- 00:31:23 it like you can with an object
- 00:31:25 you could store a function as a value
- 00:31:27 but that function would not really be
- 00:31:30 able to interact with the other
- 00:31:32 map key value pairs and that's a
- 00:31:33 difference to objects
- 00:31:35 maps really are meant to be data stores
- 00:31:38 objects are not really focused to be
- 00:31:40 data stores
- 00:31:41 objects are just constructs that also
- 00:31:44 happen to work well as data stores
- 00:31:47 maps are just data stores just that
- 00:31:50 nothing else so let's now take a look at
- 00:31:53 maps
- 00:31:53 in code again back in an empty app.js
- 00:31:57 file we can create our map
- 00:32:00 let's say our result
- 00:32:03 data map by calling new map
- 00:32:08 now on our result data map we can now
- 00:32:10 call set
- 00:32:11 to add a new key value pair like for
- 00:32:14 example
- 00:32:15 average 1.53
- 00:32:20 and we can also add another key value
- 00:32:23 pair
- 00:32:24 for example last result
- 00:32:32 undefined or null so you can really have
- 00:32:35 different kinds of values in there
- 00:32:38 now you can also use non-string
- 00:32:41 number or symbol keys though that is one
- 00:32:43 important difference
- 00:32:44 you could for example have let's say an
- 00:32:47 object a country
- 00:32:48 which has a name of germany and then
- 00:32:51 let's say a population
- 00:32:53 of 82 million people and if you want it
- 00:32:58 you could use that as a key you could
- 00:33:00 set country as a key
- 00:33:02 and then store a value for it
- 00:33:05 for example 0.89 if that would be some
- 00:33:09 result which we want to store for a
- 00:33:11 specific country and i'll actually name
- 00:33:13 this
- 00:33:13 germany to be a bit more realistic so
- 00:33:16 now germany here is a valid key
- 00:33:18 even though it's an object this would
- 00:33:20 not be allowed in objects
- 00:33:21 in objects your keys may not be
- 00:33:24 other objects in maps this is allowed
- 00:33:29 now we can also use for off and
- 00:33:32 loop through result data like this and
- 00:33:35 then simply console.log
- 00:33:37 our elements so let's see what that
- 00:33:39 gives us
- 00:33:40 if we save it we see what we get back
- 00:33:44 are actually a bunch of arrays
- 00:33:46 every key value pair that's saved in the
- 00:33:48 map is
- 00:33:49 output as an array where you always have
- 00:33:51 exactly two elements
- 00:33:53 per array and the first element is
- 00:33:55 always your key name
- 00:33:56 and the second element is always your
- 00:33:58 value so that is what's being output
- 00:34:00 here
- 00:34:02 now as i mentioned if we set the same
- 00:34:05 key multiple times
- 00:34:07 like if we set average again
- 00:34:10 then it will simply be overwritten so
- 00:34:12 now you won't have two
- 00:34:14 key value pairs with the same key
- 00:34:16 instead you just have one
- 00:34:17 key value pair where the previous value
- 00:34:19 was now overwritten
- 00:34:21 and we can cancel log result data here
- 00:34:23 to have a look at it real quick
- 00:34:27 here we go now we see this average key
- 00:34:30 has this last value which we assigned
- 00:34:33 and the
- 00:34:34 earlier value was simply overwritten
- 00:34:38 now with our map we can do more we can
- 00:34:41 for example get access to all the values
- 00:34:43 or adjust the keys if we wanted to
- 00:34:45 and that gives us new iterables through
- 00:34:47 which we could loop in case we don't
- 00:34:49 want these
- 00:34:49 key value arrays but we are just
- 00:34:51 interested in just the keys or just the
- 00:34:53 values
- 00:34:54 we can use get to retrieve a value by
- 00:34:56 key
- 00:34:58 like this because the dot notation
- 00:35:02 and the square bracket notation you have
- 00:35:03 on objects is actually
- 00:35:05 not supported if i try this here and i
- 00:35:08 try to get my average like that
- 00:35:10 you will see the first time when i use
- 00:35:13 the get method
- 00:35:14 i get the value for the second try here
- 00:35:18 where i use the dot notation i get
- 00:35:20 undefined
- 00:35:21 i get undefined and not an error because
- 00:35:24 we can use the dot notation
- 00:35:26 because result data is also an object as
- 00:35:29 i mentioned
- 00:35:30 everything in javascript is an object in
- 00:35:32 the end but it's not our map
- 00:35:34 object where the data is in instead it's
- 00:35:36 the map
- 00:35:38 object in the sense of a construct in
- 00:35:40 our code
- 00:35:41 the map data store only gives us access
- 00:35:44 to our data
- 00:35:45 with its built-in methods like the get
- 00:35:47 method
- 00:35:48 now besides the get method we of course
- 00:35:50 also for example have the delete method
- 00:35:52 which allows us to delete an element by
- 00:35:55 key for example
- 00:35:56 delete germany here by using its key
- 00:36:00 if i console.log result data thereafter
- 00:36:04 you will see that germany is missing
- 00:36:07 now we only have average and the last
- 00:36:09 result and no longer our object
- 00:36:12 key of course here it's important to
- 00:36:14 keep in mind
- 00:36:15 that if you are using objects as keys
- 00:36:18 you really have to use the exact same
- 00:36:21 object when you try to delete it
- 00:36:23 just replicating the object so if you
- 00:36:26 would just copy this here
- 00:36:28 and try that would not work if we tried
- 00:36:32 this code we see
- 00:36:33 germany is still in here it is that's
- 00:36:35 our germany object as a key
- 00:36:37 and the reason for that of course is
- 00:36:39 that objects are reference values
- 00:36:42 and here we are creating a brand new
- 00:36:44 object and even though it looks like the
- 00:36:46 other object to us humans
- 00:36:47 it's a different place in memory and
- 00:36:50 therefore this
- 00:36:51 is technically a different key even
- 00:36:53 though it looks the same
- 00:36:54 this is nothing map specific that is how
- 00:36:57 javascript works
- 00:36:58 with reference and primitive values and
- 00:37:00 if that's unclear
- 00:37:01 attached to this video you'll find an
- 00:37:03 article and a video on reference and
- 00:37:05 primitive values
- 00:37:06 so that we're all on the same page there
- 00:37:09 that's it
- 00:37:09 for maps though that is what you need to
- 00:37:11 know about maps
- 00:37:13 and what you need to know to progress
- 00:37:15 with the course
- 00:37:20 now previously we had a look at arrays
- 00:37:22 versus sets
- 00:37:23 now since we learned about objects and
- 00:37:25 maps we can clearly tell that
- 00:37:27 these two constructs are also related
- 00:37:31 we always manage key value pairs after
- 00:37:33 all
- 00:37:34 so what should you use objects or maps
- 00:37:37 well it's a little bit as with arrays
- 00:37:39 and sets
- 00:37:40 objects are the way more common data
- 00:37:43 structure in javascript
- 00:37:44 because objects are super versatile
- 00:37:48 and super easy to use you have to use
- 00:37:52 them
- 00:37:52 if you want to add extra functionality
- 00:37:54 like a method that's able to interact
- 00:37:56 with the other data stored in the object
- 00:37:59 maps on the other hand are really just
- 00:38:01 focused on data storage
- 00:38:02 they don't have this extra functionality
- 00:38:05 thing
- 00:38:06 but the advantage maps could have over
- 00:38:08 objects
- 00:38:09 is that they can simplify and actually
- 00:38:11 improve
- 00:38:12 data access compared to objects so when
- 00:38:15 we talk about retrieving and deleting
- 00:38:17 key value pairs
- 00:38:19 we have these convenient methods and
- 00:38:21 depending on the kind of data you're
- 00:38:23 storing
- 00:38:24 and on the amount of data you have in
- 00:38:26 your object
- 00:38:27 maps can also be quicker they can be
- 00:38:30 faster than objects
- 00:38:32 however just as with arrays and sets
- 00:38:35 this will really only matter if we talk
- 00:38:37 about huge
- 00:38:38 objects with tons of data in there
- 00:38:41 therefore most of the time you're going
- 00:38:44 to use
- 00:38:44 objects in javascript it's a good to be
- 00:38:47 aware of
- 00:38:48 maps though because you can actually use
- 00:38:50 them if you just need a key value store
- 00:38:52 if you don't want any extra
- 00:38:54 functionality in there
- 00:38:55 and in such a case maps might be worth a
- 00:38:58 closer look
- 00:39:03 now that we had a look at arrays sets
- 00:39:06 objects and maps we got all the
- 00:39:08 basics that we need for this course to
- 00:39:10 finally also dive into custom data
- 00:39:13 structures
- 00:39:14 however not before i at least also
- 00:39:16 briefly
- 00:39:17 touch on weak sets and weak maps we
- 00:39:19 learned about set and map
- 00:39:21 weak set and weep map are simply
- 00:39:24 variations of set and map
- 00:39:26 the difference to set and map is that in
- 00:39:29 the weak set and the week map
- 00:39:31 the values in the case of the weak set
- 00:39:33 and the keys
- 00:39:34 in the case of the weak map are only
- 00:39:37 weakly
- 00:39:38 referenced now that's an abstract term
- 00:39:41 it simply means that the javascript
- 00:39:43 garbage collection
- 00:39:45 which is part of the javascript engine
- 00:39:47 part of the browser for example
- 00:39:49 is able to actually delete values or
- 00:39:52 keys and their values
- 00:39:54 if those values or keys are not
- 00:39:57 referenced
- 00:39:57 anywhere else in your app so if you for
- 00:40:00 example have
- 00:40:01 a set and you got a bunch of ids in
- 00:40:03 there and javascript finds out
- 00:40:05 that nowhere else in your code you're
- 00:40:08 using that value anymore
- 00:40:10 in such a case it frees up that space in
- 00:40:12 memory
- 00:40:13 and therefore weak sets and weak maps
- 00:40:15 can give you
- 00:40:16 an extra memory advantage because unused
- 00:40:20 space
- 00:40:21 can be cleared up in a traditional set
- 00:40:23 or map
- 00:40:24 and also in traditional arrays and
- 00:40:26 objects such space is not cleared up
- 00:40:29 the values are kept around forever as
- 00:40:32 long as your array and object
- 00:40:34 exists basically no matter if you still
- 00:40:36 use a value in an array
- 00:40:37 or not now again in a lot of scenarios
- 00:40:41 this won't matter
- 00:40:42 but if you have a really performance
- 00:40:44 intensive
- 00:40:45 application that uses a lot of memory if
- 00:40:48 you're building your own framework and
- 00:40:50 you need every piece of optimization
- 00:40:52 then weak set and weak map could help
- 00:40:55 you with memory management
- 00:40:57 now we won't need them in the course
- 00:40:58 here and arguably
- 00:41:00 you won't need them in a lot of
- 00:41:01 applications you're going to build
- 00:41:03 probably
- 00:41:04 but still it is worth knowing them and
- 00:41:06 since we talk about data structures here
- 00:41:08 i certainly can't move on without at
- 00:41:10 least mentioning them
- 00:41:12 with it however let's finally dive into
- 00:41:14 a custom data structure
- 00:41:20 so now we explored the built-in data
- 00:41:23 structures you have in javascript
- 00:41:25 this course however of course is not
- 00:41:27 focused on those built-in data
- 00:41:29 structures
- 00:41:30 you already know these and you'll learn
- 00:41:32 about them in every javascript course
- 00:41:34 like in my javascript the complete guide
- 00:41:37 course
- 00:41:37 instead this course is about custom data
- 00:41:40 structures
- 00:41:41 and that's why now we're going to dive
- 00:41:43 into the
- 00:41:44 linked list custom data structure our
- 00:41:47 first
- 00:41:48 very custom data structure which we're
- 00:41:50 going to build from scratch
- 00:41:52 first of all before we build it however
- 00:41:54 let's understand
- 00:41:55 what it is and how it works and we'll
- 00:41:57 then later also explore why we might
- 00:42:00 need or want this custom data structure
- 00:42:02 and what sets it apart from the built-in
- 00:42:04 ones
- 00:42:06 a linked list in the end as the name
- 00:42:08 implies is a list data structure
- 00:42:10 so a bit like an array we can store
- 00:42:13 values in there
- 00:42:14 values of any kind for example numbers
- 00:42:16 strings
- 00:42:17 objects whatever you want and in a
- 00:42:20 linked list
- 00:42:21 the interesting thing is that you don't
- 00:42:23 work with
- 00:42:24 indexes as in an array and you also
- 00:42:27 don't just have unique values like
- 00:42:30 in a set but instead every element
- 00:42:33 in the linked list does not just know
- 00:42:36 its
- 00:42:36 value but it also has a pointer at the
- 00:42:40 next
- 00:42:40 element in line and that continues
- 00:42:44 so a linked list and that's where the
- 00:42:47 name comes from
- 00:42:48 is a list full of elements that are
- 00:42:51 linked
- 00:42:51 to each other so every element knows
- 00:42:54 about the next element in line
- 00:42:56 and only about that element an element
- 00:42:58 does
- 00:42:59 not know about the element in front of
- 00:43:01 it so for example here
- 00:43:03 hi knows nothing about five high only
- 00:43:06 knows about
- 00:43:07 eight and that is how the entire list is
- 00:43:09 then structured so every element knows
- 00:43:11 about the next element
- 00:43:13 now why might we want or need such a
- 00:43:16 linked list
- 00:43:17 linked lists historically were invented
- 00:43:20 because they
- 00:43:21 were really flexible when it came to
- 00:43:23 resizing
- 00:43:24 the list and for memory management and
- 00:43:27 even today they bring
- 00:43:28 one important advantage and that is that
- 00:43:31 the insertion at the start and also
- 00:43:33 typically at the end of the list is very
- 00:43:36 efficient
- 00:43:37 more efficient so then in an array but
- 00:43:39 again i will come back to that
- 00:43:41 comparison
- 00:43:42 later so that is a linked list and
- 00:43:46 how it should work how could we now
- 00:43:48 implement
- 00:43:49 such a linked list how could the code
- 00:43:51 for such a linked list
- 00:43:52 look like thereafter once we have that
- 00:43:55 code we'll compare it to the array and
- 00:43:57 again
- 00:43:57 come back to the question why and when
- 00:44:00 you might want to use a linked list
- 00:44:07 so let's write our first custom data
- 00:44:09 structure
- 00:44:10 a linked list now a linked list is
- 00:44:13 a data structure of course this entire
- 00:44:15 course is about data structures
- 00:44:17 and therefore unlike in my algorithms
- 00:44:19 course
- 00:44:20 we're now not just going to write some
- 00:44:22 function that does
- 00:44:23 something because we're not just going
- 00:44:25 to write the solution for a problem
- 00:44:27 instead we want to store data and that
- 00:44:30 has one important
- 00:44:31 implication in this course the data
- 00:44:35 structures we're going to build
- 00:44:36 will build up on the core data
- 00:44:39 structures that are built into
- 00:44:41 javascript
- 00:44:42 obviously because if that would not be
- 00:44:44 the case
- 00:44:45 well we would have to build up on the
- 00:44:47 language with which
- 00:44:49 javascript is implemented and ultimately
- 00:44:52 we could go
- 00:44:52 all the way down to machine code right
- 00:44:54 if we want to reinvent the wheel
- 00:44:57 so that's not what we're going to do not
- 00:44:59 that we could easily do it in javascript
- 00:45:01 but that's not what we want to do either
- 00:45:03 instead we'll take what javascript has
- 00:45:06 arrays objects and so on and will
- 00:45:09 enhance this
- 00:45:10 we'll enhance this to build a new data
- 00:45:13 structure on top
- 00:45:15 of those built-in ones to then with our
- 00:45:18 new data structure
- 00:45:19 use those built-in ones in a better way
- 00:45:22 to then enhance those built-in
- 00:45:25 structures such that our
- 00:45:26 custom data structure does a certain
- 00:45:29 thing in a better way
- 00:45:30 otherwise there would be no reason to
- 00:45:32 come up with a custom data structure if
- 00:45:34 it would do just the same thing
- 00:45:35 right so in the case of the linked list
- 00:45:37 we're also going to build up on some
- 00:45:39 built-in data structures
- 00:45:41 and then we're going to enhance those
- 00:45:44 with a certain functionality
- 00:45:46 now therefore we're not going to write a
- 00:45:48 function because a function is basically
- 00:45:50 there to execute
- 00:45:51 code right to to solve a problem to take
- 00:45:53 some inputs and produce a result
- 00:45:56 instead a data structure of course is in
- 00:45:58 the end in javascript
- 00:46:00 an object even arrays are objects in the
- 00:46:03 end right so
- 00:46:04 we're going to build our custom object
- 00:46:06 here therefore
- 00:46:07 and specifically i will build my own
- 00:46:10 class here
- 00:46:11 so that we have a blueprint for our
- 00:46:13 custom data structure
- 00:46:15 and we can simply instantiate our class
- 00:46:17 to then have a new instance of our
- 00:46:19 custom data structure
- 00:46:20 and i think that should make a lot of
- 00:46:22 sense because if you recall
- 00:46:24 the recaps about sets and maps there we
- 00:46:28 also created a new map or a new set
- 00:46:30 with the constructor function so those
- 00:46:33 built-in data structures also in the end
- 00:46:36 are just
- 00:46:36 constructor functions and therefore just
- 00:46:39 classes behind the scenes you could say
- 00:46:41 and by the way for objects and arrays
- 00:46:43 it's not that different
- 00:46:45 we have those shortcuts with the square
- 00:46:47 brackets and the curly braces
- 00:46:49 but ultimately we can create an array
- 00:46:51 with the
- 00:46:52 arrayconstructor function and we can
- 00:46:54 also create an object with help of the
- 00:46:56 built-in object constructor function so
- 00:46:58 that's all
- 00:46:59 how javascript works and that's what
- 00:47:01 we're going to utilize here as well
- 00:47:03 so i'm going to create a class and i'll
- 00:47:05 name it linked list
- 00:47:06 because we're going to build a blueprint
- 00:47:08 for a linked list object
- 00:47:10 so that we later can build as many
- 00:47:12 different linked lists as we want
- 00:47:15 based on this blueprint that's what
- 00:47:17 classes are there for
- 00:47:19 so what do we want to do inside of this
- 00:47:22 linked list
- 00:47:22 class well we should add a constructor
- 00:47:25 function
- 00:47:26 because the constructor function in a
- 00:47:28 class is the first code that executes
- 00:47:30 whenever you later call new linked list
- 00:47:34 so that is when we want to construct a
- 00:47:36 linked list
- 00:47:38 linked list one that is what we want to
- 00:47:40 be able to call later
- 00:47:41 and of course therefore when we do that
- 00:47:44 something should happen
- 00:47:45 and that something when new is used well
- 00:47:48 that goes into the constructor function
- 00:47:51 now to get an idea for what we want to
- 00:47:53 do in the constructor function
- 00:47:55 let's again have a look at how a linked
- 00:47:58 list should look like in the end
- 00:48:00 we have these elements in there and we
- 00:48:03 also typically call those elements in a
- 00:48:05 linked list
- 00:48:06 nodes so when you hear me say node i
- 00:48:09 mean
- 00:48:09 an element in a linked list so we have
- 00:48:12 these nodes
- 00:48:12 in this linked list example we have four
- 00:48:15 nodes
- 00:48:16 and to help us with efficiently
- 00:48:18 inserting
- 00:48:19 new nodes at least at the end and the
- 00:48:21 beginning of the list
- 00:48:22 we also typically keep track of the
- 00:48:25 first node which is called the head node
- 00:48:28 or just head
- 00:48:29 and the last node which is called tail
- 00:48:31 node or
- 00:48:32 tail so we have nodes in the linked list
- 00:48:35 and we got two specific nodes or
- 00:48:37 two specific markers which we want to
- 00:48:39 place and which we want to keep
- 00:48:41 updated and that's the head marker which
- 00:48:44 always points at the first
- 00:48:46 node in the linked list and the tail
- 00:48:48 marker
- 00:48:49 which always points at the last node in
- 00:48:51 the linked list
- 00:48:52 and we'll need head and tail to make
- 00:48:55 sure
- 00:48:55 that we can efficiently prepend and
- 00:48:57 append
- 00:48:58 elements to that linked list
- 00:49:02 so nodes head and tail these are a
- 00:49:04 couple of
- 00:49:05 important terms now in the constructor
- 00:49:08 initially we have no nodes because
- 00:49:10 initially when we
- 00:49:12 just created the linked list it's an
- 00:49:13 empty linked list
- 00:49:15 so therefore you could imagine that here
- 00:49:18 you want to for example add a nodes
- 00:49:20 property to our class and set this to an
- 00:49:23 empty array
- 00:49:24 right that is something that could come
- 00:49:26 to your mind you want to add
- 00:49:27 this empty array and in this array you
- 00:49:29 later want to manage the nodes
- 00:49:32 we could do this but if we do this we're
- 00:49:34 back to basically
- 00:49:36 just rebuilding an array we would just
- 00:49:39 wrap the built-in array with our own
- 00:49:41 object
- 00:49:42 and chances are that we don't really
- 00:49:45 have a
- 00:49:45 much better data structure thereafter
- 00:49:48 maybe
- 00:49:49 we can improve it in some parts but
- 00:49:51 ultimately
- 00:49:52 i don't just want to rebuild an array
- 00:49:54 here
- 00:49:55 instead the idea will be that we don't
- 00:49:58 store
- 00:49:59 the entire list anywhere we just
- 00:50:02 store our different nodes and every node
- 00:50:05 knows about the next node
- 00:50:06 but every node itself does not
- 00:50:08 necessarily know something about the
- 00:50:10 list it's part of and the list
- 00:50:12 also doesn't know all its nodes instead
- 00:50:15 the list
- 00:50:16 should know the first and the last node
- 00:50:19 of its list elements
- 00:50:21 and the nodes themselves then know about
- 00:50:23 the next one in line
- 00:50:25 so there is no place where the entire
- 00:50:27 list is
- 00:50:28 stored it's just implicitly stored
- 00:50:31 because a list
- 00:50:32 knows it's starting an ending value and
- 00:50:34 every value then knows the next value in
- 00:50:36 line
- 00:50:37 that's the idea of a linked list and
- 00:50:39 therefore we won't have a nodes
- 00:50:41 property here instead we'll have our
- 00:50:43 head property
- 00:50:45 which i add with this head and initially
- 00:50:48 that's null because initially we have no
- 00:50:50 head property
- 00:50:51 and i'll add the tail property which
- 00:50:53 alls is null initially
- 00:50:55 and that will be the first element of
- 00:50:57 the list
- 00:50:58 and that here will be the last element
- 00:51:00 of the list
- 00:51:01 initially both is null because initially
- 00:51:04 we have no elements
- 00:51:05 of course you by the way could tweak the
- 00:51:07 constructor to accept a starting and
- 00:51:09 ending value if you wanted to
- 00:51:11 but here i'll start simple and not allow
- 00:51:14 this functionality
- 00:51:16 so this is now my linked list
- 00:51:18 constructor not too exciting
- 00:51:20 right now it's an empty list now let's
- 00:51:22 make sure we can add
- 00:51:24 something to the list so therefore we
- 00:51:26 probably want to add an append method
- 00:51:28 and this is how we can add a method in a
- 00:51:30 class
- 00:51:31 append should take a value and that
- 00:51:34 value can actually be of any kind we
- 00:51:36 don't care
- 00:51:37 can be a string can be a number it can
- 00:51:38 be an object can be an array
- 00:51:40 everything is allowed it should be some
- 00:51:42 value and that value should be added to
- 00:51:44 our
- 00:51:45 linked list therefore here
- 00:51:48 i then want to create my new node
- 00:51:51 you can of course name this constant
- 00:51:52 however you want and that should always
- 00:51:55 be an object
- 00:51:56 now why is new node an object and not
- 00:51:58 just a value
- 00:52:00 because you have to keep in mind that
- 00:52:02 every node knows about the next node in
- 00:52:05 line
- 00:52:06 every element knows about the next
- 00:52:07 element so it's not enough to just
- 00:52:09 store the value we also need to store a
- 00:52:12 pointer
- 00:52:13 at the next element in line otherwise
- 00:52:15 it's no linked list otherwise it's a
- 00:52:17 standalone value that doesn't know
- 00:52:19 anything
- 00:52:20 and since our list also doesn't know all
- 00:52:22 values all values would be lost in the
- 00:52:24 end
- 00:52:24 so therefore it's not enough to just
- 00:52:26 store the value we want an
- 00:52:28 object instead and this can be a very
- 00:52:31 trivial object though
- 00:52:33 it would have a value property which
- 00:52:35 holds the value we're getting
- 00:52:37 so this is the name of the property this
- 00:52:39 is the name of this
- 00:52:40 parameter we're getting which value
- 00:52:43 we're then storing
- 00:52:44 as a value for the value property okay
- 00:52:46 that's a lot of values
- 00:52:47 but i think value is a name that makes
- 00:52:49 sense here so we have
- 00:52:51 value stored as a property with the
- 00:52:53 input value we received here
- 00:52:55 and then that's important we'll also add
- 00:52:58 another property which is called
- 00:53:00 next and this should point at the next
- 00:53:03 element in line
- 00:53:05 now of course initially right now we
- 00:53:08 have no next element
- 00:53:10 right so this can simply be null because
- 00:53:12 if we just
- 00:53:13 append a new element append means that
- 00:53:16 it's added at the end of the list
- 00:53:19 and naturally such an element never
- 00:53:22 has a pointer at some next element
- 00:53:24 because it's the last one in the list
- 00:53:26 there is no next element
- 00:53:28 so therefore this is our new node which
- 00:53:30 we want to create
- 00:53:32 and this node should then be
- 00:53:35 added to our list now what does that
- 00:53:37 mean however
- 00:53:38 we're not managing the list as an array
- 00:53:41 so we don't do
- 00:53:42 this list push or anything like that
- 00:53:45 that's not what we do because we have no
- 00:53:47 list in its entirety
- 00:53:49 instead appending means that we now need
- 00:53:52 to go
- 00:53:53 to the previously last element
- 00:53:56 so to our tail and we need to update
- 00:54:00 the next value on the tail and make sure
- 00:54:03 that the next value
- 00:54:05 of our previous tail node now points at
- 00:54:09 this new node
- 00:54:10 that is what we need to do so for this
- 00:54:14 we should reach out to this tail and
- 00:54:16 then to the next
- 00:54:17 property of the tail and set this
- 00:54:21 equal to new node so basically
- 00:54:24 our new node is now stored in the next
- 00:54:27 property
- 00:54:28 of the previously last node
- 00:54:32 and once we updated the next property of
- 00:54:35 our old tail
- 00:54:37 we can override the tail property of
- 00:54:39 this constructor
- 00:54:40 with our new node now this does not mean
- 00:54:43 that we replace
- 00:54:44 the old tail object in memory the old
- 00:54:48 element that was our tail previously
- 00:54:50 still exists in memory
- 00:54:52 it's just that in this linked list
- 00:54:54 object we store a new value
- 00:54:57 for the tail property this does not
- 00:54:59 delete the old object which was detailed
- 00:55:01 previously
- 00:55:02 it's just not tied to the tail property
- 00:55:04 anymore that's why this order
- 00:55:06 here matters because here we still reach
- 00:55:08 out to the old
- 00:55:09 tale and update the old tales next
- 00:55:11 property
- 00:55:12 and thereafter we replace the old tale
- 00:55:15 in the linked list
- 00:55:17 with our new node now the element which
- 00:55:20 was our tail previously still exists
- 00:55:22 and the next property of that previous
- 00:55:25 tail element
- 00:55:26 also still points at the new node so
- 00:55:28 that is not overwritten by this line
- 00:55:31 now of course this implementation has
- 00:55:33 one flaw initially tail is null
- 00:55:35 so reaching out to the next property
- 00:55:38 will fail
- 00:55:39 so we should actually check if we have a
- 00:55:42 tail
- 00:55:42 before we try to do so before we try to
- 00:55:46 edit our old tale if we don't have a
- 00:55:50 tail
- 00:55:50 so basically if our list is empty then
- 00:55:53 of course we don't want to update detail
- 00:55:56 because then there is nothing to update
- 00:55:58 so if we don't have a tail yet it's
- 00:56:00 enough to just
- 00:56:01 set the tail to the new node we always
- 00:56:03 want to do that
- 00:56:04 but we only want to update the old tail
- 00:56:06 if we have one
- 00:56:08 we also of course want to set our head
- 00:56:11 equal to the new node if we don't have a
- 00:56:14 head yet
- 00:56:14 which would be the case if the list is
- 00:56:16 still empty so
- 00:56:17 i also want to add another if check and
- 00:56:19 check if we have a head
- 00:56:21 property and if we don't have it hence
- 00:56:24 the exclamation mark
- 00:56:25 if head is falsy so if it's null for
- 00:56:28 example
- 00:56:28 then i want to set this head equal to
- 00:56:30 the new node as well
- 00:56:32 typically when we append a value the
- 00:56:35 head should not be updated because the
- 00:56:37 head is the first value of the list
- 00:56:39 and appending means that we add it at
- 00:56:41 the end but if the list is empty if it
- 00:56:43 has no element yet
- 00:56:44 if both head and tail is null then of
- 00:56:47 course the head should also be updated
- 00:56:48 because then we just added the only new
- 00:56:51 element
- 00:56:52 to this list so now the list has exactly
- 00:56:54 one element
- 00:56:55 and of course that element then if it's
- 00:56:57 the only element is both head and tail
- 00:56:59 so this is kind of a special case so
- 00:57:02 this is now an append function that
- 00:57:04 should
- 00:57:04 do the trick now in order to see
- 00:57:08 whether our linked list and its append
- 00:57:10 function works
- 00:57:11 we also certainly want some method in
- 00:57:13 our linked list that outputs
- 00:57:15 all the nodes so that we can print it to
- 00:57:18 the console for example
- 00:57:19 that's something we're going to
- 00:57:21 implement next
- 00:57:26 to output our list we could add a two
- 00:57:29 array method the two array method would
- 00:57:32 convert our list
- 00:57:34 to an array of course with that we lose
- 00:57:36 the advantages but that's just a method
- 00:57:38 we can call
- 00:57:39 if we for example want to have a look at
- 00:57:41 all the elements we got
- 00:57:42 or if we simply need to convert it
- 00:57:44 because we now need an array to continue
- 00:57:47 that still allows us to use the linked
- 00:57:49 list advantages when we need them
- 00:57:50 but we can easily pull out all the
- 00:57:52 elements and convert them to an array
- 00:57:54 with that method if we need that so two
- 00:57:57 arrays should basically go through all
- 00:57:59 nodes
- 00:58:00 and then add all nodes to an array and
- 00:58:02 ultimately return that array
- 00:58:04 so here i'll have my
- 00:58:08 elements array which is empty initially
- 00:58:12 and i'm going to populate with a loop
- 00:58:14 now where we go through
- 00:58:16 all the nodes now how would you go
- 00:58:18 through all the nodes here
- 00:58:19 if you have no property that stores all
- 00:58:21 nodes
- 00:58:23 well you get the head and the tail right
- 00:58:25 so we can't just
- 00:58:26 start at the head and the head will be a
- 00:58:28 node that has a next
- 00:58:30 property which points at the next node
- 00:58:32 so all we need to do
- 00:58:33 is we need to start at the head and then
- 00:58:36 look at the node which is in its
- 00:58:38 next property and then basically do the
- 00:58:41 same for
- 00:58:41 that node which is in that next property
- 00:58:43 and look at that node's
- 00:58:45 next property and so on so we drill into
- 00:58:48 all those nodes that are connected to
- 00:58:51 each other
- 00:58:52 and doing that is rather simple we can
- 00:58:54 start with our
- 00:58:56 current node here which is this tail
- 00:58:58 because we want to start at the first
- 00:58:59 element
- 00:59:00 and then we can utilize a while loop to
- 00:59:02 go through all
- 00:59:04 the nodes because as long as we have a
- 00:59:07 current node
- 00:59:08 so as long as this is truthy which of
- 00:59:10 course would not be the case if it's
- 00:59:12 null so if it's an empty list we would
- 00:59:14 automatically stop
- 00:59:15 but as long as it's true fee so as long
- 00:59:17 as we have some object here
- 00:59:19 we'll continue looping so we access the
- 00:59:21 tail if this is an object we make it
- 00:59:23 into
- 00:59:24 the while loop and in here i will now
- 00:59:26 reach out to my elements and push
- 00:59:29 kernode to this array so that i add this
- 00:59:31 node element to the array
- 00:59:34 and thereafter we of course have to
- 00:59:35 replace kernode with a new node
- 00:59:37 and that is simply curnode.next so now
- 00:59:40 we have a look at the next property of
- 00:59:41 the current node
- 00:59:42 and that node which we find there is now
- 00:59:45 our new current node
- 00:59:46 if that should be null we'll simply stop
- 00:59:49 because then
- 00:59:50 this is falsy and we won't continue with
- 00:59:52 the loop if it's not
- 00:59:53 null because it's an object because it's
- 00:59:55 a node we'll continue
- 00:59:57 and therefore ultimately at the end we
- 00:59:59 can return elements here
- 01:00:01 and with that we should be able to look
- 01:00:03 into our linked list
- 01:00:05 and therefore now we can have a look and
- 01:00:07 see whether it works correctly
- 01:00:09 we can reach out to our linked list here
- 01:00:11 and call our pend a couple of times
- 01:00:13 append one and then also append
- 01:00:17 hello there and append
- 01:00:21 max my name and maybe append true
- 01:00:25 to also have a different value and then
- 01:00:27 also a number like
- 01:00:29 this and once we did all of that
- 01:00:32 i'm going to console log linked
- 01:00:36 list 1 to array and this should now
- 01:00:39 console log an array which
- 01:00:41 should contain all those values and if
- 01:00:43 we get this array this proves that our
- 01:00:45 linked list works
- 01:00:46 otherwise we would not be able to get
- 01:00:48 all those values because we get those
- 01:00:50 elements
- 01:00:51 these values which we want to output by
- 01:00:53 going through our linked list nodes
- 01:00:56 so let's save that and head over to the
- 01:00:59 browser
- 01:01:01 and i get an array but actually it only
- 01:01:03 has one element
- 01:01:05 and that element is simply the last
- 01:01:07 element i
- 01:01:08 added so clearly something is wrong
- 01:01:11 about this linked list
- 01:01:13 well it's a simple error i always talked
- 01:01:16 about the fact that i want to start at
- 01:01:17 the beginning of the list
- 01:01:19 and yet i used this tail of course this
- 01:01:22 should be this head
- 01:01:23 head is the start of the list not tail
- 01:01:26 so
- 01:01:26 this head and if you do that indeed
- 01:01:30 you should get your array with all the
- 01:01:32 nodes and you see
- 01:01:33 for every node there is the value but
- 01:01:36 then also next which holds the next node
- 01:01:38 in line
- 01:01:39 so for the first element for example
- 01:01:41 next points at the object with hello
- 01:01:43 there
- 01:01:43 and indeed that is the next object here
- 01:01:46 and that continues all the way to the
- 01:01:48 last node which then has a null value
- 01:01:50 for next because there is no next
- 01:01:52 element to point at
- 01:01:54 so our linked list works thus far we are
- 01:01:57 able to append elements
- 01:01:58 we are now also able to output those
- 01:02:00 elements with two array
- 01:02:02 now of course we don't have all the
- 01:02:05 functionalities we typically want
- 01:02:07 we also want to be able to prepend an
- 01:02:09 element we want to be able to delete an
- 01:02:11 element
- 01:02:12 we want to be able to find a specific
- 01:02:14 element as well probably
- 01:02:17 and therefore we should absolutely add
- 01:02:19 more functionalities
- 01:02:24 now let's continue with prepending
- 01:02:26 elements and absolutely try this on your
- 01:02:29 own first
- 01:02:30 here's a quick pause which you have now
- 01:02:31 to pause the video and give this a try
- 01:02:33 on your
- 01:02:34 own thereafter we'll implement this
- 01:02:36 prepend functionality together
- 01:02:41 were you successful let's add prepend
- 01:02:46 upend add something at the end prepend
- 01:02:49 also takes a value but it should add
- 01:02:50 this value at the beginning of the list
- 01:02:53 so how could prepend look like therefore
- 01:02:56 well again we want to create a new node
- 01:02:58 and that new node will be exactly the
- 01:03:00 same node
- 01:03:01 as up there so we can copy that code
- 01:03:04 and create our new node like this this
- 01:03:06 node is always the same
- 01:03:08 our nodes always have the same structure
- 01:03:10 of course
- 01:03:12 now the insertion logic differs we want
- 01:03:15 to add it at the beginning
- 01:03:16 of the list now not at the end so
- 01:03:20 therefore what you of course know is
- 01:03:22 that we'll overwrite the head
- 01:03:24 which as we learned is the first element
- 01:03:26 of the list now even i learned it
- 01:03:28 we want to override the head with our
- 01:03:30 new node we don't need to
- 01:03:32 save or do anything with the existing
- 01:03:34 head first
- 01:03:35 because of course we might already have
- 01:03:37 a first element because overriding it
- 01:03:39 like this
- 01:03:39 again will not remove the existing head
- 01:03:42 object from memory it just means that
- 01:03:44 it's no longer stored specifically in a
- 01:03:46 property of the linked list
- 01:03:48 but the object that wasde had previously
- 01:03:50 still exists in memory
- 01:03:52 however of course we need to do one
- 01:03:54 thing to not lose it eventually
- 01:03:56 because right now indeed the old head
- 01:03:59 would not be used
- 01:04:00 anywhere in our code and therefore
- 01:04:02 ultimately javascript garbage collection
- 01:04:04 would pick it up
- 01:04:05 and get rid of it and to avoid it the
- 01:04:08 structure of our new node should be the
- 01:04:09 same
- 01:04:10 but the next value will not be the same
- 01:04:12 as in the case when we append it
- 01:04:14 when we append a new node it's always
- 01:04:17 the last element of the list
- 01:04:18 therefore next always is null if we
- 01:04:21 prepend
- 01:04:22 an element then next should not be null
- 01:04:25 instead next of course will be well
- 01:04:28 the element that previously was our
- 01:04:30 first element
- 01:04:31 so this head so before we override head
- 01:04:35 with the new node
- 01:04:35 we want to take the old value that was
- 01:04:38 stored in head
- 01:04:39 the previously first node of the linked
- 01:04:41 list and stored that
- 01:04:43 in our next property of the new node so
- 01:04:45 that the new node is aware
- 01:04:47 of the node that previously was the
- 01:04:49 first element of the list
- 01:04:50 since the new node will be the new first
- 01:04:53 element of the list it should of course
- 01:04:54 be aware of the element that previously
- 01:04:56 was the first element
- 01:04:57 because that will make the previously
- 01:04:59 first element the second element
- 01:05:01 effectively so with that we update this
- 01:05:05 and we store the old
- 01:05:06 first node the old head node and
- 01:05:09 with that we're almost done here there's
- 01:05:12 just one thing left to do
- 01:05:14 we also want to check if we maybe are
- 01:05:16 dealing with an empty list
- 01:05:18 so if we had no head and if we had no
- 01:05:20 tail
- 01:05:21 if that's the case if we don't have a
- 01:05:23 tail so if the list is empty
- 01:05:25 if this is the first element we add and
- 01:05:28 we simply decided to do this with
- 01:05:29 prepend instead of
- 01:05:30 append then i want to set the tail equal
- 01:05:34 to the new node as well
- 01:05:35 because then tail and head both is the
- 01:05:37 same node because it's the first node we
- 01:05:39 ever added to the list
- 01:05:41 and that is it with that prepend should
- 01:05:43 work and we can test this
- 01:05:46 here we are appending a bunch of values
- 01:05:48 now at the end here i will prepend a new
- 01:05:51 value
- 01:05:52 and i'll name it first value and this
- 01:05:54 should now indeed be the first value
- 01:05:56 because i prepend it
- 01:05:58 to array still should work no changes
- 01:06:00 should be required there
- 01:06:01 because the logic for going for the
- 01:06:03 entire list is still the same
- 01:06:05 and if we now reload therefore we see
- 01:06:08 first value here
- 01:06:09 and we see that the next value of the
- 01:06:11 first value indeed is the value
- 01:06:14 1 here and that is the next value so
- 01:06:17 that all
- 01:06:18 works one also still points at the
- 01:06:20 correct next value thereafter
- 01:06:22 so prepend seems to do its job
- 01:06:26 now let's explore how we can delete
- 01:06:30 elements
- 01:06:33 adding elements is good but sometimes
- 01:06:35 you also want to get rid of elements so
- 01:06:37 therefore we want to add a delete method
- 01:06:40 which also should take a value that we
- 01:06:42 want to get rid of
- 01:06:43 now deleting is a bit more complex than
- 01:06:46 adding elements
- 01:06:47 because to delete an element we first of
- 01:06:49 all have to find it
- 01:06:51 and chances are that the value that
- 01:06:53 should be deleted
- 01:06:54 is not always just a tail or the head
- 01:06:57 in addition since we just get a value
- 01:07:00 here of course we want to find
- 01:07:01 all occurrences of that value and delete
- 01:07:04 it
- 01:07:04 so if i for example added max twice here
- 01:07:08 to my list and then i print it here
- 01:07:12 and thereafter i call linked list delete
- 01:07:15 max like this i expect that if i print
- 01:07:18 it again
- 01:07:19 both occurrences of macs were deleted
- 01:07:21 and not just one of them
- 01:07:23 so that's something we also have to
- 01:07:24 ensure that delete
- 01:07:26 really finds all occurrences no matter
- 01:07:29 where they are in the list
- 01:07:30 and no matter how often we have that
- 01:07:32 value in the list
- 01:07:34 so what do we want to do in the lead
- 01:07:35 therefore well first of all there is a
- 01:07:37 simple check
- 01:07:38 we should implement we should check if
- 01:07:40 we maybe don't have a head
- 01:07:42 so if you don't have a first element if
- 01:07:44 we don't even have a first
- 01:07:45 element we know that the list is empty
- 01:07:48 and in that case i can return
- 01:07:49 null here as a result you can also
- 01:07:52 return nothing if you want to
- 01:07:53 in the end you just want to return here
- 01:07:55 to make sure that no other code in this
- 01:07:57 method
- 01:07:58 executes because if the list is empty
- 01:08:00 deleting
- 01:08:01 does nothing alternatively if you wanted
- 01:08:04 you could also throw an
- 01:08:05 error and let the user of your list
- 01:08:07 handle it whatever you want
- 01:08:09 i will just return here now assuming
- 01:08:12 that we do have a head element
- 01:08:14 so assuming that the list is not empty
- 01:08:16 we should again
- 01:08:18 loop through the entire list just as we
- 01:08:20 do it with
- 01:08:21 two array and find all nodes that should
- 01:08:24 be deleted
- 01:08:25 so therefore again we can implement our
- 01:08:27 current node here and start at the head
- 01:08:29 element so start at the first element
- 01:08:32 and then add a while loop where we
- 01:08:35 essentially
- 01:08:36 well keep on looping as long as we have
- 01:08:38 a current node
- 01:08:39 now in this while loop we now
- 01:08:41 theoretically need to do two things
- 01:08:44 we need to check whether the current
- 01:08:45 node has the value we want to delete
- 01:08:47 but that's then not all we also want to
- 01:08:49 check if the next node in line maybe is
- 01:08:52 the one we want to delete we want to
- 01:08:53 again
- 01:08:54 go through all the nodes that need
- 01:08:56 deletion
- 01:08:57 now what does deleting mean in the
- 01:08:59 context of a linked list though
- 01:09:02 it actually simply means that we take
- 01:09:04 the
- 01:09:06 next value of a node
- 01:09:09 and instead of letting it point at the
- 01:09:11 next value it previously pointed at
- 01:09:14 we simply skip that value and point at
- 01:09:16 the well
- 01:09:17 value thereafter in line so if you
- 01:09:19 wanted to delete one for example
- 01:09:21 this node here if we wanted to delete
- 01:09:23 the node with value one
- 01:09:25 we should be able to find out that this
- 01:09:27 is not the first node of course because
- 01:09:29 it has a value of first value
- 01:09:31 but then it's the next node thereafter
- 01:09:34 we can determine this by looking at the
- 01:09:36 next property of the first node
- 01:09:38 now we see the value here for the next
- 01:09:40 node is the value we want to delete
- 01:09:42 let's say and therefore we now want to
- 01:09:45 update
- 01:09:45 next on the first note with the note
- 01:09:48 after the one we want to delete and this
- 01:09:50 effectively deletes the
- 01:09:52 node with value 1 because we remove the
- 01:09:55 pointer
- 01:09:55 at this node and therefore it's lost in
- 01:09:58 memory no one points at it anymore
- 01:10:00 we have no upper place that would point
- 01:10:02 at this node and therefore eventually it
- 01:10:04 will be garbage collected
- 01:10:06 that is what deleting nodes means in
- 01:10:09 linked lists
- 01:10:10 so therefore in our deletion
- 01:10:14 loop here i actually don't want to
- 01:10:17 look at the current node itself here i
- 01:10:20 want to look at the next
- 01:10:22 node in line here and compare that next
- 01:10:25 node's value
- 01:10:26 now by doing that we're not checking the
- 01:10:28 current node
- 01:10:29 value which is a flaw which we'll fix
- 01:10:32 but we'll simply start at the second
- 01:10:34 node for now and i'll take care about
- 01:10:35 the first node and so on later too
- 01:10:37 but with that we look at the next node
- 01:10:39 in line and check if that know its value
- 01:10:41 is the value we want to get rid of
- 01:10:43 for that we can simply add a if check in
- 01:10:45 the while loop and check
- 01:10:46 if current node.next
- 01:10:51 dot value so the value of the next node
- 01:10:53 in line
- 01:10:54 is equal to the value we got as an input
- 01:10:59 if that is the same we know we want to
- 01:11:01 delete that next node
- 01:11:03 and how do we delete it well as i just
- 01:11:05 said we update
- 01:11:07 current node next keep in mind that
- 01:11:10 current node is an object so if we
- 01:11:11 update
- 01:11:12 its next property we're doing this on
- 01:11:14 the node object
- 01:11:15 itself because it's a reference value so
- 01:11:17 we're not just doing this on some
- 01:11:19 variable which cloned the value
- 01:11:20 no it's one of the same object in memory
- 01:11:23 so we're then
- 01:11:24 updating the next property of the
- 01:11:26 current node
- 01:11:27 with the node that comes after the node
- 01:11:29 that should be deleted
- 01:11:30 and how can we get access to the node
- 01:11:32 after the next node
- 01:11:34 well by accessing the next node and then
- 01:11:37 the next property of that node
- 01:11:39 this gives us access to the node after
- 01:11:42 the node that should be deleted
- 01:11:43 and by storing that node after the node
- 01:11:46 that should be deleted
- 01:11:47 in the current node's next pointer we
- 01:11:49 effectively delete
- 01:11:50 the next node in line because no one is
- 01:11:53 pointing at it then
- 01:11:57 now we also of course have the else case
- 01:11:59 that the next
- 01:12:00 node in line is not a node we want to
- 01:12:03 delete
- 01:12:03 and in that case we just update current
- 01:12:05 node with currentnode.net
- 01:12:08 so that's now the same logic as we had
- 01:12:10 it down there when we went
- 01:12:11 through all the nodes in our list that
- 01:12:14 simply means we move on to the next node
- 01:12:16 and have a look at that node's
- 01:12:18 next value can take a while to wrap your
- 01:12:21 head around
- 01:12:22 this but hopefully i could make the core
- 01:12:24 logic here very clear
- 01:12:25 you can always of course throw in some
- 01:12:27 console log statements
- 01:12:29 if you want to get a detailed log of
- 01:12:32 what's happening at which point of time
- 01:12:35 with that we're always looking at the
- 01:12:36 next notes and we delete them by not
- 01:12:38 pointing at them anymore
- 01:12:40 but we skip the very first note of our
- 01:12:44 linked list because we initialize
- 01:12:46 current node with this head
- 01:12:48 but then we start by looking at the next
- 01:12:50 node's value
- 01:12:51 we never evaluate the value of current
- 01:12:53 node
- 01:12:55 well simply because if it's the first
- 01:12:57 value which we want to delete
- 01:12:59 we have a special case i want to create
- 01:13:04 a new while loop here
- 01:13:05 where i simply keep on going as long as
- 01:13:08 my head
- 01:13:09 value is truthy but not just that but as
- 01:13:12 long as the head is truthy so as long as
- 01:13:14 we have a head value
- 01:13:16 and this had value
- 01:13:19 so the value stored in the headnode is
- 01:13:21 equal to the value i want to delete
- 01:13:23 as long as that's the case so as long as
- 01:13:26 the first node is the one we want to
- 01:13:28 delete
- 01:13:29 i will update my head with this head
- 01:13:32 next so this means that if the first
- 01:13:35 value is the one we want to delete
- 01:13:37 we go into this loop and we replace the
- 01:13:41 first
- 01:13:41 node with the previously second node now
- 01:13:44 i'm writing this as a while loop
- 01:13:46 and not just as a if statement because
- 01:13:49 theoretically of course
- 01:13:50 that new first node could again have the
- 01:13:52 same value as the old first node and
- 01:13:54 therefore that new
- 01:13:55 first node also needs to be deleted
- 01:13:58 that's why i want to
- 01:13:59 keep on going as long as the first note
- 01:14:03 has the value that should be deleted as
- 01:14:05 soon as we hit
- 01:14:06 a first note that does not have the
- 01:14:09 value we want it to get rid of
- 01:14:11 we'll make it out of this while loop so
- 01:14:14 this simply is some extra code that
- 01:14:15 ensures
- 01:14:16 that we get rid of all head nodes that
- 01:14:20 might have the value we want to delete
- 01:14:22 now after this while loop we will also
- 01:14:25 need to add some special code
- 01:14:26 because whilst this while loop will
- 01:14:28 delete all nodes that need to be deleted
- 01:14:30 we want to update our tail property
- 01:14:34 this property here if we happened to
- 01:14:36 delete
- 01:14:37 the last node so if the last node was a
- 01:14:40 node that needed to be deleted
- 01:14:42 with the while loop here we want to
- 01:14:44 update the tail property
- 01:14:45 so that head and tail always point at
- 01:14:48 valid
- 01:14:49 existing nodes so therefore here i'll
- 01:14:52 check if
- 01:14:54 this tail dot value is equal to the
- 01:14:56 value that needs to be deleted
- 01:14:58 and in this case i'll set this tail
- 01:15:00 equal to the last current node we
- 01:15:02 derived which will be the last node that
- 01:15:04 was not deleted
- 01:15:07 and with that we have our delete
- 01:15:09 function
- 01:15:10 now let's give it a try i'm already
- 01:15:12 deleting max here
- 01:15:14 so both maxes should be deleted i then
- 01:15:17 also want to delete
- 01:15:20 first value which is our first value
- 01:15:23 because we prepend it here
- 01:15:25 so that we can check whether that really
- 01:15:27 works and
- 01:15:28 i will also delete 18.51 to see if that
- 01:15:33 last node deletion works correctly
- 01:15:37 i will also prepend first value twice so
- 01:15:40 i duplicated this line here
- 01:15:41 to see whether this head loop here
- 01:15:44 really does its job and gets rid of
- 01:15:46 all head nodes that need to be deleted
- 01:15:49 with that let's save it and let's go
- 01:15:51 back
- 01:15:53 initially i print this array here
- 01:15:57 this is coming from line 75 that is
- 01:15:59 printing my linked list with
- 01:16:01 all those elements in it and that looks
- 01:16:03 good
- 01:16:04 and thereafter we just have three
- 01:16:06 elements in there
- 01:16:07 one hello there and true
- 01:16:11 now let's see if that makes sense
- 01:16:14 we delete max so these two elements
- 01:16:17 should indeed be deleted
- 01:16:19 we delete first value so these two
- 01:16:21 elements indeed should be deleted
- 01:16:22 and we delete 18.51 so this element also
- 01:16:26 should be deleted
- 01:16:27 so the remaining elements indeed should
- 01:16:29 be one
- 01:16:30 true and hello there in between so one
- 01:16:33 hello there
- 01:16:34 and true that should be our remaining
- 01:16:36 elements
- 01:16:37 and that indeed is what we have here now
- 01:16:40 let's see if the next pointers were
- 01:16:42 updated correctly
- 01:16:43 next on the first element indeed points
- 01:16:45 at hello there
- 01:16:46 next at hello there it indeed points at
- 01:16:49 true and next
- 01:16:50 there indeed points at null so the
- 01:16:52 leading
- 01:16:53 seems to work and with that we got the
- 01:16:56 functionality to append something
- 01:16:58 to prepend something and also to delete
- 01:17:00 something
- 01:17:05 now we can add more functionalities to
- 01:17:07 our linked list
- 01:17:08 one functionality which i think would
- 01:17:11 make sense as well
- 01:17:12 is that we can also find a specific
- 01:17:14 value and with
- 01:17:16 find here i mean that i want to find the
- 01:17:18 first occurrence of that value
- 01:17:21 we can of course have the same value in
- 01:17:23 the list multiple times as you see here
- 01:17:25 at the example of max or first value but
- 01:17:27 i just want to find the first occurrence
- 01:17:30 let's say
- 01:17:30 of course you could also add other
- 01:17:32 functionalities where you find all
- 01:17:34 occurrences
- 01:17:34 or account how often an element exists
- 01:17:37 in the list
- 01:17:38 but here i just want to find the first
- 01:17:40 occurrence and therefore here
- 01:17:42 maybe between prepend and delete but the
- 01:17:45 position doesn't matter
- 01:17:46 i'll add a find method which receives
- 01:17:49 the value that should be found
- 01:17:52 now first of all just as with delete
- 01:17:54 i'll check if we don't have a head
- 01:17:56 so if the list is empty in which case
- 01:17:58 i'll return nothing because we can't
- 01:18:00 find anything if the list is empty
- 01:18:02 and thereafter again we can start with
- 01:18:04 current node equal to this hat
- 01:18:07 to then go through all our elements so
- 01:18:10 here i'll again go through all
- 01:18:12 current nodes so same logic as in two
- 01:18:14 array
- 01:18:15 i'll go through all the nodes i have
- 01:18:18 here
- 01:18:19 and i want to check if currentnode.value
- 01:18:24 is equal to the value
- 01:18:28 i got here as an argument
- 01:18:31 if that is the case i know that i found
- 01:18:34 the node
- 01:18:34 i wanted to find and then i'll return
- 01:18:37 this current node
- 01:18:40 thereafter we can simply set current
- 01:18:42 node equal to current node
- 01:18:43 next that is our looping logic we got in
- 01:18:46 the two array method as well
- 01:18:49 so with that we check the value of every
- 01:18:52 node and the first time we find a node
- 01:18:54 with the value we're looking for we
- 01:18:56 return that node and by calling return
- 01:18:59 here of course we'll then not continue
- 01:19:01 with the loop
- 01:19:01 will not continue with this function
- 01:19:03 that is what i mean with
- 01:19:04 finding the first occurrence we finish
- 01:19:07 after we have at least
- 01:19:08 one hit if we make it through the loop
- 01:19:11 without finding anything i'll return
- 01:19:13 nothing or maybe we simply return null
- 01:19:16 in
- 01:19:16 both cases so here at the end and in
- 01:19:19 this initial if check
- 01:19:20 so that we make it clear that we didn't
- 01:19:22 find anything
- 01:19:24 let's give it a try here after doing
- 01:19:27 all those things here let's now call
- 01:19:30 find for max which we
- 01:19:34 shouldn't find but then also for
- 01:19:37 hello there which we never deleted so
- 01:19:40 which we should find
- 01:19:41 so let's save that reload and we see
- 01:19:45 null here
- 01:19:46 from line 99 so we didn't find max
- 01:19:49 as we expected but we see a value for
- 01:19:52 hello there
- 01:19:53 which is the correct node so that also
- 01:19:55 works
- 01:19:56 and with that we also implemented a find
- 01:19:59 method
- 01:20:00 now to conclude this linked list let's
- 01:20:03 build up on the
- 01:20:04 find method and let's maybe add a
- 01:20:07 insert after method insert
- 01:20:11 after the idea here is that we
- 01:20:14 can insert a value but we specify after
- 01:20:17 which
- 01:20:18 value it should be inserted so that we
- 01:20:20 also get a second parameter here
- 01:20:22 the after value now the idea is simple
- 01:20:26 we find the after value
- 01:20:28 so we find the node with this value and
- 01:20:30 if we do find a node so if this doesn't
- 01:20:32 return null
- 01:20:33 then we want to create a new node after
- 01:20:36 that old node
- 01:20:37 after that well value we found
- 01:20:41 for that let's first of all check
- 01:20:44 whether we do find
- 01:20:45 a node for after value so here i will
- 01:20:48 then
- 01:20:48 find my existing node by calling this
- 01:20:52 find this refers to the class so this
- 01:20:56 find for after value and this should
- 01:20:58 return null if it doesn't find it or
- 01:21:00 return the first node it found if it did
- 01:21:03 find it
- 01:21:04 and important we therefore insert the
- 01:21:06 value after the first node we find
- 01:21:08 not after every node we find for that
- 01:21:10 value that's not the functionality we
- 01:21:12 have here so we find
- 01:21:14 our node here we want to check if
- 01:21:17 existing node is
- 01:21:18 truthy if it's not there's nothing we
- 01:21:21 need to do because we can't insert it
- 01:21:23 if we don't find the after value but if
- 01:21:26 we do find that value if we do get a
- 01:21:28 node for that
- 01:21:29 then of course we need a new node so we
- 01:21:31 can copy that code
- 01:21:33 and now of course the next value of the
- 01:21:35 new node should not be our
- 01:21:36 head but instead the next value here
- 01:21:40 should be since we added after the
- 01:21:43 existing node
- 01:21:44 well it should be the next value of the
- 01:21:46 existing node because we
- 01:21:48 insert the new value between the
- 01:21:50 existing node and
- 01:21:51 the old next value after the existing
- 01:21:54 node
- 01:21:55 so here we use existing node dot next
- 01:21:58 that is the next value of the new node
- 01:22:01 and
- 01:22:01 we then update existing nodes next value
- 01:22:05 with the new node so that we basically
- 01:22:08 put new node between
- 01:22:09 existing node and the old existing
- 01:22:12 next node
- 01:22:16 and this should be all let's see whether
- 01:22:17 that works
- 01:22:19 for that here
- 01:22:23 i'm going to add a new call to linked
- 01:22:26 list one
- 01:22:27 insert after and let's say after
- 01:22:34 one so after the first element i want to
- 01:22:35 insert something and after hello there i
- 01:22:37 wanna insert something
- 01:22:38 so i wanna insert after one let's say
- 01:22:43 new value one and then i wanna insert
- 01:22:47 after hello there
- 01:22:50 new value 2 and thereafter i'll again
- 01:22:54 simply print this entire array
- 01:22:58 let's give it a try and reload here is
- 01:23:00 our array and in there we see
- 01:23:02 1 is still the first value but
- 01:23:04 thereafter i inserted new
- 01:23:06 value 1 and the next value is hello
- 01:23:09 there
- 01:23:10 so that is the next element the next
- 01:23:12 node in line
- 01:23:13 and after hello there i also inserted a
- 01:23:16 new value 2.
- 01:23:17 and that's exactly what i wanted new
- 01:23:19 value 1 after 1
- 01:23:22 that's what we got here and new value 2
- 01:23:26 after hello there that is what we got
- 01:23:28 here
- 01:23:29 so with that we also have the insert
- 01:23:31 after method
- 01:23:32 now you could add more and more methods
- 01:23:34 for accounting elements or whatever you
- 01:23:36 want to do
- 01:23:37 but i would say we have a decent linked
- 01:23:40 list here
- 01:23:41 now with that linked list created let's
- 01:23:44 take a step back
- 01:23:45 and let's again check what the advantage
- 01:23:49 of this might be
- 01:23:50 and how it actually compares to the
- 01:23:53 array
- 01:23:53 which ships with javascript where is the
- 01:23:56 linked list
- 01:24:00 better so
- 01:24:02 why would you want to use a linked list
- 01:24:05 now the linked list is a pretty old data
- 01:24:08 structure
- 01:24:08 it's not a new invention it's been
- 01:24:10 around forever in programming
- 01:24:12 historically and in other programming
- 01:24:15 languages
- 01:24:16 the linked list could help with memory
- 01:24:18 management because in other programming
- 01:24:20 languages
- 01:24:21 you often need to specify the size of an
- 01:24:23 array in advance
- 01:24:25 and that could be a problem especially
- 01:24:27 if memory is a scarce
- 01:24:29 resource now of course still you
- 01:24:31 shouldn't create apps that
- 01:24:33 occupy tons of memory but memory of
- 01:24:36 course was a much bigger issue
- 01:24:38 a couple of years or decades ago then
- 01:24:41 linked lists could be helpful because
- 01:24:43 for linked lists you don't need to
- 01:24:45 specify the length in advance and that
- 01:24:47 was
- 01:24:48 one of the primary reasons why linked
- 01:24:50 lists were invented and used
- 01:24:52 in javascript we honestly don't have
- 01:24:54 that problem because the built-in array
- 01:24:56 is dynamic
- 01:24:57 and grows and shrinks with the number of
- 01:25:00 elements
- 01:25:00 so we don't use linked lists in
- 01:25:02 javascript because of memory reasons
- 01:25:04 typically
- 01:25:05 instead linked lists can be useful
- 01:25:08 if you do a lot of insertions at the
- 01:25:11 beginning
- 01:25:12 of lists specifically for arrays
- 01:25:15 we have the problem that if we add an
- 01:25:18 element at the beginning of an array we
- 01:25:20 have to shift
- 01:25:21 all our elements by one element we have
- 01:25:24 to move them
- 01:25:25 by one element and linked lists
- 01:25:28 are faster than arrays at this because
- 01:25:31 there we don't keep track of the
- 01:25:33 position of elements
- 01:25:35 we don't have a long list of elements
- 01:25:37 where every element has an index that we
- 01:25:39 need to update
- 01:25:40 instead inserting an element simply
- 01:25:42 means that we
- 01:25:44 add it and store the next element in the
- 01:25:46 next property and that's
- 01:25:48 it the other nodes don't even recognize
- 01:25:51 that something changed at the beginning
- 01:25:53 of the list
- 01:25:54 and that's a scenario where linked lists
- 01:25:57 shine
- 01:25:58 now of course that means that if you
- 01:26:00 never add elements of the beginning of
- 01:26:01 an array
- 01:26:02 you very likely don't have a use case
- 01:26:05 where you want a linked list
- 01:26:06 and even if you do you would have to use
- 01:26:09 a very
- 01:26:10 big array where you add elements at the
- 01:26:13 beginning
- 01:26:14 with a high frequency to really consider
- 01:26:17 a linked list
- 01:26:18 but that's the thing about data
- 01:26:19 structures we use them for niche
- 01:26:21 optimizations and the insertion at the
- 01:26:24 beginning
- 01:26:25 would be the main advantage of the
- 01:26:27 linked list now of course
- 01:26:28 i can just tell you that and my
- 01:26:30 explanations hopefully also make sense
- 01:26:33 but how would you typically compare
- 01:26:36 or measure something like this how did
- 01:26:39 we do it in the algorithms course in
- 01:26:41 case you watched it
- 01:26:42 how do you in general compare algorithms
- 01:26:46 well with time complexity and the big o
- 01:26:48 notation
- 01:26:50 and here's a brief refresher even though
- 01:26:52 i will say you should know that
- 01:26:54 before diving deeper into the course so
- 01:26:57 if time complexity and big o doesn't
- 01:26:59 tell you
- 01:26:59 anything definitely make sure you go
- 01:27:02 through my algorithms course first
- 01:27:05 time complexity is simply how we measure
- 01:27:08 and compare algorithms typically
- 01:27:10 and we use something which is called the
- 01:27:12 big o notation
- 01:27:13 to express this time complexity in an
- 01:27:16 easy way
- 01:27:17 if we consider this simple algorithm
- 01:27:19 here a function that sums up all the
- 01:27:21 numbers up to a number
- 01:27:23 we will see that the higher the number
- 01:27:26 is we pass
- 01:27:26 in the longer this will take to complete
- 01:27:30 and that would for example describe a
- 01:27:33 linear time complexity here
- 01:27:35 this function has a linear time
- 01:27:37 complexity for a bigger number we take
- 01:27:40 longer
- 01:27:40 and the extra time we take grows in a
- 01:27:43 linear way
- 01:27:44 now we don't just have linear time
- 01:27:46 complexity in programming
- 01:27:48 besides that we also find constant time
- 01:27:51 so where
- 01:27:51 the time it takes never changes
- 01:27:53 quadratic time
- 01:27:55 where it changes at a faster rate and
- 01:27:57 all the cubic time
- 01:27:59 and upper time complexities what we
- 01:28:02 typically care about
- 01:28:03 is not the time in milliseconds because
- 01:28:05 that depends way too much
- 01:28:07 on the underlying device on other
- 01:28:11 processes that might be running in the
- 01:28:12 background and so on
- 01:28:14 instead we care about the trend about
- 01:28:16 the growth rate you could say
- 01:28:17 and that is what we express with the big
- 01:28:19 o notation
- 01:28:21 linear time would be expressed as o of n
- 01:28:24 constant time o of 1
- 01:28:26 quadratic time o of n squared cubic time
- 01:28:29 o of
- 01:28:29 n at the power of 3 and so on
- 01:28:32 now we cannot just use time complexity
- 01:28:35 and big o notation to describe
- 01:28:37 algorithms though and to compare them
- 01:28:39 but we can also use that
- 01:28:41 to compare data structures we can
- 01:28:43 compare
- 01:28:44 linked lists to arrays for example now
- 01:28:47 of course not the data structure as a
- 01:28:49 whole
- 01:28:49 because that's just something that's
- 01:28:51 being stored in memory
- 01:28:52 there we could compare the space
- 01:28:54 complexity but instead
- 01:28:56 we would look at the different
- 01:28:57 operations we want to perform
- 01:28:59 because those operations of course again
- 01:29:01 are functions
- 01:29:03 and therefore we can then find out what
- 01:29:05 the time complexities of the different
- 01:29:07 operations are
- 01:29:08 so for example the time complexity of
- 01:29:11 finding
- 01:29:12 and accessing an element and by doing so
- 01:29:15 we can find out which operation we are
- 01:29:18 most likely to perform
- 01:29:20 and that then allows us to find out
- 01:29:22 whether we want to use an array
- 01:29:24 or in this example a linked list
- 01:29:30 now with that what would be the time
- 01:29:32 complexity of
- 01:29:34 accessing an element well let's have a
- 01:29:37 look at our linked list
- 01:29:39 there we want to find an element
- 01:29:42 and for that we can use the find method
- 01:29:45 what the find method does
- 01:29:46 is it in the end goes through all the
- 01:29:49 nodes
- 01:29:50 up to the node up to the value we want
- 01:29:52 to find
- 01:29:53 so it simply loops through all node
- 01:29:56 elements
- 01:29:57 of course if the element we want to find
- 01:29:59 is the first one that loop will be done
- 01:30:01 rather quickly but if it's the last one
- 01:30:04 then we have to go through
- 01:30:05 all nodes and therefore if we wanna
- 01:30:09 access one specific node for a specific
- 01:30:11 value
- 01:30:12 we have a time complexity of o of n so
- 01:30:14 we have linear time because we simply
- 01:30:17 need to go through all the elements
- 01:30:19 that should be rather straightforward
- 01:30:21 and again if you're not sure how you
- 01:30:22 derive that
- 01:30:24 definitely take my algorithms course
- 01:30:25 first i do explain it in great detail
- 01:30:28 there
- 01:30:29 now how about arrays well if you want to
- 01:30:32 find
- 01:30:32 an element in an array you also would
- 01:30:35 have linear time because you will also
- 01:30:37 have to go through all the elements in
- 01:30:39 an array
- 01:30:40 but the good thing about arrays is we
- 01:30:42 have a quicker way of accessing an
- 01:30:44 element
- 01:30:45 if we know the index in advance we have
- 01:30:47 constant time there
- 01:30:49 so for finding elements indeed we would
- 01:30:51 have linear time
- 01:30:53 but if we know the index we can
- 01:30:54 definitely get to the value quicker with
- 01:30:57 arrays
- 01:30:57 because then we can just access the
- 01:30:59 element by index
- 01:31:01 and that takes constant time because it
- 01:31:03 does not have to go through
- 01:31:05 all other elements so here arrays are
- 01:31:08 faster
- 01:31:09 now what if we want to insert something
- 01:31:11 at the end of the list
- 01:31:13 with the linked list we built we have
- 01:31:16 constant time which is super fast and
- 01:31:19 the reason for that is that
- 01:31:21 inserting something at the end is done
- 01:31:23 with append
- 01:31:24 now since we keep track of our current
- 01:31:27 tail
- 01:31:27 which is the last element of the linked
- 01:31:29 list we can just access this tail
- 01:31:32 and add our new node like this so it's
- 01:31:35 just one operation
- 01:31:36 we don't need to go through the entire
- 01:31:38 list you will also find linked list
- 01:31:41 implementations
- 01:31:42 that don't keep track of the tail
- 01:31:44 because theoretically you only need the
- 01:31:46 head right you only need to start
- 01:31:48 and then since every note knows about
- 01:31:51 the next note
- 01:31:52 you could go through the entire list
- 01:31:54 with just that information
- 01:31:56 storing the tail besides the head is an
- 01:31:59 extra convenience
- 01:32:00 we built into this linked list so that
- 01:32:03 adding elements at the end
- 01:32:04 is faster if you don't store
- 01:32:08 the tail we would have o of n as a time
- 01:32:11 complexity here so it really comes down
- 01:32:13 to
- 01:32:14 how you implemented your linked list for
- 01:32:16 that now
- 01:32:17 for an array it's always o of one
- 01:32:20 because we can simply use the push
- 01:32:22 method to add a new element
- 01:32:24 and for that the array is implemented
- 01:32:27 internally
- 01:32:28 such that it doesn't have to go through
- 01:32:30 all the other elements
- 01:32:31 because of course arrays no indexes they
- 01:32:34 know
- 01:32:35 positions and they know their current
- 01:32:37 length so in an array
- 01:32:38 internally it's very easy to jump to the
- 01:32:41 end of the array and add a new element
- 01:32:43 and inserting something at the end also
- 01:32:46 doesn't affect the other elements
- 01:32:47 therefore it's o of 1 for arrays
- 01:32:51 now how about insertion at the beginning
- 01:32:54 if we add something at the beginning for
- 01:32:57 the linked list again
- 01:32:59 we have o of one so we have constant
- 01:33:01 time here
- 01:33:02 and the reason for that is our prepend
- 01:33:04 method we simply add a new node here as
- 01:33:07 our head
- 01:33:08 and that's just one operation no need to
- 01:33:10 loop
- 01:33:11 through all the other elements no need
- 01:33:13 to evaluate everything
- 01:33:16 therefore it's o of one and here we have
- 01:33:18 the big difference compared to arrays
- 01:33:20 here we have the linked list advantage
- 01:33:23 for arrays that's
- 01:33:24 o of n because when we insert an element
- 01:33:28 at the beginning of an array
- 01:33:30 all other elements have to be moved one
- 01:33:33 element to the right
- 01:33:34 so to say right the index of all our
- 01:33:37 elements has to be
- 01:33:38 incremented because if we add a new
- 01:33:40 element at the beginning
- 01:33:42 that new element has the index 0.
- 01:33:46 that means that the element that
- 01:33:47 previously was the first one
- 01:33:49 and which previously had index 0 now
- 01:33:52 needs to receive index 1.
- 01:33:54 that means that the element which
- 01:33:55 previously had index 1
- 01:33:57 now needs to get 2 and so on so they all
- 01:34:00 need to be moved
- 01:34:01 and that's why here the linked list is
- 01:34:04 faster
- 01:34:05 now what about insertion at the middle
- 01:34:08 well
- 01:34:08 there in the end it's search time
- 01:34:11 plus of one for the linked list
- 01:34:15 and i'll come back to what the search
- 01:34:16 time is in a second
- 01:34:18 for arrays it's o of n the reason why
- 01:34:21 it's o of
- 01:34:22 n for arrays is simply that for arrays
- 01:34:25 if we want to insert something
- 01:34:26 inside of a list we again have to move
- 01:34:28 all elements thereafter
- 01:34:30 so the same logic as with insertion at
- 01:34:32 the beginning
- 01:34:34 now for searching elements and that is
- 01:34:36 where the search time comes from
- 01:34:38 we have o of n in a linked list it's
- 01:34:40 basically our element
- 01:34:42 access time we had at the top if we want
- 01:34:44 to find a specific
- 01:34:46 element and that is what we need to do
- 01:34:48 to insert something in the middle
- 01:34:50 for insert after we are calling find
- 01:34:52 after all
- 01:34:53 if we need to find something we again
- 01:34:55 need to go through
- 01:34:56 all the nodes until we found the element
- 01:34:59 and therefore here the time complexity
- 01:35:00 is o of n
- 01:35:01 because we theoretically loop through
- 01:35:04 all elements
- 01:35:05 and only then we can insert the element
- 01:35:07 the insertion itself
- 01:35:09 is then o of one because there we don't
- 01:35:11 need to update the other elements but
- 01:35:14 finding the place where to insert it
- 01:35:16 that takes o of n
- 01:35:19 for an array the search time is also of
- 01:35:22 and because if we don't know the index
- 01:35:24 if we want to search for an element
- 01:35:26 and that's the difference to line one
- 01:35:28 element axis by the way
- 01:35:30 if we want to find an element and we
- 01:35:31 don't know the index
- 01:35:33 well then we also have to loop through
- 01:35:35 all the elements to get access to it
- 01:35:38 this is how we could compare this and
- 01:35:39 therefore we see the linked list
- 01:35:42 really only wins in one place and that's
- 01:35:45 the insertion at the beginning
- 01:35:47 which is of course a very nichey
- 01:35:49 scenario
- 01:35:50 but again i mentioned it before and i
- 01:35:53 really want to emphasize it
- 01:35:54 data structures are for niche use cases
- 01:35:57 or custom data structures are for niche
- 01:36:00 use cases i should say
- 01:36:02 you have amazing built-in data
- 01:36:04 structures in javascript
- 01:36:06 and in the vast majority of cases those
- 01:36:09 data structures
- 01:36:10 give you everything you need but if you
- 01:36:12 for example
- 01:36:13 have a scenario where you have a long
- 01:36:15 list and you
- 01:36:16 always add elements at the beginning of
- 01:36:18 the list and you do that quite a lot
- 01:36:21 then a linked list might be a good
- 01:36:23 alternative
- 01:36:24 now it's needless to say that this is
- 01:36:26 not a scenario you will have all the
- 01:36:28 time
- 01:36:28 but it definitely is a scenario you
- 01:36:30 could face in bigger applications
- 01:36:46 you
