Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,252 --> 00:00:02,835 (upbeat music) 2 2 00:00:05,400 --> 00:00:07,430 All right so in the last couple of videos 3 3 00:00:07,430 --> 00:00:09,000 we looked at singly linked lists. 4 4 00:00:09,000 --> 00:00:11,610 And now we're going to look at a double linked list, 5 5 00:00:11,610 --> 00:00:13,290 or a doubly linked list. 6 6 00:00:13,290 --> 00:00:15,482 With a doubly linked list we have nodes. 7 7 00:00:15,482 --> 00:00:18,530 We have a head, we have a tail, 8 8 00:00:18,530 --> 00:00:22,600 and each node in the list points to the next item 9 9 00:00:22,600 --> 00:00:26,330 in the list and to the previous item in the list. 10 10 00:00:26,330 --> 00:00:29,700 And so this time we have two reference fields, 11 11 00:00:29,700 --> 00:00:31,070 this would be the next field, 12 12 00:00:31,070 --> 00:00:32,620 and this would be the previous field. 13 13 00:00:32,620 --> 00:00:35,210 And as you can see, for the first item in the list 14 14 00:00:35,210 --> 00:00:37,350 the previous field will point to null 15 15 00:00:37,350 --> 00:00:38,990 and the last item in the list, 16 16 00:00:38,990 --> 00:00:40,600 the next field, will point to null. 17 17 00:00:40,600 --> 00:00:43,450 Just like it does with singly linked lists. 18 18 00:00:43,450 --> 00:00:46,000 And so as I said, this time we have references 19 19 00:00:46,000 --> 00:00:47,040 to the head and the tail. 20 20 00:00:47,040 --> 00:00:50,270 So in this list, Jane would be the head node 21 21 00:00:50,270 --> 00:00:52,280 and Mike would be the tail node. 22 22 00:00:52,280 --> 00:00:55,610 And so we can traverse the list from front to back. 23 23 00:00:55,610 --> 00:00:56,710 From front to tail. 24 24 00:00:56,710 --> 00:00:58,800 Or from tail to head. 25 25 00:00:58,800 --> 00:01:03,060 And this time if we want to insert or remove a node 26 26 00:01:03,060 --> 00:01:05,960 from the end of the list we can do it in constant time 27 27 00:01:05,960 --> 00:01:08,920 because we have a pointer, or a reference, 28 28 00:01:08,920 --> 00:01:10,770 to the tail of the list. 29 29 00:01:10,770 --> 00:01:13,510 And so the advantage of using a doubly linked list 30 30 00:01:13,510 --> 00:01:16,890 is you can work with the node at the front of the list 31 31 00:01:16,890 --> 00:01:19,847 or the node at the end of the list in constant time. 32 32 00:01:19,847 --> 00:01:22,910 But if you want to work with nodes in the middle of the list 33 33 00:01:22,910 --> 00:01:24,380 you're gonna have the same problem 34 34 00:01:24,380 --> 00:01:26,040 that a singly linked list had. 35 35 00:01:26,040 --> 00:01:27,560 You're gonna have to traverse 36 36 00:01:27,560 --> 00:01:28,927 from the head or from the tail, 37 37 00:01:28,927 --> 00:01:30,926 find the node you wanna work with, 38 38 00:01:30,926 --> 00:01:34,510 and in the worst case, that could be a linear operation. 39 39 00:01:34,510 --> 00:01:38,070 So let's look at inserting and deleting nodes 40 40 00:01:38,070 --> 00:01:39,520 into a doubly linked list. 41 41 00:01:39,520 --> 00:01:41,510 So we have a little more work to do now 42 42 00:01:41,510 --> 00:01:44,000 because we have two references that we have to manage, 43 43 00:01:44,000 --> 00:01:45,700 the next and the previous. 44 44 00:01:45,700 --> 00:01:48,526 And so if we wanted to insert Bill at the head 45 45 00:01:48,526 --> 00:01:51,201 we'd start out the same way that we did 46 46 00:01:51,201 --> 00:01:54,200 for inserting a node in a singly linked list. 47 47 00:01:54,200 --> 00:01:55,750 We're gonna create a new node 48 48 00:01:55,750 --> 00:01:58,150 for the new information. 49 49 00:01:58,150 --> 00:02:03,020 And now we need to set Bill's next and previous fields. 50 50 00:02:03,020 --> 00:02:05,430 So his next field is going to be whatever 51 51 00:02:05,430 --> 00:02:07,730 is currently being pointed to by head. 52 52 00:02:07,730 --> 00:02:11,290 So this is the same as when we did singly linked lists. 53 53 00:02:11,290 --> 00:02:14,390 And his previous field is going to point to 54 54 00:02:14,390 --> 00:02:16,720 whatever Jane's previous field is, 55 55 00:02:16,720 --> 00:02:19,484 because if, if we're inserting Bill in front of Jane, 56 56 00:02:19,484 --> 00:02:22,680 which is what we're doing, then Jane's previous field 57 57 00:02:22,680 --> 00:02:24,500 is now going to become Bill. 58 58 00:02:24,500 --> 00:02:26,790 And Bill's previous field will become whatever 59 59 00:02:26,790 --> 00:02:27,770 Jane was pointing to. 60 60 00:02:27,770 --> 00:02:29,530 Now if we're always inserting at the head, 61 61 00:02:29,530 --> 00:02:31,330 that would mean that Bill's previous field 62 62 00:02:31,330 --> 00:02:32,740 is going to point to null. 63 63 00:02:32,740 --> 00:02:35,550 And now we have to fix Jane's previous field 64 64 00:02:35,550 --> 00:02:38,900 because Bill is being inserted in front of her. 65 65 00:02:38,900 --> 00:02:41,980 And so we want her previous field to now point to Bill. 66 66 00:02:41,980 --> 00:02:45,270 And then we're going to assign the head field to Bill 67 67 00:02:45,270 --> 00:02:48,000 because Bill becomes the new node 68 68 00:02:48,000 --> 00:02:49,890 that's at the front of the list. 69 69 00:02:49,890 --> 00:02:52,550 And so essentially when we insert a node 70 70 00:02:52,550 --> 00:02:54,900 it's all about setting the references of the node 71 71 00:02:54,900 --> 00:02:58,168 we're inserting and also updating the previous field 72 72 00:02:58,168 --> 00:03:00,450 of the current head node. 73 73 00:03:00,450 --> 00:03:02,380 And so after we've done all of that 74 74 00:03:02,380 --> 00:03:03,920 this is what the list will look like. 75 75 00:03:03,920 --> 00:03:06,350 So we didn't have to change Jane's next field 76 76 00:03:06,350 --> 00:03:08,710 because when we're inserting in front of the list 77 77 00:03:08,710 --> 00:03:11,430 what comes after Jane isn't going to change. 78 78 00:03:11,430 --> 00:03:13,420 We had to update the previous field 79 79 00:03:13,420 --> 00:03:17,050 because the previous field would have been pointing to null 80 80 00:03:17,050 --> 00:03:19,470 but now it's going to point to the new node. 81 81 00:03:19,470 --> 00:03:21,890 Because this previous field used to point here. 82 82 00:03:21,890 --> 00:03:24,510 We're dropping a node in front of it. 83 83 00:03:24,510 --> 00:03:26,750 And so we need to update the previous field. 84 84 00:03:26,750 --> 00:03:29,150 And so we need to update Bill's previous field 85 85 00:03:29,150 --> 00:03:32,090 to point to whatever Jane's previous field was pointing to. 86 86 00:03:32,090 --> 00:03:35,290 And then on the final step we just set the head to Bill. 87 87 00:03:35,290 --> 00:03:37,560 We go through the same steps if we were to insert 88 88 00:03:37,560 --> 00:03:38,950 Bill somewhere else. 89 89 00:03:38,950 --> 00:03:41,900 In that case we'd have more references to update. 90 90 00:03:41,900 --> 00:03:43,970 But we'd go through a bunch of similar steps. 91 91 00:03:43,970 --> 00:03:47,160 We basically would have to set Bill's previous and next 92 92 00:03:47,160 --> 00:03:49,100 and then we'd have to update the next field 93 93 00:03:49,100 --> 00:03:51,270 on the node in front and the previous field 94 94 00:03:51,270 --> 00:03:54,350 of the node that comes after the one we inserted. 95 95 00:03:54,350 --> 00:03:56,550 But as I said, when you're working with linked lists 96 96 00:03:56,550 --> 00:03:59,810 you mainly wanna be focusing on working with 97 97 00:03:59,810 --> 00:04:01,500 items that are at the front of the list, 98 98 00:04:01,500 --> 00:04:03,420 or in the case of doubly linked lists 99 99 00:04:03,420 --> 00:04:04,810 at the tail of the list. 100 100 00:04:04,810 --> 00:04:07,060 If you start playing around with items in the middle 101 101 00:04:07,060 --> 00:04:09,560 you're gonna lose the advantage of a linked list, 102 102 00:04:09,560 --> 00:04:13,040 which is that inserting and deleting items from the front, 103 103 00:04:13,040 --> 00:04:15,400 and in the case of a doubly linked list from the end, 104 104 00:04:15,400 --> 00:04:17,030 you can do that in constant time. 105 105 00:04:17,030 --> 00:04:18,700 Once you start playing with other nodes 106 106 00:04:18,700 --> 00:04:21,160 you're getting up into potentially linear time. 107 107 00:04:21,160 --> 00:04:23,670 Okay, so that's inserting a node at the head. 108 108 00:04:23,670 --> 00:04:25,810 So let's go back to pour original list 109 109 00:04:25,810 --> 00:04:27,640 just to remind ourselves of what it looked like. 110 110 00:04:27,640 --> 00:04:30,270 So we're back to before we inserted Bill. 111 111 00:04:30,270 --> 00:04:33,340 Now we're going to insert at the tail. 112 112 00:04:33,340 --> 00:04:35,790 So once again, if we want to insert Bill at the tail 113 113 00:04:35,790 --> 00:04:37,800 we'll create a new node called Bill. 114 114 00:04:37,800 --> 00:04:40,380 And we want to assign the tail's next field 115 115 00:04:40,380 --> 00:04:41,550 to Bill's next field. 116 116 00:04:41,550 --> 00:04:43,400 Because if we go back to the previous slide, 117 117 00:04:43,400 --> 00:04:45,200 if we're gonna drop Bill in here, 118 118 00:04:45,200 --> 00:04:48,574 then whatever this guy is currently pointing to is next, 119 119 00:04:48,574 --> 00:04:49,407 we're gonna want Bill to point to as next. 120 120 00:04:51,088 --> 00:04:54,450 And so we're gonna assign the current tail's next field 121 121 00:04:54,450 --> 00:04:55,900 to Bill's next field. 122 122 00:04:55,900 --> 00:04:58,520 We're going to assign whatever, the current tail 123 123 00:04:58,520 --> 00:05:02,410 to Bill's previous field because Mike is currently the tail. 124 124 00:05:02,410 --> 00:05:04,460 And so if we put Bill in here we're gonna want 125 125 00:05:04,460 --> 00:05:06,410 Bill's previous field to point to Mike. 126 126 00:05:06,410 --> 00:05:09,040 So we want to point the previous field 127 127 00:05:09,040 --> 00:05:10,170 to the current tail. 128 128 00:05:10,170 --> 00:05:12,766 And then we're gonna assign, want to assign the tail's 129 129 00:05:12,766 --> 00:05:14,525 next field to Bill. 130 130 00:05:14,525 --> 00:05:16,204 And so Mike is the current tail. 131 131 00:05:16,204 --> 00:05:18,283 And after the insertion, his next field, 132 132 00:05:18,283 --> 00:05:20,020 we want him to point to Bill. 133 133 00:05:20,020 --> 00:05:23,620 And finally we're gonna assign the tail to Bill. 134 134 00:05:23,620 --> 00:05:25,800 And we can do that in constant time complexity. 135 135 00:05:25,800 --> 00:05:28,685 It doesn't matter how many items are in the list. 136 136 00:05:28,685 --> 00:05:30,870 You're gonna go through the same number of steps 137 137 00:05:30,870 --> 00:05:33,380 to insert a new item at the tail. 138 138 00:05:33,380 --> 00:05:36,380 And so after the insertion this is the situation we'll have. 139 139 00:05:36,380 --> 00:05:39,400 So Mike's next field has been updated to Bill. 140 140 00:05:39,400 --> 00:05:41,600 Bill's previous field has been set to Mike. 141 141 00:05:41,600 --> 00:05:43,580 And his next field has been set to null. 142 142 00:05:43,580 --> 00:05:45,930 Which is what Mike's next field used to be. 143 143 00:05:45,930 --> 00:05:48,350 And the tail has now been set to Bill. 144 144 00:05:48,350 --> 00:05:51,440 So let's say we want to delete from the head of the list. 145 145 00:05:51,440 --> 00:05:53,070 So we wanna delete Jane. 146 146 00:05:53,070 --> 00:05:55,690 Well let's look first at what we'd have to do. 147 147 00:05:55,690 --> 00:05:58,820 Well we're gonna assign Jane to a remove node. 148 148 00:05:58,820 --> 00:06:02,290 And then we wanna assign John's previous field 149 149 00:06:02,290 --> 00:06:04,690 to whatever Jane's previous field is pointing at 150 150 00:06:04,690 --> 00:06:05,760 because we're removing her. 151 151 00:06:05,760 --> 00:06:08,433 So we wanna take that reference and go here. 152 152 00:06:08,433 --> 00:06:12,170 And then we just need to move the head reference to John. 153 153 00:06:12,170 --> 00:06:15,039 And that effectively moves, removes Jane from the list. 154 154 00:06:15,039 --> 00:06:19,040 So we're gonna assign Jane to remove node. 155 155 00:06:19,040 --> 00:06:21,160 We're gonna assign John's previous field 156 156 00:06:21,160 --> 00:06:22,540 to Jane's previous field. 157 157 00:06:22,540 --> 00:06:26,330 We're gonna assign head to whatever is at Jane's next field. 158 158 00:06:26,330 --> 00:06:28,390 Because Jane's next field is pointing to John 159 159 00:06:28,390 --> 00:06:30,350 so we're gonna assign John to head. 160 160 00:06:30,350 --> 00:06:33,410 And then we're gonna return, remove node from the method. 161 161 00:06:33,410 --> 00:06:37,060 And if we wanted to we could clean up Jane's next field 162 162 00:06:37,060 --> 00:06:38,090 by setting it to null. 163 163 00:06:38,090 --> 00:06:39,383 We don't have to but we could. 164 164 00:06:39,383 --> 00:06:43,100 And once again, that'll be constant time complexity. 165 165 00:06:43,100 --> 00:06:45,629 And so once we've gone through that, Jane will be gone. 166 166 00:06:45,629 --> 00:06:48,320 And John will be the new head of the list. 167 167 00:06:48,320 --> 00:06:50,240 So let's put Jane back in. 168 168 00:06:50,240 --> 00:06:52,740 And let's look at removing the tail instead. 169 169 00:06:52,740 --> 00:06:54,570 So this time we're gonna remove Bill. 170 170 00:06:54,570 --> 00:06:56,360 And so how would we do that? 171 171 00:06:56,360 --> 00:06:58,540 Well we're gonna wanna take Mike's next field 172 172 00:06:58,540 --> 00:06:59,980 and point it to null. 173 173 00:06:59,980 --> 00:07:02,360 And we're gonna wanna move the tail to Mike's. 174 174 00:07:02,360 --> 00:07:03,780 So the tail will be moved 175 175 00:07:03,780 --> 00:07:06,920 to the current tail's previous node. 176 176 00:07:06,920 --> 00:07:09,390 And so we'll assign Bill to remove node. 177 177 00:07:09,390 --> 00:07:12,300 We'll assign Mike's next field to Bill's next field. 178 178 00:07:12,300 --> 00:07:16,530 We'll assign the tail to Bill's previous field, 179 179 00:07:16,530 --> 00:07:17,720 which is Mike. 180 180 00:07:17,720 --> 00:07:20,010 And then we'll return remove node from the method. 181 181 00:07:20,010 --> 00:07:22,600 And once again we can do this in constant time. 182 182 00:07:22,600 --> 00:07:25,750 It doesn't matter how many items are in the list. 183 183 00:07:25,750 --> 00:07:28,236 If we wanna delete an item from the tail 184 184 00:07:28,236 --> 00:07:30,783 we can do it using the same number of steps. 185 185 00:07:30,783 --> 00:07:33,600 And so after the deletion, we'll have this situation 186 186 00:07:33,600 --> 00:07:35,380 where Mike is now the tail. 187 187 00:07:35,380 --> 00:07:37,030 And Bill is gone. 188 188 00:07:37,030 --> 00:07:40,020 So in general to insert a node A 189 189 00:07:40,020 --> 00:07:43,880 between nodes B and C, we want to plop A 190 190 00:07:43,880 --> 00:07:45,117 between B and C. 191 191 00:07:45,117 --> 00:07:48,940 And we're gonna assign A's next field to B's next field 192 192 00:07:48,940 --> 00:07:51,360 because B's next field will be pointing to C. 193 193 00:07:51,360 --> 00:07:52,780 And we're gonna put A between them. 194 194 00:07:52,780 --> 00:07:55,190 So we want A's next field to point to C. 195 195 00:07:55,190 --> 00:07:59,230 We're gonna assign A's previous field to C's previous field 196 196 00:07:59,230 --> 00:08:01,870 because C's previous field will be B. 197 197 00:08:01,870 --> 00:08:04,350 And we want A, we're gonna drop A in between them, 198 198 00:08:04,350 --> 00:08:06,980 so we're gonna want A's previous field to be B. 199 199 00:08:06,980 --> 00:08:09,860 And then we assign B's next field to A. 200 200 00:08:09,860 --> 00:08:11,900 And C's previous field to A. 201 201 00:08:11,900 --> 00:08:15,720 Now to do those four steps is constant time but, 202 202 00:08:15,720 --> 00:08:16,800 unless we're doing this 203 203 00:08:16,800 --> 00:08:18,460 at the beginning or the end of the list 204 204 00:08:18,460 --> 00:08:21,190 we have to find nodes B and C first. 205 205 00:08:21,190 --> 00:08:23,160 And we're gonna have to traverse the list to do that. 206 206 00:08:23,160 --> 00:08:26,580 And so, the worst case for this is actually linear time. 207 207 00:08:26,580 --> 00:08:27,520 O to the n. 208 208 00:08:27,520 --> 00:08:30,540 Now to remove a node A from between B and C, 209 209 00:08:30,540 --> 00:08:34,840 so this time we have nodes B followed by A followed by C, 210 210 00:08:34,840 --> 00:08:36,910 we assign A to remove node. 211 211 00:08:36,910 --> 00:08:40,630 We want C's previous field to now point to B 212 212 00:08:40,630 --> 00:08:42,000 because we're removing A. 213 213 00:08:42,000 --> 00:08:45,660 So we'll assign C's previous field to A's previous field. 214 214 00:08:45,660 --> 00:08:48,040 Because A's previous field is pointing to B. 215 215 00:08:48,040 --> 00:08:50,770 We want B's next field to point to C. 216 216 00:08:50,770 --> 00:08:54,340 So we'll assign B's next field with whatever A's next field 217 217 00:08:54,340 --> 00:08:56,340 is pointing at because A's next field 218 218 00:08:56,340 --> 00:08:58,780 is currently pointing to C because it's in between them. 219 219 00:08:58,780 --> 00:09:01,310 And then we just return A from the method. 220 220 00:09:01,310 --> 00:09:03,910 Once again, these steps are constant time. 221 221 00:09:03,910 --> 00:09:07,160 But, we have to find A first in the list. 222 222 00:09:07,160 --> 00:09:10,630 So unless A is at the head or the tail, 223 223 00:09:10,630 --> 00:09:11,840 we're gonna have to find it. 224 224 00:09:11,840 --> 00:09:13,810 And so this, the worst case for this 225 225 00:09:13,810 --> 00:09:15,800 would actually be linear time. 226 226 00:09:15,800 --> 00:09:19,500 And that's it for looking at how doubly linked lists work. 227 227 00:09:19,500 --> 00:09:22,130 Once again we're gonna do a simple implementation 228 228 00:09:22,130 --> 00:09:23,870 of a doubly linked list. 229 229 00:09:23,870 --> 00:09:27,330 We're gonna update our singly linked list implementation 230 230 00:09:27,330 --> 00:09:29,357 to turn it into a doubly linked list. 231 231 00:09:29,357 --> 00:09:31,360 So let's go ahead and do that. 232 232 00:09:31,360 --> 00:09:32,910 I'll see you in the next video. 20694