Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,125 --> 00:00:02,545 (futuristic electronic music) 2 2 00:00:02,545 --> 00:00:05,840 (keyboard keys clack) 3 3 00:00:05,840 --> 00:00:08,360 All right, so this is a data structures 4 4 00:00:08,360 --> 00:00:10,830 and algorithms for Java course, 5 5 00:00:10,830 --> 00:00:12,990 and if you wanna use a linked list in Java, 6 6 00:00:12,990 --> 00:00:14,450 you're probably going to use 7 7 00:00:14,450 --> 00:00:16,950 the LinkedList class in the JDK. 8 8 00:00:16,950 --> 00:00:19,960 So here we are at the Java doc for the LinkedList class, 9 9 00:00:19,960 --> 00:00:21,630 and the first thing we'll notice 10 10 00:00:21,630 --> 00:00:25,730 is it says this is a doubly linked list implementation, 11 11 00:00:25,730 --> 00:00:27,350 and so, if you use this class, 12 12 00:00:27,350 --> 00:00:29,360 you're actually getting a doubly linked list, 13 13 00:00:29,360 --> 00:00:31,070 not a singly linked list. 14 14 00:00:31,070 --> 00:00:34,010 We'll also notice that it implements the List interface 15 15 00:00:34,010 --> 00:00:36,930 and the Deque interface. 16 16 00:00:36,930 --> 00:00:38,610 We're gonna look at queues later. 17 17 00:00:38,610 --> 00:00:41,140 Now because it implements the List interface, 18 18 00:00:41,140 --> 00:00:42,990 all the methods in the List interface 19 19 00:00:42,990 --> 00:00:45,470 are in the LinkedList class, so, 20 20 00:00:45,470 --> 00:00:47,423 we have methods like add, 21 21 00:00:49,104 --> 00:00:49,937 indexOf, 22 22 00:00:51,940 --> 00:00:54,530 size, toArray, 23 23 00:00:54,530 --> 00:00:55,733 remove. 24 24 00:00:58,910 --> 00:01:01,040 Now, this class uses generics, 25 25 00:01:01,040 --> 00:01:03,970 so you can use this LinkedList class 26 26 00:01:03,970 --> 00:01:05,790 with any type of object, 27 27 00:01:05,790 --> 00:01:08,170 including our Employee object. 28 28 00:01:08,170 --> 00:01:09,860 Now what about the Node class? 29 29 00:01:09,860 --> 00:01:13,310 Well, the LinkedList class has its own implementation 30 30 00:01:13,310 --> 00:01:14,290 of the Node class, 31 31 00:01:14,290 --> 00:01:17,600 so we don't have to write a Node class ourselves. 32 32 00:01:17,600 --> 00:01:18,840 Now it's important to note 33 33 00:01:18,840 --> 00:01:21,240 that this class is not synchronised. 34 34 00:01:21,240 --> 00:01:23,140 This implementation is not synchronised, 35 35 00:01:23,140 --> 00:01:25,880 so if you wanna use a LinkedList instance 36 36 00:01:25,880 --> 00:01:27,370 from multiple threads, 37 37 00:01:27,370 --> 00:01:29,640 you'll have to synchronise the calls 38 38 00:01:29,640 --> 00:01:31,900 to any of the LinkedList methods. 39 39 00:01:31,900 --> 00:01:33,270 You'll have to do that yourself. 40 40 00:01:33,270 --> 00:01:35,070 All right, let's go over to the IDE. 41 41 00:01:39,090 --> 00:01:40,690 So I've created a new project. 42 42 00:01:40,690 --> 00:01:42,350 I've put the code into package 43 43 00:01:42,350 --> 00:01:46,390 academy.learnprogramming.jdklinkedlists, 44 44 00:01:46,390 --> 00:01:49,950 and I've created the usual Employee instances. 45 45 00:01:49,950 --> 00:01:53,020 To do that, I've obviously copied over the Employee class 46 46 00:01:53,020 --> 00:01:54,020 that we've been using, 47 47 00:01:54,020 --> 00:01:55,760 and it's the exact same class. 48 48 00:01:55,760 --> 00:01:58,510 I just copied and pasted the code over from 49 49 00:01:58,510 --> 00:02:00,170 one of the other projects. 50 50 00:02:00,170 --> 00:02:03,660 So let's create a linked list for our Employee 51 51 00:02:03,660 --> 00:02:05,620 so we'll say LinkedList, 52 52 00:02:06,800 --> 00:02:07,883 Employee, 53 53 00:02:08,750 --> 00:02:10,980 list equals 54 54 00:02:10,980 --> 00:02:12,440 new LinkedList, 55 55 00:02:15,530 --> 00:02:18,640 and it's gonna ask me to raise my language level 56 56 00:02:18,640 --> 00:02:21,360 'cause the default language level is 1.6, 57 57 00:02:21,360 --> 00:02:23,100 and I believe this needs 1.7. 58 58 00:02:23,100 --> 00:02:25,310 So I want that light bulb to come up, 59 59 00:02:25,310 --> 00:02:27,440 not that one, the red one. 60 60 00:02:27,440 --> 00:02:30,950 There it is, and I'll just say Set language level to seven. 61 61 00:02:30,950 --> 00:02:32,910 Okay, so let's do what we did before. 62 62 00:02:32,910 --> 00:02:35,790 We'll add a bunch of employees to the front of the list, 63 63 00:02:35,790 --> 00:02:37,543 so I'll say list.addFirst. 64 64 00:02:39,480 --> 00:02:41,730 So this is the method you call 65 65 00:02:41,730 --> 00:02:45,450 if you want to add an item to the front of the LinkedList, 66 66 00:02:45,450 --> 00:02:46,927 and we'll add janeJones. 67 67 00:02:50,110 --> 00:02:50,943 list.addFirst 68 68 00:02:52,178 --> 00:02:53,011 johnDoe. 69 69 00:02:54,893 --> 00:02:55,976 list.addFirst 70 70 00:02:57,940 --> 00:02:59,020 marySmith, 71 71 00:02:59,020 --> 00:03:00,870 and list.addFirst 72 72 00:03:02,730 --> 00:03:04,464 mikeWilson. 73 73 00:03:04,464 --> 00:03:07,210 The LinkedList class doesn't have a handy printList method, 74 74 00:03:07,210 --> 00:03:08,680 but it does have an iterator, 75 75 00:03:08,680 --> 00:03:11,270 so that's how we're going to print what's in the list. 76 76 00:03:11,270 --> 00:03:12,733 So we'll say Iterator, 77 77 00:03:16,800 --> 00:03:19,900 and I'll call it iter, equals, 78 78 00:03:19,900 --> 00:03:23,350 and you'll notice there's multiple choices here for Iterator 79 79 00:03:23,350 --> 00:03:25,660 so I'm gonna press Alt + Enter, 80 80 00:03:25,660 --> 00:03:28,590 and I want the java.util iterator, 81 81 00:03:28,590 --> 00:03:30,623 equals list.iterator, 82 82 00:03:31,550 --> 00:03:33,123 and then, while iter.hasNext. 83 83 00:03:37,170 --> 00:03:38,400 We'll just print out 84 84 00:03:40,100 --> 00:03:41,633 iter.next. 85 85 00:03:43,110 --> 00:03:47,200 We could also use a for loop to print out the list. 86 86 00:03:47,200 --> 00:03:51,110 I'll put that as a comment, so we could say for 87 87 00:03:51,110 --> 00:03:53,630 Employee employee 88 88 00:03:53,630 --> 00:03:54,913 in the list, 89 89 00:03:55,890 --> 00:03:58,390 System.out.println employee, 90 90 00:03:58,390 --> 00:03:59,853 so we could do that, 91 91 00:04:00,720 --> 00:04:03,460 and I'll put this in a comment just so that you can see. 92 92 00:04:03,460 --> 00:04:05,260 So both of these will print the list. 93 93 00:04:05,260 --> 00:04:06,570 Now obviously, it's not gonna have 94 94 00:04:06,570 --> 00:04:08,580 the nice arrow that we had. 95 95 00:04:08,580 --> 00:04:12,400 We're gonna be printing each employee on a single line. 96 96 00:04:12,400 --> 00:04:16,490 Well I suppose I could add that in myself, so, 97 97 00:04:16,490 --> 00:04:19,033 I'll say System.out.print, 98 98 00:04:20,670 --> 00:04:21,503 HEAD. 99 99 00:04:24,080 --> 00:04:26,030 Pretty much do the same thing we did before, 100 100 00:04:26,030 --> 00:04:28,160 and then, I'll change that to print, 101 101 00:04:28,160 --> 00:04:31,950 and then, I'll say System.out.print, 102 102 00:04:31,950 --> 00:04:33,410 and we'll do the double arrow 103 103 00:04:33,410 --> 00:04:35,230 'cause this is a doubly linked list, 104 104 00:04:35,230 --> 00:04:37,493 and then, at the very end, we'll print null. 105 105 00:04:42,540 --> 00:04:44,020 So now, we're doing the same thing 106 106 00:04:44,020 --> 00:04:45,260 that we did in our printList 107 107 00:04:45,260 --> 00:04:49,240 except we're an iterator to print out the items. 108 108 00:04:49,240 --> 00:04:50,173 So let's run, 109 109 00:04:54,640 --> 00:04:56,760 and we'll see that we have the same thing we had before. 110 110 00:04:56,760 --> 00:04:59,580 We've got our head and then we've got Mike Wilson, 111 111 00:04:59,580 --> 00:05:04,233 Mary Smith, John Doe, and Jane Jones. 112 112 00:05:05,510 --> 00:05:09,410 So let's say we wanna add Bill End to the end of the list. 113 113 00:05:09,410 --> 00:05:12,080 So right now, we've got addFirst, 114 114 00:05:12,080 --> 00:05:16,150 and so, let me create a Bill End employee. 115 115 00:05:16,150 --> 00:05:18,250 I'll add him up here, so Employee 116 116 00:05:20,015 --> 00:05:23,783 billEnd equals new Employee Bill, 117 117 00:05:25,800 --> 00:05:27,070 End, 118 118 00:05:27,070 --> 00:05:28,520 and I think his ID 119 119 00:05:28,520 --> 00:05:30,540 that we gave him in the last video was 78. 120 120 00:05:30,540 --> 00:05:32,150 Now we can't use addFirst 121 121 00:05:32,150 --> 00:05:34,840 because addFirst adds to the front of the list, 122 122 00:05:34,840 --> 00:05:38,603 and so, instead, we use the add method. 123 123 00:05:40,030 --> 00:05:43,710 So for LinkedList, the add methods adds 124 124 00:05:43,710 --> 00:05:46,490 an item to the end of the list. 125 125 00:05:46,490 --> 00:05:48,410 It adds it at the tail, 126 126 00:05:48,410 --> 00:05:51,733 and so, we wanna add billEnd at the tail, 127 127 00:05:52,630 --> 00:05:54,223 and then, copy this code. 128 128 00:05:56,360 --> 00:05:58,100 I suppose I could put this in a method, 129 129 00:05:58,100 --> 00:05:59,943 but we'll just go with this for now. 130 130 00:06:01,450 --> 00:06:05,703 Don't need to declare the iterator again, and let's run, 131 131 00:06:09,340 --> 00:06:12,270 and so, Mike's still at the front of the list. 132 132 00:06:12,270 --> 00:06:13,920 Everybody's in the same position 133 133 00:06:13,920 --> 00:06:16,820 except at the end, we have Bill End. 134 134 00:06:16,820 --> 00:06:18,320 So this is important to remember 135 135 00:06:18,320 --> 00:06:20,890 when you're working with the JDK LinkedList class. 136 136 00:06:20,890 --> 00:06:24,870 The add method, the implementation of the add method 137 137 00:06:24,870 --> 00:06:26,600 from the List interface, 138 138 00:06:26,600 --> 00:06:30,520 adds the item to the end of the linked list. 139 139 00:06:30,520 --> 00:06:32,060 If you want an item added to the front, 140 140 00:06:32,060 --> 00:06:34,210 you have to use the addFirst method. 141 141 00:06:34,210 --> 00:06:36,280 So it's important to read the description 142 142 00:06:36,280 --> 00:06:37,550 of the method you wanna use 143 143 00:06:37,550 --> 00:06:40,870 to make sure it's adding the item where you want it added. 144 144 00:06:40,870 --> 00:06:42,420 Now, we could also use addLast. 145 145 00:06:44,810 --> 00:06:49,063 So if I change this addLast and run, 146 146 00:06:51,060 --> 00:06:52,310 we'll get the same thing. 147 147 00:06:53,640 --> 00:06:55,490 So we'll see that Bill's been added to the end. 148 148 00:06:55,490 --> 00:06:58,640 So you can use add, or if you wanna be really clear 149 149 00:06:58,640 --> 00:07:00,840 that you're adding the item to the end of the list, 150 150 00:07:00,840 --> 00:07:02,600 you can use addLast. 151 151 00:07:02,600 --> 00:07:04,310 Okay, and I'll close this down again, 152 152 00:07:04,310 --> 00:07:07,850 and let's go look at the code for LinkedList. 153 153 00:07:07,850 --> 00:07:12,850 So I'm gonna right-click and say go to the Declaration, 154 154 00:07:13,370 --> 00:07:16,860 and we'll see that it is using a Node class, 155 155 00:07:16,860 --> 00:07:17,870 first and last. 156 156 00:07:17,870 --> 00:07:22,050 So first is basically the head and last is the tail. 157 157 00:07:22,050 --> 00:07:25,610 It's got a size and so this looks familiar, doesn't it? 158 158 00:07:25,610 --> 00:07:27,510 Now what's the underlying data structure 159 159 00:07:27,510 --> 00:07:28,720 being used for the LinkedList? 160 160 00:07:28,720 --> 00:07:31,030 Remember when we looked at ArrayList and Vector, 161 161 00:07:31,030 --> 00:07:34,290 we discovered that it was an array. 162 162 00:07:34,290 --> 00:07:35,670 Well, we'll see that the class 163 163 00:07:35,670 --> 00:07:38,310 extends AbstractSequentialList, 164 164 00:07:38,310 --> 00:07:39,963 and if we take a look at that, 165 165 00:07:43,990 --> 00:07:46,260 we'll see that this kind of provides 166 166 00:07:46,260 --> 00:07:49,710 a skeletal implementation of the List interface 167 167 00:07:49,710 --> 00:07:51,810 to reduce the amount of work required 168 168 00:07:51,810 --> 00:07:54,230 for classes that wanna implement List. 169 169 00:07:54,230 --> 00:07:57,600 So basically, if you wanna implement the List interface 170 170 00:07:57,600 --> 00:07:59,020 and you don't wanna start from scratch 171 171 00:07:59,020 --> 00:08:00,830 and have to implement every single method, 172 172 00:08:00,830 --> 00:08:03,430 instead of just implementing List, 173 173 00:08:03,430 --> 00:08:06,890 you can extend this class if you want a sequential list, 174 174 00:08:06,890 --> 00:08:08,670 and you get a bunch of stuff for free, 175 175 00:08:08,670 --> 00:08:11,490 and then, you can just override what you wanna override, 176 176 00:08:11,490 --> 00:08:12,900 and that's all fine and dandy, 177 177 00:08:12,900 --> 00:08:15,670 but how is a linked list being stored? 178 178 00:08:15,670 --> 00:08:17,820 Well, you can see how it's being stored. 179 179 00:08:17,820 --> 00:08:22,210 It's exactly similar to the way that we implemented our, 180 180 00:08:22,210 --> 00:08:24,760 our simple, single, singly linked list 181 181 00:08:24,760 --> 00:08:25,890 and doubly linked list. 182 182 00:08:25,890 --> 00:08:28,520 The linked list itself is the data structure, 183 183 00:08:28,520 --> 00:08:30,860 so it's not being backed by anything. 184 184 00:08:30,860 --> 00:08:32,920 The linked list is just containing 185 185 00:08:32,920 --> 00:08:35,690 references to a head and a tail, 186 186 00:08:35,690 --> 00:08:39,533 and this Node class, let's have a look at it, 187 187 00:08:42,670 --> 00:08:45,920 has the item which is, 188 188 00:08:45,920 --> 00:08:47,630 in our case, would be the employee, 189 189 00:08:47,630 --> 00:08:50,190 and then, it's got next and previous. 190 190 00:08:50,190 --> 00:08:53,390 So the linked list itself is the data structure. 191 191 00:08:53,390 --> 00:08:55,530 There's nothing that's backing it, 192 192 00:08:55,530 --> 00:08:57,100 and since we went through 193 193 00:08:57,100 --> 00:08:59,060 a simple implementation of a linked list, 194 194 00:08:59,060 --> 00:09:00,060 this should look familiar, 195 195 00:09:00,060 --> 00:09:02,530 and that's why we went through those simple implementations, 196 196 00:09:02,530 --> 00:09:04,670 so you have some idea of what's going on 197 197 00:09:04,670 --> 00:09:05,530 underneath the covers 198 198 00:09:05,530 --> 00:09:07,170 when you're working with a linked list. 199 199 00:09:07,170 --> 00:09:09,230 Okay, so let's go back to the main method. 200 200 00:09:09,230 --> 00:09:11,060 So we've added employees. 201 201 00:09:11,060 --> 00:09:12,310 How do we remove them? 202 202 00:09:12,310 --> 00:09:14,578 Well, if you guessed that there are removeFirst 203 203 00:09:14,578 --> 00:09:16,943 and removeLast methods, you're right. 204 204 00:09:17,940 --> 00:09:19,750 So let's go ahead here. 205 205 00:09:19,750 --> 00:09:22,693 I'm just gonna copy this whole thing. 206 206 00:09:26,380 --> 00:09:30,693 Instead of adding last, let's remove the first, 207 207 00:09:32,280 --> 00:09:34,260 and we don't have to pass anything 208 208 00:09:34,260 --> 00:09:37,840 'cause we're always gonna remove the first item here, 209 209 00:09:37,840 --> 00:09:38,873 and let's run, 210 210 00:09:41,510 --> 00:09:44,150 and we'll see that Mike is gone. 211 211 00:09:44,150 --> 00:09:46,340 Because we called removeFirst, 212 212 00:09:46,340 --> 00:09:48,890 Mary is now the first item in the list, 213 213 00:09:48,890 --> 00:09:51,573 and if we go to the end, Bill's still there, 214 214 00:09:53,270 --> 00:09:54,850 but if I 215 215 00:09:56,090 --> 00:09:57,470 copy this code again 216 216 00:09:57,470 --> 00:09:59,433 and say list.removeLast, 217 217 00:10:03,940 --> 00:10:06,990 Bill should now be taken from the list, 218 218 00:10:06,990 --> 00:10:08,450 and let's check it out. 219 219 00:10:08,450 --> 00:10:11,100 So Mary's still first on the list, 220 220 00:10:11,100 --> 00:10:14,880 but we go to the end, we'll see that Bill is now gone, 221 221 00:10:14,880 --> 00:10:18,257 and so, that's how you remove items from the front 222 222 00:10:18,257 --> 00:10:20,110 and the end of the list. 223 223 00:10:20,110 --> 00:10:21,470 You have to be careful, though, 224 224 00:10:21,470 --> 00:10:24,420 because, let me just close this down, 225 225 00:10:24,420 --> 00:10:26,120 when we were talking about add, 226 226 00:10:26,120 --> 00:10:28,320 I said if you just call the add method, 227 227 00:10:28,320 --> 00:10:31,020 it will add an item to the end of the list. 228 228 00:10:31,020 --> 00:10:35,190 Well, in the remove case, if you just call remove like this, 229 229 00:10:35,190 --> 00:10:37,870 it will remove the first item on the list, 230 230 00:10:37,870 --> 00:10:41,450 so as I said, make sure that you always, 231 231 00:10:41,450 --> 00:10:42,330 let me just undo that, 232 232 00:10:42,330 --> 00:10:44,720 make sure that you always read the 233 233 00:10:44,720 --> 00:10:46,500 description of the method you're using 234 234 00:10:46,500 --> 00:10:48,410 to make sure that it's gonna be operating 235 235 00:10:48,410 --> 00:10:51,480 at the end of the list that you want it to be operating at. 236 236 00:10:51,480 --> 00:10:53,140 So there are other removal methods. 237 237 00:10:53,140 --> 00:10:56,080 For example, you could remove a specific employee. 238 238 00:10:56,080 --> 00:10:57,650 Of course, that would mean that 239 239 00:10:57,650 --> 00:11:00,400 the method has to search the list for that employee, 240 240 00:11:00,400 --> 00:11:02,890 and so, it's gonna be slower operation. 241 241 00:11:02,890 --> 00:11:05,490 There are also methods that let you insert an employee 242 242 00:11:05,490 --> 00:11:08,040 or a node at a specific point in the list. 243 243 00:11:08,040 --> 00:11:09,570 You know, you can say something like 244 244 00:11:09,570 --> 00:11:13,560 insert Joan as the sixth employee in the list, 245 245 00:11:13,560 --> 00:11:14,870 but again, if you do that, 246 246 00:11:14,870 --> 00:11:16,870 those operations are gonna be slower. 247 247 00:11:16,870 --> 00:11:18,760 The quickest operations are gonna be those 248 248 00:11:18,760 --> 00:11:21,330 that are working at the head or at the tail. 249 249 00:11:21,330 --> 00:11:23,520 Anyway, I encourage you to take a look 250 250 00:11:23,520 --> 00:11:26,820 at the LinkedList class and see what's available. 251 251 00:11:26,820 --> 00:11:28,010 The important point here 252 252 00:11:28,010 --> 00:11:30,170 is that if you wanna use a linked list in Java, 253 253 00:11:30,170 --> 00:11:31,820 you can use the LinkedList class 254 254 00:11:31,820 --> 00:11:34,670 as long as you don't mind the extra memory overhead 255 255 00:11:34,670 --> 00:11:36,900 due to the next and previous fields. 256 256 00:11:36,900 --> 00:11:40,200 If you're going to need a lot of nodes and memory is tight, 257 257 00:11:40,200 --> 00:11:43,210 you might want to consider another type of data structure, 258 258 00:11:43,210 --> 00:11:44,750 or if it makes sense, 259 259 00:11:44,750 --> 00:11:47,600 you might want to implement a singly linked list, 260 260 00:11:47,600 --> 00:11:50,350 but most of the time, memory won't be an issue. 261 261 00:11:50,350 --> 00:11:52,010 Now before we leave linked lists, 262 262 00:11:52,010 --> 00:11:54,310 I'll just mention that there's another type of linked list 263 263 00:11:54,310 --> 00:11:56,500 called a circular linked list, 264 264 00:11:56,500 --> 00:11:59,880 and this is a variation on the singly linked list, 265 265 00:11:59,880 --> 00:12:01,360 and in this variation, 266 266 00:12:01,360 --> 00:12:03,990 the last node in the list doesn't point to null. 267 267 00:12:03,990 --> 00:12:05,460 Instead, it loops back, 268 268 00:12:05,460 --> 00:12:07,930 and it points to the head of the list, 269 269 00:12:07,930 --> 00:12:09,570 and one advantage to this 270 270 00:12:09,570 --> 00:12:11,850 is that you can traverse the entire list 271 271 00:12:11,850 --> 00:12:13,340 starting at any node. 272 272 00:12:13,340 --> 00:12:14,890 So if for some reason, 273 273 00:12:14,890 --> 00:12:17,670 that feature is important to your application, 274 274 00:12:17,670 --> 00:12:20,290 then a circular linked list might work for you. 275 275 00:12:20,290 --> 00:12:22,040 So I just wanted to mention that to you. 276 276 00:12:22,040 --> 00:12:23,690 We're not gonna implement it, 277 277 00:12:23,690 --> 00:12:27,040 but there is a variation called circular linked list 278 278 00:12:27,040 --> 00:12:30,590 where the last node in the list points to the head node. 279 279 00:12:30,590 --> 00:12:32,010 Okay, that's all for linked lists. 280 280 00:12:32,010 --> 00:12:33,560 I'll see you in the next video. 23577