1 00:00:00,000 --> 00:00:08,250 2 00:00:08,250 --> 00:00:12,680 >> JASON HIRSCHHORN: Welcome everyone to the Section Seven. 3 00:00:12,680 --> 00:00:15,040 We are in week seven of the course. 4 00:00:15,040 --> 00:00:18,440 And this upcoming Thursday is Halloween so I am 5 00:00:18,440 --> 00:00:21,420 dressed up like a pumpkin. 6 00:00:21,420 --> 00:00:23,460 I couldn't bend over and put on my shoes, so that's why I'm 7 00:00:23,460 --> 00:00:25,660 just wearing socks. 8 00:00:25,660 --> 00:00:29,220 I'm also not wearing anything under this, so I can't take it off if it's 9 00:00:29,220 --> 00:00:29,950 distracting to you. 10 00:00:29,950 --> 00:00:31,860 I apologize in advance for that. 11 00:00:31,860 --> 00:00:33,170 You don't need to imagine what's going on. 12 00:00:33,170 --> 00:00:34,240 I am wearing boxers. 13 00:00:34,240 --> 00:00:36,170 So it's all good. 14 00:00:36,170 --> 00:00:41,120 >> I have a longer story about why I'm dressed as a pumpkin, but I'm going to 15 00:00:41,120 --> 00:00:45,110 save that for later in this section because I do want to get started. 16 00:00:45,110 --> 00:00:47,720 We have a lot of exciting things to go over this week. 17 00:00:47,720 --> 00:00:51,810 Most of them relate directly to this week's problem set, misspellings. 18 00:00:51,810 --> 00:00:54,680 We're going to be going over linked lists and hash tables 19 00:00:54,680 --> 00:00:57,160 for the entire section. 20 00:00:57,160 --> 00:01:02,490 I put this list up every week, a list of resources for you to help you with 21 00:01:02,490 --> 00:01:04,120 the material on this course. 22 00:01:04,120 --> 00:01:07,600 If at a loss or if looking for some more information, check out one of 23 00:01:07,600 --> 00:01:09,930 these resources. 24 00:01:09,930 --> 00:01:14,530 >> Again, pset6 is misspellings, this week's pset. 25 00:01:14,530 --> 00:01:17,690 And it also encourages you, and I encourage you, to use some other 26 00:01:17,690 --> 00:01:20,320 resources specifically for this pset. 27 00:01:20,320 --> 00:01:23,390 In particular, the three I've listed up on the screen-- 28 00:01:23,390 --> 00:01:27,160 gdb, which we've been familiar with and been using for a while now, is 29 00:01:27,160 --> 00:01:29,270 going to be very helpful this week. 30 00:01:29,270 --> 00:01:30,190 So I put that up here. 31 00:01:30,190 --> 00:01:32,910 But whenever you're working with C, you should always be using gdb to 32 00:01:32,910 --> 00:01:34,430 debug your programs. 33 00:01:34,430 --> 00:01:36,660 This week also valgrind. 34 00:01:36,660 --> 00:01:38,535 Does anybody know what valgrind does? 35 00:01:38,535 --> 00:01:42,184 36 00:01:42,184 --> 00:01:43,890 >> AUDIENCE: It checks for memory leaks? 37 00:01:43,890 --> 00:01:45,950 >> JASON HIRSCHHORN: Valgrind checks for memory leaks. 38 00:01:45,950 --> 00:01:49,970 So if you malloc something in your program, you're asking for memory. 39 00:01:49,970 --> 00:01:52,920 At the end of your program, you have to write free on everything you've 40 00:01:52,920 --> 00:01:54,800 malloced to give the memory back. 41 00:01:54,800 --> 00:01:58,420 If you don't write free at the end and your program comes to a conclusion, 42 00:01:58,420 --> 00:02:00,000 everything will automatically be freed. 43 00:02:00,000 --> 00:02:02,340 And for small programs, it's not that big a deal. 44 00:02:02,340 --> 00:02:05,250 But if you're writing a longer running program that doesn't quit, 45 00:02:05,250 --> 00:02:09,180 necessarily, in a couple of minutes or a couple of seconds, then memory leaks 46 00:02:09,180 --> 00:02:10,710 can become a huge deal. 47 00:02:10,710 --> 00:02:14,940 >> So for pset6, the expectation is that you will have zero memory leaks with 48 00:02:14,940 --> 00:02:15,910 your program. 49 00:02:15,910 --> 00:02:18,690 To check for memory leaks, run valgrind and it'll give you some nice 50 00:02:18,690 --> 00:02:21,190 output letting you know whether or not everything was free. 51 00:02:21,190 --> 00:02:23,940 We'll practice with it later today, hopefully. 52 00:02:23,940 --> 00:02:25,790 >> Finally, the diff command. 53 00:02:25,790 --> 00:02:28,900 You used something similar to it in pset5 with the peek tool. 54 00:02:28,900 --> 00:02:30,780 Allowed you to look inside. 55 00:02:30,780 --> 00:02:33,400 You also used diff, too, per the problem set spec. 56 00:02:33,400 --> 00:02:35,950 But in allowed you to compare two files. 57 00:02:35,950 --> 00:02:39,180 You could compare the bitmap file and info headers of a staff solution and 58 00:02:39,180 --> 00:02:42,200 your solution in pset5 if you chose to use it. 59 00:02:42,200 --> 00:02:44,030 Diff will allow you to do that, as well. 60 00:02:44,030 --> 00:02:48,620 You can compare the correct answer for this week's problem set to your answer 61 00:02:48,620 --> 00:02:52,210 and see if it lines up or see where the errors are. 62 00:02:52,210 --> 00:02:55,870 >> So those are three good tools that you should use for this week, and 63 00:02:55,870 --> 00:02:58,130 definitely check your program with these three tools 64 00:02:58,130 --> 00:03:00,520 before turning it in. 65 00:03:00,520 --> 00:03:04,650 Again, as I have mentioned every week, if you have any feedback for me-- both 66 00:03:04,650 --> 00:03:06,470 positive and constructive-- 67 00:03:06,470 --> 00:03:09,930 feel free to head to the website at the bottom of this slide 68 00:03:09,930 --> 00:03:11,270 and input it there. 69 00:03:11,270 --> 00:03:13,440 I really appreciate any and all feedback. 70 00:03:13,440 --> 00:03:17,360 And if you give me specific things that I can do to improve or that I'm 71 00:03:17,360 --> 00:03:21,350 doing well that you would like me to continue, I take that to heart and 72 00:03:21,350 --> 00:03:24,040 really try hard to listen to your feedback. 73 00:03:24,040 --> 00:03:27,720 I can't promise I'm going to do everything, though, like wearing a 74 00:03:27,720 --> 00:03:30,700 pumpkin costume every week. 75 00:03:30,700 --> 00:03:34,020 >> So we are going to spend the bulk of section, as I mentioned, talking about 76 00:03:34,020 --> 00:03:37,240 linked lists and hash tables, which will be directly applicable to the 77 00:03:37,240 --> 00:03:38,780 problem set this week. 78 00:03:38,780 --> 00:03:42,580 Linked lists we'll go over relatively quickly because we've spent a fair bit 79 00:03:42,580 --> 00:03:44,930 of time going over it in section. 80 00:03:44,930 --> 00:03:48,680 And so we'll get straight into the coding problems for linked lists. 81 00:03:48,680 --> 00:03:52,740 And then at the end we'll talk about hash tables and how they apply to this 82 00:03:52,740 --> 00:03:55,280 week's problem set. 83 00:03:55,280 --> 00:03:57,560 >> You've seen this code before. 84 00:03:57,560 --> 00:04:02,730 This is a struct, and it is defining something new called a node. 85 00:04:02,730 --> 00:04:10,660 And inside a node there is an integer right here and there is a pointer to 86 00:04:10,660 --> 00:04:11,830 another node. 87 00:04:11,830 --> 00:04:12,790 We've seen this before. 88 00:04:12,790 --> 00:04:14,830 This has been coming up for a couple of weeks now. 89 00:04:14,830 --> 00:04:18,680 It combines pointers, which we've been working with, and structs, which allow 90 00:04:18,680 --> 00:04:22,079 us to combine two different things into one data type. 91 00:04:22,079 --> 00:04:24,830 92 00:04:24,830 --> 00:04:26,490 >> There's a lot going on on the screen. 93 00:04:26,490 --> 00:04:30,220 But all of it should be relatively familiar with you. 94 00:04:30,220 --> 00:04:33,810 On the first line, we declare a new node. 95 00:04:33,810 --> 00:04:41,650 And then inside that new node, I set the integer in that node to one. 96 00:04:41,650 --> 00:04:44,950 We see on the next line I'm doing a printf command, but I've grayed out 97 00:04:44,950 --> 00:04:48,080 the printf command because the really important part is this line here-- 98 00:04:48,080 --> 00:04:50,020 new_node.n. 99 00:04:50,020 --> 00:04:51,270 What does the dot mean? 100 00:04:51,270 --> 00:04:53,810 101 00:04:53,810 --> 00:04:57,240 >> AUDIENCE: Go to the node and assess the n value for it. 102 00:04:57,240 --> 00:04:58,370 >> JASON HIRSCHHORN: That's exactly right. 103 00:04:58,370 --> 00:05:03,300 Dot means access the n part of this new node. 104 00:05:03,300 --> 00:05:05,690 This next line does what? 105 00:05:05,690 --> 00:05:16,140 106 00:05:16,140 --> 00:05:17,050 Michael. 107 00:05:17,050 --> 00:05:21,910 >> AUDIENCE: It creates another node that will point to the new node. 108 00:05:21,910 --> 00:05:24,870 >> JASON HIRSCHHORN: So it doesn't create a new node. 109 00:05:24,870 --> 00:05:26,120 It creates a what? 110 00:05:26,120 --> 00:05:28,300 111 00:05:28,300 --> 00:05:29,300 >> AUDIENCE: A pointer. 112 00:05:29,300 --> 00:05:33,460 >> JASON HIRSCHHORN: A pointer to a node, as indicated by this node* here. 113 00:05:33,460 --> 00:05:34,800 So it creates a pointer to a node. 114 00:05:34,800 --> 00:05:37,490 And which node is it pointing to, Michael? 115 00:05:37,490 --> 00:05:38,440 >> AUDIENCE: New node? 116 00:05:38,440 --> 00:05:39,240 >> JASON HIRSCHHORN: New node. 117 00:05:39,240 --> 00:05:43,020 And it's pointing there because we've given it the address of new node. 118 00:05:43,020 --> 00:05:45,820 And now in this line we see two different ways of 119 00:05:45,820 --> 00:05:46,910 expressing the same thing. 120 00:05:46,910 --> 00:05:49,650 And I wanted to point out how these two things are the same. 121 00:05:49,650 --> 00:05:54,740 In the first line, we dereference the pointer. 122 00:05:54,740 --> 00:05:55,830 So we go to the node. 123 00:05:55,830 --> 00:05:56,830 That's what this star means. 124 00:05:56,830 --> 00:05:57,930 We've seen that before with pointers. 125 00:05:57,930 --> 00:05:59,280 Go to that node. 126 00:05:59,280 --> 00:06:00,370 That's in parentheses. 127 00:06:00,370 --> 00:06:04,610 And then access via the dot operator the n element of that node. 128 00:06:04,610 --> 00:06:08,430 >> So that's taking the syntax we saw right here and now 129 00:06:08,430 --> 00:06:09,670 using it with a pointer. 130 00:06:09,670 --> 00:06:13,730 Of course, it gets kind of busy if you're writing those parentheses-- 131 00:06:13,730 --> 00:06:14,940 that star and that dot. 132 00:06:14,940 --> 00:06:16,220 It gets a little busy. 133 00:06:16,220 --> 00:06:18,500 So we have some syntactic sugar. 134 00:06:18,500 --> 00:06:19,920 And this line right here-- 135 00:06:19,920 --> 00:06:21,170 ptr_node->n. 136 00:06:21,170 --> 00:06:25,400 137 00:06:25,400 --> 00:06:28,000 That does the same exact thing. 138 00:06:28,000 --> 00:06:30,840 So those two lines of code are equivalent and will do 139 00:06:30,840 --> 00:06:31,650 the exact same thing. 140 00:06:31,650 --> 00:06:34,210 >> But I wanted to point those out before we go any further so you understand 141 00:06:34,210 --> 00:06:39,000 that really this thing right here is just syntactic sugar for dereferencing 142 00:06:39,000 --> 00:06:44,200 the pointer and then going to the n part of that struct. 143 00:06:44,200 --> 00:06:45,525 Any questions about this slide? 144 00:06:45,525 --> 00:06:53,020 145 00:06:53,020 --> 00:06:54,390 OK. 146 00:06:54,390 --> 00:06:58,510 >> So we're going to go through a couple of operations that you can do on 147 00:06:58,510 --> 00:06:59,730 linked lists. 148 00:06:59,730 --> 00:07:05,770 A linked list, recall, is a series of nodes that point to one another. 149 00:07:05,770 --> 00:07:12,470 And we generally start with a pointer called head, generally, that points to 150 00:07:12,470 --> 00:07:14,040 the first thing in the list. 151 00:07:14,040 --> 00:07:18,900 So on the first line here, we have our original L first. 152 00:07:18,900 --> 00:07:21,370 So that thing you can think of-- this text right here you can think of as 153 00:07:21,370 --> 00:07:23,560 just the pointer we've stored somewhere that points 154 00:07:23,560 --> 00:07:24,670 to the first element. 155 00:07:24,670 --> 00:07:27,500 And in this linked list we have four nodes. 156 00:07:27,500 --> 00:07:29,530 Each node is a big box. 157 00:07:29,530 --> 00:07:33,430 The larger box inside the big box is the integer part. 158 00:07:33,430 --> 00:07:37,400 And then we have a pointer part. 159 00:07:37,400 --> 00:07:39,630 >> These boxes aren't drawn to scale because how big is 160 00:07:39,630 --> 00:07:42,320 an integer in bytes? 161 00:07:42,320 --> 00:07:43,290 How big now? 162 00:07:43,290 --> 00:07:43,710 Four. 163 00:07:43,710 --> 00:07:45,470 And how big's a pointer? 164 00:07:45,470 --> 00:07:45,940 Four. 165 00:07:45,940 --> 00:07:48,180 So really, if we were to draw this to scale both boxes 166 00:07:48,180 --> 00:07:49,690 would be the same size. 167 00:07:49,690 --> 00:07:52,870 In this case, we want to insert something into the linked list. 168 00:07:52,870 --> 00:07:57,190 So you can see down here we're inserting five We traverse through the 169 00:07:57,190 --> 00:08:01,310 linked list, find where five goes, and then insert it. 170 00:08:01,310 --> 00:08:03,560 >> Let's break that down and go a little bit more slowly. 171 00:08:03,560 --> 00:08:05,510 I'm going to point to the board. 172 00:08:05,510 --> 00:08:09,930 So we have our node five that we've created in mallocs. 173 00:08:09,930 --> 00:08:11,190 Why is everybody laughing? 174 00:08:11,190 --> 00:08:12,130 Just kidding. 175 00:08:12,130 --> 00:08:13,310 OK. 176 00:08:13,310 --> 00:08:14,820 So we've malloced five. 177 00:08:14,820 --> 00:08:16,310 We've created this node somewhere else. 178 00:08:16,310 --> 00:08:17,740 We have it ready to go. 179 00:08:17,740 --> 00:08:20,130 We start at the front of our list with two. 180 00:08:20,130 --> 00:08:22,380 And we want to insert in a sorted fashion. 181 00:08:22,380 --> 00:08:27,550 >> So if we see two and we want to put in five, what do we do when we see 182 00:08:27,550 --> 00:08:28,800 something less than us? 183 00:08:28,800 --> 00:08:31,850 184 00:08:31,850 --> 00:08:33,520 What? 185 00:08:33,520 --> 00:08:36,750 We want to insert five into this linked list, keeping it sorted. 186 00:08:36,750 --> 00:08:37,520 We see number two. 187 00:08:37,520 --> 00:08:38,769 So what do we do? 188 00:08:38,769 --> 00:08:39,179 Marcus? 189 00:08:39,179 --> 00:08:40,679 >> AUDIENCE: Call the pointer to the next node. 190 00:08:40,679 --> 00:08:42,530 >> JASON HIRSCHHORN: And why do we go to the next one? 191 00:08:42,530 --> 00:08:45,970 >> AUDIENCE: Because it's the next node in the list. 192 00:08:45,970 --> 00:08:48,310 And we only know that other location. 193 00:08:48,310 --> 00:08:50,410 >> JASON HIRSCHHORN: And five is greater than two, in particular. 194 00:08:50,410 --> 00:08:51,600 Because we want to keep it sorted. 195 00:08:51,600 --> 00:08:52,730 So five is greater than two. 196 00:08:52,730 --> 00:08:54,460 So we move on to the next one. 197 00:08:54,460 --> 00:08:55,240 And now we reach four. 198 00:08:55,240 --> 00:08:56,490 And what happens when we reach four? 199 00:08:56,490 --> 00:08:58,920 200 00:08:58,920 --> 00:09:00,310 >> Five is greater than four. 201 00:09:00,310 --> 00:09:01,460 So we keep going. 202 00:09:01,460 --> 00:09:03,110 And now we're at six. 203 00:09:03,110 --> 00:09:04,360 And what do we see at six? 204 00:09:04,360 --> 00:09:08,672 205 00:09:08,672 --> 00:09:09,608 Yes, Carlos? 206 00:09:09,608 --> 00:09:10,544 >> AUDIENCE: Six is greater than five. 207 00:09:10,544 --> 00:09:11,480 >> JASON HIRSCHHORN: Six is greater than five. 208 00:09:11,480 --> 00:09:13,660 So that's where we want to insert five. 209 00:09:13,660 --> 00:09:17,320 However, keep in mind that if we only have one pointer here-- 210 00:09:17,320 --> 00:09:19,840 this is our extra pointer that's traversing through the list. 211 00:09:19,840 --> 00:09:21,860 And we're pointing to six. 212 00:09:21,860 --> 00:09:25,010 We've lost track of what comes before six. 213 00:09:25,010 --> 00:09:29,130 So if we want to insert something into this list keeping it sorted, we 214 00:09:29,130 --> 00:09:31,630 probably need how many pointers? 215 00:09:31,630 --> 00:09:32,280 >> AUDIENCE: Two. 216 00:09:32,280 --> 00:09:32,920 >> JASON HIRSCHORN: Two. 217 00:09:32,920 --> 00:09:35,720 One to keep track of the current one and one to keep track of 218 00:09:35,720 --> 00:09:37,050 the previous one. 219 00:09:37,050 --> 00:09:38,450 This is only a singly linked list. 220 00:09:38,450 --> 00:09:39,670 It only goes one direction. 221 00:09:39,670 --> 00:09:43,220 If we had a doubly linked list, where everything was pointing to the thing 222 00:09:43,220 --> 00:09:46,240 after it and the thing before it, then we wouldn't need to do that. 223 00:09:46,240 --> 00:09:49,350 But in this case we don't want to lose track of what came before us in case 224 00:09:49,350 --> 00:09:53,350 we need to insert five somewhere in the middle. 225 00:09:53,350 --> 00:09:55,610 Say we were inserting nine. 226 00:09:55,610 --> 00:09:57,260 What would happen when we got to eight? 227 00:09:57,260 --> 00:10:01,860 228 00:10:01,860 --> 00:10:04,880 >> AUDIENCE: You'd have to get that null point. 229 00:10:04,880 --> 00:10:07,820 Instead of having null point you'd have to add an element and then have 230 00:10:07,820 --> 00:10:09,216 it point to nine. 231 00:10:09,216 --> 00:10:09,700 >> JASON HIRSCHORN: Exactly. 232 00:10:09,700 --> 00:10:10,600 So we get eight. 233 00:10:10,600 --> 00:10:13,140 We reach the end of the list because this is pointing to null. 234 00:10:13,140 --> 00:10:16,330 And now, instead of having it point to null we have it point to our new node. 235 00:10:16,330 --> 00:10:19,870 And we set the pointer in our new node to null. 236 00:10:19,870 --> 00:10:21,445 Does anybody have any questions about inserting? 237 00:10:21,445 --> 00:10:25,620 238 00:10:25,620 --> 00:10:28,100 What if I don't care about keeping the list sorted? 239 00:10:28,100 --> 00:10:31,701 240 00:10:31,701 --> 00:10:34,350 >> AUDIENCE: Stick it at the beginning or the end. 241 00:10:34,350 --> 00:10:35,510 >> JASON HIRSCHORN: Stick it at the beginning or the end. 242 00:10:35,510 --> 00:10:37,276 Which one should we do? 243 00:10:37,276 --> 00:10:38,770 Bobby? 244 00:10:38,770 --> 00:10:41,020 Why the end? 245 00:10:41,020 --> 00:10:43,250 >> AUDIENCE: Because the beginning is already filled. 246 00:10:43,250 --> 00:10:43,575 >> JASON HIRSCHORN: OK. 247 00:10:43,575 --> 00:10:44,360 The beginning is already filled. 248 00:10:44,360 --> 00:10:46,090 Who wants to argue against Bobby. 249 00:10:46,090 --> 00:10:47,290 Marcus. 250 00:10:47,290 --> 00:10:48,910 >> AUDIENCE: Well you probably want to stick it at the beginning because 251 00:10:48,910 --> 00:10:50,140 otherwise if you put it at the end you'd have to 252 00:10:50,140 --> 00:10:51,835 traverse the entire list. 253 00:10:51,835 --> 00:10:52,990 >> JASON HIRSCHORN: Exactly. 254 00:10:52,990 --> 00:10:57,970 So if we're thinking about runtime, the runtime of inserting at the end 255 00:10:57,970 --> 00:11:00,110 would be n, the size of this. 256 00:11:00,110 --> 00:11:03,080 What's the big O runtime of inserting at the beginning? 257 00:11:03,080 --> 00:11:04,170 Constant time. 258 00:11:04,170 --> 00:11:07,075 So if you don't care about keeping something sorted, much better to just 259 00:11:07,075 --> 00:11:08,420 insert at the beginning of this list. 260 00:11:08,420 --> 00:11:10,320 And that can be done in constant time. 261 00:11:10,320 --> 00:11:13,900 262 00:11:13,900 --> 00:11:14,690 >> OK. 263 00:11:14,690 --> 00:11:18,870 Next operation is find, which other-- we've phrased this as search. 264 00:11:18,870 --> 00:11:22,470 But we're going to look through the linked list for some object. 265 00:11:22,470 --> 00:11:26,000 You guys have seen code for search before in lecture. 266 00:11:26,000 --> 00:11:29,490 But we sort of just did it with insert, or at least inserting 267 00:11:29,490 --> 00:11:30,580 something sorted. 268 00:11:30,580 --> 00:11:36,350 You look through, going node by node, until you find the number that you're 269 00:11:36,350 --> 00:11:37,780 looking for. 270 00:11:37,780 --> 00:11:39,670 What happens if you reach the end of the list? 271 00:11:39,670 --> 00:11:43,020 Say I'm looking for nine and I reach the end of the list. 272 00:11:43,020 --> 00:11:44,270 What do we do? 273 00:11:44,270 --> 00:11:47,147 274 00:11:47,147 --> 00:11:48,110 >> AUDIENCE: Return false? 275 00:11:48,110 --> 00:11:48,690 >> JASON HIRSCHORN: Return false. 276 00:11:48,690 --> 00:11:49,960 We didn't find it. 277 00:11:49,960 --> 00:11:52,010 If you reach the end of the list and you didn't find the number you're 278 00:11:52,010 --> 00:11:54,170 looking for, it's not in there. 279 00:11:54,170 --> 00:11:55,420 Any questions about find? 280 00:11:55,420 --> 00:11:59,530 281 00:11:59,530 --> 00:12:04,615 If this was a sorted list, what would be different for our searching? 282 00:12:04,615 --> 00:12:07,370 283 00:12:07,370 --> 00:12:08,103 Yeah. 284 00:12:08,103 --> 00:12:10,600 >> AUDIENCE: It would find the first value that's greater than the one 285 00:12:10,600 --> 00:12:12,390 you're looking for and then return false. 286 00:12:12,390 --> 00:12:13,190 >> JASON HIRSCHORN: Exactly. 287 00:12:13,190 --> 00:12:17,310 So if it's a sorted list, if we get to something that's greater than what 288 00:12:17,310 --> 00:12:20,180 we're looking for, we don't need to keep going to the end of the list. 289 00:12:20,180 --> 00:12:24,060 We can at that point return false because we're not going to find it. 290 00:12:24,060 --> 00:12:27,340 The question is now, we've talked about keeping linked lists sorted, 291 00:12:27,340 --> 00:12:28,180 keeping them unsorted. 292 00:12:28,180 --> 00:12:30,050 That's going to be something you're probably going to have to think about 293 00:12:30,050 --> 00:12:34,240 when coding problem set five if you choose a hash table with separate 294 00:12:34,240 --> 00:12:36,360 chaining approach, which we'll talk about later. 295 00:12:36,360 --> 00:12:41,400 >> But is it worth it to keep the list sorted and then be able to maybe have 296 00:12:41,400 --> 00:12:42,310 quicker searches? 297 00:12:42,310 --> 00:12:47,220 Or is it better to quickly insert something in constant runtime but then 298 00:12:47,220 --> 00:12:48,430 have longer searching? 299 00:12:48,430 --> 00:12:52,250 That's a tradeoff right there that you get to decide what is more appropriate 300 00:12:52,250 --> 00:12:53,590 for your specific problem. 301 00:12:53,590 --> 00:12:56,680 And there's not necessarily one absolutely right answer. 302 00:12:56,680 --> 00:12:59,520 But it's certainly a decision you get to make, and probably good to defend 303 00:12:59,520 --> 00:13:05,270 that in, say, a comment or two why you chose one over the other. 304 00:13:05,270 --> 00:13:06,490 >> Finally, deleting. 305 00:13:06,490 --> 00:13:08,100 We've seen deleting. 306 00:13:08,100 --> 00:13:09,180 It's similar to searching. 307 00:13:09,180 --> 00:13:11,020 We look for the element. 308 00:13:11,020 --> 00:13:12,390 Say we're trying to delete six. 309 00:13:12,390 --> 00:13:14,450 So we find six right here. 310 00:13:14,450 --> 00:13:18,860 The thing that we have to make sure we do is that whatever is pointing to 311 00:13:18,860 --> 00:13:21,220 six-- as we see in step two down here-- 312 00:13:21,220 --> 00:13:26,500 whatever's pointing to six needs to skip six now and be changed to 313 00:13:26,500 --> 00:13:28,160 whatever six is pointing to. 314 00:13:28,160 --> 00:13:31,410 We don't want to ever orphan the rest of our list by forgetting to set that 315 00:13:31,410 --> 00:13:32,960 previous pointer. 316 00:13:32,960 --> 00:13:35,960 And then sometimes, depending on the program, they'll just 317 00:13:35,960 --> 00:13:37,380 delete this node entirely. 318 00:13:37,380 --> 00:13:40,135 Sometimes you'll want to return the value that's in this node. 319 00:13:40,135 --> 00:13:42,490 So that's how deleting works. 320 00:13:42,490 --> 00:13:44,610 Any questions on delete? 321 00:13:44,610 --> 00:13:51,280 322 00:13:51,280 --> 00:13:53,850 >> AUDIENCE: So if you're going to delete it, would you just use free because 323 00:13:53,850 --> 00:13:55,655 presumably it was malloced? 324 00:13:55,655 --> 00:13:57,976 >> JASON HIRSCHORN: If you want to free something that's exactly right and you 325 00:13:57,976 --> 00:13:58,540 malloced it. 326 00:13:58,540 --> 00:14:00,410 Say we wanted to return this value. 327 00:14:00,410 --> 00:14:04,010 We might return six and then free this node and call free on it. 328 00:14:04,010 --> 00:14:06,180 Or we'd probably call free first and then return six. 329 00:14:06,180 --> 00:14:11,210 330 00:14:11,210 --> 00:14:11,580 >> OK. 331 00:14:11,580 --> 00:14:14,010 So let's move on to practice coding. 332 00:14:14,010 --> 00:14:16,090 We're going to code three functions. 333 00:14:16,090 --> 00:14:18,260 The first one is called insert_node. 334 00:14:18,260 --> 00:14:22,170 So you have code that I emailed you, and if you're watching this later on 335 00:14:22,170 --> 00:14:28,020 you can access the code in linked.c on the CS50 website. 336 00:14:28,020 --> 00:14:30,880 But in linked.c, there's some skeleton code that's already 337 00:14:30,880 --> 00:14:32,280 been written for you. 338 00:14:32,280 --> 00:14:34,560 And then there's a couple functions you need to write. 339 00:14:34,560 --> 00:14:36,380 >> First we're going to write insert_node. 340 00:14:36,380 --> 00:14:39,800 And what insert_node does is inserts an integer. 341 00:14:39,800 --> 00:14:42,440 And you're giving the integer into a linked list. 342 00:14:42,440 --> 00:14:45,470 And in particular, you need to keep the list sorted 343 00:14:45,470 --> 00:14:47,650 from smallest to largest. 344 00:14:47,650 --> 00:14:51,360 Also, you don't want to insert any duplicates. 345 00:14:51,360 --> 00:14:54,600 Finally, as you can see insert_node returns a bool. 346 00:14:54,600 --> 00:14:57,140 So you're supposed to let the user know whether or not the insert was 347 00:14:57,140 --> 00:15:00,800 successful by returning true or false. 348 00:15:00,800 --> 00:15:02,580 At the end of this program-- 349 00:15:02,580 --> 00:15:05,750 and for this stage you don't need to worry about freeing anything. 350 00:15:05,750 --> 00:15:11,790 So all you're doing is taking an integer and inserting it into a list. 351 00:15:11,790 --> 00:15:13,890 >> That is what I'm asking you to do now. 352 00:15:13,890 --> 00:15:17,620 Again, in the linked.c, which you all have, is the skeleton code. 353 00:15:17,620 --> 00:15:20,980 And you should see towards the bottom the sample function declaration. 354 00:15:20,980 --> 00:15:27,390 However, before going into coding it in C, I highly encourage you to go 355 00:15:27,390 --> 00:15:29,330 through the steps we've been practicing each week. 356 00:15:29,330 --> 00:15:31,100 We've already gone through a picture of this. 357 00:15:31,100 --> 00:15:33,380 So you should have some understanding of how this works. 358 00:15:33,380 --> 00:15:36,590 But I would encourage you to write some pseudocode before diving in. 359 00:15:36,590 --> 00:15:38,640 And we're going to go over pseudocode as a group. 360 00:15:38,640 --> 00:15:41,470 And then once you've written your pseudocode, and once we've written our 361 00:15:41,470 --> 00:15:45,850 pseudocode as a group, you can go into coding it in C. 362 00:15:45,850 --> 00:15:49,980 >> As a heads up, the insert_node function is probably the trickiest of 363 00:15:49,980 --> 00:15:53,550 the three we're going to write because I added some additional constraints to 364 00:15:53,550 --> 00:15:57,190 your programming, in particular that you're not going to insert any 365 00:15:57,190 --> 00:15:59,880 duplicates and that the list should remain sorted. 366 00:15:59,880 --> 00:16:02,660 So this is a non-trivial program that you need to code. 367 00:16:02,660 --> 00:16:06,470 And why don't you take five to seven minutes just to get working on the 368 00:16:06,470 --> 00:16:07,640 pseudocode and the code. 369 00:16:07,640 --> 00:16:09,460 And then we will start going as a group. 370 00:16:09,460 --> 00:16:11,680 Again, if you have any questions just raise your hand and I'll come around. 371 00:16:11,680 --> 00:16:15,258 372 00:16:15,258 --> 00:16:16,508 . 373 00:16:16,508 --> 00:18:28,370 374 00:18:28,370 --> 00:18:30,120 >> We also generally do these-- 375 00:18:30,120 --> 00:18:32,070 or I don't explicitly say you can work with people. 376 00:18:32,070 --> 00:18:36,500 But obviously, I highly encourage you, if you have questions, to ask the 377 00:18:36,500 --> 00:18:39,840 neighbor sitting next to you or even work with somebody 378 00:18:39,840 --> 00:18:40,510 else if you want to. 379 00:18:40,510 --> 00:18:42,600 This does not have to be an individual silent activity. 380 00:18:42,600 --> 00:20:11,770 381 00:20:11,770 --> 00:20:16,330 >> Let's start with writing some pseudocode on the board. 382 00:20:16,330 --> 00:20:19,395 Who can give me the first line of pseudocode for this program? 383 00:20:19,395 --> 00:20:22,240 384 00:20:22,240 --> 00:20:23,640 For this function, rather-- insert_node. 385 00:20:23,640 --> 00:20:29,960 386 00:20:29,960 --> 00:20:31,830 Alden? 387 00:20:31,830 --> 00:20:36,560 >> AUDIENCE: So the first thing I did was create a new pointer to the node and I 388 00:20:36,560 --> 00:20:41,320 initialized it pointing to the same thing that list is pointing to. 389 00:20:41,320 --> 00:20:41,550 >> JASON HIRSCHORN: OK. 390 00:20:41,550 --> 00:20:45,190 So you're creating a new pointer to the list, not to the node. 391 00:20:45,190 --> 00:20:45,420 >> AUDIENCE: Right. 392 00:20:45,420 --> 00:20:46,150 Yeah. 393 00:20:46,150 --> 00:20:46,540 >> JASON HIRSCHORN: OK. 394 00:20:46,540 --> 00:20:48,221 And then what do we want to do? 395 00:20:48,221 --> 00:20:49,163 What's after that? 396 00:20:49,163 --> 00:20:50,105 What about the node? 397 00:20:50,105 --> 00:20:51,050 We don't have a node. 398 00:20:51,050 --> 00:20:52,300 We just have a value. 399 00:20:52,300 --> 00:20:55,918 400 00:20:55,918 --> 00:20:58,890 If we want to insert a node, what do we need to do first before we can even 401 00:20:58,890 --> 00:20:59,980 think about inserting it? 402 00:20:59,980 --> 00:21:00,820 >> AUDIENCE: Oh, sorry. 403 00:21:00,820 --> 00:21:02,160 we need to malloc space for a node. 404 00:21:02,160 --> 00:21:02,455 >> JASON HIRSCHORN: Excellent. 405 00:21:02,455 --> 00:21:03,210 Let's do-- 406 00:21:03,210 --> 00:21:04,628 OK. 407 00:21:04,628 --> 00:21:06,065 Can't reach that high. 408 00:21:06,065 --> 00:21:08,939 409 00:21:08,939 --> 00:21:09,897 OK. 410 00:21:09,897 --> 00:21:13,236 We're going to go down, and then we're using two columns. 411 00:21:13,236 --> 00:21:13,732 I can't go that-- 412 00:21:13,732 --> 00:21:14,982 OK. 413 00:21:14,982 --> 00:21:23,660 414 00:21:23,660 --> 00:21:25,130 Create a new node. 415 00:21:25,130 --> 00:21:29,380 You can create another pointer to list or you can just use list as it exists. 416 00:21:29,380 --> 00:21:30,720 You don't really need to do that. 417 00:21:30,720 --> 00:21:31,750 >> So we create a new node. 418 00:21:31,750 --> 00:21:32,010 Great. 419 00:21:32,010 --> 00:21:32,840 That's what we do first. 420 00:21:32,840 --> 00:21:34,870 What's next? 421 00:21:34,870 --> 00:21:35,080 >> AUDIENCE: Wait. 422 00:21:35,080 --> 00:21:38,330 Should we create a new node now or should we wait to make sure that 423 00:21:38,330 --> 00:21:42,260 there's no duplicates of the node on the list before we create it? 424 00:21:42,260 --> 00:21:43,100 >> JASON HIRSCHORN: Good question. 425 00:21:43,100 --> 00:21:47,770 Let's hold that for later because the majority of the time we'll be creating 426 00:21:47,770 --> 00:21:48,220 a new node. 427 00:21:48,220 --> 00:21:49,110 So we'll keep that here. 428 00:21:49,110 --> 00:21:51,006 But that's a good question. 429 00:21:51,006 --> 00:21:53,250 If we create it and we find a duplicate, what should 430 00:21:53,250 --> 00:21:54,490 we do before returning? 431 00:21:54,490 --> 00:21:55,190 >> AUDIENCE: Free it. 432 00:21:55,190 --> 00:21:55,470 >> JASON HIRSCHORN: Yeah. 433 00:21:55,470 --> 00:21:56,500 Probably free it. 434 00:21:56,500 --> 00:21:56,760 OK. 435 00:21:56,760 --> 00:21:59,850 What do we do after we create a new node? 436 00:21:59,850 --> 00:22:02,260 Annie? 437 00:22:02,260 --> 00:22:04,780 >> AUDIENCE: We put the number in the node? 438 00:22:04,780 --> 00:22:05,140 >> JASON HIRSCHORN: Exactly. 439 00:22:05,140 --> 00:22:07,190 We put the number-- we malloc space. 440 00:22:07,190 --> 00:22:08,160 I'm going to leave that all as one line. 441 00:22:08,160 --> 00:22:08,720 But you're right. 442 00:22:08,720 --> 00:22:10,305 We malloc space, and then we put the number in. 443 00:22:10,305 --> 00:22:12,585 We can even set the pointer part of it to null. 444 00:22:12,585 --> 00:22:13,720 That's exactly right. 445 00:22:13,720 --> 00:22:17,400 And then what about after that? 446 00:22:17,400 --> 00:22:18,490 We drew this picture on the board. 447 00:22:18,490 --> 00:22:21,190 So what do we do? 448 00:22:21,190 --> 00:22:22,680 >> AUDIENCE: We go through the list. 449 00:22:22,680 --> 00:22:23,930 >> JASON HIRSCHORN: Go through the list. 450 00:22:23,930 --> 00:22:30,620 451 00:22:30,620 --> 00:22:31,100 OK. 452 00:22:31,100 --> 00:22:34,280 And what do we check for at each node. 453 00:22:34,280 --> 00:22:35,955 Kurt, what do we check for at each node? 454 00:22:35,955 --> 00:22:41,640 >> AUDIENCE: See whether the n value of that node is greater than the n value 455 00:22:41,640 --> 00:22:43,070 of our node. 456 00:22:43,070 --> 00:22:43,340 >> JASON HIRSCHORN: OK. 457 00:22:43,340 --> 00:22:44,280 I'm going to do-- 458 00:22:44,280 --> 00:22:45,855 yeah, OK. 459 00:22:45,855 --> 00:22:48,160 So it's n-- 460 00:22:48,160 --> 00:22:59,040 I'm going to say if value is greater than this node, then what do we do? 461 00:22:59,040 --> 00:23:07,290 >> AUDIENCE: Well, then we insert the thing right before that. 462 00:23:07,290 --> 00:23:07,970 >> JASON HIRSCHORN: OK. 463 00:23:07,970 --> 00:23:09,410 So if it's greater than this, then we want to insert. 464 00:23:09,410 --> 00:23:14,010 But we want to insert it right before because we also would need to be 465 00:23:14,010 --> 00:23:16,070 keeping track, then, of what was before. 466 00:23:16,070 --> 00:23:22,690 So insert before. 467 00:23:22,690 --> 00:23:25,120 So we probably missed something earlier on. 468 00:23:25,120 --> 00:23:27,770 We probably need to be keeping track of what's going on. 469 00:23:27,770 --> 00:23:28,460 But we'll get back there. 470 00:23:28,460 --> 00:23:30,160 So what value is less than? 471 00:23:30,160 --> 00:23:38,030 472 00:23:38,030 --> 00:23:39,710 Kurt, what do we do if value is less than? 473 00:23:39,710 --> 00:23:43,000 >> AUDIENCE: Then you just keep going unless it's the last one. 474 00:23:43,000 --> 00:23:43,550 >> JASON HIRSCHORN: I like that. 475 00:23:43,550 --> 00:23:44,800 So go to the next node. 476 00:23:44,800 --> 00:23:47,410 477 00:23:47,410 --> 00:23:48,930 Unless it's the last one-- 478 00:23:48,930 --> 00:23:51,100 we're probably checking for that in the terms of a condition. 479 00:23:51,100 --> 00:23:54,870 But yeah, next node. 480 00:23:54,870 --> 00:23:58,680 And that's getting too low, so we'll move over here. 481 00:23:58,680 --> 00:24:02,030 But if-- 482 00:24:02,030 --> 00:24:03,280 can everybody see this? 483 00:24:03,280 --> 00:24:07,230 484 00:24:07,230 --> 00:24:11,610 If we're equal what do we do? 485 00:24:11,610 --> 00:24:15,740 If the value we're trying to insert is equal to this node's value? 486 00:24:15,740 --> 00:24:16,320 Yeah? 487 00:24:16,320 --> 00:24:18,400 >> AUDIENCE: [INAUDIBLE]. 488 00:24:18,400 --> 00:24:18,850 >> JASON HIRSCHORN: Yeah. 489 00:24:18,850 --> 00:24:19,290 Given this-- 490 00:24:19,290 --> 00:24:20,090 Marcus is right. 491 00:24:20,090 --> 00:24:21,330 We could have maybe done something different. 492 00:24:21,330 --> 00:24:25,360 But given that we've created it, here we should free and then return. 493 00:24:25,360 --> 00:24:26,774 Oh boy. 494 00:24:26,774 --> 00:24:30,080 Is that better? 495 00:24:30,080 --> 00:24:31,850 How's that? 496 00:24:31,850 --> 00:24:33,100 OK. 497 00:24:33,100 --> 00:24:35,360 498 00:24:35,360 --> 00:24:37,640 Free and then what do we return, [INAUDIBLE]? 499 00:24:37,640 --> 00:24:41,330 500 00:24:41,330 --> 00:24:44,110 OK. 501 00:24:44,110 --> 00:24:45,360 Are we missing anything? 502 00:24:45,360 --> 00:24:53,500 503 00:24:53,500 --> 00:24:59,650 So where are we keeping track of the prior node? 504 00:24:59,650 --> 00:25:02,370 >> AUDIENCE: I think it would go after create a new node. 505 00:25:02,370 --> 00:25:02,600 >> JASON HIRSCHORN: OK. 506 00:25:02,600 --> 00:25:03,940 So at the beginning we'll probably-- 507 00:25:03,940 --> 00:25:07,175 yeah, we can create a pointer to a new node, like a previous node pointer and 508 00:25:07,175 --> 00:25:09,600 a current node pointer. 509 00:25:09,600 --> 00:25:12,640 So let's insert that here. 510 00:25:12,640 --> 00:25:15,610 511 00:25:15,610 --> 00:25:26,900 Create current and previous pointers to the nodes. 512 00:25:26,900 --> 00:25:28,955 But when do we adjust those pointers? 513 00:25:28,955 --> 00:25:30,205 Where do we do that in the code? 514 00:25:30,205 --> 00:25:33,830 515 00:25:33,830 --> 00:25:34,160 Jeff? 516 00:25:34,160 --> 00:25:35,170 >> AUDIENCE: -- value conditions? 517 00:25:35,170 --> 00:25:36,420 >> JASON HIRSCHORN: Which one in particular? 518 00:25:36,420 --> 00:25:39,862 519 00:25:39,862 --> 00:25:40,720 >> AUDIENCE: I'm just confused. 520 00:25:40,720 --> 00:25:44,200 If value is greater than this node, doesn't that mean that you want to go 521 00:25:44,200 --> 00:25:45,320 to the next node? 522 00:25:45,320 --> 00:25:49,515 >> JASON HIRSCHHORN: So if our value is greater than the value of this node. 523 00:25:49,515 --> 00:25:52,130 >> AUDIENCE: Yeah, then you'd want to go further down the line, right? 524 00:25:52,130 --> 00:25:52,590 >> JASON HIRSCHHORN: Right. 525 00:25:52,590 --> 00:25:53,840 So we don't insert it here. 526 00:25:53,840 --> 00:25:58,430 527 00:25:58,430 --> 00:26:03,240 If value is less than this node, then we go to the next node-- or then we 528 00:26:03,240 --> 00:26:03,835 insert before. 529 00:26:03,835 --> 00:26:05,966 >> AUDIENCE: Wait, which is this node and which is value? 530 00:26:05,966 --> 00:26:08,510 531 00:26:08,510 --> 00:26:09,280 >> JASON HIRSCHHORN: Good question. 532 00:26:09,280 --> 00:26:13,260 Value per this function definition is what we're given. 533 00:26:13,260 --> 00:26:16,910 So value is the number we're given. 534 00:26:16,910 --> 00:26:21,120 So if the value is less than this node, we need time to insert. 535 00:26:21,120 --> 00:26:24,575 If value is greater than this node, we go to the next node. 536 00:26:24,575 --> 00:26:26,790 And back to the original question, though, where-- 537 00:26:26,790 --> 00:26:29,060 >> AUDIENCE: If value is greater than this node. 538 00:26:29,060 --> 00:26:30,310 >> JASON HIRSCHHORN: And so what do we do here? 539 00:26:30,310 --> 00:26:36,790 540 00:26:36,790 --> 00:26:38,160 Sweet. 541 00:26:38,160 --> 00:26:38,860 That is correct. 542 00:26:38,860 --> 00:26:41,370 I'm just going to write update pointers. 543 00:26:41,370 --> 00:26:44,010 But yes, with the current one you would update it to 544 00:26:44,010 --> 00:26:46,080 point to the next one. 545 00:26:46,080 --> 00:26:47,330 Anything else we're missing? 546 00:26:47,330 --> 00:26:52,710 547 00:26:52,710 --> 00:26:54,940 So I'm going to type this code into gedit. 548 00:26:54,940 --> 00:26:58,375 And while I do this, you can have a couple more minutes to work on coding 549 00:26:58,375 --> 00:28:19,240 this in C. 550 00:28:19,240 --> 00:28:20,940 >> So I have input the pseudocode. 551 00:28:20,940 --> 00:28:22,940 A quick note before we get started. 552 00:28:22,940 --> 00:28:25,560 We may not be able to completely finish this in all 553 00:28:25,560 --> 00:28:27,300 three of these functions. 554 00:28:27,300 --> 00:28:30,630 There is correct solutions to them that I will email out to you guys 555 00:28:30,630 --> 00:28:33,730 after section, and it will be posted on CS50.net. 556 00:28:33,730 --> 00:28:35,640 So I don't encourage you to go look at the sections. 557 00:28:35,640 --> 00:28:40,550 I encourage you to try these on your own, and then use the the practice 558 00:28:40,550 --> 00:28:41,760 problems to check your answers. 559 00:28:41,760 --> 00:28:47,070 These have all been designed to closely relate to and adhere to what 560 00:28:47,070 --> 00:28:48,400 you have to do on the problem set. 561 00:28:48,400 --> 00:28:53,820 So I do encourage you to practice this on your own and then use the code to 562 00:28:53,820 --> 00:28:54,660 check your answers. 563 00:28:54,660 --> 00:28:57,060 Because I do want to move on to hash tables at some point in the section. 564 00:28:57,060 --> 00:28:58,150 So we might not get through it all. 565 00:28:58,150 --> 00:28:59,960 But we'll do as much we can now. 566 00:28:59,960 --> 00:29:00,370 >> OK. 567 00:29:00,370 --> 00:29:01,960 Let us begin. 568 00:29:01,960 --> 00:29:04,770 Asam, how do we create a new node? 569 00:29:04,770 --> 00:29:06,810 >> AUDIENCE: You do struct*. 570 00:29:06,810 --> 00:29:09,640 >> JASON HIRSCHHORN: So we have that up here. 571 00:29:09,640 --> 00:29:10,040 Oh, sorry. 572 00:29:10,040 --> 00:29:13,530 You were saying struct*. 573 00:29:13,530 --> 00:29:17,260 >> AUDIENCE: And then [? kind ?] node or c node. 574 00:29:17,260 --> 00:29:17,780 >> JASON HIRSCHHORN: OK. 575 00:29:17,780 --> 00:29:19,740 I'm going to call it new_node so we can stay consistent. 576 00:29:19,740 --> 00:29:22,646 577 00:29:22,646 --> 00:29:33,180 >> AUDIENCE: And you want to set that to head, the first node. 578 00:29:33,180 --> 00:29:33,580 >> JASON HIRSCHHORN: OK. 579 00:29:33,580 --> 00:29:37,290 So now this pointing to-- so this hasn't created a new node yet. 580 00:29:37,290 --> 00:29:41,380 This is just pointing to the first node in the list. 581 00:29:41,380 --> 00:29:42,630 How do I create a new node? 582 00:29:42,630 --> 00:29:45,490 583 00:29:45,490 --> 00:29:48,070 If I need space to create a new node. 584 00:29:48,070 --> 00:29:49,230 Malloc. 585 00:29:49,230 --> 00:29:51,710 And how big? 586 00:29:51,710 --> 00:30:00,390 >> AUDIENCE: The size of the struct. 587 00:30:00,390 --> 00:30:01,150 >> JASON HIRSCHHORN: The size of the struct. 588 00:30:01,150 --> 00:30:02,400 And what's the struct called? 589 00:30:02,400 --> 00:30:09,670 590 00:30:09,670 --> 00:30:09,840 >> AUDIENCE: Node? 591 00:30:09,840 --> 00:30:11,640 >> JASON HIRSCHHORN: Node. 592 00:30:11,640 --> 00:30:17,640 So malloc(sizeof(node)); gives us space. 593 00:30:17,640 --> 00:30:19,740 And is this line-- 594 00:30:19,740 --> 00:30:21,740 one thing is incorrect on this line. 595 00:30:21,740 --> 00:30:24,430 Is new_node a pointer to a struct? 596 00:30:24,430 --> 00:30:25,650 That's a generic name. 597 00:30:25,650 --> 00:30:26,520 What is it-- 598 00:30:26,520 --> 00:30:27,450 node, exactly. 599 00:30:27,450 --> 00:30:29,340 It's a node*. 600 00:30:29,340 --> 00:30:33,010 And what do we do right after we malloc something, Asan? 601 00:30:33,010 --> 00:30:34,476 What's the first thing we do ? 602 00:30:34,476 --> 00:30:38,850 603 00:30:38,850 --> 00:30:40,320 What if it doesn't work? 604 00:30:40,320 --> 00:30:42,430 >> AUDIENCE: Oh, check if it points to the node? 605 00:30:42,430 --> 00:30:43,310 >> JASON HIRSCHHORN: Exactly. 606 00:30:43,310 --> 00:30:46,750 So if you new_node equals equals null, what do we do? 607 00:30:46,750 --> 00:30:51,650 608 00:30:51,650 --> 00:30:54,820 This returns a bool, this function. 609 00:30:54,820 --> 00:30:57,760 Exactly. 610 00:30:57,760 --> 00:30:58,450 Looks good. 611 00:30:58,450 --> 00:30:59,680 Anything to add there? 612 00:30:59,680 --> 00:31:00,670 We'll add things at the end. 613 00:31:00,670 --> 00:31:03,160 But that so far looks good. 614 00:31:03,160 --> 00:31:06,170 Create current and previous pointers. 615 00:31:06,170 --> 00:31:08,650 Michael, how do I do this? 616 00:31:08,650 --> 00:31:12,810 >> AUDIENCE: You would have to do a node*. 617 00:31:12,810 --> 00:31:21,800 618 00:31:21,800 --> 00:31:25,502 You'd have to make one not for new_node but for the 619 00:31:25,502 --> 00:31:26,905 nodes we already have. 620 00:31:26,905 --> 00:31:27,230 >> JASON HIRSCHHORN: OK. 621 00:31:27,230 --> 00:31:29,255 So the current node we're on. 622 00:31:29,255 --> 00:31:30,505 I'll call that curr. 623 00:31:30,505 --> 00:31:39,650 624 00:31:39,650 --> 00:31:39,770 All right. 625 00:31:39,770 --> 00:31:41,620 We've decided we want to keep two because we need to know 626 00:31:41,620 --> 00:31:42,870 what's before it. 627 00:31:42,870 --> 00:31:45,770 628 00:31:45,770 --> 00:31:47,020 What do they get initialized to? 629 00:31:47,020 --> 00:31:49,874 630 00:31:49,874 --> 00:31:54,180 >> AUDIENCE: Their value in our list. 631 00:31:54,180 --> 00:31:58,090 >> JASON HIRSCHHORN: So what is the first thing on our list? 632 00:31:58,090 --> 00:32:04,050 Or how do we know where the beginning of our list is? 633 00:32:04,050 --> 00:32:08,015 >> AUDIENCE: Isn't it passed into the function? 634 00:32:08,015 --> 00:32:08,466 >> JASON HIRSCHHORN: Right. 635 00:32:08,466 --> 00:32:09,716 It was passed in right here. 636 00:32:09,716 --> 00:32:15,910 637 00:32:15,910 --> 00:32:18,980 So if it's passed into the function, the start of the list, what should we 638 00:32:18,980 --> 00:32:21,270 set current equal to? 639 00:32:21,270 --> 00:32:22,110 >> AUDIENCE: List. 640 00:32:22,110 --> 00:32:22,900 >> JASON HIRSCHHORN: List. 641 00:32:22,900 --> 00:32:24,090 That's exactly right. 642 00:32:24,090 --> 00:32:26,290 Now it has the address of the start of our list. 643 00:32:26,290 --> 00:32:28,450 And what about previous? 644 00:32:28,450 --> 00:32:31,920 >> AUDIENCE: List minus one? 645 00:32:31,920 --> 00:32:32,690 >> JASON HIRSCHHORN: There's nothing before it. 646 00:32:32,690 --> 00:32:34,580 So what can we do to signify nothing? 647 00:32:34,580 --> 00:32:35,050 >> AUDIENCE: Null. 648 00:32:35,050 --> 00:32:35,450 >> JASON HIRSCHHORN: Yeah. 649 00:32:35,450 --> 00:32:37,950 That sounds like a good idea. 650 00:32:37,950 --> 00:32:38,360 Perfect. 651 00:32:38,360 --> 00:32:39,630 Thank you. 652 00:32:39,630 --> 00:32:42,850 Go through the list. 653 00:32:42,850 --> 00:32:45,490 Constantine, how long are we going to go through the list? 654 00:32:45,490 --> 00:32:49,010 >> AUDIENCE: Until We reach null. 655 00:32:49,010 --> 00:32:49,390 >> JASON HIRSCHHORN: OK. 656 00:32:49,390 --> 00:32:50,430 So if, while, for loop. 657 00:32:50,430 --> 00:32:52,200 What are we doing? 658 00:32:52,200 --> 00:32:53,320 >> AUDIENCE: Maybe a for loop? 659 00:32:53,320 --> 00:32:53,910 >> JASON HIRSCHHORN: Let's do a for loop. 660 00:32:53,910 --> 00:32:55,870 OK. 661 00:32:55,870 --> 00:33:02,465 >> AUDIENCE: And we say for-- 662 00:33:02,465 --> 00:33:09,764 663 00:33:09,764 --> 00:33:13,390 until the current pointer is not equal to null. 664 00:33:13,390 --> 00:33:19,160 >> JASON HIRSCHHORN: So if we know the condition, how can we write a loop 665 00:33:19,160 --> 00:33:21,740 based off that condition. 666 00:33:21,740 --> 00:33:24,380 What kind of a loop should we use? 667 00:33:24,380 --> 00:33:25,260 >> AUDIENCE: While. 668 00:33:25,260 --> 00:33:25,590 >> JASON HIRSCHHORN: Yeah. 669 00:33:25,590 --> 00:33:27,130 That makes more sense based off of what you said. 670 00:33:27,130 --> 00:33:29,430 If we just want to go into we it would just know that thing, it would make 671 00:33:29,430 --> 00:33:31,680 sense to do a while loop. 672 00:33:31,680 --> 00:33:39,880 While current does not equal null, if value is less than this node. 673 00:33:39,880 --> 00:33:41,650 Akshar, give me this line. 674 00:33:41,650 --> 00:33:48,810 675 00:33:48,810 --> 00:33:56,955 >> AUDIENCE: If current->n n less than value. 676 00:33:56,955 --> 00:34:00,170 677 00:34:00,170 --> 00:34:03,260 Or reverse that. 678 00:34:03,260 --> 00:34:06,140 Switch that bracket. 679 00:34:06,140 --> 00:34:06,620 >> JASON HIRSCHHORN: Sorry. 680 00:34:06,620 --> 00:34:08,760 >> AUDIENCE: Change the bracket. 681 00:34:08,760 --> 00:34:10,914 >> JASON HIRSCHHORN: So if it's greater than value. 682 00:34:10,914 --> 00:34:18,719 683 00:34:18,719 --> 00:34:22,120 Because that's confusing with the comment above, I'm going to do that. 684 00:34:22,120 --> 00:34:22,480 But yes. 685 00:34:22,480 --> 00:34:25,125 If our value is less than this node, what do we do? 686 00:34:25,125 --> 00:34:25,540 Oh. 687 00:34:25,540 --> 00:34:26,710 I have it right here. 688 00:34:26,710 --> 00:34:27,960 Insert before. 689 00:34:27,960 --> 00:34:32,080 690 00:34:32,080 --> 00:34:32,370 OK. 691 00:34:32,370 --> 00:34:33,933 How do we do that? 692 00:34:33,933 --> 00:34:34,900 >> AUDIENCE: Is it still me? 693 00:34:34,900 --> 00:34:36,150 >> JASON HIRSCHHORN: Yeah. 694 00:34:36,150 --> 00:34:38,520 695 00:34:38,520 --> 00:34:39,770 >> AUDIENCE: You-- 696 00:34:39,770 --> 00:34:42,909 697 00:34:42,909 --> 00:34:44,159 new_node->next. 698 00:34:44,159 --> 00:34:46,770 699 00:34:46,770 --> 00:34:50,163 >> JASON HIRSCHHORN: So what's that going to equal? 700 00:34:50,163 --> 00:34:52,070 >> AUDIENCE: It's going to equal current. 701 00:34:52,070 --> 00:34:53,889 >> JASON HIRSCHHORN: Exactly. 702 00:34:53,889 --> 00:34:55,730 And so the other-- 703 00:34:55,730 --> 00:34:56,730 what else do we need to update? 704 00:34:56,730 --> 00:34:59,982 >> AUDIENCE: Check if past equals null. 705 00:34:59,982 --> 00:35:01,870 >> JASON HIRSCHHORN: If prev-- 706 00:35:01,870 --> 00:35:03,730 so if prev equals null. 707 00:35:03,730 --> 00:35:05,990 >> AUDIENCE: That means it's going to become the head. 708 00:35:05,990 --> 00:35:06,780 >> JASON HIRSCHHORN: That means it's become the head. 709 00:35:06,780 --> 00:35:07,620 So then what do we do? 710 00:35:07,620 --> 00:35:12,510 >> AUDIENCE: We do head equals new_node. 711 00:35:12,510 --> 00:35:16,690 >> JASON HIRSCHHORN: Head equals new_node. 712 00:35:16,690 --> 00:35:20,540 And why head here, not list? 713 00:35:20,540 --> 00:35:24,940 >> AUDIENCE: Because head is a global variable, which is the starting place. 714 00:35:24,940 --> 00:35:26,190 >> JASON HIRSCHHORN: Sweet. 715 00:35:26,190 --> 00:35:33,750 716 00:35:33,750 --> 00:35:34,170 OK. 717 00:35:34,170 --> 00:35:36,150 And-- 718 00:35:36,150 --> 00:35:53,796 >> AUDIENCE: Then you do else prev-> next equals new_node. 719 00:35:53,796 --> 00:35:55,080 And then you return true. 720 00:35:55,080 --> 00:35:59,560 721 00:35:59,560 --> 00:36:02,700 >> JASON HIRSCHHORN: Where do we set new_node end? 722 00:36:02,700 --> 00:36:04,850 >> AUDIENCE: I would-- 723 00:36:04,850 --> 00:36:06,180 I set that at the start. 724 00:36:06,180 --> 00:36:07,430 >> JASON HIRSCHHORN: So what line? 725 00:36:07,430 --> 00:36:10,000 726 00:36:10,000 --> 00:36:12,598 >> AUDIENCE: After the if statement checking if it's known. 727 00:36:12,598 --> 00:36:13,057 >> JASON HIRSCHHORN: Right here? 728 00:36:13,057 --> 00:36:18,335 >> AUDIENCE: I'd do new_node->n equals value. 729 00:36:18,335 --> 00:36:19,585 >> JASON HIRSCHHORN: Sounds good. 730 00:36:19,585 --> 00:36:21,740 731 00:36:21,740 --> 00:36:25,090 Probably it makes sense-- we don't need to know what list we're on 732 00:36:25,090 --> 00:36:26,280 because we're only dealing with one list. 733 00:36:26,280 --> 00:36:29,560 So a better function declaration for this is just to get rid of this 734 00:36:29,560 --> 00:36:34,360 entirely and just insert a value into head. 735 00:36:34,360 --> 00:36:35,930 We don't even need to know what list we're in. 736 00:36:35,930 --> 00:36:39,140 But I will keep it for now and then change it upon updating 737 00:36:39,140 --> 00:36:42,590 the slides and code. 738 00:36:42,590 --> 00:36:44,980 So that looks good for now. 739 00:36:44,980 --> 00:36:46,560 If value-- who can do this line? 740 00:36:46,560 --> 00:36:47,810 If-- 741 00:36:47,810 --> 00:36:52,240 742 00:36:52,240 --> 00:36:53,840 what do we do here, Noah. 743 00:36:53,840 --> 00:36:57,890 744 00:36:57,890 --> 00:37:07,100 >> AUDIENCE: If value is greater than curr->n-- 745 00:37:07,100 --> 00:37:16,830 746 00:37:16,830 --> 00:37:18,240 >> JASON HIRSCHHORN: How do we go to the next node? 747 00:37:18,240 --> 00:37:27,760 748 00:37:27,760 --> 00:37:30,530 >> AUDIENCE: Curr->n is equal to new_node. 749 00:37:30,530 --> 00:37:37,630 750 00:37:37,630 --> 00:37:39,195 >> JASON HIRSCHHORN: So n is what part of the struct? 751 00:37:39,195 --> 00:37:43,065 752 00:37:43,065 --> 00:37:46,020 The integer. 753 00:37:46,020 --> 00:37:50,420 And new_node is a pointer to a node. 754 00:37:50,420 --> 00:37:51,880 So what part of curr should we update? 755 00:37:51,880 --> 00:38:03,900 756 00:38:03,900 --> 00:38:05,400 If not n, then what's the other part? 757 00:38:05,400 --> 00:38:21,680 758 00:38:21,680 --> 00:38:22,810 Noah, what's the other part. 759 00:38:22,810 --> 00:38:23,570 >> AUDIENCE: Oh, next. 760 00:38:23,570 --> 00:38:25,645 >> JASON HIRSCHHORN: Next, exactly. 761 00:38:25,645 --> 00:38:26,410 Exactly. 762 00:38:26,410 --> 00:38:28,770 Next is the right one. 763 00:38:28,770 --> 00:38:31,540 And what else do we need to update, Noah? 764 00:38:31,540 --> 00:38:32,840 >> AUDIENCE: The pointers. 765 00:38:32,840 --> 00:38:34,840 >> JASON HIRSCHHORN: So we updated current. 766 00:38:34,840 --> 00:38:36,090 >> AUDIENCE: Prev->next. 767 00:38:36,090 --> 00:38:48,160 768 00:38:48,160 --> 00:38:49,410 >> JASON HIRSCHHORN: Yeah. 769 00:38:49,410 --> 00:38:57,465 770 00:38:57,465 --> 00:38:58,370 OK, we'll pause. 771 00:38:58,370 --> 00:39:02,200 Who can help us out here? 772 00:39:02,200 --> 00:39:03,385 Manu, what should we do? 773 00:39:03,385 --> 00:39:05,615 >> AUDIENCE: You've got to set it equal to curr->next. 774 00:39:05,615 --> 00:39:09,110 775 00:39:09,110 --> 00:39:11,630 But do that before the previous line. 776 00:39:11,630 --> 00:39:12,880 >> JASON HIRSCHHORN: OK. 777 00:39:12,880 --> 00:39:16,590 778 00:39:16,590 --> 00:39:18,260 Anything else? 779 00:39:18,260 --> 00:39:19,170 Akshar. 780 00:39:19,170 --> 00:39:22,680 >> AUDIENCE: I don't think you're meant to change curr->next. 781 00:39:22,680 --> 00:39:29,270 I think you're meant to do curr equals curr->next to go to the next node. 782 00:39:29,270 --> 00:39:30,500 >> JASON HIRSCHHORN: So sorry, where? 783 00:39:30,500 --> 00:39:32,680 On what line? 784 00:39:32,680 --> 00:39:33,420 This line? 785 00:39:33,420 --> 00:39:33,750 >> AUDIENCE: Yeah. 786 00:39:33,750 --> 00:39:35,745 Make curr equals curr->next. 787 00:39:35,745 --> 00:39:39,690 788 00:39:39,690 --> 00:39:43,360 >> JASON HIRSCHHORN: So that's correct because current is a 789 00:39:43,360 --> 00:39:45,220 pointer to a node. 790 00:39:45,220 --> 00:39:48,550 And we want it to point to the next node of what's getting currently 791 00:39:48,550 --> 00:39:49,930 pointed to. 792 00:39:49,930 --> 00:39:54,410 Curr itself has a next. 793 00:39:54,410 --> 00:39:58,620 But if we were to update curr.next, we would be updating the actual note 794 00:39:58,620 --> 00:40:01,430 itself, not where this pointer was pointing. 795 00:40:01,430 --> 00:40:02,680 What about this line, though. 796 00:40:02,680 --> 00:40:05,160 797 00:40:05,160 --> 00:40:07,330 Avi? 798 00:40:07,330 --> 00:40:09,590 >> AUDIENCE: Prev->next equals curr. 799 00:40:09,590 --> 00:40:12,500 800 00:40:12,500 --> 00:40:19,440 >> JASON HIRSCHHORN: So again, if prev is a pointer to a node, prev->next is the 801 00:40:19,440 --> 00:40:23,020 actual pointer in the node. 802 00:40:23,020 --> 00:40:27,190 So this would be updating a pointer in a node to curr. 803 00:40:27,190 --> 00:40:28,570 We don't want to update a pointer in a node. 804 00:40:28,570 --> 00:40:30,570 We want to update previous. 805 00:40:30,570 --> 00:40:31,850 So how do we do that? 806 00:40:31,850 --> 00:40:34,250 >> AUDIENCE: It would just be prev. 807 00:40:34,250 --> 00:40:34,565 >> JASON HIRSCHHORN: Right. 808 00:40:34,565 --> 00:40:35,560 Prev is a pointer to a node. 809 00:40:35,560 --> 00:40:38,750 Now we're changing it to a new pointer to a node. 810 00:40:38,750 --> 00:40:40,830 OK Let us move down. 811 00:40:40,830 --> 00:40:41,940 Finally, this last condition. 812 00:40:41,940 --> 00:40:44,896 Jeff, what do we do here? 813 00:40:44,896 --> 00:40:47,515 >> AUDIENCE: If value is equal to curr->n. 814 00:40:47,515 --> 00:40:51,030 815 00:40:51,030 --> 00:40:51,300 >> JASON HIRSCHHORN: Sorry. 816 00:40:51,300 --> 00:40:52,372 Oh my goodness. 817 00:40:52,372 --> 00:40:54,330 What? 818 00:40:54,330 --> 00:40:55,580 Value==curr->n. 819 00:40:55,580 --> 00:41:01,050 820 00:41:01,050 --> 00:41:02,300 What do we do? 821 00:41:02,300 --> 00:41:04,760 822 00:41:04,760 --> 00:41:10,950 >> AUDIENCE: You'd free our new_node, and then you'd return false. 823 00:41:10,950 --> 00:41:21,410 824 00:41:21,410 --> 00:41:23,460 >> JASON HIRSCHHORN: This is what we have written so far. 825 00:41:23,460 --> 00:41:25,710 Does anybody have anything to add before we make? 826 00:41:25,710 --> 00:41:35,460 827 00:41:35,460 --> 00:41:35,710 OK. 828 00:41:35,710 --> 00:41:36,960 Let's try it. 829 00:41:36,960 --> 00:41:44,180 830 00:41:44,180 --> 00:41:46,110 Control may reach the end of a non-void function. 831 00:41:46,110 --> 00:41:48,310 Avi, what's going on? 832 00:41:48,310 --> 00:41:51,380 >> AUDIENCE: Are you supposed to put return true outside of the while loop? 833 00:41:51,380 --> 00:41:53,900 834 00:41:53,900 --> 00:41:54,400 >> JASON HIRSCHHORN: I don't know. 835 00:41:54,400 --> 00:41:54,780 Do you want me to? 836 00:41:54,780 --> 00:41:55,520 >> AUDIENCE: Never mind. 837 00:41:55,520 --> 00:41:56,350 No. 838 00:41:56,350 --> 00:41:57,180 >> JASON HIRSCHHORN: Akshar? 839 00:41:57,180 --> 00:41:59,460 >> AUDIENCE: I think you meant to put return false at the end 840 00:41:59,460 --> 00:42:02,230 of the while loop. 841 00:42:02,230 --> 00:42:03,270 >> JASON HIRSCHHORN: So where do you want it to go? 842 00:42:03,270 --> 00:42:05,270 >> AUDIENCE: Like outside the while loop. 843 00:42:05,270 --> 00:42:08,800 So if you exit the while loop that means that you've reached the end and 844 00:42:08,800 --> 00:42:09,980 nothing's happened. 845 00:42:09,980 --> 00:42:10,410 >> JASON HIRSCHHORN: OK. 846 00:42:10,410 --> 00:42:12,340 So what do we do in here? 847 00:42:12,340 --> 00:42:13,702 >> AUDIENCE: You return false there as well. 848 00:42:13,702 --> 00:42:15,040 >> JASON HIRSCHHORN: Oh, we do it in both places? 849 00:42:15,040 --> 00:42:15,650 >> AUDIENCE: Yeah. 850 00:42:15,650 --> 00:42:16,900 >> JASON HIRSCHHORN: OK. 851 00:42:16,900 --> 00:42:24,840 852 00:42:24,840 --> 00:42:26,160 Should we go? 853 00:42:26,160 --> 00:42:26,980 Oh my goodness. 854 00:42:26,980 --> 00:42:27,290 I'm sorry. 855 00:42:27,290 --> 00:42:28,480 I apologize for the screen. 856 00:42:28,480 --> 00:42:30,530 It's kind of freaking out on us. 857 00:42:30,530 --> 00:42:31,520 So choose an option. 858 00:42:31,520 --> 00:42:35,260 Zero, per the code, quits the program. 859 00:42:35,260 --> 00:42:36,700 One inserts something. 860 00:42:36,700 --> 00:42:37,990 Let's insert three. 861 00:42:37,990 --> 00:42:42,900 862 00:42:42,900 --> 00:42:45,380 The insert was not successful. 863 00:42:45,380 --> 00:42:46,500 I'm going to print out. 864 00:42:46,500 --> 00:42:48,050 I don't have anything. 865 00:42:48,050 --> 00:42:48,450 OK. 866 00:42:48,450 --> 00:42:50,250 Maybe that was just a fluke. 867 00:42:50,250 --> 00:42:52,810 Insert one. 868 00:42:52,810 --> 00:42:55,770 Not successful. 869 00:42:55,770 --> 00:42:57,470 OK. 870 00:42:57,470 --> 00:43:02,400 Let's run through GDB really quickly to check out what is going on. 871 00:43:02,400 --> 00:43:06,055 >> Remember gdb./ the name of your program gets us into GDB. 872 00:43:06,055 --> 00:43:07,610 Is that a lot to handle? 873 00:43:07,610 --> 00:43:08,560 The flashing? 874 00:43:08,560 --> 00:43:10,400 Probably. 875 00:43:10,400 --> 00:43:12,760 Close your eyes and take some deep breaths if you get tired 876 00:43:12,760 --> 00:43:13,580 of looking at it. 877 00:43:13,580 --> 00:43:14,200 I'm in GDB. 878 00:43:14,200 --> 00:43:15,830 What's the first thing I do in GDB? 879 00:43:15,830 --> 00:43:17,050 We've got to figure out what's going on here. 880 00:43:17,050 --> 00:43:17,310 Let's see. 881 00:43:17,310 --> 00:43:21,650 We have six minutes to figure out what's going on. 882 00:43:21,650 --> 00:43:22,900 Break main. 883 00:43:22,900 --> 00:43:25,950 884 00:43:25,950 --> 00:43:28,130 And then what do I do? 885 00:43:28,130 --> 00:43:29,180 Carlos? 886 00:43:29,180 --> 00:43:31,060 Run. 887 00:43:31,060 --> 00:43:32,250 OK. 888 00:43:32,250 --> 00:43:34,160 Let's choose an option. 889 00:43:34,160 --> 00:43:36,330 And what does N do? 890 00:43:36,330 --> 00:43:38,480 Next. 891 00:43:38,480 --> 00:43:38,950 Yeah. 892 00:43:38,950 --> 00:43:39,740 >> AUDIENCE: Didn't you mention-- 893 00:43:39,740 --> 00:43:45,230 didn't you say that the head, it was initialized to null at the beginning. 894 00:43:45,230 --> 00:43:47,140 But I thought you said that was OK. 895 00:43:47,140 --> 00:43:50,040 896 00:43:50,040 --> 00:43:52,640 >> JASON HIRSCHHORN: Let's go-- let's look in GDB, and then we'll go back. 897 00:43:52,640 --> 00:43:54,910 But it sounds like you already have some ideas about what's going on. 898 00:43:54,910 --> 00:43:58,340 So we want to insert something. 899 00:43:58,340 --> 00:43:59,390 OK. 900 00:43:59,390 --> 00:44:00,150 We have insert. 901 00:44:00,150 --> 00:44:00,770 Please enter an int. 902 00:44:00,770 --> 00:44:01,990 We'll insert three. 903 00:44:01,990 --> 00:44:03,000 And then I'm on this line. 904 00:44:03,000 --> 00:44:07,030 How do I go start debugging the insert known function? 905 00:44:07,030 --> 00:44:08,280 Oh my goodness. 906 00:44:08,280 --> 00:44:10,990 907 00:44:10,990 --> 00:44:12,240 That's a lot. 908 00:44:12,240 --> 00:44:14,372 909 00:44:14,372 --> 00:44:16,445 Is that freaking out a lot? 910 00:44:16,445 --> 00:44:19,696 911 00:44:19,696 --> 00:44:21,680 >> AUDIENCE: Oh, it died. 912 00:44:21,680 --> 00:44:22,930 >> JASON HIRSCHHORN: I just pulled it out. 913 00:44:22,930 --> 00:44:27,364 914 00:44:27,364 --> 00:44:28,310 OK. 915 00:44:28,310 --> 00:44:29,560 >> AUDIENCE: Maybe it's the other end of the wire. 916 00:44:29,560 --> 00:44:37,000 917 00:44:37,000 --> 00:44:39,470 >> JASON HIRSCHHORN: Wow. 918 00:44:39,470 --> 00:44:42,330 So the bottom line-- 919 00:44:42,330 --> 00:44:43,470 what did you say? 920 00:44:43,470 --> 00:44:46,040 >> AUDIENCE: I said the irony of technical difficulties in this class. 921 00:44:46,040 --> 00:44:46,410 >> JASON HIRSCHHORN: I know. 922 00:44:46,410 --> 00:44:48,660 If only I had control over that part. 923 00:44:48,660 --> 00:44:49,910 [INAUDIBLE] 924 00:44:49,910 --> 00:44:54,430 925 00:44:54,430 --> 00:44:55,400 That sounds great. 926 00:44:55,400 --> 00:44:58,680 Why don't you guys start thinking about what we could have done wrong, 927 00:44:58,680 --> 00:45:01,140 and we will be back in 90 seconds. 928 00:45:01,140 --> 00:46:18,160 929 00:46:18,160 --> 00:46:23,010 >> Avica, I'm going to ask you how to go inside insert_node to debug it. 930 00:46:23,010 --> 00:46:28,940 931 00:46:28,940 --> 00:46:31,460 So this is where we last left off. 932 00:46:31,460 --> 00:46:35,110 How do I go inside insert_node, Avica, to examine what's going on? 933 00:46:35,110 --> 00:46:36,360 What GDB command? 934 00:46:36,360 --> 00:46:41,050 935 00:46:41,050 --> 00:46:42,390 Break would not take me inside. 936 00:46:42,390 --> 00:46:46,200 937 00:46:46,200 --> 00:46:47,130 Does Marquise know? 938 00:46:47,130 --> 00:46:48,240 >> AUDIENCE: What? 939 00:46:48,240 --> 00:46:51,780 >> JASON HIRSCHHORN: What GDB command I use to go inside this function? 940 00:46:51,780 --> 00:46:52,070 >> AUDIENCE: Step? 941 00:46:52,070 --> 00:46:55,140 >> JASON HIRSCHHORN: Step via S. That takes me inside. 942 00:46:55,140 --> 00:46:55,476 OK. 943 00:46:55,476 --> 00:46:58,040 New_node mallocing some space. 944 00:46:58,040 --> 00:46:59,120 That all looks like its going. 945 00:46:59,120 --> 00:47:00,370 Let's examine new_node. 946 00:47:00,370 --> 00:47:03,270 947 00:47:03,270 --> 00:47:05,410 It got some memory address. 948 00:47:05,410 --> 00:47:07,440 Let's check-- 949 00:47:07,440 --> 00:47:08,500 that is all correct. 950 00:47:08,500 --> 00:47:12,220 So everything here seems to be working correctly. 951 00:47:12,220 --> 00:47:14,530 >> AUDIENCE: What's the difference between P and display? 952 00:47:14,530 --> 00:47:16,160 >> JASON HIRSCHHORN: P stands for print. 953 00:47:16,160 --> 00:47:19,310 And so you're asking what's the difference between that and this? 954 00:47:19,310 --> 00:47:22,330 In this case, nothing. 955 00:47:22,330 --> 00:47:26,960 But generally there are some differences. 956 00:47:26,960 --> 00:47:28,220 And you should look in the GDB manual. 957 00:47:28,220 --> 00:47:29,560 But in this case, nothing. 958 00:47:29,560 --> 00:47:31,460 We tend to use print, though, because we don't need to do much more than 959 00:47:31,460 --> 00:47:33,960 print a single value. 960 00:47:33,960 --> 00:47:34,640 >> OK. 961 00:47:34,640 --> 00:47:40,300 So we are on line 80 of our code, setting node* curr equal to list. 962 00:47:40,300 --> 00:47:42,500 Let us print out curr. 963 00:47:42,500 --> 00:47:45,260 964 00:47:45,260 --> 00:47:46,840 It equals list. 965 00:47:46,840 --> 00:47:48,850 Sweet. 966 00:47:48,850 --> 00:47:49,340 Wait. 967 00:47:49,340 --> 00:47:50,590 It equals something. 968 00:47:50,590 --> 00:47:53,680 969 00:47:53,680 --> 00:47:56,190 That doesn't seem right. 970 00:47:56,190 --> 00:47:56,840 There we go. 971 00:47:56,840 --> 00:47:59,470 It's because in GDB, right, if it's the line you're on it 972 00:47:59,470 --> 00:48:00,330 hasn't executed yet. 973 00:48:00,330 --> 00:48:03,100 So you need to actually type next to execute the line 974 00:48:03,100 --> 00:48:05,230 before seeing its results. 975 00:48:05,230 --> 00:48:06,680 So here we are. 976 00:48:06,680 --> 00:48:09,490 We just executed this line, previous equals null. 977 00:48:09,490 --> 00:48:13,590 So again, if we print previous we won't see anything weird. 978 00:48:13,590 --> 00:48:18,680 But if we actually execute that line, then we will see 979 00:48:18,680 --> 00:48:20,380 that that line worked. 980 00:48:20,380 --> 00:48:21,060 >> So we have curr. 981 00:48:21,060 --> 00:48:23,180 Those are both good. 982 00:48:23,180 --> 00:48:24,010 Right? 983 00:48:24,010 --> 00:48:28,130 Now we're on this line right here. 984 00:48:28,130 --> 00:48:29,310 While curr does not equal null. 985 00:48:29,310 --> 00:48:31,110 Well, what does curr equal? 986 00:48:31,110 --> 00:48:32,450 We just saw it equalled null. 987 00:48:32,450 --> 00:48:33,210 We printed it out. 988 00:48:33,210 --> 00:48:35,110 I'll print it out again. 989 00:48:35,110 --> 00:48:36,720 So is that while loop going to execute? 990 00:48:36,720 --> 00:48:37,270 >> AUDIENCE: No. 991 00:48:37,270 --> 00:48:39,790 >> JASON HIRSCHHORN: So when I typed that line, you see we jumped all the way 992 00:48:39,790 --> 00:48:41,390 down to the bottom, return false. 993 00:48:41,390 --> 00:48:44,520 And then we're going to return false and go back to our program and 994 00:48:44,520 --> 00:48:48,020 eventually print out, like we saw, the insert was not successful. 995 00:48:48,020 --> 00:48:51,010 So, anybody have any ideas on what we need to do to fix this? 996 00:48:51,010 --> 00:48:54,200 997 00:48:54,200 --> 00:48:57,570 I'm going to wait until I see a couple of hands go up. 998 00:48:57,570 --> 00:48:58,830 We didn't execute this. 999 00:48:58,830 --> 00:49:01,660 Keep in mind, this was the first thing we were doing. 1000 00:49:01,660 --> 00:49:02,430 I'm not going to do a couple. 1001 00:49:02,430 --> 00:49:03,670 I'm going to do a few. 1002 00:49:03,670 --> 00:49:04,830 Because a couple means two. 1003 00:49:04,830 --> 00:49:07,620 I'll wait for more than two. 1004 00:49:07,620 --> 00:49:10,690 >> The first insertion, curr, by default equals null. 1005 00:49:10,690 --> 00:49:14,050 And this loop only executes if curr is not null. 1006 00:49:14,050 --> 00:49:18,740 So how can I get around this? 1007 00:49:18,740 --> 00:49:19,990 I see three hands. 1008 00:49:19,990 --> 00:49:28,490 1009 00:49:28,490 --> 00:49:29,780 I'll wait for more than three. 1010 00:49:29,780 --> 00:49:33,460 1011 00:49:33,460 --> 00:49:35,940 Marcus, what do you think? 1012 00:49:35,940 --> 00:49:37,730 >> AUDIENCE: Well, if you need it to execute more than once, you just 1013 00:49:37,730 --> 00:49:39,948 change it to a do-while loop. 1014 00:49:39,948 --> 00:49:41,250 >> JASON HIRSCHHORN: OK. 1015 00:49:41,250 --> 00:49:44,240 Will that solve our problem, though? 1016 00:49:44,240 --> 00:49:47,750 >> AUDIENCE: In this case no because of the fact that the list is empty. 1017 00:49:47,750 --> 00:49:52,150 So then you probably just need to add a statement that if the loop exits 1018 00:49:52,150 --> 00:49:55,312 then you have to be at the end of the list, at which point you 1019 00:49:55,312 --> 00:49:56,562 can just insert it. 1020 00:49:56,562 --> 00:49:58,920 1021 00:49:58,920 --> 00:49:59,680 >> JASON HIRSCHHORN: I like that. 1022 00:49:59,680 --> 00:50:00,500 That makes sense. 1023 00:50:00,500 --> 00:50:03,390 If the loop exits-- 1024 00:50:03,390 --> 00:50:04,800 because it'll return false here. 1025 00:50:04,800 --> 00:50:08,220 So if the loop exits, then we're at the end of the list, or maybe the 1026 00:50:08,220 --> 00:50:10,690 start of a list if there's nothing in it, which is the same as the end. 1027 00:50:10,690 --> 00:50:12,770 So now we want to insert something here. 1028 00:50:12,770 --> 00:50:17,380 So how does that code look, Marcus? 1029 00:50:17,380 --> 00:50:21,600 >> AUDIENCE: If you already got the node malloced, you could just say 1030 00:50:21,600 --> 00:50:25,400 new_node->next equals null because it has to be at the end. 1031 00:50:25,400 --> 00:50:27,510 Or new_node->next equals null. 1032 00:50:27,510 --> 00:50:27,765 >> JASON HIRSCHHORN: OK. 1033 00:50:27,765 --> 00:50:28,190 Sorry. 1034 00:50:28,190 --> 00:50:35,760 New_node->next equals null because we're at the end. 1035 00:50:35,760 --> 00:50:36,460 That doesn't put it in. 1036 00:50:36,460 --> 00:50:37,710 How do we put it in the list? 1037 00:50:37,710 --> 00:50:46,130 1038 00:50:46,130 --> 00:50:46,460 Right. 1039 00:50:46,460 --> 00:50:47,750 That's just setting it equal to. 1040 00:50:47,750 --> 00:50:50,940 No how do we actually put it in the list? 1041 00:50:50,940 --> 00:50:54,170 What's pointing to the end of the list? 1042 00:50:54,170 --> 00:50:56,090 >> AUDIENCE: Head. 1043 00:50:56,090 --> 00:50:57,566 >> JASON HIRSCHHORN: Sorry? 1044 00:50:57,566 --> 00:50:59,440 >> AUDIENCE: Head is pointing to the end of the list. 1045 00:50:59,440 --> 00:51:01,480 >> JASON HIRSCHHORN: If there's nothing in the list, head is pointing to the 1046 00:51:01,480 --> 00:51:04,170 end of the list. 1047 00:51:04,170 --> 00:51:06,920 So that'll work for the first insertion. 1048 00:51:06,920 --> 00:51:09,810 What about if there are a couple things in the list? 1049 00:51:09,810 --> 00:51:12,470 Than we don't want to set head equal to new_node. 1050 00:51:12,470 --> 00:51:13,790 What do we want to do there? 1051 00:51:13,790 --> 00:51:15,610 Yeah? 1052 00:51:15,610 --> 00:51:16,860 Probably previous. 1053 00:51:16,860 --> 00:51:23,560 1054 00:51:23,560 --> 00:51:24,810 Will that work? 1055 00:51:24,810 --> 00:51:28,950 1056 00:51:28,950 --> 00:51:33,050 Recall that previous is just a pointer to a node. 1057 00:51:33,050 --> 00:51:34,770 And previous is a local variable. 1058 00:51:34,770 --> 00:51:38,080 So this line will set a local variable, previous, equal to or 1059 00:51:38,080 --> 00:51:39,380 pointing to this new node. 1060 00:51:39,380 --> 00:51:41,500 That won't actually put it in our list, though. 1061 00:51:41,500 --> 00:51:44,330 How do we put it in our list? 1062 00:51:44,330 --> 00:51:45,620 Akchar? 1063 00:51:45,620 --> 00:51:46,870 >> AUDIENCE: I think you do current->next. 1064 00:51:46,870 --> 00:51:50,186 1065 00:51:50,186 --> 00:51:52,550 >> JASON HIRSCHHORN: OK. 1066 00:51:52,550 --> 00:51:54,010 curr->next. 1067 00:51:54,010 --> 00:51:58,768 So again, the only reason we're down here is, what does current equal? 1068 00:51:58,768 --> 00:51:59,760 >> AUDIENCE: Equals null. 1069 00:51:59,760 --> 00:52:01,790 >> JASON HIRSCHHORN: And so what happens if we do null->next? 1070 00:52:01,790 --> 00:52:02,810 What do we going to get? 1071 00:52:02,810 --> 00:52:04,060 We'll get a segmentation fault. 1072 00:52:04,060 --> 00:52:06,600 1073 00:52:06,600 --> 00:52:08,880 >> AUDIENCE: Do curr equals null. 1074 00:52:08,880 --> 00:52:10,760 >> JASON HIRSCHHORN: That's the same thing as prev, though, because there's 1075 00:52:10,760 --> 00:52:12,820 a local variable we're setting equal to this new node. 1076 00:52:12,820 --> 00:52:16,680 1077 00:52:16,680 --> 00:52:20,920 Let's go back to our picture of inserting something. 1078 00:52:20,920 --> 00:52:25,500 Say we're inserting at the end of the list, so right here. 1079 00:52:25,500 --> 00:52:30,010 We have a current pointer that's pointing to null and a previous point 1080 00:52:30,010 --> 00:52:32,800 that's pointing to 8. 1081 00:52:32,800 --> 00:52:35,330 So what do we need to update, Avi? 1082 00:52:35,330 --> 00:52:36,680 >> AUDIENCE: Previous->next? 1083 00:52:36,680 --> 00:52:41,980 >> JASON HIRSCHHORN: Previous->next is what we want to update because that 1084 00:52:41,980 --> 00:52:44,960 will actually insert it at the end of the list. 1085 00:52:44,960 --> 00:52:47,220 We still have one bug, though, that we're going to run into. 1086 00:52:47,220 --> 00:52:50,090 What's that bug? 1087 00:52:50,090 --> 00:52:50,790 Yeah? 1088 00:52:50,790 --> 00:52:53,860 >> AUDIENCE: It's going to return false in this case? 1089 00:52:53,860 --> 00:52:56,380 >> JASON HIRSCHHORN: Oh, is is going to return false. 1090 00:52:56,380 --> 00:52:57,430 But there's another bug. 1091 00:52:57,430 --> 00:52:58,930 So we'll need to put in return true. 1092 00:52:58,930 --> 00:53:01,370 >> AUDIENCE: Does previous still equal null at the top of the list? 1093 00:53:01,370 --> 00:53:03,645 >> JASON HIRSCHHORN: So previous still equals null at the very beginning. 1094 00:53:03,645 --> 00:53:07,480 1095 00:53:07,480 --> 00:53:10,440 So how can we get over that? 1096 00:53:10,440 --> 00:53:10,950 Yeah? 1097 00:53:10,950 --> 00:53:15,280 >> AUDIENCE: I think you can do a check before the while loop to see if it's 1098 00:53:15,280 --> 00:53:16,610 an empty list. 1099 00:53:16,610 --> 00:53:17,000 >> JASON HIRSCHHORN: OK. 1100 00:53:17,000 --> 00:53:17,710 So let's go here. 1101 00:53:17,710 --> 00:53:18,530 Do a check. 1102 00:53:18,530 --> 00:53:19,380 If-- 1103 00:53:19,380 --> 00:53:20,770 >> AUDIENCE: So if head equals equals null. 1104 00:53:20,770 --> 00:53:24,300 1105 00:53:24,300 --> 00:53:26,320 >> JASON HIRSCHHORN: If head equals equals null-- 1106 00:53:26,320 --> 00:53:27,790 that'll tell us if it's an empty list. 1107 00:53:27,790 --> 00:53:31,090 >> AUDIENCE: And then you do head equals new. 1108 00:53:31,090 --> 00:53:34,740 >> JASON HIRSCHHORN: Head equals new_node? 1109 00:53:34,740 --> 00:53:35,730 And what else do we need to do? 1110 00:53:35,730 --> 00:53:37,020 >> AUDIENCE: And then you return true. 1111 00:53:37,020 --> 00:53:37,535 >> JASON HIRSCHHORN: Not quite. 1112 00:53:37,535 --> 00:53:38,785 We're missing one step. 1113 00:53:38,785 --> 00:53:41,590 1114 00:53:41,590 --> 00:53:43,710 >> AUDIENCE: New_node next has to point to null. 1115 00:53:43,710 --> 00:53:44,570 >> JASON HIRSCHHORN: Exactly, Alden. 1116 00:53:44,570 --> 00:53:46,600 And then we can return true. 1117 00:53:46,600 --> 00:53:47,560 OK. 1118 00:53:47,560 --> 00:53:51,630 But it's still a good idea to do things at the end of the list, right? 1119 00:53:51,630 --> 00:53:51,950 All right. 1120 00:53:51,950 --> 00:53:54,450 We still might actually get to the end of the list. 1121 00:53:54,450 --> 00:53:57,870 So is this code fine if we're at the end of the list and there are some 1122 00:53:57,870 --> 00:53:59,120 things in the list? 1123 00:53:59,120 --> 00:54:01,830 1124 00:54:01,830 --> 00:54:02,040 Right? 1125 00:54:02,040 --> 00:54:03,540 Because we still have Marcus's idea. 1126 00:54:03,540 --> 00:54:06,870 We might exit this loop because we're at the end of the list. 1127 00:54:06,870 --> 00:54:09,308 So do we still want this code down here? 1128 00:54:09,308 --> 00:54:10,520 >> AUDIENCE: Yes. 1129 00:54:10,520 --> 00:54:11,000 >> JASON HIRSCHHORN: Yeah. 1130 00:54:11,000 --> 00:54:14,190 And what do we need to change this to? 1131 00:54:14,190 --> 00:54:15,440 True. 1132 00:54:15,440 --> 00:54:19,580 1133 00:54:19,580 --> 00:54:21,640 Does that sound good to everyone so far? 1134 00:54:21,640 --> 00:54:22,420 Anybody have any-- 1135 00:54:22,420 --> 00:54:23,480 Avi, do you have something to add? 1136 00:54:23,480 --> 00:54:23,920 >> AUDIENCE: No. 1137 00:54:23,920 --> 00:54:25,276 >> JASON HIRSCHHORN: OK. 1138 00:54:25,276 --> 00:54:27,010 So we've made a couple of changes. 1139 00:54:27,010 --> 00:54:29,540 We've made this check before we went in for an empty list. 1140 00:54:29,540 --> 00:54:31,790 So we've taken care of an empty list. 1141 00:54:31,790 --> 00:54:35,500 And here we took care of inserting something at the end of the list. 1142 00:54:35,500 --> 00:54:38,930 So it seems like this while loop taking care of things in between, 1143 00:54:38,930 --> 00:54:41,920 somewhere in the list if there are things in the list. 1144 00:54:41,920 --> 00:54:42,280 >> OK. 1145 00:54:42,280 --> 00:54:44,310 Let us run this program again. 1146 00:54:44,310 --> 00:54:50,170 1147 00:54:50,170 --> 00:54:50,755 Not successful. 1148 00:54:50,755 --> 00:54:52,190 >> AUDIENCE: You didn't make it. 1149 00:54:52,190 --> 00:54:53,940 >> JASON HIRSCHHORN: Oh, I didn't make it. 1150 00:54:53,940 --> 00:54:56,250 Good point, Michael. 1151 00:54:56,250 --> 00:54:57,500 Let's add a make linked. 1152 00:54:57,500 --> 00:55:01,590 1153 00:55:01,590 --> 00:55:04,830 Line 87 there's an error. 1154 00:55:04,830 --> 00:55:05,420 Line 87. 1155 00:55:05,420 --> 00:55:06,600 Alden, this was the line you gave me. 1156 00:55:06,600 --> 00:55:08,962 What's wrong? 1157 00:55:08,962 --> 00:55:10,710 >> AUDIENCE: It has to be to null. 1158 00:55:10,710 --> 00:55:11,000 >> JASON HIRSCHHORN: Excellent. 1159 00:55:11,000 --> 00:55:11,630 Exactly right. 1160 00:55:11,630 --> 00:55:13,290 It should be null. 1161 00:55:13,290 --> 00:55:15,210 Let's make again. 1162 00:55:15,210 --> 00:55:17,220 Compile. 1163 00:55:17,220 --> 00:55:17,890 OK. 1164 00:55:17,890 --> 00:55:19,400 Let's insert three. 1165 00:55:19,400 --> 00:55:20,570 The insert was successful. 1166 00:55:20,570 --> 00:55:21,660 Let's print it out. 1167 00:55:21,660 --> 00:55:23,590 Oh, if only we could check. 1168 00:55:23,590 --> 00:55:25,500 But we haven't done the print function yet. 1169 00:55:25,500 --> 00:55:27,840 Let's enter something else. 1170 00:55:27,840 --> 00:55:29,090 What should we enter? 1171 00:55:29,090 --> 00:55:31,120 1172 00:55:31,120 --> 00:55:31,940 >> AUDIENCE: Seven. 1173 00:55:31,940 --> 00:55:33,340 >> JASON HIRSCHHORN: Seven? 1174 00:55:33,340 --> 00:55:34,590 >> AUDIENCE: Yes. 1175 00:55:34,590 --> 00:55:38,680 1176 00:55:38,680 --> 00:55:39,780 >> JASON HIRSCHHORN: We have a seg fault. 1177 00:55:39,780 --> 00:55:43,760 So we got one, but we clearly can't get two. 1178 00:55:43,760 --> 00:55:45,690 It is 5:07. 1179 00:55:45,690 --> 00:55:48,370 So we could debug this for three minutes. 1180 00:55:48,370 --> 00:55:51,240 But I'm going to leave us here and move on to hash tables. 1181 00:55:51,240 --> 00:55:54,290 But again, the answers for this code I will email it to you in a bit. 1182 00:55:54,290 --> 00:55:55,440 We are very close to it. 1183 00:55:55,440 --> 00:55:58,300 I highly encourage you to figure out what's going on here and fix it. 1184 00:55:58,300 --> 00:56:02,400 So I'll email you this code as well plus the solution-- 1185 00:56:02,400 --> 00:56:03,670 probably the solution later on. 1186 00:56:03,670 --> 00:56:05,110 First this code. 1187 00:56:05,110 --> 00:56:08,290 >> The other thing I want to do before we finish is we haven't freed anything. 1188 00:56:08,290 --> 00:56:10,370 So I want to show you what valgrind looks like. 1189 00:56:10,370 --> 00:56:14,310 If we run valgrind boundaries on our program, ./linked. 1190 00:56:14,310 --> 00:56:22,540 Again, according to this slide, we should run valgrind with some type of 1191 00:56:22,540 --> 00:56:26,410 option, in this case --leak-check=full. 1192 00:56:26,410 --> 00:56:27,660 So let's write valgrind --leak-check=full. 1193 00:56:27,660 --> 00:56:31,910 1194 00:56:31,910 --> 00:56:35,080 So this will run valgrind on our program. 1195 00:56:35,080 --> 00:56:37,000 And now the program actually runs. 1196 00:56:37,000 --> 00:56:40,190 So we're going to run it just like before, put something in. 1197 00:56:40,190 --> 00:56:40,830 I'm going to put in three. 1198 00:56:40,830 --> 00:56:41,790 That works. 1199 00:56:41,790 --> 00:56:43,202 I'm not going to try to put in something else because we're going to 1200 00:56:43,202 --> 00:56:44,710 get a seg false in that case. 1201 00:56:44,710 --> 00:56:46,700 So I'm just going to quit. 1202 00:56:46,700 --> 00:56:50,160 >> And now you see down here leak and heap summary. 1203 00:56:50,160 --> 00:56:52,310 These are the good things that you want to check out. 1204 00:56:52,310 --> 00:56:56,780 So the heap summary-- it says, in use at exit-- eight bytes in one block. 1205 00:56:56,780 --> 00:56:58,370 That one block is the node we malloced. 1206 00:56:58,370 --> 00:57:02,230 Michael, you said before a node is eight bites because it has the integer 1207 00:57:02,230 --> 00:57:02,680 and the pointer. 1208 00:57:02,680 --> 00:57:04,550 So that's our node. 1209 00:57:04,550 --> 00:57:08,170 And then it says we used malloc seven times and we freed 1210 00:57:08,170 --> 00:57:08,940 something six times. 1211 00:57:08,940 --> 00:57:13,680 But we never called free, so I have no idea what this is talking about. 1212 00:57:13,680 --> 00:57:18,490 >> But suffice it to say that when your program runs, malloc is being called 1213 00:57:18,490 --> 00:57:20,330 in some other places that we don't need to worry about. 1214 00:57:20,330 --> 00:57:22,460 So malloc was probably called in some places. 1215 00:57:22,460 --> 00:57:24,480 We don't need to worry where. 1216 00:57:24,480 --> 00:57:26,240 But this is really us. 1217 00:57:26,240 --> 00:57:27,380 This first line is us. 1218 00:57:27,380 --> 00:57:28,320 We left that block. 1219 00:57:28,320 --> 00:57:30,330 And you can see that here in the leak summary. 1220 00:57:30,330 --> 00:57:31,950 Still reachable-- 1221 00:57:31,950 --> 00:57:32,930 eight bytes in one block. 1222 00:57:32,930 --> 00:57:34,100 That means that memory-- 1223 00:57:34,100 --> 00:57:35,730 we have leaked that memory. 1224 00:57:35,730 --> 00:57:37,570 Definitely lost-- 1225 00:57:37,570 --> 00:57:38,770 something is lost for good. 1226 00:57:38,770 --> 00:57:40,590 Generally, you won't see anything there. 1227 00:57:40,590 --> 00:57:44,780 Still reachable is generally where you'll see things, where you'll want 1228 00:57:44,780 --> 00:57:48,900 to look to see what code should you have freed but you forgot to free. 1229 00:57:48,900 --> 00:57:53,170 >> And then if this wasn't the case, if we did free everything, 1230 00:57:53,170 --> 00:57:54,360 we can check that. 1231 00:57:54,360 --> 00:57:57,330 Let's just run the program not putting in anything. 1232 00:57:57,330 --> 00:57:59,800 You'll see down here in use at exit-- 1233 00:57:59,800 --> 00:58:01,310 zero bytes in zero blocks. 1234 00:58:01,310 --> 00:58:06,310 That means we had nothing left when this program exited. 1235 00:58:06,310 --> 00:58:12,090 So before turning in pset6, run valgrind and make sure you do not have 1236 00:58:12,090 --> 00:58:15,310 any memory leaks in your program. 1237 00:58:15,310 --> 00:58:17,910 If you have any questions with valgrind, feel free to reach out. 1238 00:58:17,910 --> 00:58:18,700 But this is how you use it. 1239 00:58:18,700 --> 00:58:20,890 Very simple-- see if you have in use at exit-- 1240 00:58:20,890 --> 00:58:22,270 any bytes in any blocks. 1241 00:58:22,270 --> 00:58:27,890 1242 00:58:27,890 --> 00:58:29,580 >> So we were working on insert node. 1243 00:58:29,580 --> 00:58:33,840 I had two other functions here-- print nodes and free nodes. 1244 00:58:33,840 --> 00:58:37,780 Again, these are functions that are going to be good for you to practice 1245 00:58:37,780 --> 00:58:40,990 because they will help you not only with these sample exercises but also 1246 00:58:40,990 --> 00:58:42,180 on the problem set. 1247 00:58:42,180 --> 00:58:44,230 They map on pretty closely to things you're going to have to do in the 1248 00:58:44,230 --> 00:58:45,010 problem set. 1249 00:58:45,010 --> 00:58:47,640 But I do want to make sure we touch on everything. 1250 00:58:47,640 --> 00:58:50,400 And hash tables are also crucial to what we're doing in section this 1251 00:58:50,400 --> 00:58:51,980 week-- or in the problem set. 1252 00:58:51,980 --> 00:58:55,200 >> So we're going to finish the section talking about hash tables. 1253 00:58:55,200 --> 00:58:58,140 If you notice I made a little hash table. 1254 00:58:58,140 --> 00:59:00,020 That is not what we're talking about, however. 1255 00:59:00,020 --> 00:59:03,540 We are talking about a different type of hash tables. 1256 00:59:03,540 --> 00:59:07,300 And at its core, a hash table is nothing more than an 1257 00:59:07,300 --> 00:59:08,860 array plus a hash function. 1258 00:59:08,860 --> 00:59:11,150 We're going to talk for a bit just to make sure everybody understands what a 1259 00:59:11,150 --> 00:59:12,110 hash function is. 1260 00:59:12,110 --> 00:59:15,420 And I'm telling you now that it is nothing more than two things-- 1261 00:59:15,420 --> 00:59:18,590 an array and a hash function. 1262 00:59:18,590 --> 00:59:20,716 And here are the steps through which this operates. 1263 00:59:20,716 --> 00:59:31,560 1264 00:59:31,560 --> 00:59:32,810 >> There's our array. 1265 00:59:32,810 --> 00:59:38,460 1266 00:59:38,460 --> 00:59:39,460 There's our function. 1267 00:59:39,460 --> 00:59:43,180 In particular, hash functions need to do a couple of things with this. 1268 00:59:43,180 --> 00:59:45,040 I'm going to talk specifically about this problem set. 1269 00:59:45,040 --> 00:59:46,450 It's probably going to take in a string. 1270 00:59:46,450 --> 00:59:50,570 1271 00:59:50,570 --> 00:59:51,770 And what's it going to return? 1272 00:59:51,770 --> 00:59:52,640 What data type? 1273 00:59:52,640 --> 00:59:54,260 Alden? 1274 00:59:54,260 --> 00:59:55,760 Your hash function return? 1275 00:59:55,760 --> 00:59:58,760 An integer. 1276 00:59:58,760 --> 01:00:01,700 So this is what the hash table consists of-- 1277 01:00:01,700 --> 01:00:05,430 a table in the form of array and a hash function. 1278 01:00:05,430 --> 01:00:06,010 How it works? 1279 01:00:06,010 --> 01:00:07,300 It works in three steps. 1280 01:00:07,300 --> 01:00:08,740 We give it a key. 1281 01:00:08,740 --> 01:00:11,470 In this case, we'll give it a string. 1282 01:00:11,470 --> 01:00:18,140 We call the hash function per step one on the key and we get a value. 1283 01:00:18,140 --> 01:00:20,310 >> Specifically, we'll say we get an integer. 1284 01:00:20,310 --> 01:00:25,630 That integer, there are very specific limits to what that integer can be. 1285 01:00:25,630 --> 01:00:28,880 In this example, our array is of size three. 1286 01:00:28,880 --> 01:00:32,330 So what numbers can that integer be. 1287 01:00:32,330 --> 01:00:35,970 What is the range of valid values for that integer, the return type of this 1288 01:00:35,970 --> 01:00:37,220 hash function? 1289 01:00:37,220 --> 01:00:40,440 1290 01:00:40,440 --> 01:00:42,110 Zero, one and two. 1291 01:00:42,110 --> 01:00:46,060 The point of the hash function is to figure out the place in the array 1292 01:00:46,060 --> 01:00:47,790 where our key is going. 1293 01:00:47,790 --> 01:00:51,290 There are only three possible places here-- 1294 01:00:51,290 --> 01:00:52,130 zero, one, or two. 1295 01:00:52,130 --> 01:00:55,360 So this function better return zero, one, or two. 1296 01:00:55,360 --> 01:00:58,740 Some valid indice in this array. 1297 01:00:58,740 --> 01:01:02,770 >> And then depending on where it returns, you can see there array open 1298 01:01:02,770 --> 01:01:03,730 bracket the value. 1299 01:01:03,730 --> 01:01:05,800 That's where we put the key. 1300 01:01:05,800 --> 01:01:11,280 So we throw in the pumpkin, we get out zero. 1301 01:01:11,280 --> 01:01:15,540 At array bracket 0, we put pumpkin. 1302 01:01:15,540 --> 01:01:21,070 We throw in cats, we get out one. 1303 01:01:21,070 --> 01:01:24,110 We put cat at one. 1304 01:01:24,110 --> 01:01:25,480 We put in spider. 1305 01:01:25,480 --> 01:01:26,710 We get out two. 1306 01:01:26,710 --> 01:01:30,200 We put spider at array bracket two. 1307 01:01:30,200 --> 01:01:32,300 It would be so nice if it worked like that. 1308 01:01:32,300 --> 01:01:35,570 But unfortunately, as we'll see, it's a bit more complicated. 1309 01:01:35,570 --> 01:01:37,570 >> Before we get there, any questions about this basic 1310 01:01:37,570 --> 01:01:38,820 set-up of a hash table? 1311 01:01:38,820 --> 01:01:49,050 1312 01:01:49,050 --> 01:01:51,940 This is an image of exactly what we drew on the board. 1313 01:01:51,940 --> 01:01:55,420 But since we drew it on the board, I am not going to go into it further. 1314 01:01:55,420 --> 01:02:00,430 Essentially keys, the magic black box-- or in this case, teal box-- of a 1315 01:02:00,430 --> 01:02:02,410 hash function puts them in buckets. 1316 01:02:02,410 --> 01:02:04,690 And in this example we're not putting the name. 1317 01:02:04,690 --> 01:02:07,880 We're putting the associated phone number of the name in the bucket. 1318 01:02:07,880 --> 01:02:10,430 But you could very well just put the name in the bucket. 1319 01:02:10,430 --> 01:02:12,950 >> This is just a picture of what we drew on the board. 1320 01:02:12,950 --> 01:02:14,460 We have potential pitfalls, though. 1321 01:02:14,460 --> 01:02:17,470 And there are two in particular slides that I want to go over. 1322 01:02:17,470 --> 01:02:20,230 The first one is about a hash function. 1323 01:02:20,230 --> 01:02:22,620 So I asked the question, what makes a good hash function? 1324 01:02:22,620 --> 01:02:24,220 I give two answers. 1325 01:02:24,220 --> 01:02:26,630 The first is that it's deterministic. 1326 01:02:26,630 --> 01:02:29,660 In the context of hash functions, what does this mean? 1327 01:02:29,660 --> 01:02:37,840 1328 01:02:37,840 --> 01:02:39,282 Yes? 1329 01:02:39,282 --> 01:02:42,850 >> AUDIENCE: It can find the index in constant time? 1330 01:02:42,850 --> 01:02:43,810 >> JASON HIRSCHHORN: That is not what it means. 1331 01:02:43,810 --> 01:02:44,725 But that's a good guess. 1332 01:02:44,725 --> 01:02:46,100 Anybody else have a guess to what this means? 1333 01:02:46,100 --> 01:02:47,780 That a good hash function is deterministic? 1334 01:02:47,780 --> 01:02:48,280 Annie? 1335 01:02:48,280 --> 01:02:51,680 >> AUDIENCE: That a key can only be mapped to one place in the hash table. 1336 01:02:51,680 --> 01:02:53,070 >> JASON HIRSCHHORN: That's exactly right. 1337 01:02:53,070 --> 01:02:57,430 Every time you put in pumpkin, it always returns zero. 1338 01:02:57,430 --> 01:03:01,660 If you put in pumpkin and your hash function returns zero but has a 1339 01:03:01,660 --> 01:03:06,060 probability of returning something else greater than zero-- 1340 01:03:06,060 --> 01:03:09,280 so maybe it can return one sometimes or two other times-- 1341 01:03:09,280 --> 01:03:11,100 that is not a good hash function. 1342 01:03:11,100 --> 01:03:11,800 You're exactly right. 1343 01:03:11,800 --> 01:03:15,680 Your hash function should return the same exact integer, in this case, for 1344 01:03:15,680 --> 01:03:17,780 the same exact string. 1345 01:03:17,780 --> 01:03:22,210 >> Maybe it returns the same exact integer for the same exact string 1346 01:03:22,210 --> 01:03:24,430 regardless of capitalization. 1347 01:03:24,430 --> 01:03:27,980 But in that case it's still deterministic because multiple things 1348 01:03:27,980 --> 01:03:29,350 are mapped onto the same value. 1349 01:03:29,350 --> 01:03:30,170 That's fine. 1350 01:03:30,170 --> 01:03:32,615 As long as there is only one output for a given input. 1351 01:03:32,615 --> 01:03:35,630 1352 01:03:35,630 --> 01:03:36,350 >> OK. 1353 01:03:36,350 --> 01:03:38,340 The second thing is that it returns valid indices. 1354 01:03:38,340 --> 01:03:40,220 We brought up that earlier. 1355 01:03:40,220 --> 01:03:41,860 This hash function-- 1356 01:03:41,860 --> 01:03:43,710 oh boy-- 1357 01:03:43,710 --> 01:03:46,840 a hash function should return valid indices. 1358 01:03:46,840 --> 01:03:47,740 So say-- 1359 01:03:47,740 --> 01:03:48,990 let's go back to this example. 1360 01:03:48,990 --> 01:03:52,580 1361 01:03:52,580 --> 01:03:57,540 My hash function counts up the letters in the word. 1362 01:03:57,540 --> 01:03:58,380 That's the hash function. 1363 01:03:58,380 --> 01:03:59,740 And returns that integer. 1364 01:03:59,740 --> 01:04:04,280 So if I have the word A, it's going to return one. 1365 01:04:04,280 --> 01:04:06,900 And it's going to put A right here. 1366 01:04:06,900 --> 01:04:09,430 What if I put in the word bat? 1367 01:04:09,430 --> 01:04:11,310 It's going to return three. 1368 01:04:11,310 --> 01:04:12,560 Where does bat go? 1369 01:04:12,560 --> 01:04:18,730 1370 01:04:18,730 --> 01:04:19,750 >> It doesn't fit. 1371 01:04:19,750 --> 01:04:21,000 But it needs to go somewhere. 1372 01:04:21,000 --> 01:04:23,340 This is my hash table after all, and everything needs to go somewhere. 1373 01:04:23,340 --> 01:04:24,590 So where should bat go? 1374 01:04:24,590 --> 01:04:28,020 1375 01:04:28,020 --> 01:04:28,710 Any thoughts? 1376 01:04:28,710 --> 01:04:29,450 Guesses? 1377 01:04:29,450 --> 01:04:30,280 Good guesses? 1378 01:04:30,280 --> 01:04:31,220 >> AUDIENCE: Zero. 1379 01:04:31,220 --> 01:04:32,120 >> JASON HIRSCHHORN: Why zero? 1380 01:04:32,120 --> 01:04:35,990 >> AUDIENCE: Because three modulo three is zero? 1381 01:04:35,990 --> 01:04:38,620 >> JASON HIRSCHHORN: Three modulo three is zero. 1382 01:04:38,620 --> 01:04:40,810 That is a great guess, and that's correct. 1383 01:04:40,810 --> 01:04:43,870 So in this case it should probably go at zero. 1384 01:04:43,870 --> 01:04:51,080 So a good way to ensure that this hash function only returns valid indices is 1385 01:04:51,080 --> 01:04:54,580 to modulo it by the size of the table. 1386 01:04:54,580 --> 01:04:57,360 If you modulo whatever this returns by three, you're always going to get 1387 01:04:57,360 --> 01:05:00,930 something between zero, one, and two. 1388 01:05:00,930 --> 01:05:05,160 And if this always returns seven, and you always modulo by three, you're 1389 01:05:05,160 --> 01:05:06,030 always going to get the same thing. 1390 01:05:06,030 --> 01:05:09,270 >> So it's still deterministic if you modulo. 1391 01:05:09,270 --> 01:05:11,420 But that will ensure that you never get something-- 1392 01:05:11,420 --> 01:05:12,940 an invalid industry. 1393 01:05:12,940 --> 01:05:16,840 Generally, that modulo should happen inside your hash function. 1394 01:05:16,840 --> 01:05:18,240 So you don't need to worry about this. 1395 01:05:18,240 --> 01:05:20,555 You just can ensure that this is a valid indice. 1396 01:05:20,555 --> 01:05:23,700 1397 01:05:23,700 --> 01:05:26,700 Any questions on this potential pitfall? 1398 01:05:26,700 --> 01:05:36,590 1399 01:05:36,590 --> 01:05:39,060 >> OK. 1400 01:05:39,060 --> 01:05:40,290 And there we go. 1401 01:05:40,290 --> 01:05:42,890 Next potential pitfall, and this is the big one. 1402 01:05:42,890 --> 01:05:46,880 What if two keys map to the same value? 1403 01:05:46,880 --> 01:05:49,350 So there are two ways to handle this. 1404 01:05:49,350 --> 01:05:53,140 1405 01:05:53,140 --> 01:05:56,020 The first one is called linear probing, which I'm 1406 01:05:56,020 --> 01:05:57,300 not going to go over. 1407 01:05:57,300 --> 01:06:01,120 But you should be familiar with how that works and what that is. 1408 01:06:01,120 --> 01:06:05,610 >> The second one I am going to go over because that is the one that many 1409 01:06:05,610 --> 01:06:08,290 people will probably end up deciding to use in their problem set. 1410 01:06:08,290 --> 01:06:09,820 Of course, you don't have to. 1411 01:06:09,820 --> 01:06:15,280 But for the problem set, many people tend to choose to create a hash table 1412 01:06:15,280 --> 01:06:17,950 with separate chaining to implement their dictionary. 1413 01:06:17,950 --> 01:06:21,390 So we're going to go over what it means to create a hash table with 1414 01:06:21,390 --> 01:06:23,890 separate chaining. 1415 01:06:23,890 --> 01:06:26,260 >> So I put in pumpkin. 1416 01:06:26,260 --> 01:06:29,560 It returns zero. 1417 01:06:29,560 --> 01:06:31,410 And I put pumpkin here. 1418 01:06:31,410 --> 01:06:35,880 1419 01:06:35,880 --> 01:06:37,930 Then I put in-- 1420 01:06:37,930 --> 01:06:39,922 what's another Halloween-themed thing? 1421 01:06:39,922 --> 01:06:42,200 >> AUDIENCE: Candy. 1422 01:06:42,200 --> 01:06:42,770 >> JASON HIRSCHHORN: Candy! 1423 01:06:42,770 --> 01:06:43,910 That's a great one. 1424 01:06:43,910 --> 01:06:47,760 I put in candy, and candy also gives me zero. 1425 01:06:47,760 --> 01:06:49,350 What do I do? 1426 01:06:49,350 --> 01:06:51,940 Any ideas? 1427 01:06:51,940 --> 01:06:53,940 Because you all sort of know what separate chaining is. 1428 01:06:53,940 --> 01:06:55,190 So any ideas what to do? 1429 01:06:55,190 --> 01:06:58,170 1430 01:06:58,170 --> 01:06:59,110 Yeah. 1431 01:06:59,110 --> 01:07:03,810 >> AUDIENCE: Putting the string actually in the hash table. 1432 01:07:03,810 --> 01:07:08,910 >> JASON HIRSCHHORN: So we're going to draw the good idea over here. 1433 01:07:08,910 --> 01:07:09,340 OK. 1434 01:07:09,340 --> 01:07:12,290 >> AUDIENCE: Have the hashtable [INAUDIBLE] 1435 01:07:12,290 --> 01:07:16,640 the pointer that points to the beginning of a list. 1436 01:07:16,640 --> 01:07:20,930 And then have pumpkin be the first value in that linked list and candy be 1437 01:07:20,930 --> 01:07:22,800 the second value in that linked list. 1438 01:07:22,800 --> 01:07:23,420 >> JASON HIRSCHHORN: OK. 1439 01:07:23,420 --> 01:07:24,670 Marcus, that was outstanding. 1440 01:07:24,670 --> 01:07:26,160 I'm going to break that down. 1441 01:07:26,160 --> 01:07:28,890 Marcus is saying don't overwrite pumpkin. 1442 01:07:28,890 --> 01:07:30,660 That would be bad. 1443 01:07:30,660 --> 01:07:33,640 Don't put candy somewhere else. 1444 01:07:33,640 --> 01:07:35,390 We're going to put them both at zero. 1445 01:07:35,390 --> 01:07:37,770 But we're going to deal with putting them at zero by 1446 01:07:37,770 --> 01:07:39,395 creating a list at zero. 1447 01:07:39,395 --> 01:07:42,430 And we're going to create a list of everything that mapped to zero. 1448 01:07:42,430 --> 01:07:47,960 And the best way we learned to create a list that can grow and shrink 1449 01:07:47,960 --> 01:07:49,840 dynamically is not within another array. 1450 01:07:49,840 --> 01:07:51,510 So not a multi-dimensional array. 1451 01:07:51,510 --> 01:07:54,080 But to just create a linked list. 1452 01:07:54,080 --> 01:07:55,330 >> So what he proposed-- 1453 01:07:55,330 --> 01:07:57,950 1454 01:07:57,950 --> 01:07:59,200 I'm going to get a new-- 1455 01:07:59,200 --> 01:08:15,380 1456 01:08:15,380 --> 01:08:19,689 is create an array with pointers, an array of pointers. 1457 01:08:19,689 --> 01:08:20,580 OK. 1458 01:08:20,580 --> 01:08:24,180 Any idea or hint what the type of this pointers should be? 1459 01:08:24,180 --> 01:08:26,290 Marcus? 1460 01:08:26,290 --> 01:08:27,250 >> AUDIENCE: Pointers to-- 1461 01:08:27,250 --> 01:08:28,609 >> JASON HIRSCHHORN: Because you said a linked list, so-- 1462 01:08:28,609 --> 01:08:29,520 >> AUDIENCE: Node pointers? 1463 01:08:29,520 --> 01:08:30,670 >> JASON HIRSCHHORN: Node pointers. 1464 01:08:30,670 --> 01:08:32,830 If the things in our linked list are nodes then they 1465 01:08:32,830 --> 01:08:34,370 should be node pointers. 1466 01:08:34,370 --> 01:08:35,939 And what do they equal initially? 1467 01:08:35,939 --> 01:08:36,990 >> AUDIENCE: Null. 1468 01:08:36,990 --> 01:08:38,240 >> JASON HIRSCHHORN: Null. 1469 01:08:38,240 --> 01:08:44,540 1470 01:08:44,540 --> 01:08:46,080 So there's our empty thing. 1471 01:08:46,080 --> 01:08:47,170 Pumpkin returns zero. 1472 01:08:47,170 --> 01:08:48,569 What do we do? 1473 01:08:48,569 --> 01:08:49,609 Walk me through it? 1474 01:08:49,609 --> 01:08:50,810 Actually, Marcus already gave me. 1475 01:08:50,810 --> 01:08:52,439 Somebody else walk me through it. 1476 01:08:52,439 --> 01:08:54,760 What we do when we-- 1477 01:08:54,760 --> 01:08:56,609 this looks very similar to what we were just doing. 1478 01:08:56,609 --> 01:08:57,396 Avi. 1479 01:08:57,396 --> 01:08:59,090 >> AUDIENCE: I'm going to take a guess. 1480 01:08:59,090 --> 01:09:01,250 So when you get candy. 1481 01:09:01,250 --> 01:09:01,640 >> JASON HIRSCHHORN: Yeah. 1482 01:09:01,640 --> 01:09:03,120 Well, we got pumpkin. 1483 01:09:03,120 --> 01:09:03,870 Let's get our first one. 1484 01:09:03,870 --> 01:09:04,324 We got pumpkin. 1485 01:09:04,324 --> 01:09:04,779 >> AUDIENCE: OK. 1486 01:09:04,779 --> 01:09:05,880 Pumpkin returns zero. 1487 01:09:05,880 --> 01:09:08,770 So you put it in that. 1488 01:09:08,770 --> 01:09:10,810 Or actually, you put it in the linked list. 1489 01:09:10,810 --> 01:09:13,550 >> JASON HIRSCHHORN: How do we put it in the linked list? 1490 01:09:13,550 --> 01:09:15,479 >> AUDIENCE: Oh, the actual syntax? 1491 01:09:15,479 --> 01:09:16,240 >> JASON HIRSCHHORN: Just walk-- 1492 01:09:16,240 --> 01:09:16,740 say more. 1493 01:09:16,740 --> 01:09:19,310 What do we do? 1494 01:09:19,310 --> 01:09:22,100 >> AUDIENCE: You just insert it as the first node. 1495 01:09:22,100 --> 01:09:22,675 >> JASON HIRSCHHORN: OK. 1496 01:09:22,675 --> 01:09:29,069 So we have our node, pumpkin. 1497 01:09:29,069 --> 01:09:31,560 And now how do I insert it? 1498 01:09:31,560 --> 01:09:34,590 1499 01:09:34,590 --> 01:09:37,090 >> AUDIENCE: You assign it to the pointer. 1500 01:09:37,090 --> 01:09:37,970 >> JASON HIRSCHHORN: Which pointer? 1501 01:09:37,970 --> 01:09:39,620 >> AUDIENCE: The pointer at zero. 1502 01:09:39,620 --> 01:09:41,420 >> JASON HIRSCHHORN: So where does this point? 1503 01:09:41,420 --> 01:09:42,810 >> AUDIENCE: To null right now. 1504 01:09:42,810 --> 01:09:43,529 >> JASON HIRSCHHORN: Well, it's pointing to null. 1505 01:09:43,529 --> 01:09:44,499 But I'm putting in pumpkin. 1506 01:09:44,499 --> 01:09:46,053 So where should it point? 1507 01:09:46,053 --> 01:09:46,880 >> AUDIENCE: To pumpkin. 1508 01:09:46,880 --> 01:09:47,399 >> JASON HIRSCHHORN: To pumpkin. 1509 01:09:47,399 --> 01:09:48,760 Exactly. 1510 01:09:48,760 --> 01:09:50,010 So this points to pumpkin. 1511 01:09:50,010 --> 01:09:52,500 1512 01:09:52,500 --> 01:09:54,250 And where does this pointer in pumpkin point? 1513 01:09:54,250 --> 01:09:57,986 1514 01:09:57,986 --> 01:09:58,340 To 1515 01:09:58,340 --> 01:09:58,590 >> AUDIENCE: Null. 1516 01:09:58,590 --> 01:09:59,210 >> JASON HIRSCHHORN: To null. 1517 01:09:59,210 --> 01:10:00,460 Exactly. 1518 01:10:00,460 --> 01:10:03,570 1519 01:10:03,570 --> 01:10:05,140 So we just inserted something into the linked list. 1520 01:10:05,140 --> 01:10:07,210 We just wrote this code to do this. 1521 01:10:07,210 --> 01:10:09,520 Almost we almost got it completely cracked. 1522 01:10:09,520 --> 01:10:10,790 Now we insert candy. 1523 01:10:10,790 --> 01:10:13,480 Our candy also goes to zero. 1524 01:10:13,480 --> 01:10:16,100 So what do we do with candy? 1525 01:10:16,100 --> 01:10:18,790 >> AUDIENCE: It depends on whether or not we're trying to sort it. 1526 01:10:18,790 --> 01:10:19,640 >> JASON HIRSCHHORN: That's exactly right. 1527 01:10:19,640 --> 01:10:21,070 It depends on whether or not we're trying to sort it. 1528 01:10:21,070 --> 01:10:22,660 Let's assume we're not going to sort it. 1529 01:10:22,660 --> 01:10:24,880 >> AUDIENCE: Well then, as we discussed before, it's simplest just to put it 1530 01:10:24,880 --> 01:10:28,590 right at the beginning so the pointer from zero points to candy. 1531 01:10:28,590 --> 01:10:29,020 >> JASON HIRSCHHORN: OK. 1532 01:10:29,020 --> 01:10:29,380 Hold on. 1533 01:10:29,380 --> 01:10:30,630 Let me create candy right here. 1534 01:10:30,630 --> 01:10:34,030 1535 01:10:34,030 --> 01:10:35,150 So this pointer-- 1536 01:10:35,150 --> 01:10:37,590 >> AUDIENCE: Yeah, should now be pointing to candy. 1537 01:10:37,590 --> 01:10:40,580 Then have the pointer from candy point to pumpkin. 1538 01:10:40,580 --> 01:10:43,140 1539 01:10:43,140 --> 01:10:44,560 >> JASON HIRSCHHORN: Like that? 1540 01:10:44,560 --> 01:10:47,380 And say we got another thing to map to zero? 1541 01:10:47,380 --> 01:10:48,660 >> AUDIENCE: Well, you just do the same thing? 1542 01:10:48,660 --> 01:10:50,290 >> JASON HIRSCHHORN: Do the same thing. 1543 01:10:50,290 --> 01:10:53,700 So in this case, if we don't want to keep it sorted it 1544 01:10:53,700 --> 01:10:55,270 sounds rather simple. 1545 01:10:55,270 --> 01:10:59,920 We take the pointer in the indice given by our hash function. 1546 01:10:59,920 --> 01:11:03,830 We have that point to our new node. 1547 01:11:03,830 --> 01:11:07,830 And then whatever it was pointing to previously-- 1548 01:11:07,830 --> 01:11:10,620 in this case null, in the second case pumpkin-- 1549 01:11:10,620 --> 01:11:15,310 that, whatever it's pointing to previously, we add into the next of 1550 01:11:15,310 --> 01:11:17,810 our new node. 1551 01:11:17,810 --> 01:11:19,650 We're inserting something in the beginning. 1552 01:11:19,650 --> 01:11:22,900 In fact this is a lot simpler than trying to keep the list sorted. 1553 01:11:22,900 --> 01:11:25,340 But again, searching will be more complicated on here. 1554 01:11:25,340 --> 01:11:28,300 We'll always have to go to the end. 1555 01:11:28,300 --> 01:11:29,650 >> OK. 1556 01:11:29,650 --> 01:11:32,750 Any questions about separate chaining? 1557 01:11:32,750 --> 01:11:34,690 How that works? 1558 01:11:34,690 --> 01:11:35,820 Please ask them now. 1559 01:11:35,820 --> 01:11:39,260 I really want to make sure you all understand this before we head out. 1560 01:11:39,260 --> 01:11:48,410 1561 01:11:48,410 --> 01:11:52,060 >> AUDIENCE: Why do you put pumpkin and candy into the same 1562 01:11:52,060 --> 01:11:54,108 part of the hash table? 1563 01:11:54,108 --> 01:11:55,860 >> JASON HIRSCHHORN: Good question. 1564 01:11:55,860 --> 01:11:59,140 Why do we put them in the same part of the hash table? 1565 01:11:59,140 --> 01:12:03,200 Well, in this case our hash function returns zero for both of them. 1566 01:12:03,200 --> 01:12:05,310 So they need to go at indice zero because that's where we're going to 1567 01:12:05,310 --> 01:12:07,420 look for them if we ever want to look them up. 1568 01:12:07,420 --> 01:12:11,750 Again, with a linear probing approach we wouldn't put them both at zero. 1569 01:12:11,750 --> 01:12:13,900 But in the separate chain approach, we're going to put them both at zero 1570 01:12:13,900 --> 01:12:16,620 and then create a list off of zero. 1571 01:12:16,620 --> 01:12:20,140 >> And we don't want to overwrite pumpkin simply for that because then we'll 1572 01:12:20,140 --> 01:12:21,860 assume that pumpkin was never inserted. 1573 01:12:21,860 --> 01:12:25,230 If we just keep one thing in the location that would be bad. 1574 01:12:25,230 --> 01:12:28,590 Then there would be no chance of us ever-- 1575 01:12:28,590 --> 01:12:31,660 if we ever had a duplicate, then we would just erase our initial value. 1576 01:12:31,660 --> 01:12:34,090 So that's why we do this approach. 1577 01:12:34,090 --> 01:12:36,580 Or that's why we chose-- but again, we chose the separate chaining approach, 1578 01:12:36,580 --> 01:12:39,670 which there are many other approaches one could choose. 1579 01:12:39,670 --> 01:12:41,185 Does that answer your question? 1580 01:12:41,185 --> 01:12:41,660 >> OK. 1581 01:12:41,660 --> 01:12:42,910 Carlos. 1582 01:12:42,910 --> 01:12:46,130 1583 01:12:46,130 --> 01:12:47,720 Linear probing would involve-- 1584 01:12:47,720 --> 01:12:51,913 if we found a collision at zero, we would look in the next spot to see if 1585 01:12:51,913 --> 01:12:54,310 it was open and put it there. 1586 01:12:54,310 --> 01:12:57,320 And then we look in the next sport and see if that was open and put it there. 1587 01:12:57,320 --> 01:12:59,780 So we find the next available open spot and put it there. 1588 01:12:59,780 --> 01:13:02,580 1589 01:13:02,580 --> 01:13:03,890 Any other questions? 1590 01:13:03,890 --> 01:13:05,370 Yeah, Avi. 1591 01:13:05,370 --> 01:13:07,490 >> AUDIENCE: As a follow up to that, what do you mean by next spot? 1592 01:13:07,490 --> 01:13:10,250 In the hash table or in a linked list. 1593 01:13:10,250 --> 01:13:12,100 >> JASON HIRSCHHORN: For linear programming, no linked lists. 1594 01:13:12,100 --> 01:13:13,400 The next spot on the hash table. 1595 01:13:13,400 --> 01:13:13,820 >> AUDIENCE: OK. 1596 01:13:13,820 --> 01:13:17,570 So the hash table would be initialized to the size-- 1597 01:13:17,570 --> 01:13:19,560 like the number of strings that you were inserting? 1598 01:13:19,560 --> 01:13:22,170 >> JASON HIRSCHHORN: You would want it to be really big. 1599 01:13:22,170 --> 01:13:23,910 Yes. 1600 01:13:23,910 --> 01:13:27,900 Here is a picture of what we just drew on the board. 1601 01:13:27,900 --> 01:13:29,470 Again, we have a collision right here. 1602 01:13:29,470 --> 01:13:30,710 at 152. 1603 01:13:30,710 --> 01:13:33,570 And you'll see we created a linked list off of it. 1604 01:13:33,570 --> 01:13:38,200 1605 01:13:38,200 --> 01:13:41,850 Again, the hash table separate chaining approach is not the one you 1606 01:13:41,850 --> 01:13:45,590 have to take for problems set six but is one that a lot of 1607 01:13:45,590 --> 01:13:47,100 students tend to take. 1608 01:13:47,100 --> 01:13:51,140 So on that note, let us talk briefly before we head out about problem six, 1609 01:13:51,140 --> 01:13:52,160 and then I'll share a story with you. 1610 01:13:52,160 --> 01:13:55,120 We have three minutes. 1611 01:13:55,120 --> 01:13:55,750 >> Problem set six. 1612 01:13:55,750 --> 01:13:57,790 You have four functions-- 1613 01:13:57,790 --> 01:14:02,430 load, check, size, and unload. 1614 01:14:02,430 --> 01:14:03,380 Load-- 1615 01:14:03,380 --> 01:14:07,120 well, we've been going over load just now. 1616 01:14:07,120 --> 01:14:09,330 We drew load on the board. 1617 01:14:09,330 --> 01:14:13,230 And we even started coding a lot of inserting into a linked list. 1618 01:14:13,230 --> 01:14:18,020 So load is not much more than what we've just been doing. 1619 01:14:18,020 --> 01:14:21,070 >> Check is once you have something loaded. 1620 01:14:21,070 --> 01:14:22,580 It's the same process as this. 1621 01:14:22,580 --> 01:14:26,845 The same first two parts where you throw something into the hash function 1622 01:14:26,845 --> 01:14:29,190 and get its value. 1623 01:14:29,190 --> 01:14:30,700 But now we're not inserting it. 1624 01:14:30,700 --> 01:14:33,350 Now we're looking for it. 1625 01:14:33,350 --> 01:14:37,130 I have sample code written for finding something in a linked list. 1626 01:14:37,130 --> 01:14:38,250 I encourage you to practice that. 1627 01:14:38,250 --> 01:14:43,000 But intuitively finding something is pretty similar to inserting something. 1628 01:14:43,000 --> 01:14:46,540 Indeed, we drew a picture of finding something in a linked list, moving 1629 01:14:46,540 --> 01:14:48,910 through until you got to the end. 1630 01:14:48,910 --> 01:14:52,430 And if you got to the end and couldn't find it, then it's not there. 1631 01:14:52,430 --> 01:14:55,400 So that's check, essentially. 1632 01:14:55,400 --> 01:14:57,030 >> Next is size. 1633 01:14:57,030 --> 01:14:57,910 Let's skip size. 1634 01:14:57,910 --> 01:15:00,040 Finally you have unload. 1635 01:15:00,040 --> 01:15:02,890 Unload is one we haven't drawn on the board or coded yet. 1636 01:15:02,890 --> 01:15:05,990 But I encourage you to try coding it in our sample linked list example. 1637 01:15:05,990 --> 01:15:11,440 But unload intuitively is similar to free-- 1638 01:15:11,440 --> 01:15:14,010 or I mean is similar to check. 1639 01:15:14,010 --> 01:15:17,350 Except for now each time you're going through, you're not simply checking to 1640 01:15:17,350 --> 01:15:19,090 see if you have your value there. 1641 01:15:19,090 --> 01:15:22,490 But you're taking that node and freeing it, essentially. 1642 01:15:22,490 --> 01:15:23,610 That's what unload asks you to do. 1643 01:15:23,610 --> 01:15:24,670 Free everything you've malloced. 1644 01:15:24,670 --> 01:15:27,480 So you're going through the whole list again, going through the whole hash 1645 01:15:27,480 --> 01:15:27,760 table again. 1646 01:15:27,760 --> 01:15:29,240 This time don't check to see what's there. 1647 01:15:29,240 --> 01:15:31,080 Just free what's there. 1648 01:15:31,080 --> 01:15:33,260 >> And finally size. 1649 01:15:33,260 --> 01:15:34,350 Size should be implemented. 1650 01:15:34,350 --> 01:15:35,590 If you do not implement size-- 1651 01:15:35,590 --> 01:15:36,250 I'll say it like this. 1652 01:15:36,250 --> 01:15:39,740 If you do not implement size in exactly one line of code including the 1653 01:15:39,740 --> 01:15:43,760 return statement, you are doing size incorrectly. 1654 01:15:43,760 --> 01:15:47,170 So make sure size, for full design points, you're doing it in exactly one 1655 01:15:47,170 --> 01:15:49,970 line of code, including the return statement. 1656 01:15:49,970 --> 01:15:52,450 >> And don't pack up yet, Akchar. 1657 01:15:52,450 --> 01:15:53,700 Eager beaver. 1658 01:15:53,700 --> 01:15:55,820 1659 01:15:55,820 --> 01:16:01,300 I wanted to say thank you guys for coming to section. 1660 01:16:01,300 --> 01:16:02,550 Have a Happy Halloween. 1661 01:16:02,550 --> 01:16:05,300 1662 01:16:05,300 --> 01:16:05,960 This is my costume. 1663 01:16:05,960 --> 01:16:08,850 I'll be wearing this on Thursday if I see you at office hours. 1664 01:16:08,850 --> 01:16:14,640 And if you're curious about some more background as to this costume, feel 1665 01:16:14,640 --> 01:16:19,135 free to check out 2011 section for a story on why I'm 1666 01:16:19,135 --> 01:16:20,900 wearing the pumpkin costume. 1667 01:16:20,900 --> 01:16:23,680 And it is a sad story. 1668 01:16:23,680 --> 01:16:27,050 So make sure you have some tissues nearby. 1669 01:16:27,050 --> 01:16:28,680 But on that, if you have any questions I'll stick around 1670 01:16:28,680 --> 01:16:29,960 outside after section. 1671 01:16:29,960 --> 01:16:31,510 Good luck on problem set six. 1672 01:16:31,510 --> 01:16:33,540 And as always, if you have any questions, let me know. 1673 01:16:33,540 --> 01:16:35,584