Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,076 --> 00:00:02,393 (gentle music) 2 2 00:00:02,393 --> 00:00:05,220 (keys clacking) 3 3 00:00:05,220 --> 00:00:06,053 In this video, 4 4 00:00:06,053 --> 00:00:08,750 we're going to begin our look at linked lists. 5 5 00:00:08,750 --> 00:00:11,040 A linked list is a data structure. 6 6 00:00:11,040 --> 00:00:13,420 It's a sequential list of objects, 7 7 00:00:13,420 --> 00:00:16,260 but this time, arrays aren't involved. 8 8 00:00:16,260 --> 00:00:18,930 In a linked list, each item in the list 9 9 00:00:18,930 --> 00:00:22,200 is aware of another item in the list, 10 10 00:00:22,200 --> 00:00:23,740 because each item in the list 11 11 00:00:23,740 --> 00:00:27,360 contains a link to the next item in the list. 12 12 00:00:27,360 --> 00:00:29,500 Now this is different from arrays 13 13 00:00:29,500 --> 00:00:32,320 and lists that are backed by arrays. 14 14 00:00:32,320 --> 00:00:36,100 With an array, each item in the list is completely unaware 15 15 00:00:36,100 --> 00:00:39,930 of other items in the array, but items in a linked list 16 16 00:00:39,930 --> 00:00:42,200 know which item comes after them, 17 17 00:00:42,200 --> 00:00:44,070 and that means that we have to store 18 18 00:00:44,070 --> 00:00:46,780 some extra information with each item. 19 19 00:00:46,780 --> 00:00:48,910 When we have an array of integers, 20 20 00:00:48,910 --> 00:00:52,460 we just have to store the integer value in each position, 21 21 00:00:52,460 --> 00:00:54,430 but when it comes to a linked list, 22 22 00:00:54,430 --> 00:00:56,780 we have to store the integer value 23 23 00:00:56,780 --> 00:00:58,640 and we have to store a reference 24 24 00:00:58,640 --> 00:01:01,200 to the next integer in the list. 25 25 00:01:01,200 --> 00:01:02,780 So when we get to the implementation, 26 26 00:01:02,780 --> 00:01:05,190 I'm going to use the employee class we used 27 27 00:01:05,190 --> 00:01:06,790 when we looked at array lists, 28 28 00:01:06,790 --> 00:01:10,340 and so on the screen here, I have a linked list, 29 29 00:01:10,340 --> 00:01:14,230 and this would be Jane, John, Mary, and Mike. 30 30 00:01:14,230 --> 00:01:16,740 And as we can see, this blue block 31 31 00:01:16,740 --> 00:01:18,850 would be the employee object, 32 32 00:01:18,850 --> 00:01:20,560 and then there'll be a field 33 33 00:01:20,560 --> 00:01:24,050 that contains a reference to the next item in the list. 34 34 00:01:24,050 --> 00:01:27,650 Each of these items is referred to as a node, 35 35 00:01:27,650 --> 00:01:31,470 and the first item in the list is the head of the list, 36 36 00:01:31,470 --> 00:01:34,350 and the last item in the list always points to null, 37 37 00:01:34,350 --> 00:01:36,430 because nothing comes after it. 38 38 00:01:36,430 --> 00:01:39,610 And so what we'll have is a node class 39 39 00:01:39,610 --> 00:01:41,850 that contains a field for 40 40 00:01:41,850 --> 00:01:43,640 whatever data you're holding in the node. 41 41 00:01:43,640 --> 00:01:46,110 In our case, we'll have an employee field. 42 42 00:01:46,110 --> 00:01:48,380 And then we'll have a next field, 43 43 00:01:48,380 --> 00:01:51,130 and that next field will be of type node, 44 44 00:01:51,130 --> 00:01:55,900 because each node points to the node that comes after it. 45 45 00:01:55,900 --> 00:01:57,700 Now I'm going to insert a spoiler here. 46 46 00:01:57,700 --> 00:02:00,410 In Java, you wouldn't implement a linked list yourself. 47 47 00:02:00,410 --> 00:02:03,680 There's a linked list class, but to help us understand 48 48 00:02:03,680 --> 00:02:05,950 what a linked list is and what its advantages are, 49 49 00:02:05,950 --> 00:02:08,240 we will code a simple implementation. 50 50 00:02:08,240 --> 00:02:10,650 So as I said, when it comes to a linked list, 51 51 00:02:10,650 --> 00:02:13,060 there will be a head field, 52 52 00:02:13,060 --> 00:02:16,320 and the head will point to the first item in the list. 53 53 00:02:16,320 --> 00:02:19,240 So if you have a reference to the head, 54 54 00:02:19,240 --> 00:02:21,090 you can traverse the entire list. 55 55 00:02:21,090 --> 00:02:22,530 You would start at the head 56 56 00:02:22,530 --> 00:02:24,650 and then you'd go to head.next, 57 57 00:02:24,650 --> 00:02:27,840 and then you'd go to that next field, that next one, 58 58 00:02:27,840 --> 00:02:29,200 until you hit null. 59 59 00:02:29,200 --> 00:02:32,700 So for a linked list, the only thing you have to store 60 60 00:02:32,700 --> 00:02:36,260 is a reference to the head or the first node in the list. 61 61 00:02:36,260 --> 00:02:39,950 And from that, you can get to every item in the list. 62 62 00:02:39,950 --> 00:02:41,850 So let's talk about what we'd have to do 63 63 00:02:41,850 --> 00:02:44,440 to insert an item into this list. 64 64 00:02:44,440 --> 00:02:47,160 So let's say we wanted to insert Bill. 65 65 00:02:47,160 --> 00:02:48,840 Well, the first thing we're gonna have to do 66 66 00:02:48,840 --> 00:02:51,380 is create a new node for Bill. 67 67 00:02:51,380 --> 00:02:54,750 So we'd have a box somewhere that has Bill in it. 68 68 00:02:54,750 --> 00:02:56,870 When it comes to linked lists, 69 69 00:02:56,870 --> 00:03:01,060 you always insert a new element at the front of the list. 70 70 00:03:01,060 --> 00:03:02,850 And you can understand why. 71 71 00:03:02,850 --> 00:03:06,260 We only ever store a reference to the first element, 72 72 00:03:06,260 --> 00:03:08,490 and so if we wanted to insert an item 73 73 00:03:08,490 --> 00:03:10,010 anywhere other than the front, 74 74 00:03:10,010 --> 00:03:12,550 then we'd have to traverse the list to get there. 75 75 00:03:12,550 --> 00:03:15,460 And one of the advantages of using a linked list 76 76 00:03:15,460 --> 00:03:18,820 is that if you insert items at the front of the list, 77 77 00:03:18,820 --> 00:03:21,760 you can do it in constant time complexity, 78 78 00:03:21,760 --> 00:03:23,450 because the steps you have to do 79 79 00:03:23,450 --> 00:03:26,230 don't depend on the number of items in the list. 80 80 00:03:26,230 --> 00:03:28,510 You're always gonna do the same number of steps. 81 81 00:03:28,510 --> 00:03:30,900 So we create a new node for Bill, 82 82 00:03:30,900 --> 00:03:34,620 and we're gonna wanna put Bill here, or up here in front. 83 83 00:03:34,620 --> 00:03:36,860 Bill is gonna wanna point to Jane. 84 84 00:03:36,860 --> 00:03:38,660 So after we've created the new node, 85 85 00:03:38,660 --> 00:03:41,560 we'll assign the next field Jane, 86 86 00:03:41,560 --> 00:03:44,120 and then we're gonna assign head to Bill, 87 87 00:03:44,120 --> 00:03:46,960 because Bill will be the new head of the list, 88 88 00:03:46,960 --> 00:03:49,670 and so that's all we have to do to insert a node. 89 89 00:03:49,670 --> 00:03:52,150 We create the actual node instance. 90 90 00:03:52,150 --> 00:03:55,240 We point the next field at the current head of the list 91 91 00:03:55,240 --> 00:03:57,980 because the new node is gonna become the new head, 92 92 00:03:57,980 --> 00:04:00,750 and then we point the head field at the new node. 93 93 00:04:00,750 --> 00:04:03,810 And that's gonna always be constant time complexity, 94 94 00:04:03,810 --> 00:04:04,730 because it doesn't matter. 95 95 00:04:04,730 --> 00:04:06,630 You could have three items in the list 96 96 00:04:06,630 --> 00:04:08,510 or a million items in the list, 97 97 00:04:08,510 --> 00:04:10,640 and you're just gonna do the same number of steps, 98 98 00:04:10,640 --> 00:04:13,430 as long as you're inserting at the front of the list. 99 99 00:04:13,430 --> 00:04:14,910 And so after the insertion, 100 100 00:04:14,910 --> 00:04:16,520 this is what the list would look like. 101 101 00:04:16,520 --> 00:04:18,740 Bill's next field points to Jane, 102 102 00:04:18,740 --> 00:04:21,240 and the head field now points to Bill 103 103 00:04:21,240 --> 00:04:23,000 because he's at the front of the list. 104 104 00:04:23,000 --> 00:04:24,380 So how about deleting? 105 105 00:04:24,380 --> 00:04:26,480 Now what if we wanted to pull Bill off? 106 106 00:04:26,480 --> 00:04:28,320 And once again, we'll want to delete 107 107 00:04:28,320 --> 00:04:29,420 from the front of the list. 108 108 00:04:29,420 --> 00:04:31,350 Otherwise, we're gonna have to traverse the list 109 109 00:04:31,350 --> 00:04:34,260 looking for the node we want to delete. 110 110 00:04:34,260 --> 00:04:36,270 Now in the implementation, I'll show you, 111 111 00:04:36,270 --> 00:04:39,440 when we do a deletion, we return the node that we deleted. 112 112 00:04:39,440 --> 00:04:42,310 So we're first gonna assign Bill to a temporary variable 113 113 00:04:42,310 --> 00:04:45,210 called removedNode, and then what do we wanna do? 114 114 00:04:45,210 --> 00:04:48,740 Well, all we're gonna do is move the head to Jane, 115 115 00:04:48,740 --> 00:04:51,890 because that effectively removes Bill from the list. 116 116 00:04:51,890 --> 00:04:55,210 Because for a linked list, the only sort of information 117 117 00:04:55,210 --> 00:04:57,280 that we're holding is this head field. 118 118 00:04:57,280 --> 00:05:00,450 And so if we break this link to Bill 119 119 00:05:00,450 --> 00:05:03,460 and we change heads so it's pointing to Jane, 120 120 00:05:03,460 --> 00:05:05,790 Bill has effectively been removed from the list. 121 121 00:05:05,790 --> 00:05:08,500 There's no way we can get from head to Bill. 122 122 00:05:08,500 --> 00:05:11,570 And then at that point, we would return the removedNode, 123 123 00:05:11,570 --> 00:05:14,590 which we previously stored Bill into that field. 124 124 00:05:14,590 --> 00:05:17,100 And that's all we have to do to delete a node 125 125 00:05:17,100 --> 00:05:18,100 from the front of the list. 126 126 00:05:18,100 --> 00:05:20,970 Once again, this will be constant time complexity, 127 127 00:05:20,970 --> 00:05:23,350 because it doesn't matter how many items are in the list. 128 128 00:05:23,350 --> 00:05:25,630 You're gonna do the same number of steps. 129 129 00:05:25,630 --> 00:05:28,810 So after we've deleted Bill, this is the situation. 130 130 00:05:28,810 --> 00:05:31,210 We have, Bill will be hanging off here. 131 131 00:05:31,210 --> 00:05:32,930 He'll still be pointing to Jane, 132 132 00:05:32,930 --> 00:05:35,820 but there's no way for us to reach him 133 133 00:05:35,820 --> 00:05:37,100 from the head of the list. 134 134 00:05:37,100 --> 00:05:38,640 And if we wanted to do clean out, 135 135 00:05:38,640 --> 00:05:42,400 we could set Bill's next field to null if we wanted to. 136 136 00:05:42,400 --> 00:05:46,000 And so that's it for sort of the theory for linked lists. 137 137 00:05:46,000 --> 00:05:48,470 They're not that complicated. 138 138 00:05:48,470 --> 00:05:50,570 They're the second data structure we've looked at, 139 139 00:05:50,570 --> 00:05:52,410 the first one being arrays, 140 140 00:05:52,410 --> 00:05:55,240 and they differ from arrays in that, 141 141 00:05:55,240 --> 00:05:57,080 as long as you're inserting and deleting 142 142 00:05:57,080 --> 00:05:58,320 from the front of the list, 143 143 00:05:58,320 --> 00:06:01,910 the insertions and deletions are done in constant time, 144 144 00:06:01,910 --> 00:06:04,830 and that's because there's no shifting involved. 145 145 00:06:04,830 --> 00:06:08,540 And this type of list is called a singly linked list 146 146 00:06:08,540 --> 00:06:12,730 because we have one link between every node. 147 147 00:06:12,730 --> 00:06:14,740 In a little while, we're going to look at a list 148 148 00:06:14,740 --> 00:06:16,500 that's called a doubly linked list. 149 149 00:06:16,500 --> 00:06:18,780 But we're starting out with a singly linked list, 150 150 00:06:18,780 --> 00:06:21,150 and when you're working with a singly linked list, 151 151 00:06:21,150 --> 00:06:24,620 you want to insert and delete items at the front of the list 152 152 00:06:24,620 --> 00:06:28,310 because you only have a reference to the head of the list, 153 153 00:06:28,310 --> 00:06:31,090 and so if you want to insert and delete items anywhere else, 154 154 00:06:31,090 --> 00:06:32,150 you'd have to start at head 155 155 00:06:32,150 --> 00:06:34,070 and you've got to traverse the entire list 156 156 00:06:34,070 --> 00:06:35,630 to find what you're looking for. 157 157 00:06:35,630 --> 00:06:37,350 All right, so now that we know a little bit 158 158 00:06:37,350 --> 00:06:39,400 about singly linked lists, let's implement one. 159 159 00:06:39,400 --> 00:06:40,950 I'll see you in the next video. 14135