Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,266 --> 00:00:02,653 (energetic music) 2 2 00:00:02,653 --> 00:00:05,270 (keyboard clicks) 3 3 00:00:05,270 --> 00:00:07,420 Alright, this shouldn't have been too difficult. 4 4 00:00:07,420 --> 00:00:09,220 I included this challenge 5 5 00:00:09,220 --> 00:00:11,440 because I wanted you to write the code 6 6 00:00:11,440 --> 00:00:15,040 to wire up the next and previous fields 7 7 00:00:15,040 --> 00:00:17,300 when you're adding a node into the list. 8 8 00:00:17,300 --> 00:00:19,850 So I'm in the employee doubly link list class 9 9 00:00:19,850 --> 00:00:23,030 and I'm gonna go down to the add before method. 10 10 00:00:23,030 --> 00:00:24,220 Now there was a comment here 11 11 00:00:24,220 --> 00:00:26,120 saying return true if you are able 12 12 00:00:26,120 --> 00:00:28,840 to successfully add the employee into the list 13 13 00:00:28,840 --> 00:00:30,610 before the existing employee, 14 14 00:00:30,610 --> 00:00:33,150 and return false if the existing employee 15 15 00:00:33,150 --> 00:00:34,630 doesn't exist in the list. 16 16 00:00:34,630 --> 00:00:36,760 Because obviously if the existing employee 17 17 00:00:36,760 --> 00:00:38,950 doesn't exist, then you don't know where to add 18 18 00:00:38,950 --> 00:00:41,360 the new employee, so you can't do anything. 19 19 00:00:41,360 --> 00:00:43,650 Okay, so I'm gonna remove this comment here, 20 20 00:00:43,650 --> 00:00:45,200 and let's implement our method. 21 21 00:00:45,200 --> 00:00:46,720 So the first thing we're gonna do is check 22 22 00:00:46,720 --> 00:00:47,970 whether the list is empty. 23 23 00:00:47,970 --> 00:00:50,800 Because if it's empty, then we just need to return false, 24 24 00:00:50,800 --> 00:00:54,750 because obviously the employee that we want to add 25 25 00:00:54,750 --> 00:00:57,810 the new employee in front of doesn't exist in the list, 26 26 00:00:57,810 --> 00:00:59,150 so we can't do anything. 27 27 00:00:59,150 --> 00:01:03,150 So I'm just gonna say, if head equals null, return false. 28 28 00:01:05,750 --> 00:01:08,380 I could also use if is empty here. 29 29 00:01:08,380 --> 00:01:09,970 I'm just gonna say if head equals null, 30 30 00:01:09,970 --> 00:01:12,740 but you could also have said if is empty. 31 31 00:01:12,740 --> 00:01:16,580 Okay, so if it's not empty, then we have at least 32 32 00:01:16,580 --> 00:01:19,290 one employee in the list, and so the first thing 33 33 00:01:19,290 --> 00:01:22,550 we need to do is find the existing employee. 34 34 00:01:22,550 --> 00:01:26,563 So I'll say find the existing employee. 35 35 00:01:28,100 --> 00:01:33,100 So I'll say employee node current equals head, 36 36 00:01:33,150 --> 00:01:36,010 cause we're gonna start looking at the head of the list. 37 37 00:01:36,010 --> 00:01:39,703 And then while current is not equal to null, 38 38 00:01:40,980 --> 00:01:45,060 and current isn't the node that we're looking for, 39 39 00:01:45,060 --> 00:01:46,570 the employee that we're looking for, 40 40 00:01:46,570 --> 00:01:51,340 so current dot get employee dot equals 41 41 00:01:51,340 --> 00:01:53,093 the existing employee. 42 42 00:01:54,770 --> 00:01:56,560 So while current isn't null, 43 43 00:01:56,560 --> 00:02:01,465 and while current isn't equal to the existing employee, 44 44 00:02:01,465 --> 00:02:03,330 we're gonna move to the next node. 45 45 00:02:03,330 --> 00:02:05,903 Current equals current dot get next. 46 46 00:02:07,790 --> 00:02:09,360 Now when we drop out of this loop, 47 47 00:02:09,360 --> 00:02:11,830 two things are possible, either current is null, 48 48 00:02:11,830 --> 00:02:15,130 meaning that the existing employee isn't in the list, 49 49 00:02:15,130 --> 00:02:17,960 so the employee doesn't actually exist in the list, 50 50 00:02:17,960 --> 00:02:22,340 or we have found the employee that was passed in 51 51 00:02:22,340 --> 00:02:24,200 as the existing employee. 52 52 00:02:24,200 --> 00:02:27,400 So we'll handle the if current equals null case first, 53 53 00:02:27,400 --> 00:02:29,103 because if current equals null, 54 54 00:02:30,410 --> 00:02:32,480 we just want to return false. 55 55 00:02:32,480 --> 00:02:35,800 Cause obviously, if the existing employee, 56 56 00:02:35,800 --> 00:02:38,310 the one that we want to insert in front of 57 57 00:02:38,310 --> 00:02:40,403 isn't in the list, we can't do anything. 58 58 00:02:41,620 --> 00:02:43,510 Alright, so if we get down to this point, 59 59 00:02:43,510 --> 00:02:45,330 we know that we have found 60 60 00:02:45,330 --> 00:02:48,030 the existing employee in the list. 61 61 00:02:48,030 --> 00:02:50,130 So the employee exists in the list 62 62 00:02:50,130 --> 00:02:52,780 and so we want to insert the new employee 63 63 00:02:52,780 --> 00:02:55,230 in front of the existing employee. 64 64 00:02:55,230 --> 00:02:58,170 So what we'll have to do, if we're gonna plop 65 65 00:02:58,170 --> 00:03:01,930 this new employee in front of an existing employee, 66 66 00:03:01,930 --> 00:03:04,990 we're gonna have to change four fields. 67 67 00:03:04,990 --> 00:03:08,000 We're gonna have to obviously set the previous and next 68 68 00:03:08,000 --> 00:03:10,160 fields of the new employee. 69 69 00:03:10,160 --> 00:03:12,470 We're gonna have to change the previous field 70 70 00:03:12,470 --> 00:03:14,760 of the current node, because we're inserting 71 71 00:03:14,760 --> 00:03:17,010 the new employee in front of the current node, 72 72 00:03:17,010 --> 00:03:19,600 so we're gonna want the current node's previous field 73 73 00:03:19,600 --> 00:03:21,440 to point to the new employee, 74 74 00:03:21,440 --> 00:03:25,510 and then the employee that's currently in front of current 75 75 00:03:25,510 --> 00:03:28,000 is now going to be in front of the new employee, 76 76 00:03:28,000 --> 00:03:30,710 so its next field needs to be changed. 77 77 00:03:30,710 --> 00:03:32,020 So lets start doing that. 78 78 00:03:32,020 --> 00:03:34,550 So we'll start by setting the new node's 79 79 00:03:34,550 --> 00:03:36,400 next and previous fields. 80 80 00:03:36,400 --> 00:03:39,070 So the first we'll do is create a node 81 81 00:03:39,070 --> 00:03:43,330 for the employee, so we'll say employee node. 82 82 00:03:43,330 --> 00:03:46,970 New node, equals new employee node, 83 83 00:03:46,970 --> 00:03:49,903 and that's for the new employee. 84 84 00:03:51,480 --> 00:03:55,050 And then we'll set the new node's next and previous fields, 85 85 00:03:55,050 --> 00:03:58,950 so we'll say new node dot set previous, 86 86 00:03:58,950 --> 00:04:02,230 and this wants to point to whatever the current node's 87 87 00:04:02,230 --> 00:04:04,150 previous field is pointing to. 88 88 00:04:04,150 --> 00:04:07,980 Let's say we have Mary Smith and John Doe. 89 89 00:04:07,980 --> 00:04:10,810 So Mary Smith is in front of John Doe, 90 90 00:04:10,810 --> 00:04:14,040 and then we come along and we want to insert Bill End 91 91 00:04:14,040 --> 00:04:16,430 in between Mary Smith and John Doe. 92 92 00:04:16,430 --> 00:04:19,020 So right now John Doe's previous field 93 93 00:04:19,020 --> 00:04:20,340 is pointing to Mary Smith. 94 94 00:04:20,340 --> 00:04:23,120 That's what we want Bill End's previous field 95 95 00:04:23,120 --> 00:04:25,120 to point to once he's inserted. 96 96 00:04:25,120 --> 00:04:29,240 And so we want to say new node dot set previous to 97 97 00:04:29,240 --> 00:04:32,130 whatever the current node is currently pointing to 98 98 00:04:32,130 --> 00:04:33,980 in its previous field. 99 99 00:04:33,980 --> 00:04:37,180 And then because we're inserting the new employee 100 100 00:04:37,180 --> 00:04:38,980 in front of the existing employee, 101 101 00:04:38,980 --> 00:04:41,340 we want the new employee's next field 102 102 00:04:41,340 --> 00:04:43,510 to point to the existing employee. 103 103 00:04:43,510 --> 00:04:47,313 So we're going to say new node dot set next, current. 104 104 00:04:48,210 --> 00:04:51,340 And that's taken care of setting the new node's 105 105 00:04:51,340 --> 00:04:53,010 previous and next fields. 106 106 00:04:53,010 --> 00:04:55,830 Now we also need to set the previous field 107 107 00:04:55,830 --> 00:04:58,940 of the current node, because in the example I gave 108 108 00:04:58,940 --> 00:05:02,240 John Doe is no longer going to be pointing to Mary Smith 109 109 00:05:02,240 --> 00:05:05,510 as previous, he wants to point to Bill End. 110 110 00:05:05,510 --> 00:05:09,400 So we're gonna say current dot set previous, 111 111 00:05:09,400 --> 00:05:11,513 and he wants to point to the new node. 112 112 00:05:12,462 --> 00:05:15,020 And then finally we need to take care 113 113 00:05:15,020 --> 00:05:16,940 of Mary Smith's next field, 114 114 00:05:16,940 --> 00:05:19,200 but we need to be careful here. 115 115 00:05:19,200 --> 00:05:22,489 Because it's possible that John Doe, 116 116 00:05:22,489 --> 00:05:25,780 if we use him as an example of the existing employee, 117 117 00:05:25,780 --> 00:05:29,000 let's suppose that the employee that we want to insert 118 118 00:05:29,000 --> 00:05:32,510 before, that employee might be at the head of the list. 119 119 00:05:32,510 --> 00:05:34,760 And so we have to handle that special case. 120 120 00:05:34,760 --> 00:05:37,690 Let's say we say we want to insert Bill End 121 121 00:05:37,690 --> 00:05:40,790 before Mike Wilson, and Mike is at the head of the list, 122 122 00:05:40,790 --> 00:05:42,910 we don't have to set the next field 123 123 00:05:42,910 --> 00:05:44,260 of the node in front of Mike, 124 124 00:05:44,260 --> 00:05:46,040 because there is no next field. 125 125 00:05:46,040 --> 00:05:49,790 But what we would have to do is change the head field 126 126 00:05:49,790 --> 00:05:51,530 to the new employee. 127 127 00:05:51,530 --> 00:05:54,100 Because if Mike is at the head of the list, 128 128 00:05:54,100 --> 00:05:56,410 and we're inserting a new employee before Mike, 129 129 00:05:56,410 --> 00:05:59,330 then the new employee becomes the head of the list. 130 130 00:05:59,330 --> 00:06:02,963 So we're gonna say, if head equals current, 131 131 00:06:04,830 --> 00:06:08,460 then what we wanna do is set head to the new node. 132 132 00:06:08,460 --> 00:06:10,180 We don't have to handle the next field 133 133 00:06:10,180 --> 00:06:11,500 in whatever was in front of Mike, 134 134 00:06:11,500 --> 00:06:13,430 because nothing was in front of Mike. 135 135 00:06:13,430 --> 00:06:16,005 But if Mike isn't the head, then we do have to handle 136 136 00:06:16,005 --> 00:06:18,790 the next field of the node that was in front 137 137 00:06:18,790 --> 00:06:20,730 of the current node, and so we'll say, 138 138 00:06:20,730 --> 00:06:25,730 new node dot get previous dot set next, 139 139 00:06:26,160 --> 00:06:28,620 and we want to set it to the new node. 140 140 00:06:28,620 --> 00:06:32,130 So up here we've already set the new node's previous field 141 141 00:06:32,130 --> 00:06:35,150 to whatever was in front of the employee 142 142 00:06:35,150 --> 00:06:36,800 that we're inserting in front of. 143 143 00:06:36,800 --> 00:06:39,460 So in the case of inserting Bill End 144 144 00:06:39,460 --> 00:06:41,800 between Mary Smith and John Doe, 145 145 00:06:41,800 --> 00:06:45,100 we already set the new node's previous field to Mary Smith. 146 146 00:06:45,100 --> 00:06:48,303 So new node dot get previous will be Mary Smith, 147 147 00:06:48,303 --> 00:06:50,750 and we want to set her next field to the new node, 148 148 00:06:50,750 --> 00:06:52,880 because instead of pointing to John Doe, 149 149 00:06:52,880 --> 00:06:55,733 she's now gonna want to point to Bill End. 150 150 00:06:57,060 --> 00:06:58,570 And so that's what we have to do 151 151 00:06:58,570 --> 00:07:01,700 to wire up the new node properly 152 152 00:07:01,700 --> 00:07:03,990 and to change the next field of the node 153 153 00:07:03,990 --> 00:07:05,450 that's now in front of the new node, 154 154 00:07:05,450 --> 00:07:09,270 and the previous field of the existing employee. 155 155 00:07:09,270 --> 00:07:10,650 But we're not quite finished yet, 156 156 00:07:10,650 --> 00:07:14,163 we have to increment the size. 157 157 00:07:15,040 --> 00:07:19,240 And we also want change this return false, to return true. 158 158 00:07:19,240 --> 00:07:20,820 Because if we make it down here, 159 159 00:07:20,820 --> 00:07:23,790 we were able to successfully insert the new employee 160 160 00:07:23,790 --> 00:07:27,650 into the list in front of the existing employee. 161 161 00:07:27,650 --> 00:07:29,770 So let's go over to the main method, 162 162 00:07:29,770 --> 00:07:32,970 and here, this is the code 163 163 00:07:32,970 --> 00:07:34,260 that was in the starter project, 164 164 00:07:34,260 --> 00:07:35,770 so we're adding five employees, 165 165 00:07:35,770 --> 00:07:37,260 we create our list, 166 166 00:07:37,260 --> 00:07:40,220 we add Jane, John, Mary, and Mike to the list. 167 167 00:07:40,220 --> 00:07:43,880 And then we want to add Bill before John Doe. 168 168 00:07:43,880 --> 00:07:46,163 So let's run this to make sure it works. 169 169 00:07:47,910 --> 00:07:51,690 Here's the list before we add Bill End, 170 170 00:07:51,690 --> 00:07:56,690 and we can see that it contains Mike, Mary, John, and Jane. 171 171 00:07:58,590 --> 00:08:02,090 And then here's the list after we've added Bill End, 172 172 00:08:02,090 --> 00:08:04,410 and we've called the add before method, 173 173 00:08:04,410 --> 00:08:06,340 so we want to add him before John Doe, 174 174 00:08:06,340 --> 00:08:11,340 and we see Mike, Mary, Bill, and then John Doe. 175 175 00:08:12,800 --> 00:08:14,440 And finally Jane Jones. 176 176 00:08:14,440 --> 00:08:16,230 So that works. 177 177 00:08:16,230 --> 00:08:19,970 Let's add an employee before Mike Wilson, 178 178 00:08:19,970 --> 00:08:22,840 to make sure that we're handling this special case 179 179 00:08:22,840 --> 00:08:26,310 of the existing employee being the head of the list. 180 180 00:08:26,310 --> 00:08:28,510 So we'll say list dot add before, 181 181 00:08:28,510 --> 00:08:32,162 and I'll just make a new employee up on the fly. 182 182 00:08:32,162 --> 00:08:34,278 (keyboard clicks) 183 183 00:08:34,278 --> 00:08:39,278 I'll say Someone Else, and we'll give them an ID of 1111, 184 184 00:08:39,358 --> 00:08:42,870 and we want to have them in front of Mike Wilson, 185 185 00:08:42,870 --> 00:08:45,030 because he's the front of the list. 186 186 00:08:45,030 --> 00:08:47,610 And then we'll say list dot print list. 187 187 00:08:47,610 --> 00:08:48,993 So let's do that. 188 188 00:08:51,340 --> 00:08:53,320 And we'll see that Someone Else 189 189 00:08:53,320 --> 00:08:55,040 has been added at the front of the list. 190 190 00:08:55,040 --> 00:09:00,023 And we still have all the rest of our entries in the list. 191 191 00:09:02,760 --> 00:09:04,300 So that's it for this challenge, 192 192 00:09:04,300 --> 00:09:07,600 I think maybe perhaps this special case 193 193 00:09:07,600 --> 00:09:10,160 might have tripped a couple of you up at first, 194 194 00:09:10,160 --> 00:09:13,780 but otherwise it's pretty standard stuff. 195 195 00:09:13,780 --> 00:09:17,290 And as I said, I included this challenge 196 196 00:09:17,290 --> 00:09:19,810 just to have you the opportunity to go through 197 197 00:09:19,810 --> 00:09:23,750 having to wire up a node in a doubly linked list. 198 198 00:09:23,750 --> 00:09:25,370 So that's it for challenge number one, 199 199 00:09:25,370 --> 00:09:27,313 let's move on to challenge number two. 17571