1 00:00:01,050 --> 00:00:06,630 Not let's look at another list implementation which is a linked list or the linked list is based on 2 00:00:06,630 --> 00:00:08,210 a doubly linked list. 3 00:00:08,430 --> 00:00:13,650 If you're not aware of it it's a fundamental data structure and it also has a variant called as a single 4 00:00:13,650 --> 00:00:19,890 Englis which is normally referred to as a linked list but jostling list is based on bubblin and blessed 5 00:00:19,890 --> 00:00:20,150 . 6 00:00:20,170 --> 00:00:24,420 And so you're going to look at double English and also look at singly linked list. 7 00:00:24,540 --> 00:00:29,190 Now just note that linguists are pretty popular when it comes to of yours. 8 00:00:29,310 --> 00:00:35,220 And when I say English here I mean the linguists implementation itself like the single English ordered 9 00:00:35,480 --> 00:00:39,180 linguist but not the job or not you darling. 10 00:00:39,930 --> 00:00:41,880 So here is the thing with English. 11 00:00:41,880 --> 00:00:48,940 So as a nym linked list implies it has a list of elements the elements are linked. 12 00:00:49,410 --> 00:00:55,590 So here we have a few elements and elements are linked and each element is called as a note undernote 13 00:00:55,590 --> 00:00:56,990 has two components. 14 00:00:57,090 --> 00:00:59,240 One is the data which is the real data. 15 00:00:59,410 --> 00:01:02,830 On the other one is a pointer to the next note. 16 00:01:03,040 --> 00:01:10,110 OK so it links to the next not saying Djala we can have this kind of a class called Nord which has two 17 00:01:10,110 --> 00:01:10,620 variables. 18 00:01:10,620 --> 00:01:11,650 One is for the data. 19 00:01:11,670 --> 00:01:13,240 In this case it is just an integer. 20 00:01:13,240 --> 00:01:15,130 They don't but it can be anything. 21 00:01:15,240 --> 00:01:20,900 And the second one is a pointer to the next in order on hands that that type is normal. 22 00:01:21,180 --> 00:01:28,340 Now the last note here is not linking to any other nor And hence the next reference would be s.m. 23 00:01:28,380 --> 00:01:32,920 Now here the first note is called us had nor I need said Dummy. 24 00:01:33,180 --> 00:01:38,390 Which means that it doesn't have any data and all it does is connect to the first in order mechanically 25 00:01:38,440 --> 00:01:40,490 the function or ordered make on top of the last note. 26 00:01:40,530 --> 00:01:43,740 But that is dependent on the implementation. 27 00:01:43,740 --> 00:01:47,650 Now in addition to not we will also have this kind of a class call as a linguist. 28 00:01:47,730 --> 00:01:51,570 Yes so this is the main class and will be interacting with this class. 29 00:01:51,630 --> 00:01:57,640 So here you are first creating a hard note on that head Norwell point to all other notes. 30 00:01:57,930 --> 00:02:01,560 And we also have this augmented Henri will also how other methods. 31 00:02:01,560 --> 00:02:07,220 So the oddment that is taking an and data alecks see how it works. 32 00:02:07,230 --> 00:02:12,360 So the first step would be to create a brand new note on initialize it with the data. 33 00:02:12,770 --> 00:02:19,010 And the second step would be to point it to the previously I did not get to the most recently added 34 00:02:19,010 --> 00:02:19,730 note. 35 00:02:19,950 --> 00:02:26,940 So we are pointing head dot next to the next reference and newly created note. 36 00:02:27,120 --> 00:02:33,540 So at this point the old dog which was recently added It has two point one from head and the other from 37 00:02:33,540 --> 00:02:40,160 the newly created order on the next step is to assign the newly created not hug. 38 00:02:40,890 --> 00:02:48,690 So that's it singly linked list on here is there and blessed are not as the name goblin Lingula suggest 39 00:02:48,690 --> 00:02:49,210 . 40 00:02:49,440 --> 00:02:51,610 Each element has two links. 41 00:02:51,730 --> 00:02:53,580 OK it is linked to the next element. 42 00:02:53,760 --> 00:02:55,280 Like in the case of single Englis. 43 00:02:55,470 --> 00:02:58,280 But it is also linked with the previous achievement. 44 00:02:58,860 --> 00:03:03,970 So that's why you'll see dewpoint girs here and once again we have had not. 45 00:03:04,230 --> 00:03:07,480 And in this illustration we have three elements to 0 1 and 2. 46 00:03:08,250 --> 00:03:14,000 And the main thing to note here as there are a couple of properties one is if you add a new element 47 00:03:14,400 --> 00:03:17,040 it gets added right before the hack. 48 00:03:17,070 --> 00:03:22,600 In this case it is the element to iron the head is also linked with the zero element. 49 00:03:22,800 --> 00:03:24,530 OK which is the first element. 50 00:03:24,570 --> 00:03:29,530 So those are the two things that are happening here in English. 51 00:03:29,640 --> 00:03:38,440 Now one benefit of that is that what Migdal linked list also as it Deck on deck is a sub interface of 52 00:03:38,440 --> 00:03:38,780 Q. 53 00:03:38,790 --> 00:03:40,980 We discuss that earlier. 54 00:03:41,070 --> 00:03:48,040 Our deck basically has operations that frequently manipulate the first element and the last element 55 00:03:48,050 --> 00:03:48,510 . 56 00:03:48,890 --> 00:03:51,480 And here the head of it allow us to do that. 57 00:03:51,480 --> 00:03:53,090 So that's one of the benefits. 58 00:03:53,420 --> 00:04:00,780 And the second is if we want to look for an element or a particular index then we would have to traverse 59 00:04:00,780 --> 00:04:03,220 through only half of the list. 60 00:04:03,420 --> 00:04:09,270 So for that we will see if the next that is specified is close to the first element of or disclose to 61 00:04:09,270 --> 00:04:10,410 the last element. 62 00:04:10,410 --> 00:04:16,590 But if it is close to the first element we just traversed from head to the zero to node on the first 63 00:04:16,590 --> 00:04:19,550 north on so on otherwise which I was from. 64 00:04:19,930 --> 00:04:25,550 OK so how does allowing us to traverse in both directions in this case on based on the index. 65 00:04:25,650 --> 00:04:28,770 It makes a decision on which way it has to go. 66 00:04:28,770 --> 00:04:31,640 So that's another benefit of it. 67 00:04:31,800 --> 00:04:36,340 Now let's just see how this kind of a doubling can be built on for dark. 68 00:04:36,340 --> 00:04:38,590 We will use an add operation. 69 00:04:39,090 --> 00:04:45,930 So initially we will how only the head node on the head Norton next on previous point to itself because 70 00:04:45,930 --> 00:04:47,590 there are no other elements. 71 00:04:48,790 --> 00:04:50,380 So we are adding an element. 72 00:04:50,650 --> 00:04:51,370 Because of that. 73 00:04:51,400 --> 00:04:57,650 And you know it gets created just like in the case of a single English and the second step is to set 74 00:04:57,690 --> 00:05:04,270 its own going lengths which is nothing but the next and previous references since this note will be 75 00:05:04,270 --> 00:05:05,730 added right before hand. 76 00:05:05,840 --> 00:05:09,060 Its next should point to hide and that's what we are doing here in the US. 77 00:05:09,100 --> 00:05:17,800 It meant years previous has to point to the previously added element which is also linked from the previous 78 00:05:17,800 --> 00:05:22,170 set of friends in Hegg and that's the second statement here. 79 00:05:22,210 --> 00:05:26,890 So once the outgoing links are set we also have to send the incoming links. 80 00:05:27,100 --> 00:05:31,430 So one of the incoming links is from the previous. 81 00:05:31,510 --> 00:05:34,370 We need to connect to this new order. 82 00:05:34,870 --> 00:05:38,490 And the second thing is from the previously added note. 83 00:05:38,770 --> 00:05:42,480 When you do link its next node to this new unit. 84 00:05:42,910 --> 00:05:49,410 So here we can see that the new node is being assigned to the previous link and also the next reference 85 00:05:49,420 --> 00:05:49,980 . 86 00:05:50,050 --> 00:05:55,630 So no doubt next is nothing what head and yet assigning its previous reference with the new not a new 87 00:05:55,630 --> 00:05:58,300 no doc problem would be the previous day or not. 88 00:05:58,300 --> 00:06:05,310 But in this case it is it would be head our next next reference is being assigned with noon or so maybe 89 00:06:05,320 --> 00:06:08,460 a little bit confusing but if you add one more element I think it will be easier. 90 00:06:08,470 --> 00:06:09,570 So lets do that. 91 00:06:09,580 --> 00:06:11,930 So here is on your not on here are the outgoing links. 92 00:06:11,980 --> 00:06:17,760 Since its being added right before not its next Providence is wandering too hard on its previous reference 93 00:06:17,770 --> 00:06:20,140 is pointing to the previously created not. 94 00:06:20,380 --> 00:06:23,690 OK so now lets say the incoming links are in. 95 00:06:23,700 --> 00:06:24,400 Here it is. 96 00:06:24,430 --> 00:06:26,820 Are all all ordinance God disappeared. 97 00:06:27,070 --> 00:06:32,920 So the had not previous is pointing to this new Not I and the previously created nauts next is pointing 98 00:06:32,920 --> 00:06:34,630 to the new order. 99 00:06:35,080 --> 00:06:37,870 So this is the final structure that we have. 100 00:06:38,350 --> 00:06:40,640 So thats how the operation works. 101 00:06:40,720 --> 00:06:46,880 It also works in a constant time as we always have a reference to head on we just need to add the new 102 00:06:46,920 --> 00:06:49,060 Not before that. 103 00:06:50,060 --> 00:06:54,560 And here are some typical uses you would want be use a linked list. 104 00:06:54,640 --> 00:07:00,220 If you are true reading and doing that duration If you how frequent are ordering more operations then 105 00:07:00,220 --> 00:07:06,450 you will go forward it because when you do the Ardmore operation all you need as if you are just fingerlings 106 00:07:06,450 --> 00:07:07,190 . 107 00:07:07,210 --> 00:07:11,450 So there is no element sheriffs like in the case of the test. 108 00:07:11,530 --> 00:07:17,890 So if you how frequent are more during iteration you should go with a linked list on and consequently 109 00:07:17,950 --> 00:07:24,040 it is also better for remote all and retain all operations because both of these operations and remote 110 00:07:24,040 --> 00:07:26,520 elements during iteration. 111 00:07:26,620 --> 00:07:27,510 So you would go for this. 112 00:07:27,510 --> 00:07:32,800 So just remember that if I were you have to do frequent hour or more during iterations then you might 113 00:07:32,800 --> 00:07:36,870 want to pick a linked list or other implementations. 114 00:07:37,100 --> 00:07:41,040 And here are some of the matters which how linear time complexity. 115 00:07:41,110 --> 00:07:46,420 So these are get our remore index off our last mix off and the history. 116 00:07:46,420 --> 00:07:52,810 Get out and remove our position specific Mateschitz here so you can see the next eye. 117 00:07:53,330 --> 00:07:56,880 And that actually and by two oblations not even linear. 118 00:07:57,040 --> 00:08:03,760 And thats because as mentioned earlier they either try hours from the beginning or end depending on 119 00:08:03,940 --> 00:08:04,720 the index. 120 00:08:04,750 --> 00:08:09,400 If it is close to the first element then you are two hours from the first element. 121 00:08:09,400 --> 00:08:14,680 But if I was close to the last element which is the size of Dulles then you will traverse from the last 122 00:08:14,680 --> 00:08:21,560 element and said that headword allow us to do that on here is the corresponding code fragment Robsart 123 00:08:21,640 --> 00:08:24,530 on radar could try was from the beginning order. 124 00:08:24,840 --> 00:08:31,570 OK so to speak and from that Jawa source on this go to Sean here just to show you that a more efficient 125 00:08:31,570 --> 00:08:36,040 big shift operator is being used for performing division. 126 00:08:36,040 --> 00:08:42,700 Also note that for the get method idlest would work in constant time as it is based on ID which gives 127 00:08:42,700 --> 00:08:45,380 the benefit of fast random access. 128 00:08:45,970 --> 00:08:51,460 So for that matter our list is better than the length list. 129 00:08:51,460 --> 00:08:58,030 So finally the link list is basically a doubling list implementation off list on deck interfaces. 130 00:08:58,330 --> 00:09:06,490 So we will discuss DECT later but it mortal's before in freefall and the linked list actually supports 131 00:09:06,730 --> 00:09:11,260 all of the needed operations follie 454 and constant time. 132 00:09:11,260 --> 00:09:18,610 However when it comes to deck it is recommended to use a deck as it is optimized for faster manipulation 133 00:09:18,700 --> 00:09:21,730 of both first as well as last elements. 134 00:09:21,730 --> 00:09:24,030 We know that other deck implements deck. 135 00:09:24,160 --> 00:09:30,760 So I think we can restrict using linked list as a last on muddler use it when there would be frequent 136 00:09:30,820 --> 00:09:35,590 additions or deletions while iterating iron like an hour or less. 137 00:09:35,590 --> 00:09:39,440 It also allows duplicate iron not like us. 138 00:09:39,520 --> 00:09:41,320 So thats a bottling list. 139 00:09:41,350 --> 00:09:47,770 So as far as the demo goes we dont have to do any more because it is very similar Go Adela's all we 140 00:09:47,770 --> 00:09:54,380 need to do is change the implementation off other list from there or in their demo program to length 141 00:09:54,410 --> 00:09:55,060 list. 142 00:09:55,270 --> 00:10:00,150 But lets actually go ahead and see that and then we can sign off after that. 143 00:10:01,420 --> 00:10:01,660 OK. 144 00:10:01,660 --> 00:10:07,960 Here is the Arliss moment on since here we are programming to an interface we can take advantage of 145 00:10:07,990 --> 00:10:14,430 polymorphism which means that we can assign any object which implements this list interface. 146 00:10:14,550 --> 00:10:16,500 Ok so here we have idlest. 147 00:10:16,660 --> 00:10:22,510 So let's just go ahead and just change it to length list. 148 00:10:22,510 --> 00:10:23,970 I mean put that control shift. 149 00:10:23,980 --> 00:10:26,890 Oh and that's it. 150 00:10:26,890 --> 00:10:30,430 And we don't have to make any other change if we execute it. 151 00:10:30,720 --> 00:10:34,850 Everything executes as it was when we were using our list. 152 00:10:35,290 --> 00:10:36,340 So that's about it. 153 00:10:36,460 --> 00:10:37,110 Thank you. 154 00:10:37,180 --> 00:10:38,470 And happy coding.