WEBVTT 00:03.450 --> 00:06.650 In this episode we will implement a linked list. 00:06.780 --> 00:12.090 We'll start by writing the implementation of a simple linked list and then modify that implementation 00:12.090 --> 00:13.940 to implement w linked list. 00:15.090 --> 00:19.790 A link list is a data structures that represent a collection of elements. 00:20.060 --> 00:23.360 Every element is gonna hold a value. 00:23.360 --> 00:27.410 In this case a reference to the next element. 00:27.470 --> 00:30.920 So this will in the end form some sort of chain. 00:31.070 --> 00:36.830 The last element of this chain or list doesn't reference any other one which means that is the last 00:36.830 --> 00:37.520 one. 00:37.520 --> 00:44.240 So we need to define a list which points to the first element or no. 00:44.480 --> 00:47.050 And every note points to the next one. 00:47.060 --> 00:53.310 So let's write this into a code first thing way to go is to define a list. 00:54.370 --> 01:02.840 Which is a structure which will have a field call head and this head will point to note which is the 01:02.840 --> 01:05.310 type that we would need to define right now. 01:05.510 --> 01:06.870 So let's define a node. 01:07.100 --> 01:14.030 I would just so the node has a value let's just use integrals for the values and have a reference to 01:14.030 --> 01:15.040 the next one. 01:15.080 --> 01:20.180 So let's call the next which will point to a node okay. 01:20.760 --> 01:29.880 So the first model we need to define is on the list we'll call the first which will give me the first 01:30.000 --> 01:30.780 note. 01:31.080 --> 01:32.650 So this will return. 01:32.800 --> 01:39.980 Now it will be as simple as this return least of her right. 01:40.050 --> 01:46.350 Also my list will need to implement a method called push in order to push values. 01:46.370 --> 01:50.660 So every time I call Kush I add a new note to this list. 01:50.820 --> 01:56.580 So I wonder value which I said is going to be an integer and it is not going to return anything. 01:57.920 --> 02:00.760 We are gonna implement this later. 02:01.460 --> 02:04.850 So now we have all the methods I need on my list. 02:05.090 --> 02:11.780 I need to implement some methods on my note to the first method on my note will be next. 02:11.990 --> 02:15.350 So next will return me the next note. 02:15.380 --> 02:20.750 In this case when I call next on my first note it will return me the second one. 02:21.230 --> 02:24.530 So this will probably return now. 02:24.590 --> 02:27.290 The next which is very simple okay. 02:27.530 --> 02:29.730 So I have all the methods I need. 02:29.990 --> 02:38.420 I will probably need to implement push so let's start by creating a new list without any note. 02:38.490 --> 02:50.310 What I want to do is when I call push one least push 2 and least push 3 1 I will be doing will be something 02:50.310 --> 02:50.880 like this. 02:51.630 --> 02:58.140 I will be the first element when I call push again it will call after the first one and when I call 02:58.140 --> 03:01.250 it again I will call it after until later. 03:01.260 --> 03:10.510 So let's do that so the first thing is when I push I need to make sure that my list is not empty which 03:10.510 --> 03:13.690 means that hair is not new. 03:14.110 --> 03:18.770 If it's nil I will assign the first note to my head. 03:19.040 --> 03:24.450 So first I need to create my known let's create a note with value. 03:24.460 --> 03:26.120 The value that I just pass here. 03:27.320 --> 03:33.630 And if my lease is empty I will sign this note to the head which is the first element on the list. 03:33.890 --> 03:41.960 And also I will assign these to the tail and what is still still nothing but I will define it right 03:41.960 --> 03:42.820 here. 03:42.950 --> 03:48.170 So tail will point to the last element on the left or to the last note. 03:48.170 --> 03:52.920 So my list have two pointers or two reference to the first one to the last one. 03:52.920 --> 03:56.630 Everytime I push something I will appended to the last one. 03:56.780 --> 04:01.340 But if my list is empty I will also assigning to the head right. 04:01.760 --> 04:05.380 So the first element is going to be appointed by head and tail. 04:05.630 --> 04:05.970 Okay. 04:06.260 --> 04:08.900 So for now this should be working. 04:09.170 --> 04:11.270 Let's execute this. 04:11.270 --> 04:13.870 Everything is fine right now. 04:14.060 --> 04:17.240 If I want to call next on my note. 04:17.330 --> 04:19.780 So let's say you lose the first. 04:19.970 --> 04:22.940 I have my first note here. 04:22.970 --> 04:27.670 Let's bring the value let's see what happened here. 04:27.680 --> 04:28.430 This will work. 04:28.430 --> 04:29.110 It brings 1. 04:29.390 --> 04:33.430 If I change this to 2010 open print. 04:33.920 --> 04:42.950 Now if I do and is gonna be equal to and the next which will return me the next element and I print 04:42.950 --> 04:53.450 its value what happened is that I have a memory problem because next is not assigned yet and that should 04:53.450 --> 04:55.990 be made in the push method. 04:56.120 --> 05:03.470 So the fear is that if my list is not empty which means that I already have at least one known I will 05:03.470 --> 05:09.470 say this my current last known dot next is going to be equal to the note. 05:10.130 --> 05:13.810 So now this should work. 05:13.810 --> 05:14.790 What I just did. 05:15.070 --> 05:16.780 Let me show you on the picture. 05:16.780 --> 05:19.550 So let's assume my list is empty. 05:19.660 --> 05:27.640 When I assign the first note my head and my tail reference are gonna be pointing to this element. 05:27.650 --> 05:29.530 The first one A. 05:29.560 --> 05:36.310 Now when I assign a new one what I'm doing here is that I'm saying a my daily is point here which is 05:36.370 --> 05:39.030 a element when the first one I wonder. 05:39.340 --> 05:44.900 This part of the element which is the next points to the newly created element. 05:45.310 --> 05:48.940 And then I move her to point to this one. 05:49.090 --> 05:54.250 So if we go through the code here this is exactly what I'm doing. 05:54.340 --> 05:56.110 I'm creating a note for every case. 05:56.800 --> 06:03.750 If my list is empty I will create this I will assign this note to the head in every case. 06:03.760 --> 06:06.400 I will assign it to the tail as well after the. 06:07.030 --> 06:17.640 But if my list has already some element the tail the previous tail dot next is gonna be the note so 06:18.900 --> 06:21.310 this is pretty much what we need for a linguist. 06:21.360 --> 06:23.780 Now let's try to traverse this list. 06:23.850 --> 06:27.590 We know that the last element dot next is gonna be Neil. 06:27.630 --> 06:35.520 So let's do a four which we'll learn in previous section and let us start by saying an is gonna be the 06:35.520 --> 06:36.940 first note. 06:37.260 --> 06:38.420 This is my first note. 06:38.460 --> 06:44.660 Let's print the value and then let's assign to the new one. 06:44.660 --> 06:48.440 So And up next will be this. 06:48.460 --> 06:50.140 Now what happened in this is not Neil. 06:50.180 --> 06:53.140 I shouldn't continue the iteration I should start. 06:53.180 --> 06:59.520 So if n it's equal to Neil which means there's no next. 07:00.110 --> 07:01.990 I will just break the execution. 07:02.180 --> 07:02.660 That's it. 07:02.660 --> 07:06.970 I mean this should iterate until we find a Neil element. 07:07.020 --> 07:10.470 OK so we bring 1 2 3 right. 07:10.690 --> 07:13.860 So this pretty much is for the simple list. 07:13.900 --> 07:22.780 Now I want to explain you are doubly linked list in Dublin list knows points not only to the next one 07:22.990 --> 07:24.190 but to the previous one. 07:25.180 --> 07:26.290 So why is this useful. 07:26.290 --> 07:31.490 Because I can go back and forth depending on the operation that I want to do. 07:31.750 --> 07:37.060 So let's modify the current code with half in order to implement this. 07:37.090 --> 07:42.910 So the first thing we need is that as we want to traverse the list by words we need to define a method 07:42.940 --> 07:44.200 to get to the last element. 07:44.200 --> 07:50.010 Well let's define the last method which also will return a note. 07:50.020 --> 07:53.860 The implementation is as you might guess return the tail. 07:53.870 --> 07:54.880 Right. 07:55.120 --> 08:00.110 Also as we saw in our picture note has a reference to the previous element. 08:00.190 --> 08:09.050 So went into a new field called PRA which also gonna point where no and then a method which returns 08:09.050 --> 08:12.350 that is pretty obvious. 08:12.350 --> 08:18.320 Now how to traverse this is going to be like this last and then I'm going to copy this because pretty 08:18.320 --> 08:23.410 much the same but instead of going to next we should call previous. 08:23.420 --> 08:27.920 Now there's something missing here because they haven't implemented that yet. 08:27.950 --> 08:32.920 So if they run this one going forward one two three and then it stops in three. 08:32.920 --> 08:33.260 Why. 08:33.260 --> 08:38.120 Because the previous element which is here it's always empty. 08:38.360 --> 08:45.420 So that a for loop goes here and it's always needed because it's empty and it's done the execution how 08:45.420 --> 08:46.900 to do that. 08:47.220 --> 08:48.410 It's right here. 08:48.420 --> 08:55.470 So every time we assign a new element to our list we need to link it back to the note. 08:55.890 --> 09:01.460 So the new node previews is gonna be equal to the previous tale. 09:02.130 --> 09:02.560 Okay. 09:03.140 --> 09:06.320 So let's execute this and see what happened and how it works. 09:06.350 --> 09:09.870 I have one two three and then three two one. 09:09.980 --> 09:14.840 So let me go to the picture again to explain you what we just did here. 09:14.840 --> 09:24.280 Every time I push an item to the list w link that so I link the new element let's say I'm outlining 09:24.320 --> 09:33.960 B to the list as we did previously we assign B to the first element next reference but also that element 09:34.230 --> 09:38.730 which is a it's been assigned to the previous one. 09:39.390 --> 09:44.700 So again B is assigned to a and a is assigned to be. 09:45.210 --> 09:49.550 So let's just review the code one more time to understand why we just did. 09:49.560 --> 09:50.590 The list is empty. 09:50.610 --> 09:51.690 Well we just started. 09:52.650 --> 09:56.720 So these will be true had is empty. 09:57.030 --> 10:03.590 So we assign the node to head and we also assigned to the tail which is the first no is gonna be pointed 10:03.630 --> 10:07.140 by Helen pale because our lives just have one element. 10:07.500 --> 10:16.110 But on further iterations that tail dot next is going to be assigned to the newly created node and also 10:16.110 --> 10:25.440 that node that preview is gonna be assigned to the current last one item so that I can iterate over 10:25.440 --> 10:30.260 them now for traverse the list from the beginning. 10:30.420 --> 10:35.820 You call first and you do this for traversing the list backwards. 10:35.820 --> 10:39.700 Would you just call last instead of column next. 10:39.720 --> 10:40.130 No. 10:40.140 --> 10:41.110 You call previous. 10:41.110 --> 10:41.950 No no. 10:42.250 --> 10:50.010 This is maybe not very useful in a language let go because as we saw in the previous section we have 10:50.010 --> 10:59.220 slices which is pretty much the same and also go offers at least package which is pretty much what we 10:59.220 --> 11:04.410 did first with what we just did but with other names they call element instead of note. 11:04.820 --> 11:11.370 But they have next and previous they have a list and they have other methods which are like for finding 11:11.370 --> 11:15.660 elements and getting the size of the element removing elements and so on. 11:16.530 --> 11:21.870 So probably when we write production code we're not going to implement our own linked list but it's 11:21.870 --> 11:28.500 pretty good to do these kind of exercises to bring practice what we've been learning so as an exercise 11:28.500 --> 11:35.850 if you want to improve a little bit I will say try to implement and then you write it here and try to 11:35.850 --> 11:39.400 implement the fine method which you should be. 11:39.520 --> 11:45.000 I'm not gonna implement I'm just going to write a signature of the function that'll be fine and then 11:45.000 --> 11:48.590 value integer and this should return a note. 11:49.110 --> 11:56.580 So these functions should traverse the whole list and return the first note which matches that value 11:56.760 --> 12:00.280 like no good value should be equal to this value. 12:00.420 --> 12:07.110 So if you want to improve a little bit implement that and of course if you want to understand how this 12:07.110 --> 12:15.390 is implemented in the standard library you can also go here and let's say I want to see how my element 12:15.630 --> 12:17.160 is implemented. 12:17.160 --> 12:22.010 I can just come here and go to the code which is super well documented. 12:22.050 --> 12:26.770 This is going to be very useful if you want to improve your skills. 12:26.870 --> 12:28.460 So this is for this episode. 12:28.550 --> 12:31.580 I hope you enjoy it and see you on the next one. 12:31.850 --> 12:32.210 But.