1 00:00:00,000 --> 00:00:08,000 2 00:00:08,000 --> 00:00:09,000 3 00:00:09,000 --> 00:00:12,000 This presentation is delivered by the Stanford Center for Professional 4 00:00:12,000 --> 00:00:21,000 Development. 5 00:00:21,000 --> 00:00:23,000 Hey there. 6 00:00:23,000 --> 00:00:28,000 Okay, we'll start with talking about just where we're at in terms of material, right, 7 00:00:28,000 --> 00:00:31,000 as we're gonna keep talking about pointers, which we just got started with 8 00:00:31,000 --> 00:00:35,000 on Monday, and go on to use them to do some stuff with recursive data in the 9 00:00:35,000 --> 00:00:38,000 form of a link list. 10 00:00:38,000 --> 00:00:40,000 All right, 11 00:00:40,000 --> 00:00:42,000 let me 12 00:00:42,000 --> 00:00:46,000 -let me show you some code. I'm going to keep talking about the pointer idea, draw some pictures to try to get a 13 00:00:46,000 --> 00:00:48,000 visualization of what's going on, 14 00:00:48,000 --> 00:00:53,000 and then I'm going to go on to show you some of the things you do with pointers. What are 15 00:00:53,000 --> 00:00:56,000 pointers good for, right? Right now, it seems like it's kind of an obscure way to 16 00:00:56,000 --> 00:01:00,000 get at things you already know how to do. I'm going to show you some of the things that then it 17 00:01:00,000 --> 00:01:04,000 enables you to do that you couldn't do if you didn't have the pointer around. 18 00:01:04,000 --> 00:01:07,000 So I've got a little bit of code, right, that declares some variables, and I'm gonna draw the 19 00:01:07,000 --> 00:01:09,000 same picture I had at the end, right, 20 00:01:09,000 --> 00:01:14,000 that what is the stack frame for main look like? It's got an integer num, 21 00:01:14,000 --> 00:01:19,000 and it has two pointer variables, P and Q, and 22 00:01:19,000 --> 00:01:23,000 those things actually all live in the stack. So stack variables are those that you declare kind 23 00:01:23,000 --> 00:01:25,000 of as you open a 24 00:01:25,000 --> 00:01:27,000 scope, as you enter a function, things like that. 25 00:01:27,000 --> 00:01:31,000 Space for them is automatically allocated and de-allocated. You never see explicit news 26 00:01:31,000 --> 00:01:33,000 or deletes on those that are there. 27 00:01:33,000 --> 00:01:37,000 Those pointers, as they are 28 00:01:37,000 --> 00:01:39,000 set up here, have not been initialized. 29 00:01:39,000 --> 00:01:43,000 So just like num has some junk contents, right, 30 00:01:43,000 --> 00:01:45,000 so if I have just a declared numb 31 00:01:45,000 --> 00:01:49,000 and then I do cout, 32 00:01:49,000 --> 00:01:50,000 num, 33 00:01:50,000 --> 00:01:52,000 endl, 34 00:01:52,000 --> 00:01:56,000 then I'll get some junk number. It might be zero, it could be 35 00:01:56,000 --> 00:01:58,000 6,452, it could be negative 75. 36 00:01:58,000 --> 00:01:59,000 We don't know what it is, right, 37 00:01:59,000 --> 00:02:04,000 but accessing it, right, is technically legal, right? It won't complain to you about it, 38 00:02:04,000 --> 00:02:08,000 right, but it's unlikely to produce any valid result. 39 00:02:08,000 --> 00:02:11,000 Similarly with pointers, if I say P and Q, right, 40 00:02:11,000 --> 00:02:13,000 without saying what they're assigned to, 41 00:02:13,000 --> 00:02:15,000 then these have junk addresses in 42 00:02:15,000 --> 00:02:16,000 them 43 00:02:16,000 --> 00:02:17,000 -junk numbers. 44 00:02:17,000 --> 00:02:21,000 Now this turns out to be a little bit more dangerous, the use of an uninitialized 45 00:02:21,000 --> 00:02:23,000 pointer relative than an 46 00:02:23,000 --> 00:02:24,000 uninitialized variable, 47 00:02:24,000 --> 00:02:26,000 that if I were just to look at that number, 48 00:02:26,000 --> 00:02:30,000 that's unlikely to get me into trouble. If I try to follow that address as though it 49 00:02:30,000 --> 00:02:32,000 were a good address, 50 00:02:32,000 --> 00:02:35,000 that's when you end up with Binky's head getting blown off. 51 00:02:35,000 --> 00:02:38,000 If I've done nothing to P and Q 52 00:02:38,000 --> 00:02:39,000 and I say 53 00:02:39,000 --> 00:02:43,000 star P equals 42, 54 00:02:43,000 --> 00:02:48,000 it takes this junk contents, which is, like, some address to somewhere, 55 00:02:48,000 --> 00:02:50,000 and follows it and tries to write a 42. 56 00:02:50,000 --> 00:02:54,000 There's no guarantee, for example, that that number, that address there is valid, 57 00:02:54,000 --> 00:02:58,000 that it actually makes sense, that it actually even kind of exists in terms of the 58 00:02:58,000 --> 00:02:59,000 process space so far. 59 00:02:59,000 --> 00:03:03,000 It's kind of like calling a phone number just by dialing random digits on the phone. 60 00:03:03,000 --> 00:03:06,000 It's, like, more likely than not, right, you're gonna get the, you know, that number's been 61 00:03:06,000 --> 00:03:07,000 disconnected. 62 00:03:07,000 --> 00:03:11,000 It might be that you'll randomly call somebody and start having a phone 63 00:03:11,000 --> 00:03:13,000 conversation with them. The same with this 42. It's like it might be that 64 00:03:13,000 --> 00:03:17,000 it'll write somewhere and start storing a 42, but on top of something that 65 00:03:17,000 --> 00:03:20,000 wasn't intended to have that kind of adjustment made to it. 66 00:03:20,000 --> 00:03:23,000 So it's a very dangerous operation, right, that can lead to 67 00:03:23,000 --> 00:03:25,000 strange results, immediate crashes, 68 00:03:25,000 --> 00:03:29,000 you know, other strange results later on, when you didn't plan on it, other things 69 00:03:29,000 --> 00:03:32,000 changing that you weren't expecting because of this 70 00:03:32,000 --> 00:03:34,000 improper access. 71 00:03:34,000 --> 00:03:38,000 So P and Q, right, sort of that -if I see P equals new int, 72 00:03:38,000 --> 00:03:41,000 then over here in the heap, 73 00:03:41,000 --> 00:03:43,000 so 74 00:03:43,000 --> 00:03:47,000 stack here, heap over here, 75 00:03:47,000 --> 00:03:48,000 76 00:03:48,000 --> 00:03:50,000 P points to a new integer variable 77 00:03:50,000 --> 00:03:53,000 stored out in the heap, and now that's star P equals 10. 78 00:03:53,000 --> 00:03:56,000 So that word pointee, that's a Nick made-up word. No 79 00:03:56,000 --> 00:04:00,000 -you won't hear that pretty much anywhere other than the 80 00:04:00,000 --> 00:04:03,000 Binky pointer video, and sometimes I use it too, because I think it's a cute word. 81 00:04:03,000 --> 00:04:07,000 But it is not quite the official term for that, 82 00:04:07,000 --> 00:04:09,000 so P pointing to this integer out in the heap. 83 00:04:09,000 --> 00:04:12,000 And then I have these two lines that I talked about last time that I want to review what's 84 00:04:12,000 --> 00:04:14,000 going on 85 00:04:14,000 --> 00:04:15,000 that 86 00:04:15,000 --> 00:04:19,000 star P, right, it's a star Q, any time you see the pointer with that star on it, right, that's 87 00:04:19,000 --> 00:04:21,000 applying the dereference. And so it's saying 88 00:04:21,000 --> 00:04:24,000 we're not talking about manipulating the pointer itself, but what's at the other 89 00:04:24,000 --> 00:04:27,000 end of it. So reaching out to the integer. 90 00:04:27,000 --> 00:04:29,000 So the way P is declared there, I want to say 91 00:04:29,000 --> 00:04:31,000 P is a pointer to an integer, then the 92 00:04:31,000 --> 00:04:34,000 type of the expression star P is integer type. It 93 00:04:34,000 --> 00:04:35,000 refers to the integer that 94 00:04:35,000 --> 00:04:38,000 it is pointing to, which in this case is out in the heap. 95 00:04:38,000 --> 00:04:39,000 And so if I said 96 00:04:39,000 --> 00:04:42,000 Q equals new int, 97 00:04:42,000 --> 00:04:43,000 it gets a space out in the heap. 98 00:04:43,000 --> 00:04:46,000 And then when I say star Q equals star P, 99 00:04:46,000 --> 00:04:47,000 that says 100 00:04:47,000 --> 00:04:49,000 right to the integer out here, 101 00:04:49,000 --> 00:04:54,000 having read an integer from there to copy. So it copies the integer value 102 00:04:54,000 --> 00:04:58,000 that P is pointing to on top of the integer value Q is pointing to. 103 00:04:58,000 --> 00:05:00,000 So copying the integers. 104 00:05:00,000 --> 00:05:03,000 The next line, where the stars are not present, where it just says Q equals P, 105 00:05:03,000 --> 00:05:05,000 that is doing just 106 00:05:05,000 --> 00:05:08,000 pointer assignment. In this case, it's manipulating the pointers themselves, not what 107 00:05:08,000 --> 00:05:13,000 they point -the integers that they're pointing to. So when I say Q equals P, it 108 00:05:13,000 --> 00:05:16,000 effectively copies the address 109 00:05:16,000 --> 00:05:22,000 that P has. So P is pointing to the address, you know, 30,012, and so 110 00:05:22,000 --> 00:05:24,000 what's really 111 00:05:24,000 --> 00:05:28,000 at sort of the lowest level is actually written this number here. Then it writes that same 112 00:05:28,000 --> 00:05:30,000 number in this box, 113 00:05:30,000 --> 00:05:32,000 which causes Q 114 00:05:32,000 --> 00:05:36,000 to point to the same place as P now. And so changing 115 00:05:36,000 --> 00:05:41,000 star P, changing star Q, actually both of them actually are sharing or aliasing, 116 00:05:41,000 --> 00:05:44,000 and so there's only one integer that now we have two different 117 00:05:44,000 --> 00:05:48,000 ways of getting to via these two different pointers. 118 00:05:48,000 --> 00:05:51,000 So here's a little trick about C++, right, that's unique 119 00:05:51,000 --> 00:05:53,000 to those of you who've come from the Java world, is that it is your 120 00:05:53,000 --> 00:05:56,000 responsibility to deallocate things that come out of the heap. 121 00:05:56,000 --> 00:05:58,000 So whereas on the stack 122 00:05:58,000 --> 00:06:00,000 memory is allocated and deallocated automatically, 123 00:06:00,000 --> 00:06:04,000 everything in the heap is explicitly allocated and explicitly deallocated. 124 00:06:04,000 --> 00:06:08,000 If I say new, it made some space and set it aside and reserved it for my purpose in 125 00:06:08,000 --> 00:06:10,000 the heap, great. 126 00:06:10,000 --> 00:06:11,000 When I'm done with it, 127 00:06:11,000 --> 00:06:16,000 when I no longer need that piece of memory, I've discarded it, I've, you know, removed it, that 128 00:06:16,000 --> 00:06:19,000 student graduated, whatever it is that causes me to no longer need it, 129 00:06:19,000 --> 00:06:23,000 then it is the responsibility of the programmer to issue the delete call using the 130 00:06:23,000 --> 00:06:24,000 delete operator 131 00:06:24,000 --> 00:06:27,000 on the pointer to say, follow this pointer 132 00:06:27,000 --> 00:06:30,000 and take the space that it's currently pointing to 133 00:06:30,000 --> 00:06:31,000 and mark it as reclaimable 134 00:06:31,000 --> 00:06:36,000 -no longer in use, ready to be vacated for someone else's purposes. 135 00:06:36,000 --> 00:06:38,000 So when I say delete P, it 136 00:06:38,000 --> 00:06:41,000 causes the heap manager to say, oh, okay, 137 00:06:41,000 --> 00:06:42,000 this address 138 00:06:42,000 --> 00:06:44,000 is now 139 00:06:44,000 --> 00:06:46,000 free or available. 140 00:06:46,000 --> 00:06:51,000 As a consequence of that, it may or may not actually do anything right away with 141 00:06:51,000 --> 00:06:52,000 that piece of memory. 142 00:06:52,000 --> 00:06:55,000 It might be that what it just did was mark it as available, kind of it's sort of like 143 00:06:55,000 --> 00:06:58,000 having a list of vacancies in an apartment building. 144 00:06:58,000 --> 00:07:01,000 You might say okay, well, 145 00:07:01,000 --> 00:07:04,000 I'm moving out of apartment 100. You might say oh, okay, well, apartment 100 146 00:07:04,000 --> 00:07:07,000 is empty. It may go in and clean the apartment, it might go in and kind of write 147 00:07:07,000 --> 00:07:10,000 something over it, it may not. There's actually no guarantees there. 148 00:07:10,000 --> 00:07:13,000 But it does mean that now if somebody comes in and wants an apartment, right, we 149 00:07:13,000 --> 00:07:16,000 could give them that one. So if somebody asks for a new integer, we might give them 150 00:07:16,000 --> 00:07:20,000 that address, 30,012, because we no longer have it marked as being in 151 00:07:20,000 --> 00:07:21,000 use. 152 00:07:21,000 --> 00:07:23,000 So if you 153 00:07:23,000 --> 00:07:26,000 were to delete something and then start to use it again, 154 00:07:26,000 --> 00:07:30,000 so if I deleted P and then tried to do this -star P, 155 00:07:30,000 --> 00:07:31,000 you know, equals 100, 156 00:07:31,000 --> 00:07:33,000 I'm asking for trouble. 157 00:07:33,000 --> 00:07:37,000 That piece of memory has been deallocated, it might be in use somewhere else. 158 00:07:37,000 --> 00:07:40,000 At this point, I don't own it anymore, I don't have that reservation. It's kind of like 159 00:07:40,000 --> 00:07:44,000 using your keys to get back into that apartment that you've moved out of. It's like well, 160 00:07:44,000 --> 00:07:46,000 someday, somebody else's stuff is going to be in there, right? 161 00:07:46,000 --> 00:07:49,000 And you are squatting, right? You can be arrested for that. 162 00:07:49,000 --> 00:07:52,000 Well, in C++, right, you can receive program crashes and other kind of 163 00:07:52,000 --> 00:07:54,000 mystical behavior from that, 164 00:07:54,000 --> 00:07:57,000 and so it is something we have to be a little careful about. When we're done we say 165 00:07:57,000 --> 00:07:59,000 delete, but not before, 166 00:07:59,000 --> 00:08:03,000 and that once we have said delete we don't reference that piece of 167 00:08:03,000 --> 00:08:03,000 memory 168 00:08:03,000 --> 00:08:05,000 169 00:08:05,000 --> 00:08:07,000 after it's been deleted. I put a 170 00:08:07,000 --> 00:08:09,000 little note here. I said, well, delete Q. 171 00:08:09,000 --> 00:08:11,000 So here's a thing to note, is that we delete 172 00:08:11,000 --> 00:08:14,000 things that we allocated new on. It is not the case that we 173 00:08:14,000 --> 00:08:18,000 delete every pointer, though. If we have five pointers that point to one piece of 174 00:08:18,000 --> 00:08:20,000 memory, if I delete it, no matter which pointer, 175 00:08:20,000 --> 00:08:22,000 you know, I used when I made the delete call, 176 00:08:22,000 --> 00:08:26,000 they all hold the same address, and I deleted what was at that address. So if I've 177 00:08:26,000 --> 00:08:29,000 deleted the address 30,012, no 178 00:08:29,000 --> 00:08:32,000 matter how many other pointers hold that same address and point to that same place, 179 00:08:32,000 --> 00:08:34,000 I do not make multiple delete calls. 180 00:08:34,000 --> 00:08:38,000 So in this case, if I did delete P and delete Q where they're currently aliased, right, 181 00:08:38,000 --> 00:08:42,000 I would be trying to delete a piece of memory that's already deleted. 182 00:08:42,000 --> 00:08:45,000 Again, no guarantees about whether this will produce an immediate bad effect 183 00:08:45,000 --> 00:08:49,000 or some later bad effect, or maybe just turn into a no-op, but 184 00:08:49,000 --> 00:08:53,000 no matter what, it's not a good practice to get into of 185 00:08:53,000 --> 00:08:55,000 accidentally deleting things more than once. 186 00:08:55,000 --> 00:08:59,000 So a little bit more management on our part, right, than we're used to in Java, 187 00:08:59,000 --> 00:09:02,000 and then that last little bit of code I showed at the bottom, right, was just the use of 188 00:09:02,000 --> 00:09:07,000 Null, capital N-U-L-L, which is the C++ equivalent of the Java 189 00:09:07,000 --> 00:09:10,000 lowercase null, it's the zero pointer, and it's used as the sentinel value. 190 00:09:10,000 --> 00:09:12,000 191 00:09:12,000 --> 00:09:15,000 Typically when you have a pointer that you know doesn't point anywhere, you use that 192 00:09:15,000 --> 00:09:18,000 to say, well, here it is, I'm going to initialize it to Null so I know that that's the known 193 00:09:18,000 --> 00:09:21,000 sentinel value that says there's no 194 00:09:21,000 --> 00:09:25,000 current address that it's holding. 195 00:09:25,000 --> 00:09:28,000 So very much some of the things you've already seen in Java, right, this idea of having 196 00:09:28,000 --> 00:09:32,000 declaring things, and calling new to get new things that are out in the heap. The 197 00:09:32,000 --> 00:09:35,000 delete step is certainly new. 198 00:09:35,000 --> 00:09:38,000 It's one we'll work our way up to. To be honest, 199 00:09:38,000 --> 00:09:40,000 to be fair, if you 200 00:09:40,000 --> 00:09:42,000 just had no delete calls in your program, 201 00:09:42,000 --> 00:09:45,000 the consequence would be that pieces of memory like this one that I allocated 202 00:09:45,000 --> 00:09:47,000 under Q and then later 203 00:09:47,000 --> 00:09:49,000 lost track of would be orphaned. 204 00:09:49,000 --> 00:09:50,000 And so we'd end up 205 00:09:50,000 --> 00:09:54,000 having a bunch of memory that we had set aside and reserved for our use that we 206 00:09:54,000 --> 00:09:57,000 weren't currently using. If we kept doing that over a long period of time, we'd 207 00:09:57,000 --> 00:10:01,000 eventually kind of clog the heap with a bunch of waste 208 00:10:01,000 --> 00:10:03,000 that would not be reclaimable 209 00:10:03,000 --> 00:10:06,000 and it could slow the program down and even in an extreme case, right, could 210 00:10:06,000 --> 00:10:11,000 cause your machine to have significant performance problems. 211 00:10:11,000 --> 00:10:14,000 For the shape of programs we write and the size of them and the amount of 212 00:10:14,000 --> 00:10:16,000 running time they are, 213 00:10:16,000 --> 00:10:20,000 not having deletes in them is actually kind of not a particularly tragic result. 214 00:10:20,000 --> 00:10:23,000 So often, right, we'll encourage you to write programs without delete in them where you make 215 00:10:23,000 --> 00:10:25,000 news, and 216 00:10:25,000 --> 00:10:28,000 work your way up to putting deletes in, because in fact, right, they're tricky to 217 00:10:28,000 --> 00:10:31,000 get right and if you get them wrong, the consequences are sort of more deadly 218 00:10:31,000 --> 00:10:34,000 than just having the orphans 219 00:10:34,000 --> 00:10:35,000 get 220 00:10:35,000 --> 00:10:38,000 filled up in your heap. All 221 00:10:38,000 --> 00:10:43,000 right, so any questions on kind of the basic little set up here? Student:So the pointee or whatever, of Q 222 00:10:43,000 --> 00:10:46,000 original one? Yeah? Student:There's no way 223 00:10:46,000 --> 00:10:50,000 to delete it anyway? There's no way to get -I lost its address, right? I didn't 224 00:10:50,000 --> 00:10:54,000 store it anywhere, so it gave me this address. Maybe this is a, you know, 225 00:10:54,000 --> 00:10:55,000 address, 226 00:10:55,000 --> 00:10:57,000 48,012, that 227 00:10:57,000 --> 00:10:59,000 it gave me that address, I wrote it down, 228 00:10:59,000 --> 00:11:02,000 right, and then I overwrote it with something else. And so I no longer have it. 229 00:11:02,000 --> 00:11:05,000 So unless I put it somewhere, right, I have no way to know where that piece of 230 00:11:05,000 --> 00:11:08,000 memory is. Student:[Inaudible] 231 00:11:08,000 --> 00:11:11,000 Why wouldn't it be, like, delete star P? 232 00:11:11,000 --> 00:11:16,000 Well, you know, it's interesting, it kind of feels a little bit more like it's delete 233 00:11:16,000 --> 00:11:18,000 star this, right? It's like delete was at the other end. But it just happens to be that the 234 00:11:18,000 --> 00:11:23,000 operator takes the address itself, not the number that's at the other end or the 235 00:11:23,000 --> 00:11:25,000 string or whatever it's a pointer to, so, 236 00:11:25,000 --> 00:11:29,000 the operator. So it takes a pointer and it says take the contents at that address and mark it 237 00:11:29,000 --> 00:11:33,000 as available for someone else's use. Student:Is P [inaudible]? 238 00:11:33,000 --> 00:11:36,000 Student:So P still holds the same value. That's a great question, right? So P had 239 00:11:36,000 --> 00:11:37,000 30,012. 240 00:11:37,000 --> 00:11:39,000 I said delete 30,012. 241 00:11:39,000 --> 00:11:42,000 The heap manager took that request and kind of marketed it, 242 00:11:42,000 --> 00:11:45,000 but P still holds that address. And so if I did a star P equals 100, it tries 243 00:11:45,000 --> 00:11:49,000 to right back there. So in fact the delete operation doesn't change P. 244 00:11:49,000 --> 00:11:54,000 So it still holds the same address. So to be really careful about it I might want to say if 245 00:11:54,000 --> 00:11:58,000 I set it to delete P, I could set P equal to Null right after it, kind of as a safety 246 00:11:58,000 --> 00:12:00,000 catch for myself, to remind myself that 247 00:12:00,000 --> 00:12:03,000 whatever number it used to have is no longer valid. That address, right, is no 248 00:12:03,000 --> 00:12:05,000 longer mine to reference. 249 00:12:05,000 --> 00:12:08,000 So as a habit, some programmers do do that. 250 00:12:08,000 --> 00:12:11,000 Every time they make a delete call, the next thing they do is set that pointer to Null so 251 00:12:11,000 --> 00:12:14,000 that they don't actually even have a chance of reusing that address that no longer 252 00:12:14,000 --> 00:12:19,000 is valid. 253 00:12:19,000 --> 00:12:23,000 So this kind of control actually is really valuable. At first glance it just seems 254 00:12:23,000 --> 00:12:26,000 like it's like extra work. It's like well now not only do I have to allocate, I 255 00:12:26,000 --> 00:12:27,000 also have to deallocate. 256 00:12:27,000 --> 00:12:32,000 But that gives you actually very good control of exactly when it got allocated and exactly 257 00:12:32,000 --> 00:12:35,000 when it got deallocated, and that means you can control the memory usage of your 258 00:12:35,000 --> 00:12:38,000 program very precisely 259 00:12:38,000 --> 00:12:39,000 in a way that in Java, 260 00:12:39,000 --> 00:12:43,000 Java doesn't actually let you get involved in this. You can allocate things, but it 261 00:12:43,000 --> 00:12:45,000 decides when and where it's going to start doing deallocation. It may wait until 262 00:12:45,000 --> 00:12:49,000 it thinks that there's a need to do this what's called garbage collection, it may do 263 00:12:49,000 --> 00:12:52,000 it a little bit all the time, it may do a big bunch at one time. And 264 00:12:52,000 --> 00:12:56,000 it doesn't give you control in the way that C++ really just leaves it up to you. You 265 00:12:56,000 --> 00:12:59,000 decide when you needed something and when you're done with it, 266 00:12:59,000 --> 00:13:04,000 which does actually, for professional programmers, considered a real advantage in very 267 00:13:04,000 --> 00:13:05,000 precisely 268 00:13:05,000 --> 00:13:11,000 dictating about how memory gets used, and when and where. 269 00:13:11,000 --> 00:13:12,000 So a couple things 270 00:13:12,000 --> 00:13:15,000 that I just -things I wanted to remind you before we went on 271 00:13:15,000 --> 00:13:17,000 to do some other things, right, 272 00:13:17,000 --> 00:13:19,000 is that pointers are distinguished by the type of the pointee. 273 00:13:19,000 --> 00:13:23,000 That you can have a pointer to a double, a pointer to a string, a pointer to a 274 00:13:23,000 --> 00:13:23,000 scanner. 275 00:13:23,000 --> 00:13:25,000 You know, any of the types you have seen, right, 276 00:13:25,000 --> 00:13:29,000 there is a corresponding star of that type that is a pointer to one of those 277 00:13:29,000 --> 00:13:30,000 things. 278 00:13:30,000 --> 00:13:35,000 There are, in fact, right, pointers to pointers. We're not going to see that 279 00:13:35,000 --> 00:13:39,000 too commonly in this quarter, but there are, for example, int double stars, 280 00:13:39,000 --> 00:13:42,000 which is a pointer to something which is a pointer to an integer. That has kind of two arrows 281 00:13:42,000 --> 00:13:45,000 that lead to an integer, finally. 282 00:13:45,000 --> 00:13:49,000 All of these pointers, right, are distinguishable types 283 00:13:49,000 --> 00:13:49,000 that if, you know, two things that 284 00:13:49,000 --> 00:13:52,000 both point to double are the same type of pointer, but a pointer to a 285 00:13:52,000 --> 00:13:56,000 double is not the same thing as a pointer to an integer, which is not the same thing as a pointer to 286 00:13:56,000 --> 00:13:58,000 a string. So actually, the type system 287 00:13:58,000 --> 00:14:01,000 considers these different kinds of pointers to be different. 288 00:14:01,000 --> 00:14:05,000 In truth, right, the way they're being managed behind the scenes is they are all just addresses, 289 00:14:05,000 --> 00:14:07,000 but it is important to know that 290 00:14:07,000 --> 00:14:10,000 what's at the end of that address is an int as opposed to what being at that 291 00:14:10,000 --> 00:14:13,000 address as a string. And the compiler does strongly enforce this idea 292 00:14:13,000 --> 00:14:14,000 that 293 00:14:14,000 --> 00:14:17,000 if you told me what's at that address is a string, then it wouldn't be appropriate to 294 00:14:17,000 --> 00:14:20,000 suddenly start treating what's at that address as though it were an integer. So it actually 295 00:14:20,000 --> 00:14:23,000 doesn't allow you to kind of mix those types up. 296 00:14:23,000 --> 00:14:26,000 Now pointers are uninitialized until they're assigned. When you declare a pointer, right, you 297 00:14:26,000 --> 00:14:28,000 just get a junk address 298 00:14:28,000 --> 00:14:31,000 dereferencing it either to read or to write some of that contents, right, is just 299 00:14:31,000 --> 00:14:33,000 asking for 300 00:14:33,000 --> 00:14:34,000 bad trouble. 301 00:14:34,000 --> 00:14:38,000 The consequences are not that predictable, so one of the things I had tried to say 302 00:14:38,000 --> 00:14:40,000 last time was one of the reasons I think pointers are 303 00:14:40,000 --> 00:14:43,000 considered a little bit scary is because 304 00:14:43,000 --> 00:14:45,000 there are certain opportunities to make mistakes here, and those mistakes have 305 00:14:45,000 --> 00:14:50,000 pretty drastic consequences. Using an uninitialized integer is not that terrible. 306 00:14:50,000 --> 00:14:54,000 You know, if you're trying to sum the numbers in an array and you forget to initialize 307 00:14:54,000 --> 00:14:55,000 your sum, 308 00:14:55,000 --> 00:14:57,000 you get a sum that's junky 309 00:14:57,000 --> 00:14:59,000 but it doesn't crash your program, 310 00:14:59,000 --> 00:15:03,000 right? It just uses that number as the starting value and sums from there. It 311 00:15:03,000 --> 00:15:05,000 produces results you kind of figure out what happened, but it doesn't 312 00:15:05,000 --> 00:15:07,000 crash. 313 00:15:07,000 --> 00:15:10,000 Many times, right, the use of a pointer that hasn't been initialized will cause an 314 00:15:10,000 --> 00:15:15,000 immediate crash, or it could cause sort of some later consequence to crash, right, that would 315 00:15:15,000 --> 00:15:19,000 make it even more mystical to try to sort out what happened. 316 00:15:19,000 --> 00:15:21,000 So it's partly because those bugs are 317 00:15:21,000 --> 00:15:24,000 -have pretty serious consequences and kind of sometimes difficult to understand 318 00:15:24,000 --> 00:15:25,000 consequences. 319 00:15:25,000 --> 00:15:29,000 So we do dynamic allocation via new, so dynamic meaning that just we get 320 00:15:29,000 --> 00:15:31,000 to choose what we're allocating, when and where, 321 00:15:31,000 --> 00:15:36,000 at a runtime situation saying how much memory we want and when we want it, 322 00:15:36,000 --> 00:15:40,000 using new. And then when we're done with it we do a manual deallocation via 323 00:15:40,000 --> 00:15:40,000 delete. 324 00:15:40,000 --> 00:15:42,000 If we forget to delete, we orphan memory. 325 00:15:42,000 --> 00:15:44,000 As I said, an 326 00:15:44,000 --> 00:15:46,000 important thing to be conscious of but not 327 00:15:46,000 --> 00:15:50,000 in the early stages something to take too 328 00:15:50,000 --> 00:15:51,000 heavily. 329 00:15:51,000 --> 00:15:55,000 And then accessing any deleted memory, right, it has unpredictable consequences, 330 00:15:55,000 --> 00:15:58,000 similarly to using uninitialized pointers, right, going back to addresses 331 00:15:58,000 --> 00:16:00,000 that have been marked freed 332 00:16:00,000 --> 00:16:02,000 is kind of like 333 00:16:02,000 --> 00:16:06,000 going back to your apartment after you don't have a lease on it anymore, right, like 334 00:16:06,000 --> 00:16:09,000 you put your stuff in there, it might get stolen, right? Now a god 335 00:16:09,000 --> 00:16:13,000 idea. So now 336 00:16:13,000 --> 00:16:14,000 let me tell you a little bit about 337 00:16:14,000 --> 00:16:17,000 how pointers work with arrays. 338 00:16:17,000 --> 00:16:23,000 We have not talked much about the C++ built-in raw array, 339 00:16:23,000 --> 00:16:25,000 that I've encouraged you to use vector 340 00:16:25,000 --> 00:16:27,000 where you would have used array because a vector is actually just much 341 00:16:27,000 --> 00:16:31,000 easier to deal with and it has a lot of convenience and safety features built 342 00:16:31,000 --> 00:16:32,000 into it. 343 00:16:32,000 --> 00:16:34,000 But as part of kind of 344 00:16:34,000 --> 00:16:35,000 understanding how the 345 00:16:35,000 --> 00:16:37,000 basics of the language work, 346 00:16:37,000 --> 00:16:41,000 it's worth knowing that pointers and arrays have a little relationship 347 00:16:41,000 --> 00:16:44,000 that -in how they're expressed in C++. 348 00:16:44,000 --> 00:16:46,000 So this piece of code that I have here, 349 00:16:46,000 --> 00:16:58,000 right, declares an int pointer called ARR. 350 00:16:58,000 --> 00:17:00,000 And it 351 00:17:00,000 --> 00:17:01,000 immediately initializes it 352 00:17:01,000 --> 00:17:10,000 to a new integer array in the heap 353 00:17:10,000 --> 00:17:13,000 that has 10 slots. I didn't 354 00:17:13,000 --> 00:17:14,000 quite draw 10, but that's a good idea of it. 355 00:17:14,000 --> 00:17:17,000 So the new operator, 356 00:17:17,000 --> 00:17:20,000 in addition to taking a single type -making a single string or an int or a double out in 357 00:17:20,000 --> 00:17:21,000 the heap, 358 00:17:21,000 --> 00:17:25,000 also has an alternate form where you add the square brackets on it and then you 359 00:17:25,000 --> 00:17:28,000 say, inside the square brackets, how large an array of those things you would like. So 360 00:17:28,000 --> 00:17:32,000 this is creating an array of integers 10 numbers long 361 00:17:32,000 --> 00:17:35,000 out in the heap, which array is going to point to. 362 00:17:35,000 --> 00:17:40,000 Having done that, right, array now has slots zero through nine available to 363 00:17:40,000 --> 00:17:43,000 it in which it can write and do things. And so the next thing it does is go 364 00:17:43,000 --> 00:17:46,000 through and use the bracket notation that's standard for arrays to access 365 00:17:46,000 --> 00:17:50,000 in turn elements zero through nine index and assign them each their 366 00:17:50,000 --> 00:17:54,000 index number. 367 00:17:54,000 --> 00:17:58,000 It's missing two numbers that I couldn't fit there. 368 00:17:58,000 --> 00:18:02,000 And so that is the syntax in C++ for creating a new dynamic array out in the 369 00:18:02,000 --> 00:18:03,000 heap, 370 00:18:03,000 --> 00:18:07,000 accessing it either to read or to write to those contents. It looks just like the 371 00:18:07,000 --> 00:18:08,000 vector there. 372 00:18:08,000 --> 00:18:10,000 And then when I'm done with it, 373 00:18:10,000 --> 00:18:12,000 because it came out of the heap 374 00:18:12,000 --> 00:18:16,000 it was dynamically allocated manually by me, it's my job to manually delete it. 375 00:18:16,000 --> 00:18:20,000 And there's a slight variation on delete that 376 00:18:20,000 --> 00:18:23,000 matches the use of the new int bracket, 377 00:18:23,000 --> 00:18:25,000 the delete bracket. 378 00:18:25,000 --> 00:18:28,000 So if I made an array of things out there, 379 00:18:28,000 --> 00:18:30,000 then I need to use the delete array 380 00:18:30,000 --> 00:18:32,000 form of it, so the delete bracket 381 00:18:32,000 --> 00:18:34,000 as opposed to the standard delete. 382 00:18:34,000 --> 00:18:36,000 If I use just the standard delete, 383 00:18:36,000 --> 00:18:39,000 it's like it thinks there's only one integer at the end of this, and it only kind 384 00:18:39,000 --> 00:18:42,000 of tracks that space. So the 385 00:18:42,000 --> 00:18:45,000 delete bracket says there's whole arrays worth of integers, make sure all 386 00:18:45,000 --> 00:18:47,000 of them get reclaimed. 387 00:18:47,000 --> 00:18:51,000 Now again, like most memory errors, right, if you do the wrong thing it won't 388 00:18:51,000 --> 00:18:53,000 necessarily have really clear -it's not 389 00:18:53,000 --> 00:18:54,000 like 390 00:18:54,000 --> 00:18:55,000 it provides an 391 00:18:55,000 --> 00:18:58,000 error message and stops and says you used the wrong form of delete, it's more likely to actually kind of just 392 00:18:58,000 --> 00:19:02,000 misunderstand your intentions and kind of blunder on, 393 00:19:02,000 --> 00:19:05,000 producing a little bit unpredictable results from there. 394 00:19:05,000 --> 00:19:08,000 So raw arrays in general are trouble. 395 00:19:08,000 --> 00:19:11,000 We are definitely gonna use them a little bit later, in fact to build 396 00:19:11,000 --> 00:19:14,000 things like vector and stack and queue, right, 397 00:19:14,000 --> 00:19:17,000 we need to actually have this facility, right. The [inaudible] facility is what those 398 00:19:17,000 --> 00:19:19,000 tings are layered on top of. 399 00:19:19,000 --> 00:19:23,000 But as a client, I'm going to say that traditionally, right, 400 00:19:23,000 --> 00:19:24,000 401 00:19:24,000 --> 00:19:28,000 that things that you would use an array for, it's just much better 402 00:19:28,000 --> 00:19:31,000 practice to use a vector for. So I'll mention sort of why it is that, you know, arrays 403 00:19:31,000 --> 00:19:32,000 are trouble, right? 404 00:19:32,000 --> 00:19:35,000 Well, they're mainly allocated and deallocated, so that means you have to make the new 405 00:19:35,000 --> 00:19:38,000 calls, you have to make the delete calls. So forgetting one or both of those, right, has 406 00:19:38,000 --> 00:19:40,000 pretty serious consequences. 407 00:19:40,000 --> 00:19:43,000 Arrays don't know their length. 408 00:19:43,000 --> 00:19:46,000 That once I have created this array and it points to these 10 members, 409 00:19:46,000 --> 00:19:49,000 there is no mechanism to ask the array, you know, array dot length or tell me 410 00:19:49,000 --> 00:19:52,000 your length -it doesn't know. 411 00:19:52,000 --> 00:19:55,000 Internally, it may or may not have some housekeeping that's tracking it, but it's not 412 00:19:55,000 --> 00:19:57,000 exposed to you as a client. 413 00:19:57,000 --> 00:19:59,000 So it will be your job, if you are creating a manual array, 414 00:19:59,000 --> 00:20:01,000 to also be tracking its size. 415 00:20:01,000 --> 00:20:04,000 And so everywhere you were trying to use that array you'd also need to know well, here's 416 00:20:04,000 --> 00:20:07,000 where the address of that array, 417 00:20:07,000 --> 00:20:10,000 its location in the heap, and here's how many members go. You'll have to kind of just track 418 00:20:10,000 --> 00:20:13,000 those two things around and pass them in tandem. 419 00:20:13,000 --> 00:20:15,000 There is no balance checking. 420 00:20:15,000 --> 00:20:17,000 If I access the 12th member of this, 421 00:20:17,000 --> 00:20:20,000 it actually just uses a very simple calculation, which says well, here's where 422 00:20:20,000 --> 00:20:24,000 the array starts in memory. All arrays are laid out contiguously. If you ask me 423 00:20:24,000 --> 00:20:26,000 to find the 12th one, 424 00:20:26,000 --> 00:20:27,000 then I just kind of walk 425 00:20:27,000 --> 00:20:32,000 down to where the 12th spot should be, even if it's not really mine to own, 426 00:20:32,000 --> 00:20:35,000 and I will read or write to that location as you ask me. 427 00:20:35,000 --> 00:20:38,000 I can ask for the 100th member of the 1,000th member, the 6 millionth 428 00:20:38,000 --> 00:20:39,000 member, 429 00:20:39,000 --> 00:20:42,000 and all the calculations work off of well, here's where the array starts. Where 430 00:20:42,000 --> 00:20:46,000 would the 6 millionth member be if it were present? 431 00:20:46,000 --> 00:20:47,000 That piece of memory, 432 00:20:47,000 --> 00:20:50,000 if it's not allocated to this array and it's not really part of its proper bounds will 433 00:20:50,000 --> 00:20:54,000 receive no error checking, no nice out-of-bounds message. It will just kind of 434 00:20:54,000 --> 00:20:58,000 do the calculation to figure out what place in memory would be referred to 435 00:20:58,000 --> 00:21:01,000 and read or write to those contents, causing kind of unpredictable, 436 00:21:01,000 --> 00:21:02,000 weird behaviors, right, that 437 00:21:02,000 --> 00:21:05,000 would be hard to figure out. 438 00:21:05,000 --> 00:21:09,000 You can't easily change its size once it's allocated, so if I've done a new 439 00:21:09,000 --> 00:21:10,000 int bracket 10, 440 00:21:10,000 --> 00:21:11,000 I have a 10-member array. 441 00:21:11,000 --> 00:21:14,000 If I later want to put 20 things in there, 442 00:21:14,000 --> 00:21:17,000 then there is no way to take this piece of memory and stretch it to say, well, ad some 443 00:21:17,000 --> 00:21:21,000 space in the back. What I will need to do is allocate an 444 00:21:21,000 --> 00:21:22,000 array 445 00:21:22,000 --> 00:21:25,000 that's twice as long, 446 00:21:25,000 --> 00:21:29,000 copy over all the numbers I already have, 447 00:21:29,000 --> 00:21:31,000 and then, you know, 448 00:21:31,000 --> 00:21:33,000 delete the old one 449 00:21:33,000 --> 00:21:37,000 and update my pointer to point here. So the only mechanism for changing the size of 450 00:21:37,000 --> 00:21:39,000 an array, once it's been allocated 451 00:21:39,000 --> 00:21:42,000 is to really go through this process of creating a new array of the size you want, 452 00:21:42,000 --> 00:21:44,000 copying over what you wanted to retain, 453 00:21:44,000 --> 00:21:48,000 deleting the old one, updating your pointer, which, as you can imagine, gets to be 454 00:21:48,000 --> 00:21:50,000 just a bit tedious. 455 00:21:50,000 --> 00:21:51,000 So you can certainly use 456 00:21:51,000 --> 00:21:54,000 the raw array to do things, and we will definitely have to build things on 457 00:21:54,000 --> 00:21:59,000 it later, but once you have vector around, it provides so many of 458 00:21:59,000 --> 00:22:03,000 these things, right, in such a nicer form that dealing with the raw array appears too 459 00:22:03,000 --> 00:22:06,000 troublesome and too little value, right, to do so. 460 00:22:06,000 --> 00:22:09,000 So vector does use array behind the scenes, but it hides these issues, right. 461 00:22:09,000 --> 00:22:11,000 It does track its size, it does do balance checking, 462 00:22:11,000 --> 00:22:15,000 it does grow and shrink on demand, 463 00:22:15,000 --> 00:22:17,000 exactly by doing the kind of things that I said were kind of a little bit tedious to 464 00:22:17,000 --> 00:22:21,000 do, it does on your behalf. So you've 465 00:22:21,000 --> 00:22:28,000 just sort of seen the picture. Your 466 00:22:28,000 --> 00:22:29,000 hand's up. Student:You said that the type of 467 00:22:29,000 --> 00:22:36,000 pointer determines what it's pointing to. So why doesn't an array have, like, an [inaudible]? That's a great question. So it turns out that there 468 00:22:36,000 --> 00:22:39,000 is actually -maybe there's one example where I was being a little bit 469 00:22:39,000 --> 00:22:39,000 disingenuous. It turns out 470 00:22:39,000 --> 00:22:43,000 a pointer to an integer and a pointer to a sequence of integers are considered the 471 00:22:43,000 --> 00:22:46,000 same in C++. So it actually doesn't distinguish the idea that 472 00:22:46,000 --> 00:22:49,000 you gave it an address and you're telling it what kind of data's at that address. 473 00:22:49,000 --> 00:22:53,000 You are not telling it how much of those are there, how many, right? You're saying there's at 474 00:22:53,000 --> 00:22:55,000 least an integer there; 475 00:22:55,000 --> 00:22:58,000 there could be a whole sequence. So in fact it considers a pointer to an integer and a 476 00:22:58,000 --> 00:22:59,000 pointer to an array of integers 477 00:22:59,000 --> 00:23:01,000 to be type compatible. 478 00:23:01,000 --> 00:23:03,000 There are certain 479 00:23:03,000 --> 00:23:06,000 quirkinesses about that, but you can sort of see what -at least from a type 480 00:23:06,000 --> 00:23:09,000 system point of view, that actually kind of does make sense, right? They both are 481 00:23:09,000 --> 00:23:12,000 saying that well, we have these two addresses. What's at the other end of 482 00:23:12,000 --> 00:23:15,000 them? They're our integers. And how many are there? It turns out we're not -we don't track 483 00:23:15,000 --> 00:23:21,000 for you, so the fact that there's 10, the fact that there's one, is up to you to know. Way over here. Student:Why 484 00:23:21,000 --> 00:23:24,000 don't you have to dereference array when you assign it? 485 00:23:24,000 --> 00:23:28,000 So that is also an excellent question. It turns out there's a kind of a 486 00:23:28,000 --> 00:23:31,000 dereference sort of hidden in the bracket operator 487 00:23:31,000 --> 00:23:32,000 488 00:23:32,000 --> 00:23:37,000 that the bracket operator has, behind the scenes, is actually doing a calculation that 489 00:23:37,000 --> 00:23:39,000 says take this address array, 490 00:23:39,000 --> 00:23:44,000 add to it sort of I slots' worth, and then dereference that. So in fact there's kind of a star 491 00:23:44,000 --> 00:23:45,000 hidden in there, and 492 00:23:45,000 --> 00:23:48,000 it's just part of what the bracket operator does on an array. 493 00:23:48,000 --> 00:23:51,000 So you are correct, there obviously is a dereference happening 494 00:23:51,000 --> 00:23:52,000 in there, and 495 00:23:52,000 --> 00:24:02,000 it is sort of hidden in the brackets themselves is all I can say. Student:So [inaudible] when you just declare an array [inaudible]. 496 00:24:02,000 --> 00:24:04,000 Yeah, so if you just make a 497 00:24:04,000 --> 00:24:05,000 -yeah, so 498 00:24:05,000 --> 00:24:08,000 all that -it's basically the same deal, it's just where did the memory come from, 499 00:24:08,000 --> 00:24:10,000 right? So if you say int 500 00:24:10,000 --> 00:24:15,000 bracket 10, it's on the stack. If you say new in 10 it got [inaudible] heap. 501 00:24:15,000 --> 00:24:17,000 So it's just a matter of does the memory live 502 00:24:17,000 --> 00:24:21,000 over here and it was kind of automatically allocated or deallocated by entering and exiting, 503 00:24:21,000 --> 00:24:25,000 or is it explicitly allocated with new and delete over in the Heap? 504 00:24:25,000 --> 00:24:29,000 The heap tends to give you that flexibility of resizing it and moving it and stuff like 505 00:24:29,000 --> 00:24:32,000 that in a way that the stack doesn't, so that's kind of the preferred place to usually 506 00:24:32,000 --> 00:24:37,000 get an array from. 507 00:24:37,000 --> 00:24:40,000 So mostly I'm telling you this because we are going to come back to that one, but I 508 00:24:40,000 --> 00:24:43,000 just -it feels like it kind of fits with kind of getting a picture about how memory, right 509 00:24:43,000 --> 00:24:46,000 -C++ is very much exposing to you the 510 00:24:46,000 --> 00:24:50,000 sort of low-level where it puts memory and how it accesses things, right, 511 00:24:50,000 --> 00:24:52,000 that pointers are giving you 512 00:24:52,000 --> 00:24:53,000 that direct 513 00:24:53,000 --> 00:24:55,000 manipulation for. 514 00:24:55,000 --> 00:24:57,000 One of the more common uses of pointers 515 00:24:57,000 --> 00:25:00,000 is this idea of sharing. 516 00:25:00,000 --> 00:25:04,000 So if I were designing the Access database and I have this record for a 517 00:25:04,000 --> 00:25:06,000 student with their first name and their last name and their address and their phone 518 00:25:06,000 --> 00:25:10,000 number and probably a bunch more data -their student ID number 519 00:25:10,000 --> 00:25:13,000 and maybe their transcript so far. All these things that 520 00:25:13,000 --> 00:25:16,000 model the information track for a particular student in there, I 521 00:25:16,000 --> 00:25:19,000 also have a bunch of courses -CS106b, Math 51, you know, Physics 522 00:25:19,000 --> 00:25:20,000 523 00:25:20,000 --> 00:25:23,000 41. And each of those courses, right, has a list of the enrolled students in 524 00:25:23,000 --> 00:25:25,000 it. 525 00:25:25,000 --> 00:25:28,000 There is a student record that represents Michelle, right? And there's 526 00:25:28,000 --> 00:25:30,000 Michelle's record in the system. 527 00:25:30,000 --> 00:25:33,000 It could be that every class that Michelle isn't enrolled in 528 00:25:33,000 --> 00:25:35,000 copies her whole structure into it, 529 00:25:35,000 --> 00:25:37,000 so if I had declared this vector here 530 00:25:37,000 --> 00:25:41,000 as holding student T without the star, it would hold real student T 531 00:25:41,000 --> 00:25:42,000 structures. 532 00:25:42,000 --> 00:25:44,000 Then every class Michelle was enrolled in 533 00:25:44,000 --> 00:25:45,000 would have a copy of her structure. 534 00:25:45,000 --> 00:25:46,000 I would say 535 00:25:46,000 --> 00:25:50,000 add to the students in this class Michelle's record, add Michelle's record to 536 00:25:50,000 --> 00:25:51,000 this class. 537 00:25:51,000 --> 00:25:54,000 Well, each of those, right, would make a full copy -her first name, her last name, her 538 00:25:54,000 --> 00:25:56,000 address, her phone number, you know, however big this record is, right, would 539 00:25:56,000 --> 00:25:58,000 be duplicated 540 00:25:58,000 --> 00:26:01,000 throughout the system in every class she was enrolled in. 541 00:26:01,000 --> 00:26:05,000 That means that first of all, there's a lot of space that's being taken, a lot of redundancy in that 542 00:26:05,000 --> 00:26:06,000 system. 543 00:26:06,000 --> 00:26:10,000 It also means that we have a little bit of an update problem. If Michelle gets a new 544 00:26:10,000 --> 00:26:12,000 phone number 545 00:26:12,000 --> 00:26:15,000 and we'd like it to change across the system-wide, 546 00:26:15,000 --> 00:26:19,000 then I have to find every place where her record has been duplicated and updated to 547 00:26:19,000 --> 00:26:22,000 get the update to kind of flow through the whole system. So finding every course she 548 00:26:22,000 --> 00:26:25,000 was enrolled in and updating it in every place. 549 00:26:25,000 --> 00:26:27,000 If instead 550 00:26:27,000 --> 00:26:30,000 there really is just one copy of Michelle's student record -I 551 00:26:30,000 --> 00:26:33,000 allocated it in the heap, I set it up, I put things into it, 552 00:26:33,000 --> 00:26:34,000 and then 553 00:26:34,000 --> 00:26:38,000 every course that she enrolls in I store the pointer to that same record, then 554 00:26:38,000 --> 00:26:42,000 there really is only one copy of the student T structure per student, 555 00:26:42,000 --> 00:26:44,000 but multiple pointers to it 556 00:26:44,000 --> 00:26:45,000 in different places. 557 00:26:45,000 --> 00:26:48,000 When I need to update her phone number, there really is only one copy of her 558 00:26:48,000 --> 00:26:49,000 phone number. 559 00:26:49,000 --> 00:26:51,000 If I change the phone number in that one record, 560 00:26:51,000 --> 00:26:53,000 all the pointers are pointing at that one record, 561 00:26:53,000 --> 00:26:57,000 and all the updates effectively happened automatically, 562 00:26:57,000 --> 00:26:59,000 just changing in one place only. So 563 00:26:59,000 --> 00:27:02,000 this is one of the most common needs for pointers, is just any kind of data 564 00:27:02,000 --> 00:27:06,000 structure where there needs to be some kind of sharing, 565 00:27:06,000 --> 00:27:06,000 where 566 00:27:06,000 --> 00:27:07,000 you have 567 00:27:07,000 --> 00:27:10,000 information, right, that's being tracked in different ways. You want to be able to look at 568 00:27:10,000 --> 00:27:13,000 your iTunes library by genre, you want to be able to look at it by album. You want to 569 00:27:13,000 --> 00:27:15,000 look at it by artist. 570 00:27:15,000 --> 00:27:18,000 That there really is only one record for each song 571 00:27:18,000 --> 00:27:21,000 in the database that's being managed there, 572 00:27:21,000 --> 00:27:23,000 but there's a lot of different views on that data, 573 00:27:23,000 --> 00:27:26,000 and those views could each use pointers 574 00:27:26,000 --> 00:27:28,000 to refer to the one copy, 575 00:27:28,000 --> 00:27:33,000 and then make for sharing of the data without that redundancy, and then this easy 576 00:27:33,000 --> 00:27:33,000 update 577 00:27:33,000 --> 00:27:35,000 of 578 00:27:35,000 --> 00:27:37,000 only being one place to do it. 579 00:27:37,000 --> 00:27:39,000 So without pointers, right, you're kind of stuck, right? 580 00:27:39,000 --> 00:27:42,000 If you don't know about pointers, right, you end up kind of duplicating this or designing 581 00:27:42,000 --> 00:27:45,000 some more funky system where maybe you have a number here that tells you where to 582 00:27:45,000 --> 00:27:48,000 go look up them in some other place, you know. 583 00:27:48,000 --> 00:27:52,000 The pointer gives you a really clear means of just modeling there is a sharing 584 00:27:52,000 --> 00:27:55,000 relationship. That's 585 00:27:55,000 --> 00:27:57,000 pretty cool. 586 00:27:57,000 --> 00:27:59,000 So what else can pointers be good for? 587 00:27:59,000 --> 00:28:01,000 Ah. Pointers 588 00:28:01,000 --> 00:28:02,000 are good for something. 589 00:28:02,000 --> 00:28:05,000 Now here's the thing you wanted to do. You wanted to take pointers, which 590 00:28:05,000 --> 00:28:08,000 inherently are a little bit confusing, and then take recursion, which we also know is 591 00:28:08,000 --> 00:28:11,000 pretty confusing, and then put them together 592 00:28:11,000 --> 00:28:12,000 and 593 00:28:12,000 --> 00:28:16,000 make something that will make your head completely explode. 594 00:28:16,000 --> 00:28:18,000 We're talking about recursive data. 595 00:28:18,000 --> 00:28:21,000 For some people, this is actually the thing that actually does make recursion 596 00:28:21,000 --> 00:28:23,000 suddenly make sense, though, is to see it 597 00:28:23,000 --> 00:28:27,000 -to see recursion echoed in a structural way as opposed to a code way. 598 00:28:27,000 --> 00:28:28,000 So when I talk about 599 00:28:28,000 --> 00:28:33,000 recursion in the form of looking at a structure that itself kind of has embedded 600 00:28:33,000 --> 00:28:38,000 within it a smaller version. So I brought with you my 601 00:28:38,000 --> 00:28:41,000 physical embodiment of recursive data, 602 00:28:41,000 --> 00:28:43,000 which is my lovely 603 00:28:43,000 --> 00:28:45,000 Matryoshka doll. 604 00:28:45,000 --> 00:28:46,000 Ikea, 605 00:28:46,000 --> 00:28:48,000 $15. 606 00:28:48,000 --> 00:28:50,000 If you open it up, 607 00:28:50,000 --> 00:28:54,000 what's inside? 608 00:28:54,000 --> 00:28:56,000 Whoa, check that out 609 00:28:56,000 --> 00:28:58,000 -it's another Matryoshka doll. You open 610 00:28:58,000 --> 00:29:00,000 her up 611 00:29:00,000 --> 00:29:02,000 -hey, it's the -she's facing the other way. She 612 00:29:02,000 --> 00:29:04,000 was shy. You 613 00:29:04,000 --> 00:29:06,000 open her up, 614 00:29:06,000 --> 00:29:07,000 there's gonna be something good, you can feel it. 615 00:29:07,000 --> 00:29:08,000 616 00:29:08,000 --> 00:29:12,000 And then 617 00:29:12,000 --> 00:29:12,000 -little, tiny 618 00:29:12,000 --> 00:29:18,000 -this is the base case. She sits there. 619 00:29:18,000 --> 00:29:21,000 What you got there is like a doll which herself is a doll wrapped around another Matryoshka 620 00:29:21,000 --> 00:29:23,000 doll, which has kind of this 621 00:29:23,000 --> 00:29:27,000 self-referential kind of inside of it, right? There is another doll like the one you 622 00:29:27,000 --> 00:29:30,000 saw before, but a little bit smaller, a little bit tinier. Then at some point you get the one that actually is 623 00:29:30,000 --> 00:29:31,000 just 624 00:29:31,000 --> 00:29:33,000 so small that we're just done. 625 00:29:33,000 --> 00:29:36,000 And so there are things like this in the real world, things like onions. You know, you peel off the 626 00:29:36,000 --> 00:29:39,000 outer layer of an onion, there's really kind of a smaller onion underneath, and eventually you get to that 627 00:29:39,000 --> 00:29:41,000 kind of onion core, that base case. 628 00:29:41,000 --> 00:29:45,000 We're going to look at this in terms of a structure that contains a pointer 629 00:29:45,000 --> 00:29:51,000 to the same structure we started with as a way of modeling something recursively. Think 630 00:29:51,000 --> 00:29:53,000 about managing an address book. 631 00:29:53,000 --> 00:29:57,000 I've got a name and address and a phone for each of the people I wanna manage. 632 00:29:57,000 --> 00:30:00,000 I could certainly put these entries together in a vector and have kind of a 633 00:30:00,000 --> 00:30:02,000 vector of all the people in my address book. 634 00:30:02,000 --> 00:30:05,000 I'm going to choose a different way to organize this 635 00:30:05,000 --> 00:30:10,000 by virtue of making this structure have an additional field, a pointer to another 636 00:30:10,000 --> 00:30:11,000 entry. So 637 00:30:11,000 --> 00:30:15,000 I've got three fields that represent, you know, Jason's entry in my address book, 638 00:30:15,000 --> 00:30:20,000 and then he has a pointer to more entries, or at least an entry, let's say -the 639 00:30:20,000 --> 00:30:21,000 entry that follows this one, 640 00:30:21,000 --> 00:30:22,000 which itself can be 641 00:30:22,000 --> 00:30:27,000 the name and address and phone number of Joel, let's say, with a pointer to 642 00:30:27,000 --> 00:30:29,000 another entry, and so on. 643 00:30:29,000 --> 00:30:31,000 So each entry 644 00:30:31,000 --> 00:30:34,000 points to another entry. 645 00:30:34,000 --> 00:30:36,000 That's what makes for a recursive structure. 646 00:30:36,000 --> 00:30:39,000 It's kind of funny -I'm not even really done defining what the entry structure 647 00:30:39,000 --> 00:30:42,000 is, and I'm already referring to it. It's that feeling of kind of like the way 648 00:30:42,000 --> 00:30:46,000 a recursive function is written, where it makes a call back to itself before 649 00:30:46,000 --> 00:30:48,000 you're done completing your whole thought, 650 00:30:48,000 --> 00:30:50,000 saying that there is a pointer to another one of these. 651 00:30:50,000 --> 00:30:53,000 And so a link list is a pointer to an element 652 00:30:53,000 --> 00:30:54,000 which itself 653 00:30:54,000 --> 00:30:58,000 has embedded within it a pointer to another element, and so on. 654 00:30:58,000 --> 00:31:00,000 And if I use that Null 655 00:31:00,000 --> 00:31:03,000 as my terminating sentinel at the end to say that, well, Monte has no one following 656 00:31:03,000 --> 00:31:04,000 him, 657 00:31:04,000 --> 00:31:08,000 then I have this chain that I can follow from the front to the back 658 00:31:08,000 --> 00:31:13,000 to visit all the entries in my list. Okay, 659 00:31:13,000 --> 00:31:15,000 this guy is called a link list. 660 00:31:15,000 --> 00:31:18,000 So it's a list because there's a, you know, collection of things that are there. 661 00:31:18,000 --> 00:31:21,000 They are linked together 662 00:31:21,000 --> 00:31:23,000 by virtue of pointers, 663 00:31:23,000 --> 00:31:26,000 and they have a very recursive formulation, 664 00:31:26,000 --> 00:31:28,000 if you think about it, right, that 665 00:31:28,000 --> 00:31:30,000 any individual entry 666 00:31:30,000 --> 00:31:33,000 is one entry in the address book 667 00:31:33,000 --> 00:31:34,000 followed by another list. 668 00:31:34,000 --> 00:31:37,000 So the whole list has a thousands entries in it, 669 00:31:37,000 --> 00:31:39,000 but in fact if you kind of break it down recursively, you can say well, there's an 670 00:31:39,000 --> 00:31:43,000 entry in the front and it's followed by a smaller, shorter list -one shorter, in this 671 00:31:43,000 --> 00:31:45,000 case, 999 entries. 672 00:31:45,000 --> 00:31:49,000 And similarly, I can do that at every stage, which is to take each element and 673 00:31:49,000 --> 00:31:50,000 think about it as well, it's an element, 674 00:31:50,000 --> 00:31:56,000 but it points to a smaller link list behind it. 675 00:31:56,000 --> 00:32:00,000 So I'm going to actually just do this code in the compiler. 676 00:32:00,000 --> 00:32:04,000 But it's all in the handout, as well as on the slides that I'll post. 677 00:32:04,000 --> 00:32:04,000 678 00:32:04,000 --> 00:32:08,000 Just talk a little bit about doing some stuff with link lists. 679 00:32:08,000 --> 00:32:11,000 So the first thing I'm gonna do is I have 680 00:32:11,000 --> 00:32:13,000 the entry, the name of the phone number with the pointer, 681 00:32:13,000 --> 00:32:16,000 and I wrote a little print entry that printed a single one. So we're going to see a lot of 682 00:32:16,000 --> 00:32:20,000 pointers in here, we're going to refer to all these elements by their pointers, and then we're going to allocate 683 00:32:20,000 --> 00:32:23,000 them out of the heap, kind of on demand, and wire them together 684 00:32:23,000 --> 00:32:27,000 by using the pointers to get our flexibility here. 685 00:32:27,000 --> 00:32:30,000 The one routine that actually I'm gonna -I have pre-written here 686 00:32:30,000 --> 00:32:34,000 is one that will create a new entry in the heap based on information typed by 687 00:32:34,000 --> 00:32:36,000 the user at the console. 688 00:32:36,000 --> 00:32:39,000 So it prompts them to enter something. 689 00:32:39,000 --> 00:32:40,000 If they 690 00:32:40,000 --> 00:32:43,000 enter a return that's our clue that they have no more names. And otherwise, we make a 691 00:32:43,000 --> 00:32:46,000 new entry in the heap. So 692 00:32:46,000 --> 00:32:49,000 here's our call to make a new entry [inaudible] out there, store the pointer to it 693 00:32:49,000 --> 00:32:50,000 here, 694 00:32:50,000 --> 00:32:54,000 and then this access -I should mention this syntax is a little bit 695 00:32:54,000 --> 00:32:57,000 -should be -may feel a little bit new to you 696 00:32:57,000 --> 00:32:59,000 -is that 697 00:32:59,000 --> 00:33:02,000 new one dot name, that 698 00:33:02,000 --> 00:33:04,000 what I'm trying to do here is 699 00:33:04,000 --> 00:33:05,000 take new one, 700 00:33:05,000 --> 00:33:08,000 dereference it, and write to the name field. 701 00:33:08,000 --> 00:33:13,000 And so the syntax that kind of comes to mind here looks like this: 702 00:33:13,000 --> 00:33:14,000 take the new one pointer, 703 00:33:14,000 --> 00:33:18,000 dereference it to get to the entry structure, and then dot to get the name 704 00:33:18,000 --> 00:33:20,000 field out of it. 705 00:33:20,000 --> 00:33:24,000 And that is actually a sensible sort of construction. The problem with it, if I 706 00:33:24,000 --> 00:33:25,000 leave it as-is, 707 00:33:25,000 --> 00:33:30,000 is that the precedence of these two operators is not quite what you'd expect. 708 00:33:30,000 --> 00:33:34,000 That actually, the dot has a higher precedence than the star, and so in fact 709 00:33:34,000 --> 00:33:36,000 the way the complier interprets this is 710 00:33:36,000 --> 00:33:38,000 as first take new one, 711 00:33:38,000 --> 00:33:42,000 act like it's some sort of structure that has a name field in it, and then 712 00:33:42,000 --> 00:33:46,000 retrieve that name field which you suspect to be some kind of pointer, which you can 713 00:33:46,000 --> 00:33:49,000 then dereference. It's doing it exactly backwards. 714 00:33:49,000 --> 00:33:51,000 If we wanted to use that syntax as-is, 715 00:33:51,000 --> 00:33:55,000 we'd actually have to introduce these parens that said please first dereference 716 00:33:55,000 --> 00:33:57,000 new one. 717 00:33:57,000 --> 00:33:59,000 It is a pointer to an entry. 718 00:33:59,000 --> 00:34:03,000 Get the entry structure that's referred to on the other end and then dot name to 719 00:34:03,000 --> 00:34:05,000 get the field name out of it. 720 00:34:05,000 --> 00:34:09,000 And that would work just fine. Just because that's a little bit awkward to write every time, there's 721 00:34:09,000 --> 00:34:12,000 actually an alternate operator in C++, the arrow operator, 722 00:34:12,000 --> 00:34:15,000 that combines the star and the dot behind it to 723 00:34:15,000 --> 00:34:18,000 go reach out there. So this says 724 00:34:18,000 --> 00:34:20,000 following the new one's pointer, 725 00:34:20,000 --> 00:34:25,000 reach into the structure at the other end and access the name field. 726 00:34:25,000 --> 00:34:27,000 So I assign the name, I assign the phone, 727 00:34:27,000 --> 00:34:29,000 and then I set the next field to Null 728 00:34:29,000 --> 00:34:34,000 as just a good practice to say well, I've just created a little entry all by itself. 729 00:34:34,000 --> 00:34:36,000 Rather than leave that pointer initialized, let's make sure we set its Null so we 730 00:34:36,000 --> 00:34:42,000 know it's just a cell by itself and it's not connected to anything yet. Okay. 731 00:34:42,000 --> 00:34:44,000 Let me just write 732 00:34:44,000 --> 00:34:47,000 a little code to test that. 733 00:34:47,000 --> 00:34:51,000 Um, 734 00:34:51,000 --> 00:34:52,000 I'll just call it N and 735 00:34:52,000 --> 00:34:56,000 then I'll say get new entry. And 736 00:34:56,000 --> 00:34:57,000 then I'm going to call print entry on it, so 737 00:34:57,000 --> 00:34:59,000 I'm just gonna do that to see that 738 00:34:59,000 --> 00:35:00,000 739 00:35:00,000 --> 00:35:02,000 I can allocate an entry 740 00:35:02,000 --> 00:35:05,000 and then do something with it. I can say it's 741 00:35:05,000 --> 00:35:08,000 Julie and my phone number is 742 00:35:08,000 --> 00:35:11,000 -and then it prints out my name and my phone number. Okay. Try 743 00:35:11,000 --> 00:35:13,000 it again, now 744 00:35:13,000 --> 00:35:16,000 I can say Jason, 745 00:35:16,000 --> 00:35:18,000 Jason's phone number is -oh, 746 00:35:18,000 --> 00:35:21,000 Jason has lots of digits in his phone number, okay. So 747 00:35:21,000 --> 00:35:24,000 we've got a little bit of stuff going here. 748 00:35:24,000 --> 00:35:27,000 Now what I'm going to do is I'm going to 749 00:35:27,000 --> 00:35:29,000 build a link list. I'm gonna 750 00:35:29,000 --> 00:35:33,000 use this get new entry function to give me individual cells, 751 00:35:33,000 --> 00:35:42,000 and then I'm gonna wire them together and build a link list out of it. 752 00:35:42,000 --> 00:35:46,000 So I'm gonna start by having my list be empty so the standard sentinel 753 00:35:46,000 --> 00:35:49,000 value, Null, is used when you -to indicate that you have no more cells or 754 00:35:49,000 --> 00:35:52,000 you've started with a totally empty list. 755 00:35:52,000 --> 00:35:57,000 I'm going to keep asking for new cells 756 00:35:57,000 --> 00:35:59,000 until they don't have any more, 757 00:35:59,000 --> 00:36:02,000 and so get new entry returns Null 758 00:36:02,000 --> 00:36:05,000 if they have indicated they have no more. 759 00:36:05,000 --> 00:36:07,000 So I'll just go ahead and break out of the loop when that happens. 760 00:36:07,000 --> 00:36:10,000 Otherwise, right, I have a new entry 761 00:36:10,000 --> 00:36:13,000 that they just gave me, and I'm gonna wire it into my list. 762 00:36:13,000 --> 00:36:15,000 Okay, so let's think a little bit about 763 00:36:15,000 --> 00:36:22,000 how the pointers are gonna work on this. 764 00:36:22,000 --> 00:36:24,000 So here's my 765 00:36:24,000 --> 00:36:27,000 list pointer, and it points to a cell, 766 00:36:27,000 --> 00:36:28,000 which points to a cell, 767 00:36:28,000 --> 00:36:31,000 you know, which points to a cell and 768 00:36:31,000 --> 00:36:31,000 so on, 769 00:36:31,000 --> 00:36:35,000 that there's information here, you know -this is Jason, this 770 00:36:35,000 --> 00:36:40,000 is Joel, this 771 00:36:40,000 --> 00:36:43,000 is Brittany, okay. I get a new cell, 772 00:36:43,000 --> 00:36:46,000 it is Jake. 773 00:36:46,000 --> 00:36:49,000 Back 774 00:36:49,000 --> 00:36:51,000 from my get new entry. 775 00:36:51,000 --> 00:36:53,000 And I wanna attach Jake 776 00:36:53,000 --> 00:36:54,000 into my list 777 00:36:54,000 --> 00:36:57,000 to join it with the ones I have. 778 00:36:57,000 --> 00:37:01,000 So I've got an existing list and a new cell to add to it. 779 00:37:01,000 --> 00:37:06,000 There are two obvious places to add the cell. Typically, when you have a list, 780 00:37:06,000 --> 00:37:09,000 it seems like probably putting it at one of the ends, given that I'm not trying to maintain 781 00:37:09,000 --> 00:37:16,000 any sorting order at this time, is gonna be the easiest place to put it. 782 00:37:16,000 --> 00:37:18,000 So tell me, 783 00:37:18,000 --> 00:37:22,000 think about this. Should I may Jake's first or last? 784 00:37:22,000 --> 00:37:26,000 Is there any reason to prefer one to the other? Is 785 00:37:26,000 --> 00:37:35,000 there any advantage to going with one way versus the other one? Why not? Yeah, 786 00:37:35,000 --> 00:37:44,000 why not first? What's good about first? 787 00:37:44,000 --> 00:37:46,000 Student:Because when you're making a new entry you can probably more easily decide what the next pointer's going to point to 788 00:37:46,000 --> 00:37:52,000 as opposed to going all the way back 789 00:37:52,000 --> 00:37:53,000 through the list and going to Brittany and assigning that pointer to something. Yeah, that is exactly true. So there's something a little 790 00:37:53,000 --> 00:37:57,000 bit quirky about link list in this respect, which is because it's a chain, right, 791 00:37:57,000 --> 00:37:59,000 where you have a pointer to the front and then 792 00:37:59,000 --> 00:38:01,000 subsequent pointers get your way down at the end [inaudible] 793 00:38:01,000 --> 00:38:03,000 it's very easy to get to the front of the list, but 794 00:38:03,000 --> 00:38:07,000 it's actually a little more work to get to the end. If I wanted to, if I had a thousand entries in 795 00:38:07,000 --> 00:38:10,000 my address book and I wanted to add each entry to the end, then I'd have to kind of 796 00:38:10,000 --> 00:38:13,000 work my way down to the end to kind of do that work. So it turns out it's actually just a 797 00:38:13,000 --> 00:38:14,000 little bit easier 798 00:38:14,000 --> 00:38:17,000 -requires less housekeeping, less work to [inaudible] if I just -I 799 00:38:17,000 --> 00:38:21,000 already have a pointer to the front. Why don't I just go ahead and put Jake on the very front. So 800 00:38:21,000 --> 00:38:23,000 prepend Jake. 801 00:38:23,000 --> 00:38:27,000 So the processes for this are going to be I have Jake in here. Typically when I am putting a 802 00:38:27,000 --> 00:38:31,000 new cell into a link list, there's going to be two pointers that need to be adjusted to 803 00:38:31,000 --> 00:38:33,000 splice it in. 804 00:38:33,000 --> 00:38:37,000 The new cell needs to have its outgoing pointer, so Jake needs to be attached 805 00:38:37,000 --> 00:38:39,000 such that if you got to Jake, 806 00:38:39,000 --> 00:38:43,000 it would lead away to some other cells. In this case, I'm gonna have Jake 807 00:38:43,000 --> 00:38:46,000 point to what 808 00:38:46,000 --> 00:38:48,000 previously was the front most cell. 809 00:38:48,000 --> 00:38:50,000 And then I need to wire the pointer 810 00:38:50,000 --> 00:38:54,000 into that cell, so, you know, Jake has to kind of exist in context, he has to have 811 00:38:54,000 --> 00:38:57,000 something coming in and something going out. The one that's gonna come in is 812 00:38:57,000 --> 00:39:00,000 gonna be the one that previously was the front most 813 00:39:00,000 --> 00:39:03,000 -the list head or the front note of the list 814 00:39:03,000 --> 00:39:06,000 is now gonna point to Jake. So the two assignments I need to make to get Jake 815 00:39:06,000 --> 00:39:08,000 into there is 816 00:39:08,000 --> 00:39:12,000 assign Jake's next field to what was previously the front most cell, 817 00:39:12,000 --> 00:39:14,000 and then make the front most cell 818 00:39:14,000 --> 00:39:16,000 point to this new one that we just got back. 819 00:39:16,000 --> 00:39:20,000 So we wired out, we wired in, and now Jake is the 820 00:39:20,000 --> 00:39:33,000 new leader of the list. 821 00:39:33,000 --> 00:39:37,000 Okay, take a look at that. Like a little bit of code, but doing something pretty 822 00:39:37,000 --> 00:39:40,000 important. 823 00:39:40,000 --> 00:39:44,000 This is Jake's next field getting sent to what was the previous front most cell, 824 00:39:44,000 --> 00:39:46,000 and then updating the front most cell 825 00:39:46,000 --> 00:39:50,000 to point to Jake so that Jake will become the new leader. So if you think of it, you know, 826 00:39:50,000 --> 00:39:53,000 on the very first iteration, it's always good to make sure those [inaudible] cases 827 00:39:53,000 --> 00:39:54,000 are gonna work fine. 828 00:39:54,000 --> 00:39:59,000 If at the beginning [inaudible] there's no cells in the list so I start with an empty list, I 829 00:39:59,000 --> 00:40:03,000 get a new cell from here and then I set that new cell's next field to be the list 830 00:40:03,000 --> 00:40:06,000 that basically says set its next field to be null, 831 00:40:06,000 --> 00:40:07,000 okay. 832 00:40:07,000 --> 00:40:11,000 That's fine, there are no existing cells to attach. And now make 833 00:40:11,000 --> 00:40:12,000 the 834 00:40:12,000 --> 00:40:16,000 head cell to the list point to this new cell. So that made us a singleton list that has one 835 00:40:16,000 --> 00:40:19,000 node in it whose next field is Null, 836 00:40:19,000 --> 00:40:22,000 and then on a subsequent call -so we come back in to put the next node in, 837 00:40:22,000 --> 00:40:24,000 we'll make a new one. 838 00:40:24,000 --> 00:40:27,000 Its next field will point to what was previously our singleton cell, and then 839 00:40:27,000 --> 00:40:31,000 we update the front most pointer to point to the new cell. So it should prepend each 840 00:40:31,000 --> 00:40:33,000 one onto the list. 841 00:40:33,000 --> 00:40:37,000 So if I type the names in A, B, C that when I go to print them back out I should probably 842 00:40:37,000 --> 00:40:39,000 get them in the other order. 843 00:40:39,000 --> 00:40:42,000 So let's take a look at this. Let's write 844 00:40:42,000 --> 00:40:45,000 build list here, 845 00:40:45,000 --> 00:40:46,000 and call it. 846 00:40:46,000 --> 00:40:48,000 And then I'm -right now it's just gonna print entry, which is going to print the very 847 00:40:48,000 --> 00:40:51,000 first one, and then I'm gonna change that to print all of them. 848 00:40:51,000 --> 00:40:55,000 So if I put Julie and some phone numbers, I put Jason and some phone numbers, 849 00:40:55,000 --> 00:40:57,000 I put 850 00:40:57,000 --> 00:40:59,000 Marcia and some phone numbers, and then I 851 00:40:59,000 --> 00:41:03,000 say I'm done, then Marcia was the first one in the list so when I said print entry, I printed 852 00:41:03,000 --> 00:41:05,000 just the first one right now 853 00:41:05,000 --> 00:41:08,000 because she was the last one I put on there. It's operating a little bit 854 00:41:08,000 --> 00:41:10,000 like a stack -last in, first out. 855 00:41:10,000 --> 00:41:13,000 Then it put them on the front, so what was ever the last one entered is the one 856 00:41:13,000 --> 00:41:19,000 that is the leader of the list at this time. 857 00:41:19,000 --> 00:41:21,000 Okay. Well, I don't have time to show you much more today, so we're gonna have to do some more of this 858 00:41:21,000 --> 00:41:23,000 on Friday. 859 00:41:23,000 --> 00:41:27,000 But we'll come back and we'll look at this to do a little bit more work and start thinking about how 860 00:41:27,000 --> 00:41:28,000 recursion is an 861 00:41:28,000 --> 00:41:34,000 interesting partner with this kind of data structure.