[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:10.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:10.00,0:00:11.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:11.00,0:00:14.00,Default,,0000,0000,0000,,This presentation is delivered by the Stanford Center for Professional
Dialogue: 0,0:00:14.00,0:00:24.00,Default,,0000,0000,0000,,Development.
Dialogue: 0,0:00:24.00,0:00:26.00,Default,,0000,0000,0000,,Welcome to Friday. I keep telling you I'm gonna talk
Dialogue: 0,0:00:26.00,0:00:29.00,Default,,0000,0000,0000,,about linked list and then we don't ever get very far, but
Dialogue: 0,0:00:29.00,0:00:33.00,Default,,0000,0000,0000,,today really we are gonna talk about linked list and do some tracing and see some
Dialogue: 0,0:00:33.00,0:00:36.00,Default,,0000,0000,0000,,recursive work we can do with linked list and then
Dialogue: 0,0:00:36.00,0:00:40.00,Default,,0000,0000,0000,,I'll probably give you a little preview of the next topic, which is the introduction
Dialogue: 0,0:00:40.00,0:00:44.00,Default,,0000,0000,0000,,algorithm analysis in Big O toward the end. We won't get very far in that, but we will be talking
Dialogue: 0,0:00:44.00,0:00:47.00,Default,,0000,0000,0000,,about that all next week, which is Chapter 7 in its full glory. That
Dialogue: 0,0:00:47.00,0:00:48.00,Default,,0000,0000,0000,,will be
Dialogue: 0,0:00:48.00,0:00:51.00,Default,,0000,0000,0000,,pretty much everything we cover next week is coming out of Chapter 7, so it's all
Dialogue: 0,0:00:51.00,0:00:53.00,Default,,0000,0000,0000,,about algorithm and sorting and different
Dialogue: 0,0:00:53.00,0:00:54.00,Default,,0000,0000,0000,,algorithms.
Dialogue: 0,0:00:54.00,0:00:58.00,Default,,0000,0000,0000,,I will not be able to go - hang out with you today after class because I have an undergraduate
Dialogue: 0,0:00:58.00,0:00:59.00,Default,,0000,0000,0000,,counsel meeting.
Dialogue: 0,0:00:59.00,0:01:00.00,Default,,0000,0000,0000,,
Dialogue: 0,0:01:00.00,0:01:03.00,Default,,0000,0000,0000,,But it's a nice day so hopefully you'll have some more
Dialogue: 0,0:01:03.00,0:01:06.00,Default,,0000,0000,0000,,fun outdoor thing to do anyway.
Dialogue: 0,0:01:06.00,0:01:09.00,Default,,0000,0000,0000,,We will meet again next Friday. So
Dialogue: 0,0:01:09.00,0:01:11.00,Default,,0000,0000,0000,,put that on your calendar if you are
Dialogue: 0,0:01:11.00,0:01:16.00,Default,,0000,0000,0000,,the type who keeps a calendar. Okay.
Dialogue: 0,0:01:16.00,0:01:20.00,Default,,0000,0000,0000,,So actually I'm gonna not even really work in the things. I'm gonna go back to my
Dialogue: 0,0:01:20.00,0:01:22.00,Default,,0000,0000,0000,,editing and talk about kind of where we were at
Dialogue: 0,0:01:22.00,0:01:25.00,Default,,0000,0000,0000,,at the end of
Dialogue: 0,0:01:25.00,0:01:27.00,Default,,0000,0000,0000,,Wednesday's lecture. Was
Dialogue: 0,0:01:27.00,0:01:29.00,Default,,0000,0000,0000,,we were doing a little bit of
Dialogue: 0,0:01:29.00,0:01:31.00,Default,,0000,0000,0000,,coding with the linked list itself.
Dialogue: 0,0:01:31.00,0:01:35.00,Default,,0000,0000,0000,,So having defined that recursive structure that has the information from
Dialogue: 0,0:01:35.00,0:01:37.00,Default,,0000,0000,0000,,one entry plus a pointer to the next
Dialogue: 0,0:01:37.00,0:01:40.00,Default,,0000,0000,0000,,and then so far the little pieces we have is something that we will print an individual
Dialogue: 0,0:01:40.00,0:01:41.00,Default,,0000,0000,0000,,entry,
Dialogue: 0,0:01:41.00,0:01:44.00,Default,,0000,0000,0000,,something that will create a new entry out in the heap, filling in with data
Dialogue: 0,0:01:44.00,0:01:47.00,Default,,0000,0000,0000,,that was read from the console typed in by the user,
Dialogue: 0,0:01:47.00,0:01:51.00,Default,,0000,0000,0000,,and then the last bit of code that we were looking at was this idea of building the
Dialogue: 0,0:01:51.00,0:01:52.00,Default,,0000,0000,0000,,list
Dialogue: 0,0:01:52.00,0:01:55.00,Default,,0000,0000,0000,,by getting a new entry.
Dialogue: 0,0:01:55.00,0:01:58.00,Default,,0000,0000,0000,,So a pointer coming back from there that points to a new heap allocated
Dialogue: 0,0:01:58.00,0:02:01.00,Default,,0000,0000,0000,,structure that has the name and the address of someone
Dialogue: 0,0:02:01.00,0:02:03.00,Default,,0000,0000,0000,,and then attaching it to the
Dialogue: 0,0:02:03.00,0:02:06.00,Default,,0000,0000,0000,,front part of the list. So we talked about why that was
Dialogue: 0,0:02:06.00,0:02:08.00,Default,,0000,0000,0000,,the easiest thing to do and I'm gonna
Dialogue: 0,0:02:08.00,0:02:11.00,Default,,0000,0000,0000,,just re-draw this picture again because we're gonna need it
Dialogue: 0,0:02:11.00,0:02:16.00,Default,,0000,0000,0000,,as we go through and do stuff. Here's the main stack frame.
Dialogue: 0,0:02:16.00,0:02:19.00,Default,,0000,0000,0000,,It's got this pointer list, which
Dialogue: 0,0:02:19.00,0:02:23.00,Default,,0000,0000,0000,,is expected to point to an entry out in the heap. It starts pointing at null.
Dialogue: 0,0:02:23.00,0:02:26.00,Default,,0000,0000,0000,,We have this local variable down here, new one
Dialogue: 0,0:02:26.00,0:02:29.00,Default,,0000,0000,0000,,that is also a pointer to an entry
Dialogue: 0,0:02:29.00,0:02:32.00,Default,,0000,0000,0000,,and based on the result from get new entry, which will either return null to say
Dialogue: 0,0:02:32.00,0:02:36.00,Default,,0000,0000,0000,,there's no more entries or a new heap allocated thing if it gives us this new
Dialogue: 0,0:02:36.00,0:02:38.00,Default,,0000,0000,0000,,entry that says
Dialogue: 0,0:02:38.00,0:02:43.00,Default,,0000,0000,0000,,here's Jason and his phone number.
Dialogue: 0,0:02:43.00,0:02:48.00,Default,,0000,0000,0000,,That the lines there - the new ones next equals list so
Dialogue: 0,0:02:48.00,0:02:52.00,Default,,0000,0000,0000,,new ones next field, right? Gets assigned the value of list, which affectively just copies
Dialogue: 0,0:02:52.00,0:02:54.00,Default,,0000,0000,0000,,a null on top of a null
Dialogue: 0,0:02:54.00,0:02:59.00,Default,,0000,0000,0000,,and then sets list to point to the same place that new 1 does.
Dialogue: 0,0:02:59.00,0:03:01.00,Default,,0000,0000,0000,,So on the first iteration,
Dialogue: 0,0:03:01.00,0:03:04.00,Default,,0000,0000,0000,,Jason is the new front most cell on the list,
Dialogue: 0,0:03:04.00,0:03:08.00,Default,,0000,0000,0000,,has a null terminator in the next field, which says there's no further cells. So we
Dialogue: 0,0:03:08.00,0:03:10.00,Default,,0000,0000,0000,,have a singleton list of just one cell.
Dialogue: 0,0:03:10.00,0:03:13.00,Default,,0000,0000,0000,,Now the subsequent iteration
Dialogue: 0,0:03:13.00,0:03:17.00,Default,,0000,0000,0000,,we call get new entry returns us a new
Dialogue: 0,0:03:17.00,0:03:23.00,Default,,0000,0000,0000,,pointer to another cell out here on the list. This one's gonna be Joel.
Dialogue: 0,0:03:23.00,0:03:27.00,Default,,0000,0000,0000,,He starts off as his own singleton list and then here's the attach again.
Dialogue: 0,0:03:27.00,0:03:29.00,Default,,0000,0000,0000,,New ones
Dialogue: 0,0:03:29.00,0:03:32.00,Default,,0000,0000,0000,,next field gets the value of list,
Dialogue: 0,0:03:32.00,0:03:35.00,Default,,0000,0000,0000,,so that changes
Dialogue: 0,0:03:35.00,0:03:38.00,Default,,0000,0000,0000,,Joel's next to
Dialogue: 0,0:03:38.00,0:03:41.00,Default,,0000,0000,0000,,point to where list does now. So I have two different ways to get to Jason's cell
Dialogue: 0,0:03:41.00,0:03:45.00,Default,,0000,0000,0000,,now. Directly, it's the front most cell of the list still, but it's now following Joel.
Dialogue: 0,0:03:45.00,0:03:47.00,Default,,0000,0000,0000,,And then I update list
Dialogue: 0,0:03:47.00,0:03:49.00,Default,,0000,0000,0000,,to point to new one,
Dialogue: 0,0:03:49.00,0:03:54.00,Default,,0000,0000,0000,,so doing pointer assignment on this. Copying the pointers, making an alias,
Dialogue: 0,0:03:54.00,0:03:55.00,Default,,0000,0000,0000,,and now
Dialogue: 0,0:03:55.00,0:03:59.00,Default,,0000,0000,0000,,at the bottom of that loop, right? I now have list pointing to Joel, which points
Dialogue: 0,0:03:59.00,0:04:02.00,Default,,0000,0000,0000,,to Jason, which points to null. So my two entry list.
Dialogue: 0,0:04:02.00,0:04:05.00,Default,,0000,0000,0000,,Every subsequent cell that's created is
Dialogue: 0,0:04:05.00,0:04:06.00,Default,,0000,0000,0000,,prepended, right?
Dialogue: 0,0:04:06.00,0:04:08.00,Default,,0000,0000,0000,,Placed in the front most position of a list
Dialogue: 0,0:04:08.00,0:04:11.00,Default,,0000,0000,0000,,and then the remainder of the list trails behind it.
Dialogue: 0,0:04:11.00,0:04:13.00,Default,,0000,0000,0000,,So we should expect that if we
Dialogue: 0,0:04:13.00,0:04:16.00,Default,,0000,0000,0000,,put in the list A, B, C that if we were to go back and traverse it we'll
Dialogue: 0,0:04:16.00,0:04:18.00,Default,,0000,0000,0000,,discover it goes C, B, A. And
Dialogue: 0,0:04:18.00,0:04:22.00,Default,,0000,0000,0000,,so I was just about to show you that and then we ran out of time. So I'm gonna go ahead and
Dialogue: 0,0:04:22.00,0:04:22.00,Default,,0000,0000,0000,,finish that because I'm gonna
Dialogue: 0,0:04:22.00,0:04:31.00,Default,,0000,0000,0000,,write something that will print an entire linked list.
Dialogue: 0,0:04:31.00,0:04:33.00,Default,,0000,0000,0000,,It will take the list that we have and I'm gonna
Dialogue: 0,0:04:33.00,0:04:35.00,Default,,0000,0000,0000,,show you
Dialogue: 0,0:04:35.00,0:04:39.00,Default,,0000,0000,0000,,that.
Dialogue: 0,0:04:39.00,0:04:42.00,Default,,0000,0000,0000,,So the idea is to
Dialogue: 0,0:04:42.00,0:04:44.00,Default,,0000,0000,0000,,traverse a pointer
Dialogue: 0,0:04:44.00,0:04:47.00,Default,,0000,0000,0000,,down the list
Dialogue: 0,0:04:47.00,0:04:49.00,Default,,0000,0000,0000,,and print each one in
Dialogue: 0,0:04:49.00,0:04:51.00,Default,,0000,0000,0000,,turn. I'm gonna do that using a four loop. It
Dialogue: 0,0:04:51.00,0:04:55.00,Default,,0000,0000,0000,,may seem a little bit like an odd use of the four loop, but in fact what
Dialogue: 0,0:04:55.00,0:04:59.00,Default,,0000,0000,0000,,we're doing is really comparable to how you would do iteration down a link, an
Dialogue: 0,0:04:59.00,0:05:00.00,Default,,0000,0000,0000,,array,
Dialogue: 0,0:05:00.00,0:05:03.00,Default,,0000,0000,0000,,using kind of zero to n, you know, I++.
Dialogue: 0,0:05:03.00,0:05:06.00,Default,,0000,0000,0000,,We're doing the same thing, but instead of advancing an integer, which
Dialogue: 0,0:05:06.00,0:05:10.00,Default,,0000,0000,0000,,indexes into that, we're actually keeping track of a pointer, which moves down.
Dialogue: 0,0:05:10.00,0:05:14.00,Default,,0000,0000,0000,,So the initial state of that pointer as we assign it to be the value of the list,
Dialogue: 0,0:05:14.00,0:05:17.00,Default,,0000,0000,0000,,so we alias to the first cell of the list.
Dialogue: 0,0:05:17.00,0:05:20.00,Default,,0000,0000,0000,,While that pointer points this invalid cell not to null,
Dialogue: 0,0:05:20.00,0:05:23.00,Default,,0000,0000,0000,,so as long as there are still cells to process
Dialogue: 0,0:05:23.00,0:05:25.00,Default,,0000,0000,0000,,then we'll print to
Dialogue: 0,0:05:25.00,0:05:28.00,Default,,0000,0000,0000,,cell. Then we'll advance the kind of equivalent of the I++.
Dialogue: 0,0:05:28.00,0:05:30.00,Default,,0000,0000,0000,,Here's the Kerr equals Kerr next.
Dialogue: 0,0:05:30.00,0:05:34.00,Default,,0000,0000,0000,,So advancing - so starting from Kerr equals Joel, right? To Kerr equals Jason and then Kerr
Dialogue: 0,0:05:34.00,0:05:38.00,Default,,0000,0000,0000,,equals null, which will terminate that. So as long as our linked list is properly
Dialogue: 0,0:05:38.00,0:05:40.00,Default,,0000,0000,0000,,terminated, right? We should print all the cells
Dialogue: 0,0:05:40.00,0:05:41.00,Default,,0000,0000,0000,,from front to back
Dialogue: 0,0:05:41.00,0:05:43.00,Default,,0000,0000,0000,,using this one loop.
Dialogue: 0,0:05:43.00,0:05:47.00,Default,,0000,0000,0000,,And so if I change this down here to be print list instead of just print to the front
Dialogue: 0,0:05:47.00,0:05:48.00,Default,,0000,0000,0000,,most entry
Dialogue: 0,0:05:48.00,0:05:56.00,Default,,0000,0000,0000,,and then I run a little test on this.
Dialogue: 0,0:05:56.00,0:05:58.00,Default,,0000,0000,0000,,So I enter Jake
Dialogue: 0,0:05:58.00,0:06:00.00,Default,,0000,0000,0000,,and his phone number,
Dialogue: 0,0:06:00.00,0:06:02.00,Default,,0000,0000,0000,,and I enter
Dialogue: 0,0:06:02.00,0:06:04.00,Default,,0000,0000,0000,,Carl and his phone number, and then I
Dialogue: 0,0:06:04.00,0:06:06.00,Default,,0000,0000,0000,,enter Ilia and
Dialogue: 0,0:06:06.00,0:06:07.00,Default,,0000,0000,0000,,his phone number, and I
Dialogue: 0,0:06:07.00,0:06:10.00,Default,,0000,0000,0000,,see that's all I have. Then they come back out in the opposite order,
Dialogue: 0,0:06:10.00,0:06:13.00,Default,,0000,0000,0000,,right? That Ilia, Carl, Jake
Dialogue: 0,0:06:13.00,0:06:17.00,Default,,0000,0000,0000,,because of the way I was placing them in the front of the list, right? Kind of effectively reversed, right? Them
Dialogue: 0,0:06:17.00,0:06:22.00,Default,,0000,0000,0000,,from the order they were inserted. Do you have a question? Do people ever
Dialogue: 0,0:06:22.00,0:06:22.00,Default,,0000,0000,0000,,make blank lists so that you can traverse backwards
Dialogue: 0,0:06:22.00,0:06:25.00,Default,,0000,0000,0000,,through them?
Dialogue: 0,0:06:25.00,0:06:28.00,Default,,0000,0000,0000,,They certainly do. So the simplest form of the linked list, right? Has only these
Dialogue: 0,0:06:28.00,0:06:33.00,Default,,0000,0000,0000,,forward links, right? So each cell gets to the one that follows it in the list,
Dialogue: 0,0:06:33.00,0:06:36.00,Default,,0000,0000,0000,,but that is gonna create certain asymmetries in how you process that list.
Dialogue: 0,0:06:36.00,0:06:38.00,Default,,0000,0000,0000,,You're always gonna start at the front and move your way to the back. Well, what happens if you're
Dialogue: 0,0:06:38.00,0:06:40.00,Default,,0000,0000,0000,,at a cell and you'd like to back up, right?
Dialogue: 0,0:06:40.00,0:06:42.00,Default,,0000,0000,0000,,It doesn't have the information
Dialogue: 0,0:06:42.00,0:06:46.00,Default,,0000,0000,0000,,in the single chain to do that. So you can build lists that either
Dialogue: 0,0:06:46.00,0:06:49.00,Default,,0000,0000,0000,,link in the other direction or link in both directions, right? To where you
Dialogue: 0,0:06:49.00,0:06:53.00,Default,,0000,0000,0000,,can, from a particular cell, find who proceeded it and who followed it. It just makes
Dialogue: 0,0:06:53.00,0:06:56.00,Default,,0000,0000,0000,,more pointers, right? And more complication. We'll see reasons why that actually
Dialogue: 0,0:06:56.00,0:06:59.00,Default,,0000,0000,0000,,becomes valuable. At this stage it turns out that it would just be
Dialogue: 0,0:06:59.00,0:07:02.00,Default,,0000,0000,0000,,complication that we wouldn't really be taking advantage of, but
Dialogue: 0,0:07:02.00,0:07:05.00,Default,,0000,0000,0000,,in a week or two we're gonna get to some place where that turns out to be a very, very
Dialogue: 0,0:07:05.00,0:07:08.00,Default,,0000,0000,0000,,useful addition to the list because it turns out that we really will need to be
Dialogue: 0,0:07:08.00,0:07:11.00,Default,,0000,0000,0000,,able to kind of move easily in both directions and right now we're not too
Dialogue: 0,0:07:11.00,0:07:12.00,Default,,0000,0000,0000,,worried about
Dialogue: 0,0:07:12.00,0:07:18.00,Default,,0000,0000,0000,,any direction other than the front ways.
Dialogue: 0,0:07:18.00,0:07:21.00,Default,,0000,0000,0000,,So this idea of
Dialogue: 0,0:07:21.00,0:07:23.00,Default,,0000,0000,0000,,the four loop, right? Is
Dialogue: 0,0:07:23.00,0:07:27.00,Default,,0000,0000,0000,,just one of the ways I could have done this. I could do this with a Y loop,
Dialogue: 0,0:07:27.00,0:07:28.00,Default,,0000,0000,0000,,right? Other sort of forms of iteration.
Dialogue: 0,0:07:28.00,0:07:31.00,Default,,0000,0000,0000,,I could also
Dialogue: 0,0:07:31.00,0:07:35.00,Default,,0000,0000,0000,,capitalize on the recursive nature of the list, and this is partly why I've chosen to introduce
Dialogue: 0,0:07:35.00,0:07:37.00,Default,,0000,0000,0000,,this topic now, is because I really do want to stress that this idea that it's a
Dialogue: 0,0:07:37.00,0:07:39.00,Default,,0000,0000,0000,,recursive structure
Dialogue: 0,0:07:39.00,0:07:42.00,Default,,0000,0000,0000,,gives us a little bit of an insight into ways that operations on it
Dialogue: 0,0:07:42.00,0:07:45.00,Default,,0000,0000,0000,,might be able to take advantage of that recursive nature.
Dialogue: 0,0:07:45.00,0:07:48.00,Default,,0000,0000,0000,,So let me write this alternate print list, and I'll
Dialogue: 0,0:07:48.00,0:07:52.00,Default,,0000,0000,0000,,call it recursive print list,
Dialogue: 0,0:07:52.00,0:07:55.00,Default,,0000,0000,0000,,that is designed to use recursion to get the job done.
Dialogue: 0,0:07:55.00,0:08:00.00,Default,,0000,0000,0000,,So in terms of thinking about it recursively, you can think of, well, a linked list is
Dialogue: 0,0:08:00.00,0:08:03.00,Default,,0000,0000,0000,,the sequence of cells and iteration kind of thinks of the whole sequence at one
Dialogue: 0,0:08:03.00,0:08:04.00,Default,,0000,0000,0000,,time.
Dialogue: 0,0:08:04.00,0:08:08.00,Default,,0000,0000,0000,,Recursion tends to take the strategy of, well, I'm just gonna separate it into
Dialogue: 0,0:08:08.00,0:08:12.00,Default,,0000,0000,0000,,something small I can deal with right now and then some instance of the same
Dialogue: 0,0:08:12.00,0:08:14.00,Default,,0000,0000,0000,,problem, but in a slightly smaller simpler form.
Dialogue: 0,0:08:14.00,0:08:18.00,Default,,0000,0000,0000,,The easy way to do that with a linked list is imagine there's the front
Dialogue: 0,0:08:18.00,0:08:20.00,Default,,0000,0000,0000,,most cell.
Dialogue: 0,0:08:20.00,0:08:23.00,Default,,0000,0000,0000,,Which I could print by calling print entry, which prints a single entry.
Dialogue: 0,0:08:23.00,0:08:26.00,Default,,0000,0000,0000,,And then there is this recursive
Dialogue: 0,0:08:26.00,0:08:29.00,Default,,0000,0000,0000,,structure left behind, which is the remainder of the list and I can say, well,
Dialogue: 0,0:08:29.00,0:08:32.00,Default,,0000,0000,0000,,I can recursively print the list
Dialogue: 0,0:08:32.00,0:08:34.00,Default,,0000,0000,0000,,that follows.
Dialogue: 0,0:08:34.00,0:08:36.00,Default,,0000,0000,0000,,So print the front most cell,
Dialogue: 0,0:08:36.00,0:08:40.00,Default,,0000,0000,0000,,let recursion work its magic on what remains.
Dialogue: 0,0:08:40.00,0:08:43.00,Default,,0000,0000,0000,,Looks pretty good. Something really critical missing?
Dialogue: 0,0:08:43.00,0:08:45.00,Default,,0000,0000,0000,,Base case. Better have a base case here.
Dialogue: 0,0:08:45.00,0:08:49.00,Default,,0000,0000,0000,,And the simplest possible base case is list equals equals null.
Dialogue: 0,0:08:49.00,0:08:53.00,Default,,0000,0000,0000,,If list equals equals null then it won't have nothing to do, so I can just return or I
Dialogue: 0,0:08:53.00,0:08:55.00,Default,,0000,0000,0000,,can actually just do it like this. Say if list
Dialogue: 0,0:08:55.00,0:08:57.00,Default,,0000,0000,0000,,does not equal null, so it has some
Dialogue: 0,0:08:57.00,0:08:59.00,Default,,0000,0000,0000,,valid contents,
Dialogue: 0,0:08:59.00,0:09:00.00,Default,,0000,0000,0000,,something to look at,
Dialogue: 0,0:09:00.00,0:09:03.00,Default,,0000,0000,0000,,then we'll print the front most one and then let recursion take care of the
Dialogue: 0,0:09:03.00,0:09:05.00,Default,,0000,0000,0000,,rest. So
Dialogue: 0,0:09:05.00,0:09:11.00,Default,,0000,0000,0000,,I'll change my called print list to be a recursive print list. And I should
Dialogue: 0,0:09:11.00,0:09:12.00,Default,,0000,0000,0000,,see some [inaudible] results here.
Dialogue: 0,0:09:12.00,0:09:15.00,Default,,0000,0000,0000,,I say that
Dialogue: 0,0:09:15.00,0:09:17.00,Default,,0000,0000,0000,,Nathan is here, I
Dialogue: 0,0:09:17.00,0:09:20.00,Default,,0000,0000,0000,,say Jason is here, I
Dialogue: 0,0:09:20.00,0:09:21.00,Default,,0000,0000,0000,,Sara,
Dialogue: 0,0:09:21.00,0:09:23.00,Default,,0000,0000,0000,,Sara are you an H? I don't
Dialogue: 0,0:09:23.00,0:09:24.00,Default,,0000,0000,0000,,remember.
Dialogue: 0,0:09:24.00,0:09:26.00,Default,,0000,0000,0000,,Today it doesn't.
Dialogue: 0,0:09:26.00,0:09:30.00,Default,,0000,0000,0000,,Sara, Jason, Nathan coming out the other way. Okay.
Dialogue: 0,0:09:30.00,0:09:33.00,Default,,0000,0000,0000,,So I want to do something kind of funny with this recursive call.
Dialogue: 0,0:09:33.00,0:09:33.00,Default,,0000,0000,0000,,So it's
Dialogue: 0,0:09:33.00,0:09:37.00,Default,,0000,0000,0000,,not really in this case - both of these look equally simple to write. We're
Dialogue: 0,0:09:37.00,0:09:40.00,Default,,0000,0000,0000,,gonna start to look at some things where this actually might buy
Dialogue: 0,0:09:40.00,0:09:43.00,Default,,0000,0000,0000,,us something. For example, lets imagine that what I wanted to do was print the
Dialogue: 0,0:09:43.00,0:09:47.00,Default,,0000,0000,0000,,list in the other order. So I don't have the list
Dialogue: 0,0:09:47.00,0:09:48.00,Default,,0000,0000,0000,,that links backwards.
Dialogue: 0,0:09:48.00,0:09:50.00,Default,,0000,0000,0000,,So if I really did want to print them
Dialogue: 0,0:09:50.00,0:09:52.00,Default,,0000,0000,0000,,with the last most element first,
Dialogue: 0,0:09:52.00,0:09:56.00,Default,,0000,0000,0000,,the way that they were added at the console,
Dialogue: 0,0:09:56.00,0:09:58.00,Default,,0000,0000,0000,,and the way I'm building the list, right? Is putting them in the other order. So, well, could I just take
Dialogue: 0,0:09:58.00,0:10:00.00,Default,,0000,0000,0000,,the list and print it back to front?
Dialogue: 0,0:10:00.00,0:10:03.00,Default,,0000,0000,0000,,I mean, it's simple enough to do that on a vector, if you had one, to work from
Dialogue: 0,0:10:03.00,0:10:06.00,Default,,0000,0000,0000,,the way back. Could I do it with the linked list?
Dialogue: 0,0:10:06.00,0:10:09.00,Default,,0000,0000,0000,,In the iterate formulation it's gonna actually get pretty messy because I'm
Dialogue: 0,0:10:09.00,0:10:12.00,Default,,0000,0000,0000,,gonna have to walk my way all the way down to the end and then print the last one, and then I'm
Dialogue: 0,0:10:12.00,0:10:15.00,Default,,0000,0000,0000,,gonna have to walk my way down to the one that points to the last one and
Dialogue: 0,0:10:15.00,0:10:18.00,Default,,0000,0000,0000,,print it, and then I'm gonna have to walk my way down to the one that printed to the penultimate
Dialogue: 0,0:10:18.00,0:10:19.00,Default,,0000,0000,0000,,one and print it,
Dialogue: 0,0:10:19.00,0:10:21.00,Default,,0000,0000,0000,,but it does involve a lot of traversal and a lot of work.
Dialogue: 0,0:10:21.00,0:10:24.00,Default,,0000,0000,0000,,I can make the recursive print one do it
Dialogue: 0,0:10:24.00,0:10:28.00,Default,,0000,0000,0000,,with just one tiny change of the code.
Dialogue: 0,0:10:28.00,0:10:30.00,Default,,0000,0000,0000,,Take this line
Dialogue: 0,0:10:30.00,0:10:34.00,Default,,0000,0000,0000,,and put it there. So
Dialogue: 0,0:10:34.00,0:10:37.00,Default,,0000,0000,0000,,what I'm doing here is letting recursion do the work for me of
Dialogue: 0,0:10:37.00,0:10:42.00,Default,,0000,0000,0000,,saying, well, print everything that follows me in the list before you print this cell. So
Dialogue: 0,0:10:42.00,0:10:46.00,Default,,0000,0000,0000,,if the list is A, B, C it says when you get to the A node it says
Dialogue: 0,0:10:46.00,0:10:49.00,Default,,0000,0000,0000,,okay, please print the things that follow me before you get back to me. Well, recursion
Dialogue: 0,0:10:49.00,0:10:52.00,Default,,0000,0000,0000,,being applied to the B, C list says, well, B says, well, hold onto B, print everything
Dialogue: 0,0:10:52.00,0:10:56.00,Default,,0000,0000,0000,,that follows me before you print B, when C gets there it says, well, print everything that
Dialogue: 0,0:10:56.00,0:10:59.00,Default,,0000,0000,0000,,follows me, which turns out to be nothing, which causes it to come back and
Dialogue: 0,0:10:59.00,0:11:02.00,Default,,0000,0000,0000,,say, well, okay, I'm done with the part that followed C, why don't we print C,
Dialogue: 0,0:11:02.00,0:11:03.00,Default,,0000,0000,0000,,and then print B, and then print A.
Dialogue: 0,0:11:03.00,0:11:09.00,Default,,0000,0000,0000,,So if I do this and
Dialogue: 0,0:11:09.00,0:11:10.00,Default,,0000,0000,0000,,print it through I put
Dialogue: 0,0:11:10.00,0:11:12.00,Default,,0000,0000,0000,,in A,
Dialogue: 0,0:11:12.00,0:11:16.00,Default,,0000,0000,0000,,B, C.
Dialogue: 0,0:11:16.00,0:11:18.00,Default,,0000,0000,0000,,Then they get printed out in the order I inserted them.
Dialogue: 0,0:11:18.00,0:11:23.00,Default,,0000,0000,0000,,They happen to be stored internally as C, B, A, but then I just do a
Dialogue: 0,0:11:23.00,0:11:25.00,Default,,0000,0000,0000,,change-a-roo was printing
Dialogue: 0,0:11:25.00,0:11:29.00,Default,,0000,0000,0000,,to print from the back of the list to the front of the list in the other order.
Dialogue: 0,0:11:29.00,0:11:32.00,Default,,0000,0000,0000,,But just the magic of recursion, right? A very simple little change, right? In terms of
Dialogue: 0,0:11:32.00,0:11:34.00,Default,,0000,0000,0000,,doing the work before the recursive call
Dialogue: 0,0:11:34.00,0:11:36.00,Default,,0000,0000,0000,,versus after
Dialogue: 0,0:11:36.00,0:11:39.00,Default,,0000,0000,0000,,gave me exactly what I wanted without any real craziness
Dialogue: 0,0:11:39.00,0:11:42.00,Default,,0000,0000,0000,,inserted in the code. We'll do a couple
Dialogue: 0,0:11:42.00,0:11:44.00,Default,,0000,0000,0000,,of other little things with you
Dialogue: 0,0:11:44.00,0:11:46.00,Default,,0000,0000,0000,,and
Dialogue: 0,0:11:46.00,0:11:49.00,Default,,0000,0000,0000,,I'm gonna do them recursively just
Dialogue: 0,0:11:49.00,0:11:50.00,Default,,0000,0000,0000,,for practice.
Dialogue: 0,0:11:50.00,0:11:53.00,Default,,0000,0000,0000,,
Dialogue: 0,0:11:53.00,0:11:57.00,Default,,0000,0000,0000,,If I wanted to count them, I wanted to know how many cells
Dialogue: 0,0:11:57.00,0:12:02.00,Default,,0000,0000,0000,,are in my list, then thinking about
Dialogue: 0,0:12:02.00,0:12:03.00,Default,,0000,0000,0000,,it recursively
Dialogue: 0,0:12:03.00,0:12:06.00,Default,,0000,0000,0000,,is a matter of saying, well, there's a cell in the front
Dialogue: 0,0:12:06.00,0:12:06.00,Default,,0000,0000,0000,,
Dialogue: 0,0:12:06.00,0:12:10.00,Default,,0000,0000,0000,,and then there's some count of the cells that follow it. If I add those together,
Dialogue: 0,0:12:10.00,0:12:12.00,Default,,0000,0000,0000,,that tells me how long this list is.
Dialogue: 0,0:12:12.00,0:12:13.00,Default,,0000,0000,0000,,
Dialogue: 0,0:12:13.00,0:12:16.00,Default,,0000,0000,0000,,Having a base case there that says when I get to the completely empty list where the list
Dialogue: 0,0:12:16.00,0:12:17.00,Default,,0000,0000,0000,,is null
Dialogue: 0,0:12:17.00,0:12:20.00,Default,,0000,0000,0000,,then there are no more cells to count that returns my zero. So it will work its way all the way down
Dialogue: 0,0:12:20.00,0:12:22.00,Default,,0000,0000,0000,,to the bottom,
Dialogue: 0,0:12:22.00,0:12:25.00,Default,,0000,0000,0000,,find that trailing null that sentinels the end, and then kind of count on its way
Dialogue: 0,0:12:25.00,0:12:28.00,Default,,0000,0000,0000,,back out. Okay, there was one before that and then one before that and add those
Dialogue: 0,0:12:28.00,0:12:29.00,Default,,0000,0000,0000,,all up
Dialogue: 0,0:12:29.00,0:12:33.00,Default,,0000,0000,0000,,to tell me how many entries are in my address book. So I can do
Dialogue: 0,0:12:33.00,0:12:36.00,Default,,0000,0000,0000,,that here. I can say what is the count in
Dialogue: 0,0:12:36.00,0:12:38.00,Default,,0000,0000,0000,,my
Dialogue: 0,0:12:38.00,0:12:43.00,Default,,0000,0000,0000,,address book? And maybe I'll stop printing it because I'm - and so
Dialogue: 0,0:12:43.00,0:12:46.00,Default,,0000,0000,0000,,I can test it on a couple of things. Well, what if I put
Dialogue: 0,0:12:46.00,0:12:50.00,Default,,0000,0000,0000,,an empty cell in so I have a null? If I get
Dialogue: 0,0:12:50.00,0:12:54.00,Default,,0000,0000,0000,,one cell in there, right? Then I should have one and I can even do a couple more. A, B, C.
Dialogue: 0,0:12:54.00,0:12:55.00,Default,,0000,0000,0000,,Got
Dialogue: 0,0:12:55.00,0:12:59.00,Default,,0000,0000,0000,,three cells. I'll
Dialogue: 0,0:12:59.00,0:13:00.00,Default,,0000,0000,0000,,do
Dialogue: 0,0:13:00.00,0:13:06.00,Default,,0000,0000,0000,,another little one while I'm here.
Dialogue: 0,0:13:06.00,0:13:08.00,Default,,0000,0000,0000,,Is that when I'm done with the linked list,
Dialogue: 0,0:13:08.00,0:13:11.00,Default,,0000,0000,0000,,all those heap allocated cells, right?
Dialogue: 0,0:13:11.00,0:13:14.00,Default,,0000,0000,0000,,Are just out there clogging up my heap. So when I'm done with this list
Dialogue: 0,0:13:14.00,0:13:16.00,Default,,0000,0000,0000,,the appropriate thing to do is to deallocate it.
Dialogue: 0,0:13:16.00,0:13:18.00,Default,,0000,0000,0000,,I will note, actually, just to be clear though,
Dialogue: 0,0:13:18.00,0:13:23.00,Default,,0000,0000,0000,,that any memory that's allocated by main and kind of in the process of working the program that
Dialogue: 0,0:13:23.00,0:13:27.00,Default,,0000,0000,0000,,when you actually exit the program it automatically deallocated. So
Dialogue: 0,0:13:27.00,0:13:29.00,Default,,0000,0000,0000,,when you are completed with the program and you're exiting
Dialogue: 0,0:13:29.00,0:13:33.00,Default,,0000,0000,0000,,you can go around and be tidy and clean stuff up, but, in fact, there's not a lot of point
Dialogue: 0,0:13:33.00,0:13:33.00,Default,,0000,0000,0000,,to it.
Dialogue: 0,0:13:33.00,0:13:36.00,Default,,0000,0000,0000,,The more important reason, right? To deallocation would be during the
Dialogue: 0,0:13:36.00,0:13:40.00,Default,,0000,0000,0000,,running of the program as you're playing games or monitoring things or doing the
Dialogue: 0,0:13:40.00,0:13:41.00,Default,,0000,0000,0000,,data.
Dialogue: 0,0:13:41.00,0:13:43.00,Default,,0000,0000,0000,,If you are not deallocating - if the program, especially if it's
Dialogue: 0,0:13:43.00,0:13:44.00,Default,,0000,0000,0000,,long
Dialogue: 0,0:13:44.00,0:13:45.00,Default,,0000,0000,0000,,running,
Dialogue: 0,0:13:45.00,0:13:49.00,Default,,0000,0000,0000,,will eventually have problems related to its kind of gargantuan memory size if it's
Dialogue: 0,0:13:49.00,0:13:52.00,Default,,0000,0000,0000,,not being careful about releasing memory.
Dialogue: 0,0:13:52.00,0:13:55.00,Default,,0000,0000,0000,,When you're done deleting it manually or just letting the system take it down as
Dialogue: 0,0:13:55.00,0:13:57.00,Default,,0000,0000,0000,,part of the process
Dialogue: 0,0:13:57.00,0:13:58.00,Default,,0000,0000,0000,,there's not much
Dialogue: 0,0:13:58.00,0:14:00.00,Default,,0000,0000,0000,,advantage to.
Dialogue: 0,0:14:00.00,0:14:03.00,Default,,0000,0000,0000,,So if I'm gonna deallocate a list,
Dialogue: 0,0:14:03.00,0:14:07.00,Default,,0000,0000,0000,,if the list does not equal null there's something deallocate.
Dialogue: 0,0:14:07.00,0:14:07.00,Default,,0000,0000,0000,,I'm
Dialogue: 0,0:14:07.00,0:14:11.00,Default,,0000,0000,0000,,gonna do this wrong first and then we'll talk about why
Dialogue: 0,0:14:11.00,0:14:15.00,Default,,0000,0000,0000,,it's not what I want to do.
Dialogue: 0,0:14:15.00,0:14:19.00,Default,,0000,0000,0000,,That's good exercise remembering things. So I think, okay, well, what I need to do
Dialogue: 0,0:14:19.00,0:14:22.00,Default,,0000,0000,0000,,is delete the front most cell
Dialogue: 0,0:14:22.00,0:14:26.00,Default,,0000,0000,0000,,and then deallocate all those cells that follow it. So
Dialogue: 0,0:14:26.00,0:14:29.00,Default,,0000,0000,0000,,using recursion, right? To kind of divide the problem up.
Dialogue: 0,0:14:29.00,0:14:32.00,Default,,0000,0000,0000,,It's a matter of deleting the front cell and then saying, okay, whatever else needs to
Dialogue: 0,0:14:32.00,0:14:35.00,Default,,0000,0000,0000,,be done needs to be done to everything that remains. List dot next gives me a pointer to that
Dialogue: 0,0:14:35.00,0:14:37.00,Default,,0000,0000,0000,,smaller sub list to work on.
Dialogue: 0,0:14:37.00,0:14:41.00,Default,,0000,0000,0000,,As written, this does try to make the right delete calls,
Dialogue: 0,0:14:41.00,0:14:44.00,Default,,0000,0000,0000,,but it does something really dangerous in terms of use of free memory. Anybody want
Dialogue: 0,0:14:44.00,0:14:46.00,Default,,0000,0000,0000,,to help me out with that? After it
Dialogue: 0,0:14:46.00,0:14:48.00,Default,,0000,0000,0000,,deletes the first
Dialogue: 0,0:14:48.00,0:14:50.00,Default,,0000,0000,0000,,element it doesn't know where to find the rest of it.
Dialogue: 0,0:14:50.00,0:14:51.00,Default,,0000,0000,0000,,That's exactly right.
Dialogue: 0,0:14:51.00,0:14:56.00,Default,,0000,0000,0000,,So this one said delete list. So if I think of it in terms of a picture here
Dialogue: 0,0:14:56.00,0:14:59.00,Default,,0000,0000,0000,,coming into the call
Dialogue: 0,0:14:59.00,0:15:01.00,Default,,0000,0000,0000,,list to some pointer
Dialogue: 0,0:15:01.00,0:15:05.00,Default,,0000,0000,0000,,to these nodes
Dialogue: 0,0:15:05.00,0:15:07.00,Default,,0000,0000,0000,,that are out here, A, B, and C,
Dialogue: 0,0:15:07.00,0:15:09.00,Default,,0000,0000,0000,,followed by null and I
Dialogue: 0,0:15:09.00,0:15:11.00,Default,,0000,0000,0000,,said delete list.
Dialogue: 0,0:15:11.00,0:15:14.00,Default,,0000,0000,0000,,So delete list says follow list to find that piece of memory out there in
Dialogue: 0,0:15:14.00,0:15:18.00,Default,,0000,0000,0000,,the heap and mark this cell
Dialogue: 0,0:15:18.00,0:15:19.00,Default,,0000,0000,0000,,as deleted,
Dialogue: 0,0:15:19.00,0:15:22.00,Default,,0000,0000,0000,,no longer in use, ready to be reclaimed.
Dialogue: 0,0:15:22.00,0:15:24.00,Default,,0000,0000,0000,,The very next line
Dialogue: 0,0:15:24.00,0:15:26.00,Default,,0000,0000,0000,,says deallocate list arrow next.
Dialogue: 0,0:15:26.00,0:15:30.00,Default,,0000,0000,0000,,And so that is actually using list, right? To point back into this piece of freed
Dialogue: 0,0:15:30.00,0:15:31.00,Default,,0000,0000,0000,,memory
Dialogue: 0,0:15:31.00,0:15:33.00,Default,,0000,0000,0000,,and try to read this number out of here.
Dialogue: 0,0:15:33.00,0:15:37.00,Default,,0000,0000,0000,,It may work in some situations. It may work long enough that you almost
Dialogue: 0,0:15:37.00,0:15:40.00,Default,,0000,0000,0000,,think it's actually correct and then some day cause some problem,
Dialogue: 0,0:15:40.00,0:15:45.00,Default,,0000,0000,0000,,right? Just in a different circumstances where this didn't succeed by accident.
Dialogue: 0,0:15:45.00,0:15:47.00,Default,,0000,0000,0000,,That I'm digging into
Dialogue: 0,0:15:47.00,0:15:51.00,Default,,0000,0000,0000,,that piece of freed memory and trying to access a field out of it, right? Which is
Dialogue: 0,0:15:51.00,0:15:54.00,Default,,0000,0000,0000,,not a reliable thing to do. C++ will let me do it,
Dialogue: 0,0:15:54.00,0:15:58.00,Default,,0000,0000,0000,,it doesn't complain about this. Ether it will compile time or run time in an obvious way,
Dialogue: 0,0:15:58.00,0:16:01.00,Default,,0000,0000,0000,,but it's just, sort of, a little bit of ticking time bomb
Dialogue: 0,0:16:01.00,0:16:04.00,Default,,0000,0000,0000,,to have that kind of code that's there.
Dialogue: 0,0:16:04.00,0:16:06.00,Default,,0000,0000,0000,,So there's two different ways I could fix this.
Dialogue: 0,0:16:06.00,0:16:08.00,Default,,0000,0000,0000,,One way would be to, before
Dialogue: 0,0:16:08.00,0:16:10.00,Default,,0000,0000,0000,,I do the delete
Dialogue: 0,0:16:10.00,0:16:14.00,Default,,0000,0000,0000,,is to just hold onto the pointer that I'm gonna need.
Dialogue: 0,0:16:14.00,0:16:21.00,Default,,0000,0000,0000,,So pull it out of the memory before we're done here.
Dialogue: 0,0:16:21.00,0:16:22.00,Default,,0000,0000,0000,,So I read it in there.
Dialogue: 0,0:16:22.00,0:16:26.00,Default,,0000,0000,0000,,So the piece of memory that's behind it is still good.
Dialogue: 0,0:16:26.00,0:16:29.00,Default,,0000,0000,0000,,The delete actually just deleted that individual cell, so whatever is previously
Dialogue: 0,0:16:29.00,0:16:32.00,Default,,0000,0000,0000,,allocated with new, which was one entry structure,
Dialogue: 0,0:16:32.00,0:16:34.00,Default,,0000,0000,0000,,was what was deleted by that call.
Dialogue: 0,0:16:34.00,0:16:36.00,Default,,0000,0000,0000,,But what I was
Dialogue: 0,0:16:36.00,0:16:38.00,Default,,0000,0000,0000,,needing here was to keep track of something in
Dialogue: 0,0:16:38.00,0:16:42.00,Default,,0000,0000,0000,,that piece of memory before, right? I obliterated it,
Dialogue: 0,0:16:42.00,0:16:44.00,Default,,0000,0000,0000,,so that I can make a further use of it.
Dialogue: 0,0:16:44.00,0:16:46.00,Default,,0000,0000,0000,,The other alternative to how to fix this
Dialogue: 0,0:16:46.00,0:16:48.00,Default,,0000,0000,0000,,would be to just merely
Dialogue: 0,0:16:48.00,0:16:53.00,Default,,0000,0000,0000,,rearrange these two lines. Same kind of fix I did up above where
Dialogue: 0,0:16:53.00,0:16:54.00,Default,,0000,0000,0000,,go ahead and delete
Dialogue: 0,0:16:54.00,0:16:58.00,Default,,0000,0000,0000,,everything that follows so when I'm doing a list like this it would say, well,
Dialogue: 0,0:16:58.00,0:17:02.00,Default,,0000,0000,0000,,delete the D and C and only after all of that has been cleaned up
Dialogue: 0,0:17:02.00,0:17:05.00,Default,,0000,0000,0000,,come back and delete the one on the front. So it would actually delete from the rear
Dialogue: 0,0:17:05.00,0:17:08.00,Default,,0000,0000,0000,,forward. Work its way all the way down to the bottom, delete the last cell, then the next to
Dialogue: 0,0:17:08.00,0:17:09.00,Default,,0000,0000,0000,,last,
Dialogue: 0,0:17:09.00,0:17:10.00,Default,,0000,0000,0000,,and work its way out.
Dialogue: 0,0:17:10.00,0:17:12.00,Default,,0000,0000,0000,,Which would also be
Dialogue: 0,0:17:12.00,0:17:13.00,Default,,0000,0000,0000,,a completely
Dialogue: 0,0:17:13.00,0:17:20.00,Default,,0000,0000,0000,,correct way to solve this problem. Okay. Any questions
Dialogue: 0,0:17:20.00,0:17:22.00,Default,,0000,0000,0000,,on that one so far? Let me go
Dialogue: 0,0:17:22.00,0:17:25.00,Default,,0000,0000,0000,,back over here and see what
Dialogue: 0,0:17:25.00,0:17:27.00,Default,,0000,0000,0000,,I want to do with you next.
Dialogue: 0,0:17:27.00,0:17:31.00,Default,,0000,0000,0000,,So I talked about this, talked about these. Okay.
Dialogue: 0,0:17:31.00,0:17:32.00,Default,,0000,0000,0000,,Now,
Dialogue: 0,0:17:32.00,0:17:34.00,Default,,0000,0000,0000,,I'm gonna do something that's actually
Dialogue: 0,0:17:34.00,0:17:36.00,Default,,0000,0000,0000,,really pretty tricky
Dialogue: 0,0:17:36.00,0:17:47.00,Default,,0000,0000,0000,,that I want you guys to watch with me. All right.
Dialogue: 0,0:17:47.00,0:17:51.00,Default,,0000,0000,0000,,So this is the same code that we had for building the address book.
Dialogue: 0,0:17:51.00,0:17:52.00,Default,,0000,0000,0000,,
Dialogue: 0,0:17:52.00,0:17:54.00,Default,,0000,0000,0000,,The listhead, the new one, and so on.
Dialogue: 0,0:17:54.00,0:17:57.00,Default,,0000,0000,0000,,And what I did was, I just did a little bit of code factoring. Where I took the steps
Dialogue: 0,0:17:57.00,0:18:01.00,Default,,0000,0000,0000,,that were designed to splice that new cell onto the front of the list
Dialogue: 0,0:18:01.00,0:18:04.00,Default,,0000,0000,0000,,and I looped them into their own function called prepend
Dialogue: 0,0:18:04.00,0:18:08.00,Default,,0000,0000,0000,,that takes two pointers. The pointer to the new entry and the pointer to the current first
Dialogue: 0,0:18:08.00,0:18:11.00,Default,,0000,0000,0000,,cell of the list and it's designed to wire them
Dialogue: 0,0:18:11.00,0:18:12.00,Default,,0000,0000,0000,,up by putting it in the front.
Dialogue: 0,0:18:12.00,0:18:15.00,Default,,0000,0000,0000,,So it looks like the code that was here, just moved up here, and then the
Dialogue: 0,0:18:15.00,0:18:19.00,Default,,0000,0000,0000,,variable names change because the parameters have slightly different names.
Dialogue: 0,0:18:19.00,0:18:22.00,Default,,0000,0000,0000,,The code as I'm showing it right here is buggy.
Dialogue: 0,0:18:22.00,0:18:24.00,Default,,0000,0000,0000,,It's almost, but not quite, what we want
Dialogue: 0,0:18:24.00,0:18:28.00,Default,,0000,0000,0000,,and I want to do this very carefully. Kind of trace through what's happening here, so you
Dialogue: 0,0:18:28.00,0:18:29.00,Default,,0000,0000,0000,,can watch with me
Dialogue: 0,0:18:29.00,0:18:32.00,Default,,0000,0000,0000,,what's happening in this process. So
Dialogue: 0,0:18:32.00,0:18:37.00,Default,,0000,0000,0000,,the variable is actually called listhead and this - I guess let me go ahead and do this.
Dialogue: 0,0:18:37.00,0:18:40.00,Default,,0000,0000,0000,,Okay. So
Dialogue: 0,0:18:40.00,0:18:43.00,Default,,0000,0000,0000,,let's imagine that we have gone through a couple of alliterations and we've got a good linked
Dialogue: 0,0:18:43.00,0:18:43.00,Default,,0000,0000,0000,,list
Dialogue: 0,0:18:43.00,0:18:44.00,Default,,0000,0000,0000,,
Dialogue: 0,0:18:44.00,0:18:46.00,Default,,0000,0000,0000,,kind of in place, so I have something to work with her.
Dialogue: 0,0:18:46.00,0:18:49.00,Default,,0000,0000,0000,,So let's imagine that listhead
Dialogue: 0,0:18:49.00,0:18:52.00,Default,,0000,0000,0000,,points to a
Dialogue: 0,0:18:52.00,0:18:53.00,Default,,0000,0000,0000,,cell A to B
Dialogue: 0,0:18:53.00,0:18:56.00,Default,,0000,0000,0000,,and then its got two cells, let's say,
Dialogue: 0,0:18:56.00,0:18:58.00,Default,,0000,0000,0000,,and then it's empty.
Dialogue: 0,0:18:58.00,0:19:00.00,Default,,0000,0000,0000,,Let's say I get a new one
Dialogue: 0,0:19:00.00,0:19:01.00,Default,,0000,0000,0000,,
Dialogue: 0,0:19:01.00,0:19:06.00,Default,,0000,0000,0000,,and this ones gonna be a J, let's say. Okay.
Dialogue: 0,0:19:06.00,0:19:09.00,Default,,0000,0000,0000,,So that's the state, let's say, that I'm coming into here and hit the
Dialogue: 0,0:19:09.00,0:19:09.00,Default,,0000,0000,0000,,prepend
Dialogue: 0,0:19:09.00,0:19:13.00,Default,,0000,0000,0000,,and I'm ready to take this J cell and put it on the front so that I have J, A, B on
Dialogue: 0,0:19:13.00,0:19:16.00,Default,,0000,0000,0000,,my list. Okay. So let me
Dialogue: 0,0:19:16.00,0:19:20.00,Default,,0000,0000,0000,,do a little dotted line here that distinguishes my two stack
Dialogue: 0,0:19:20.00,0:19:25.00,Default,,0000,0000,0000,,rings. I'm gonna make this call to prepend
Dialogue: 0,0:19:25.00,0:19:31.00,Default,,0000,0000,0000,,and prepend has two variables, ENT and first,
Dialogue: 0,0:19:31.00,0:19:33.00,Default,,0000,0000,0000,,that were copied from
Dialogue: 0,0:19:33.00,0:19:37.00,Default,,0000,0000,0000,,the variables new one and listhead that came out of the build address book. Actually,
Dialogue: 0,0:19:37.00,0:19:40.00,Default,,0000,0000,0000,,it's not called main here. Let me
Dialogue: 0,0:19:40.00,0:19:43.00,Default,,0000,0000,0000,,call this build
Dialogue: 0,0:19:43.00,0:19:47.00,Default,,0000,0000,0000,,book. Okay.
Dialogue: 0,0:19:47.00,0:19:50.00,Default,,0000,0000,0000,,So I pass the value of new one as
Dialogue: 0,0:19:50.00,0:19:51.00,Default,,0000,0000,0000,,ENT.
Dialogue: 0,0:19:51.00,0:19:53.00,Default,,0000,0000,0000,,So what we get is a pointer
Dialogue: 0,0:19:53.00,0:19:55.00,Default,,0000,0000,0000,,to this same cell,
Dialogue: 0,0:19:55.00,0:19:57.00,Default,,0000,0000,0000,,a copy, and so this case, right?
Dialogue: 0,0:19:57.00,0:20:00.00,Default,,0000,0000,0000,,We copied the pointer, so whatever address was being held there is actually
Dialogue: 0,0:20:00.00,0:20:03.00,Default,,0000,0000,0000,,copied into here as this parameter.
Dialogue: 0,0:20:03.00,0:20:04.00,Default,,0000,0000,0000,,Similarly,
Dialogue: 0,0:20:04.00,0:20:07.00,Default,,0000,0000,0000,,listhead is copied into the second parameter, which is the pointer to the
Dialogue: 0,0:20:07.00,0:20:12.00,Default,,0000,0000,0000,,first cell. Okay.
Dialogue: 0,0:20:12.00,0:20:15.00,Default,,0000,0000,0000,,I want to do this in such a way that you can follow what's going on. So let's see
Dialogue: 0,0:20:15.00,0:20:16.00,Default,,0000,0000,0000,,if I can get this
Dialogue: 0,0:20:16.00,0:20:19.00,Default,,0000,0000,0000,,to work out. So it's pointing up there to first. Okay.
Dialogue: 0,0:20:19.00,0:20:21.00,Default,,0000,0000,0000,,So I've got
Dialogue: 0,0:20:21.00,0:20:24.00,Default,,0000,0000,0000,,two pointers to this cell A.
Dialogue: 0,0:20:24.00,0:20:26.00,Default,,0000,0000,0000,,One that came off the original listhead and one that came there from the copy in first.
Dialogue: 0,0:20:26.00,0:20:29.00,Default,,0000,0000,0000,,And then I've got two pointers to this J.
Dialogue: 0,0:20:29.00,0:20:32.00,Default,,0000,0000,0000,,One that came through the variable new one in the build an address book frame and
Dialogue: 0,0:20:32.00,0:20:35.00,Default,,0000,0000,0000,,one that was ENT in the prepend frame. Now, I'm gonna
Dialogue: 0,0:20:35.00,0:20:37.00,Default,,0000,0000,0000,,trace through the code of prepend.
Dialogue: 0,0:20:37.00,0:20:39.00,Default,,0000,0000,0000,,It says ent
Dialogue: 0,0:20:39.00,0:20:41.00,Default,,0000,0000,0000,,next field equals first. Okay.
Dialogue: 0,0:20:41.00,0:20:43.00,Default,,0000,0000,0000,,So ent's
Dialogue: 0,0:20:43.00,0:20:44.00,Default,,0000,0000,0000,,next field
Dialogue: 0,0:20:44.00,0:20:48.00,Default,,0000,0000,0000,,is right here.
Dialogue: 0,0:20:48.00,0:20:53.00,Default,,0000,0000,0000,,It gets the value of first. Well, first points to this cell. Okay.
Dialogue: 0,0:20:53.00,0:20:56.00,Default,,0000,0000,0000,,So we go ahead
Dialogue: 0,0:20:56.00,0:20:59.00,Default,,0000,0000,0000,,and make the next field of J point to that cell.
Dialogue: 0,0:20:59.00,0:21:03.00,Default,,0000,0000,0000,,So that looks pretty good. That first line worked out just fine. It changed
Dialogue: 0,0:21:03.00,0:21:05.00,Default,,0000,0000,0000,,the cell J
Dialogue: 0,0:21:05.00,0:21:08.00,Default,,0000,0000,0000,,to point to what was previously the front of the list. So it looks like now it's the
Dialogue: 0,0:21:08.00,0:21:10.00,Default,,0000,0000,0000,,first cell that's followed by those.
Dialogue: 0,0:21:10.00,0:21:13.00,Default,,0000,0000,0000,,And then the next line I need to do is I need to update the listhead
Dialogue: 0,0:21:13.00,0:21:16.00,Default,,0000,0000,0000,,to point to J.
Dialogue: 0,0:21:16.00,0:21:17.00,Default,,0000,0000,0000,,So it says first
Dialogue: 0,0:21:17.00,0:21:19.00,Default,,0000,0000,0000,,equals ENT.
Dialogue: 0,0:21:19.00,0:21:20.00,Default,,0000,0000,0000,,So first
Dialogue: 0,0:21:20.00,0:21:29.00,Default,,0000,0000,0000,,gets the value of ENT. Well this just does pointer assignment.
Dialogue: 0,0:21:29.00,0:21:31.00,Default,,0000,0000,0000,,
Dialogue: 0,0:21:31.00,0:21:34.00,Default,,0000,0000,0000,,Sorry, I erased where it used to point to.
Dialogue: 0,0:21:34.00,0:21:36.00,Default,,0000,0000,0000,,And then I make it point to there, too.
Dialogue: 0,0:21:36.00,0:21:39.00,Default,,0000,0000,0000,,So at the bottom of prepend,
Dialogue: 0,0:21:39.00,0:21:43.00,Default,,0000,0000,0000,,if I were to use first as the pointer to the initial cell of the list it looks good.
Dialogue: 0,0:21:43.00,0:21:47.00,Default,,0000,0000,0000,,It points to J, which points to A, which points to B, which points to null.
Dialogue: 0,0:21:47.00,0:21:49.00,Default,,0000,0000,0000,,Everything looks fine
Dialogue: 0,0:21:49.00,0:21:50.00,Default,,0000,0000,0000,,here,
Dialogue: 0,0:21:50.00,0:21:51.00,Default,,0000,0000,0000,,right? At the end of prepend.
Dialogue: 0,0:21:51.00,0:21:53.00,Default,,0000,0000,0000,,But when I get back here
Dialogue: 0,0:21:53.00,0:21:55.00,Default,,0000,0000,0000,,to come back around on this loop;
Dialogue: 0,0:21:55.00,0:22:03.00,Default,,0000,0000,0000,,where is listhead pointing? It's pointing to A.
Dialogue: 0,0:22:03.00,0:22:09.00,Default,,0000,0000,0000,,It's pointing to A. Did anything happen to listhead in the process of this? No.
Dialogue: 0,0:22:09.00,0:22:12.00,Default,,0000,0000,0000,,That listhead points where it always pointed, which was whatever cell, right? Was
Dialogue: 0,0:22:12.00,0:22:14.00,Default,,0000,0000,0000,,previously pointed to.
Dialogue: 0,0:22:14.00,0:22:18.00,Default,,0000,0000,0000,,This attempt to pass it into prepend and have prepend update it didn't
Dialogue: 0,0:22:18.00,0:22:21.00,Default,,0000,0000,0000,,stick.
Dialogue: 0,0:22:21.00,0:22:22.00,Default,,0000,0000,0000,,Prepend
Dialogue: 0,0:22:22.00,0:22:24.00,Default,,0000,0000,0000,,has two pointers
Dialogue: 0,0:22:24.00,0:22:27.00,Default,,0000,0000,0000,,that are copies of these pointers.
Dialogue: 0,0:22:27.00,0:22:31.00,Default,,0000,0000,0000,,So like other variables, ents, and strings and
Dialogue: 0,0:22:31.00,0:22:32.00,Default,,0000,0000,0000,,vectors and anything else we have,
Dialogue: 0,0:22:32.00,0:22:36.00,Default,,0000,0000,0000,,if we just pass the variable itself into a function call
Dialogue: 0,0:22:36.00,0:22:41.00,Default,,0000,0000,0000,,then that pass by value mechanism kicks in, which causes there to be two new
Dialogue: 0,0:22:41.00,0:22:43.00,Default,,0000,0000,0000,,variables. In this case, the ENT and the first variables,
Dialogue: 0,0:22:43.00,0:22:47.00,Default,,0000,0000,0000,,that are copies of the two variables listhead and new one
Dialogue: 0,0:22:47.00,0:22:49.00,Default,,0000,0000,0000,,that were present in build address book.
Dialogue: 0,0:22:49.00,0:22:54.00,Default,,0000,0000,0000,,And the changes I make down here, if I really try to change ENT or change first,
Dialogue: 0,0:22:54.00,0:22:58.00,Default,,0000,0000,0000,,so I try to make ENT point somewhere new or make first point somewhere new,
Dialogue: 0,0:22:58.00,0:22:59.00,Default,,0000,0000,0000,,don't stick.
Dialogue: 0,0:22:59.00,0:23:03.00,Default,,0000,0000,0000,,They change the copies, not the originals.
Dialogue: 0,0:23:03.00,0:23:05.00,Default,,0000,0000,0000,,This is tricky.
Dialogue: 0,0:23:05.00,0:23:08.00,Default,,0000,0000,0000,,This is very tricky because it's entering that the first line
Dialogue: 0,0:23:08.00,0:23:10.00,Default,,0000,0000,0000,,was actually okay.
Dialogue: 0,0:23:10.00,0:23:14.00,Default,,0000,0000,0000,,That what the first line tried to do actually did have a persistent affect and
Dialogue: 0,0:23:14.00,0:23:15.00,Default,,0000,0000,0000,,the affect we wanted,
Dialogue: 0,0:23:15.00,0:23:18.00,Default,,0000,0000,0000,,which is it followed the ENT pointer
Dialogue: 0,0:23:18.00,0:23:21.00,Default,,0000,0000,0000,,to this shared location and changed its next field. So
Dialogue: 0,0:23:21.00,0:23:25.00,Default,,0000,0000,0000,,dereferencing that pointer and mucking around with the struct itself
Dialogue: 0,0:23:25.00,0:23:28.00,Default,,0000,0000,0000,,did have a persistent affect. It wasn't another copy of the entry struck. There
Dialogue: 0,0:23:28.00,0:23:33.00,Default,,0000,0000,0000,,really is just this one entry struck that new one and ENT are both pointing
Dialogue: 0,0:23:33.00,0:23:34.00,Default,,0000,0000,0000,,to.
Dialogue: 0,0:23:34.00,0:23:35.00,Default,,0000,0000,0000,,So both of them, right?
Dialogue: 0,0:23:35.00,0:23:39.00,Default,,0000,0000,0000,,Are viewing the same piece of heap memory. Changes made out there at the
Dialogue: 0,0:23:39.00,0:23:42.00,Default,,0000,0000,0000,,structure, right? Are being perceived from both ends,
Dialogue: 0,0:23:42.00,0:23:45.00,Default,,0000,0000,0000,,but the pointers themselves - the fact that I had two different pointers that
Dialogue: 0,0:23:45.00,0:23:48.00,Default,,0000,0000,0000,,pointed to the same place, I changed one of my pointers,
Dialogue: 0,0:23:48.00,0:23:51.00,Default,,0000,0000,0000,,the one whose name is first, to
Dialogue: 0,0:23:51.00,0:23:55.00,Default,,0000,0000,0000,,point somewhere new. I didn't change listhead by that action. That listhead and
Dialogue: 0,0:23:55.00,0:23:55.00,Default,,0000,0000,0000,,first
Dialogue: 0,0:23:55.00,0:23:59.00,Default,,0000,0000,0000,,were just two aliases of the same location, but they had no further
Dialogue: 0,0:23:59.00,0:24:04.00,Default,,0000,0000,0000,,relationship that is implied by that parameter passing there. How do
Dialogue: 0,0:24:04.00,0:24:07.00,Default,,0000,0000,0000,,you feel about that? Question? And
Dialogue: 0,0:24:07.00,0:24:09.00,Default,,0000,0000,0000,,first and ent
Dialogue: 0,0:24:09.00,0:24:11.00,Default,,0000,0000,0000,,are gonna disappear now, right, afterwards? No. First and ent would go away,
Dialogue: 0,0:24:11.00,0:24:15.00,Default,,0000,0000,0000,,but that just means their pointers would go. So when prepend goes away,
Dialogue: 0,0:24:15.00,0:24:18.00,Default,,0000,0000,0000,,right? This space gets deallocated, so it's
Dialogue: 0,0:24:18.00,0:24:20.00,Default,,0000,0000,0000,,like this
Dialogue: 0,0:24:20.00,0:24:23.00,Default,,0000,0000,0000,,pointer goes away
Dialogue: 0,0:24:23.00,0:24:26.00,Default,,0000,0000,0000,,and all this space down here goes
Dialogue: 0,0:24:26.00,0:24:30.00,Default,,0000,0000,0000,,away. Then what we have is list still pointing to A and B and then new one,
Dialogue: 0,0:24:30.00,0:24:33.00,Default,,0000,0000,0000,,right? Is pointing to this J, which points to A, but, in fact, right?
Dialogue: 0,0:24:33.00,0:24:36.00,Default,,0000,0000,0000,,Is effectively gonna be orphaned by the next come around of the loop when we
Dialogue: 0,0:24:36.00,0:24:37.00,Default,,0000,0000,0000,,reassign new one.
Dialogue: 0,0:24:37.00,0:24:39.00,Default,,0000,0000,0000,,So that J didn't get prepended.
Dialogue: 0,0:24:39.00,0:24:43.00,Default,,0000,0000,0000,,It got half of its attachment done. The outgoing attachment from J got done,
Dialogue: 0,0:24:43.00,0:24:45.00,Default,,0000,0000,0000,,but the incoming one
Dialogue: 0,0:24:45.00,0:24:48.00,Default,,0000,0000,0000,,didn't stick.
Dialogue: 0,0:24:48.00,0:24:51.00,Default,,0000,0000,0000,,This is pretty tricky to think about because it really requires really kind of
Dialogue: 0,0:24:51.00,0:24:53.00,Default,,0000,0000,0000,,carefully analyzing what the code is doing
Dialogue: 0,0:24:53.00,0:24:57.00,Default,,0000,0000,0000,,and not letting this idea of the pointer confuse you from what you all
Dialogue: 0,0:24:57.00,0:25:00.00,Default,,0000,0000,0000,,ready know about variables. If I pass - if you see a function call
Dialogue: 0,0:25:00.00,0:25:01.00,Default,,0000,0000,0000,,where I say
Dialogue: 0,0:25:01.00,0:25:03.00,Default,,0000,0000,0000,,binky
Dialogue: 0,0:25:03.00,0:25:05.00,Default,,0000,0000,0000,,of
Dialogue: 0,0:25:05.00,0:25:07.00,Default,,0000,0000,0000,,A and B, where A and B are integer values,
Dialogue: 0,0:25:07.00,0:25:10.00,Default,,0000,0000,0000,,if these are not by reference coming into binky then you know that when they
Dialogue: 0,0:25:10.00,0:25:13.00,Default,,0000,0000,0000,,come back A and B are what they were before. If A was 10 and B was 20,
Dialogue: 0,0:25:13.00,0:25:16.00,Default,,0000,0000,0000,,they're still that. That the only way that binky can have some persistent affect on
Dialogue: 0,0:25:16.00,0:25:20.00,Default,,0000,0000,0000,,the values of A and B would be that they were being passed by reference.
Dialogue: 0,0:25:20.00,0:25:22.00,Default,,0000,0000,0000,,If I change this piece of code,
Dialogue: 0,0:25:22.00,0:25:25.00,Default,,0000,0000,0000,,and it's just one tiny change I'm gonna
Dialogue: 0,0:25:25.00,0:25:31.00,Default,,0000,0000,0000,,make here, to add an ampersand on that first,
Dialogue: 0,0:25:31.00,0:25:38.00,Default,,0000,0000,0000,,then I'm gonna get what I wanted. So I want
Dialogue: 0,0:25:38.00,0:25:41.00,Default,,0000,0000,0000,,to draw my reference a little bit differently to remind myself about
Dialogue: 0,0:25:41.00,0:25:45.00,Default,,0000,0000,0000,,what it is. When I call prepend passing new one it got passed normally. New one
Dialogue: 0,0:25:45.00,0:25:49.00,Default,,0000,0000,0000,,is still just an ordinary pointer. So now I have two pointers
Dialogue: 0,0:25:49.00,0:25:52.00,Default,,0000,0000,0000,,where ENT and new one both point to that J.
Dialogue: 0,0:25:52.00,0:25:56.00,Default,,0000,0000,0000,,This one currently doesn't yet point up there. It's gonna in a minute, but I'll go ahead
Dialogue: 0,0:25:56.00,0:25:58.00,Default,,0000,0000,0000,,and put it back to its original state.
Dialogue: 0,0:25:58.00,0:25:59.00,Default,,0000,0000,0000,,Now, first
Dialogue: 0,0:25:59.00,0:26:03.00,Default,,0000,0000,0000,,is gonna be an alias for listhead, so that first
Dialogue: 0,0:26:03.00,0:26:09.00,Default,,0000,0000,0000,,is not going to be a copy of what listhead is. It's actually gonna be a
Dialogue: 0,0:26:09.00,0:26:11.00,Default,,0000,0000,0000,,reference back to here.
Dialogue: 0,0:26:11.00,0:26:15.00,Default,,0000,0000,0000,,And a reference looks a lot like a pointer in the way that I draw it,
Dialogue: 0,0:26:15.00,0:26:18.00,Default,,0000,0000,0000,,but the difference is gonna be I'm gonna shade or, sort of, cross hatch this box
Dialogue: 0,0:26:18.00,0:26:21.00,Default,,0000,0000,0000,,to remind myself that
Dialogue: 0,0:26:21.00,0:26:24.00,Default,,0000,0000,0000,,first is attached a listhead and there's nothing you can do to change it.
Dialogue: 0,0:26:24.00,0:26:27.00,Default,,0000,0000,0000,,That first becomes a synonym for listhead.
Dialogue: 0,0:26:27.00,0:26:31.00,Default,,0000,0000,0000,,That in the context of the prepend function, any access to first is really
Dialogue: 0,0:26:31.00,0:26:35.00,Default,,0000,0000,0000,,just an access to listhead. So trying to read from it or write to it, you know, do you
Dialogue: 0,0:26:35.00,0:26:37.00,Default,,0000,0000,0000,,reference it, it all goes back to the original
Dialogue: 0,0:26:37.00,0:26:40.00,Default,,0000,0000,0000,,that this is just standing in for.
Dialogue: 0,0:26:40.00,0:26:43.00,Default,,0000,0000,0000,,That there actually is a relationship that's permanent from the
Dialogue: 0,0:26:43.00,0:26:47.00,Default,,0000,0000,0000,,time of that call that means that yeah, there really is now new variable first. First is
Dialogue: 0,0:26:47.00,0:26:51.00,Default,,0000,0000,0000,,actually just another name for an existing variable, this one of listhead.
Dialogue: 0,0:26:51.00,0:26:55.00,Default,,0000,0000,0000,,So when I got through the ENT it gets the value - ENT's next gets the value of first.
Dialogue: 0,0:26:55.00,0:26:56.00,Default,,0000,0000,0000,,Well,
Dialogue: 0,0:26:56.00,0:26:57.00,Default,,0000,0000,0000,,first's value really is
Dialogue: 0,0:26:57.00,0:27:01.00,Default,,0000,0000,0000,,what listhead is. So that means it points up to A,
Dialogue: 0,0:27:01.00,0:27:02.00,Default,,0000,0000,0000,,so that part
Dialogue: 0,0:27:02.00,0:27:04.00,Default,,0000,0000,0000,,works as we were hoping before.
Dialogue: 0,0:27:04.00,0:27:08.00,Default,,0000,0000,0000,,Then when I make the change to first equals ENT,
Dialogue: 0,0:27:08.00,0:27:10.00,Default,,0000,0000,0000,,first is a synonym for listhead
Dialogue: 0,0:27:10.00,0:27:12.00,Default,,0000,0000,0000,,and that made listhead
Dialogue: 0,0:27:12.00,0:27:15.00,Default,,0000,0000,0000,,stop pointing to A and
Dialogue: 0,0:27:15.00,0:27:18.00,Default,,0000,0000,0000,,start pointing straight to J.
Dialogue: 0,0:27:18.00,0:27:22.00,Default,,0000,0000,0000,,And so this is still attached here. Let's do that. Let
Dialogue: 0,0:27:22.00,0:27:25.00,Default,,0000,0000,0000,,me see if I can just erase this part and make it a little clearer what's going on.
Dialogue: 0,0:27:25.00,0:27:28.00,Default,,0000,0000,0000,,So new one's pointing to J now, ENT
Dialogue: 0,0:27:28.00,0:27:31.00,Default,,0000,0000,0000,,is pointing to J,
Dialogue: 0,0:27:31.00,0:27:33.00,Default,,0000,0000,0000,,and listhead is pointing to J,
Dialogue: 0,0:27:33.00,0:27:34.00,Default,,0000,0000,0000,,and then this is still
Dialogue: 0,0:27:34.00,0:27:37.00,Default,,0000,0000,0000,,the reference pointing back to there.
Dialogue: 0,0:27:37.00,0:27:40.00,Default,,0000,0000,0000,,So now when prepend goes away,
Dialogue: 0,0:27:40.00,0:27:42.00,Default,,0000,0000,0000,,this extra pointer
Dialogue: 0,0:27:42.00,0:27:43.00,Default,,0000,0000,0000,,is removed,
Dialogue: 0,0:27:43.00,0:27:45.00,Default,,0000,0000,0000,,this reference is removed,
Dialogue: 0,0:27:45.00,0:27:47.00,Default,,0000,0000,0000,,all this space
Dialogue: 0,0:27:47.00,0:27:48.00,Default,,0000,0000,0000,,is reclaimed here in the stack,
Dialogue: 0,0:27:48.00,0:27:51.00,Default,,0000,0000,0000,,but listhead now really points to J,
Dialogue: 0,0:27:51.00,0:27:53.00,Default,,0000,0000,0000,,which points to A, which points to B as before.
Dialogue: 0,0:27:53.00,0:27:55.00,Default,,0000,0000,0000,,So we wired in two pointers, right?
Dialogue: 0,0:27:55.00,0:27:59.00,Default,,0000,0000,0000,,One going out of the new cell into what was previously the first cell and then the
Dialogue: 0,0:27:59.00,0:28:00.00,Default,,0000,0000,0000,,first cell
Dialogue: 0,0:28:00.00,0:28:04.00,Default,,0000,0000,0000,,pointer now points to the new one rather than the original first cell.
Dialogue: 0,0:28:04.00,0:28:07.00,Default,,0000,0000,0000,,It was all a matter of this one little ampersand
Dialogue: 0,0:28:07.00,0:28:09.00,Default,,0000,0000,0000,,that makes the difference, right?
Dialogue: 0,0:28:09.00,0:28:12.00,Default,,0000,0000,0000,,Without that, right? Then we are only operating on a copy.
Dialogue: 0,0:28:12.00,0:28:15.00,Default,,0000,0000,0000,,We're changing our local copy of a pointer to point somewhere new;
Dialogue: 0,0:28:15.00,0:28:17.00,Default,,0000,0000,0000,,having no permanent affect
Dialogue: 0,0:28:17.00,0:28:17.00,Default,,0000,0000,0000,,
Dialogue: 0,0:28:17.00,0:28:19.00,Default,,0000,0000,0000,,on the actual state of it.
Dialogue: 0,0:28:19.00,0:28:22.00,Default,,0000,0000,0000,,So, actually, without that ampersand in there it turns out
Dialogue: 0,0:28:22.00,0:28:26.00,Default,,0000,0000,0000,,nothing ever gets added to the list. The listhead starts as null and stays null,
Dialogue: 0,0:28:26.00,0:28:29.00,Default,,0000,0000,0000,,but all these things will copy the value of listhead as a
Dialogue: 0,0:28:29.00,0:28:33.00,Default,,0000,0000,0000,,null, change it in the local context of the called function, but then listhead
Dialogue: 0,0:28:33.00,0:28:36.00,Default,,0000,0000,0000,,will stay null. So, in fact, if I just ran this a bunch of times and I threw in a bunch of
Dialogue: 0,0:28:36.00,0:28:37.00,Default,,0000,0000,0000,,things without the ampersand
Dialogue: 0,0:28:37.00,0:28:41.00,Default,,0000,0000,0000,,I would find that all my cells just get discarded. I'd end up with an
Dialogue: 0,0:28:41.00,0:28:42.00,Default,,0000,0000,0000,,empty list when I was done. All the orphaned out
Dialogue: 0,0:28:42.00,0:28:45.00,Default,,0000,0000,0000,,in the heap
Dialogue: 0,0:28:45.00,0:28:49.00,Default,,0000,0000,0000,,attached and not really recorded permanently.
Dialogue: 0,0:28:49.00,0:28:52.00,Default,,0000,0000,0000,,That's pretty tricky. Question? Why is the
Dialogue: 0,0:28:52.00,0:28:55.00,Default,,0000,0000,0000,,ampersand after this [inaudible]?
Dialogue: 0,0:28:55.00,0:28:56.00,Default,,0000,0000,0000,,Because it is the - the
Dialogue: 0,0:28:56.00,0:29:00.00,Default,,0000,0000,0000,,ampersand applies to the - think of it more as applying to the name and it's saying this
Dialogue: 0,0:29:00.00,0:29:04.00,Default,,0000,0000,0000,,name is a reference to something of that type. So on the left-hand side
Dialogue: 0,0:29:04.00,0:29:05.00,Default,,0000,0000,0000,,is the type.
Dialogue: 0,0:29:05.00,0:29:09.00,Default,,0000,0000,0000,,What type of thing is it? Is it a string of anti-vector events or whatever? And then the
Dialogue: 0,0:29:09.00,0:29:13.00,Default,,0000,0000,0000,,ampersand can go between the type and the name to say and it is a reference to an
Dialogue: 0,0:29:13.00,0:29:17.00,Default,,0000,0000,0000,,existing variable of that type as opposed to a copy of a variable of that type. So
Dialogue: 0,0:29:17.00,0:29:19.00,Default,,0000,0000,0000,,without the ampersand it's always a copy.
Dialogue: 0,0:29:19.00,0:29:21.00,Default,,0000,0000,0000,,With the ampersand, you're saying
Dialogue: 0,0:29:21.00,0:29:25.00,Default,,0000,0000,0000,,I'm introducing first as a synonym for an existing entry star variable somewhere
Dialogue: 0,0:29:25.00,0:29:28.00,Default,,0000,0000,0000,,else and that in the context of this function
Dialogue: 0,0:29:28.00,0:29:31.00,Default,,0000,0000,0000,,access to this named parameter really is reaching out
Dialogue: 0,0:29:31.00,0:29:35.00,Default,,0000,0000,0000,,to change a variable stored elsewhere.
Dialogue: 0,0:29:35.00,0:29:41.00,Default,,0000,0000,0000,,It's quite, quite tricky to kind of get your head around what's going on here.
Dialogue: 0,0:29:41.00,0:29:44.00,Default,,0000,0000,0000,,I'm gonna use this, actually, in running another piece of code, so I want to
Dialogue: 0,0:29:44.00,0:29:46.00,Default,,0000,0000,0000,,be sure that at this point everybody feels
Dialogue: 0,0:29:46.00,0:29:54.00,Default,,0000,0000,0000,,at least reasonably okay with what I just showed you. Question? What happens if we stop
Dialogue: 0,0:29:54.00,0:29:58.00,Default,,0000,0000,0000,,ampersand [inaudible]? Jordan, you want to invert them or something like that? Yes. It turns out that that won't work.
Dialogue: 0,0:29:58.00,0:30:02.00,Default,,0000,0000,0000,,Basically, it won't compile because in this case you can't take a pointer out to an
Dialogue: 0,0:30:02.00,0:30:04.00,Default,,0000,0000,0000,,entry reference. In fact, it just won't let you. So
Dialogue: 0,0:30:04.00,0:30:07.00,Default,,0000,0000,0000,,it doesn't really make sense is the truth.
Dialogue: 0,0:30:07.00,0:30:08.00,Default,,0000,0000,0000,,But think of it as like the - sometimes people
Dialogue: 0,0:30:08.00,0:30:12.00,Default,,0000,0000,0000,,actually will draw it with the ampersand attached even without the
Dialogue: 0,0:30:12.00,0:30:15.00,Default,,0000,0000,0000,,space onto the variable name. It's just a notation. A really good clue that this name,
Dialogue: 0,0:30:15.00,0:30:18.00,Default,,0000,0000,0000,,right? Is a reference to an existing variable and that its type is kind
Dialogue: 0,0:30:18.00,0:30:19.00,Default,,0000,0000,0000,,of
Dialogue: 0,0:30:19.00,0:30:21.00,Default,,0000,0000,0000,,over here. So type,
Dialogue: 0,0:30:21.00,0:30:25.00,Default,,0000,0000,0000,,name, and then name as a reference has that ampersand attached. Question? Is
Dialogue: 0,0:30:25.00,0:30:27.00,Default,,0000,0000,0000,,there a wrong side to passing both the pointers by
Dialogue: 0,0:30:27.00,0:30:29.00,Default,,0000,0000,0000,,reference? Nope,
Dialogue: 0,0:30:29.00,0:30:32.00,Default,,0000,0000,0000,,not really. If I pass it by reference, right?
Dialogue: 0,0:30:32.00,0:30:35.00,Default,,0000,0000,0000,,Then it - nothing would change about what really happens, right? It would still leach into
Dialogue: 0,0:30:35.00,0:30:39.00,Default,,0000,0000,0000,,the thing and copy it. There is - for variables that are large, sometimes we
Dialogue: 0,0:30:39.00,0:30:42.00,Default,,0000,0000,0000,,pass them by reference just to avoid the overhead of a copy. Since a pointer is pretty small, that
Dialogue: 0,0:30:42.00,0:30:45.00,Default,,0000,0000,0000,,making a copy versus taking a reference it turns out doesn't really save you anything and
Dialogue: 0,0:30:45.00,0:30:48.00,Default,,0000,0000,0000,,actually it makes a little bit more work
Dialogue: 0,0:30:48.00,0:30:52.00,Default,,0000,0000,0000,,to access it because it has to kind of go one level out to get it. But
Dialogue: 0,0:30:52.00,0:30:54.00,Default,,0000,0000,0000,,effectively no. In
Dialogue: 0,0:30:54.00,0:30:56.00,Default,,0000,0000,0000,,general though, I would say that
Dialogue: 0,0:30:56.00,0:30:58.00,Default,,0000,0000,0000,,passing things by reference,
Dialogue: 0,0:30:58.00,0:31:01.00,Default,,0000,0000,0000,,as a habit, is probably not one you want to assume for other kinds of variables.
Dialogue: 0,0:31:01.00,0:31:02.00,Default,,0000,0000,0000,,Just
Dialogue: 0,0:31:02.00,0:31:05.00,Default,,0000,0000,0000,,because that once you've passed it by reference you've opened up the access to where if it
Dialogue: 0,0:31:05.00,0:31:08.00,Default,,0000,0000,0000,,changes it it does persistent and if you didn't intend for that that could be kind of a mystical thing
Dialogue: 0,0:31:08.00,0:31:09.00,Default,,0000,0000,0000,,to try to track down. So I
Dialogue: 0,0:31:09.00,0:31:11.00,Default,,0000,0000,0000,,think you should be quite deliberate about -
Dialogue: 0,0:31:11.00,0:31:14.00,Default,,0000,0000,0000,,I plan on changing this and I want to be sure I see that persistent
Dialogue: 0,0:31:14.00,0:31:22.00,Default,,0000,0000,0000,,effect. That I need that pass by reference there. Okay.
Dialogue: 0,0:31:22.00,0:31:26.00,Default,,0000,0000,0000,,So let me go on to kind of solve a problem with the linked list that helps to motivate what a linked
Dialogue: 0,0:31:26.00,0:31:30.00,Default,,0000,0000,0000,,list is good for. Why would you use a linked list versus a
Dialogue: 0,0:31:30.00,0:31:35.00,Default,,0000,0000,0000,,vector or an array style access for something that was a collection?
Dialogue: 0,0:31:35.00,0:31:39.00,Default,,0000,0000,0000,,And so the built in array, which is what vector is built on, so they have the same
Dialogue: 0,0:31:39.00,0:31:40.00,Default,,0000,0000,0000,,characteristics in this respect.
Dialogue: 0,0:31:40.00,0:31:42.00,Default,,0000,0000,0000,,They store elements in contiguous memory.
Dialogue: 0,0:31:42.00,0:31:44.00,Default,,0000,0000,0000,,You allocate an array of ten elements.
Dialogue: 0,0:31:44.00,0:31:48.00,Default,,0000,0000,0000,,There's a block that is ten integers wide, let's say,
Dialogue: 0,0:31:48.00,0:31:52.00,Default,,0000,0000,0000,,where they were all sitting next to each other. In address 1,000 as one,
Dialogue: 0,0:31:52.00,0:31:54.00,Default,,0000,0000,0000,,1,004 is the next, 1,008 and so on.
Dialogue: 0,0:31:54.00,0:31:58.00,Default,,0000,0000,0000,,What that gives you is fast direct access by index. You can ask for the third
Dialogue: 0,0:31:58.00,0:32:02.00,Default,,0000,0000,0000,,member, the seventh member, the 28th member, the 6 millionth member
Dialogue: 0,0:32:02.00,0:32:03.00,Default,,0000,0000,0000,,depending on how big it is, right?
Dialogue: 0,0:32:03.00,0:32:05.00,Default,,0000,0000,0000,,By, sort of, directly computing
Dialogue: 0,0:32:05.00,0:32:07.00,Default,,0000,0000,0000,,where it will be in memory. You know where it starts and you know how big each
Dialogue: 0,0:32:07.00,0:32:11.00,Default,,0000,0000,0000,,element is. Then you can say here's where I can find the 10th element.
Dialogue: 0,0:32:11.00,0:32:15.00,Default,,0000,0000,0000,,That's an advantage, right? To the array vector style of arrangement.
Dialogue: 0,0:32:15.00,0:32:16.00,Default,,0000,0000,0000,,However,
Dialogue: 0,0:32:16.00,0:32:20.00,Default,,0000,0000,0000,,the fact that it's in this big contiguous block is actually very bulky.
Dialogue: 0,0:32:20.00,0:32:21.00,Default,,0000,0000,0000,,It means that
Dialogue: 0,0:32:21.00,0:32:26.00,Default,,0000,0000,0000,,if you were to want to put a new element in the front of an array or vector that
Dialogue: 0,0:32:26.00,0:32:27.00,Default,,0000,0000,0000,,has 1,000 elements
Dialogue: 0,0:32:27.00,0:32:30.00,Default,,0000,0000,0000,,you have to move over the 1,000 elements to make space. If
Dialogue: 0,0:32:30.00,0:32:33.00,Default,,0000,0000,0000,,it's starting to address 1,000 and you have them all laid out and you want to put a new
Dialogue: 0,0:32:33.00,0:32:37.00,Default,,0000,0000,0000,,one in the front, everybody's gotta get picked up and moved over a slot to make
Dialogue: 0,0:32:37.00,0:32:39.00,Default,,0000,0000,0000,,space. So imagine you're all
Dialogue: 0,0:32:39.00,0:32:40.00,Default,,0000,0000,0000,,
Dialogue: 0,0:32:40.00,0:32:43.00,Default,,0000,0000,0000,,sitting across a lecture hall and I decided I wanted to put a new person there, everybody
Dialogue: 0,0:32:43.00,0:32:45.00,Default,,0000,0000,0000,,gets up and moves one chair to the left,
Dialogue: 0,0:32:45.00,0:32:47.00,Default,,0000,0000,0000,,but there's not a way to just stick a new chair
Dialogue: 0,0:32:47.00,0:32:49.00,Default,,0000,0000,0000,,on one end of it
Dialogue: 0,0:32:49.00,0:32:51.00,Default,,0000,0000,0000,,using the array style
Dialogue: 0,0:32:51.00,0:32:52.00,Default,,0000,0000,0000,,of layout.
Dialogue: 0,0:32:52.00,0:32:55.00,Default,,0000,0000,0000,,Same for removing, right? So any kind of access to where you want to take
Dialogue: 0,0:32:55.00,0:32:59.00,Default,,0000,0000,0000,,somebody out of the array and close over the gap or insert in the middle and the beginning and
Dialogue: 0,0:32:59.00,0:32:59.00,Default,,0000,0000,0000,,whatnot
Dialogue: 0,0:32:59.00,0:33:02.00,Default,,0000,0000,0000,,requires everybody else moving around in memory,
Dialogue: 0,0:33:02.00,0:33:06.00,Default,,0000,0000,0000,,which gets expensive. Especially for large things, right? That's a lot of work.
Dialogue: 0,0:33:06.00,0:33:09.00,Default,,0000,0000,0000,,It also can't easily grow and shrink.
Dialogue: 0,0:33:09.00,0:33:12.00,Default,,0000,0000,0000,,You allocate an array, your vector, to be a certain size
Dialogue: 0,0:33:12.00,0:33:13.00,Default,,0000,0000,0000,,
Dialogue: 0,0:33:13.00,0:33:15.00,Default,,0000,0000,0000,,underneath it. That's what vector's doing on your behalf.
Dialogue: 0,0:33:15.00,0:33:19.00,Default,,0000,0000,0000,,If you have ten elements and now you need to put in ten more
Dialogue: 0,0:33:19.00,0:33:22.00,Default,,0000,0000,0000,,what you need to do is go allocate a piece of memory that's twice as big, copy over the
Dialogue: 0,0:33:22.00,0:33:23.00,Default,,0000,0000,0000,,ten you have,
Dialogue: 0,0:33:23.00,0:33:26.00,Default,,0000,0000,0000,,and now have bigger space. If you need to shrink it down you'll have to make a
Dialogue: 0,0:33:26.00,0:33:29.00,Default,,0000,0000,0000,,smaller piece, copy it down. There's not a way to take a piece of memory and just kind
Dialogue: 0,0:33:29.00,0:33:30.00,Default,,0000,0000,0000,,of
Dialogue: 0,0:33:30.00,0:33:33.00,Default,,0000,0000,0000,,in place in memory where it is kind of extended or shrink it
Dialogue: 0,0:33:33.00,0:33:35.00,Default,,0000,0000,0000,,in the C++ language.
Dialogue: 0,0:33:35.00,0:33:38.00,Default,,0000,0000,0000,,So that the process of growing and shrinking, right? Requires this extra
Dialogue: 0,0:33:38.00,0:33:41.00,Default,,0000,0000,0000,,effort. So behind the scenes that's what vector is doing. When you keep adding to a
Dialogue: 0,0:33:41.00,0:33:43.00,Default,,0000,0000,0000,,vector, eventually it will fill to capacity. It
Dialogue: 0,0:33:43.00,0:33:46.00,Default,,0000,0000,0000,,will internally make more space and copy things over and you're
Dialogue: 0,0:33:46.00,0:33:49.00,Default,,0000,0000,0000,,paying that cost behind the scenes
Dialogue: 0,0:33:49.00,0:33:54.00,Default,,0000,0000,0000,,when you're doing a lot of additions and removals from a vector. The
Dialogue: 0,0:33:54.00,0:33:57.00,Default,,0000,0000,0000,,linked list, right? Uses this wiring them together using pointers,
Dialogue: 0,0:33:57.00,0:33:59.00,Default,,0000,0000,0000,,so it has a lot of flexibility
Dialogue: 0,0:33:59.00,0:34:00.00,Default,,0000,0000,0000,,in it that the array does not.
Dialogue: 0,0:34:00.00,0:34:04.00,Default,,0000,0000,0000,,Each element individually allocated. So that means you can pick and choose when and
Dialogue: 0,0:34:04.00,0:34:07.00,Default,,0000,0000,0000,,where you're ready to take some more space on and when you don't.
Dialogue: 0,0:34:07.00,0:34:10.00,Default,,0000,0000,0000,,So when you're ready to add a new person to the vector there's no worry
Dialogue: 0,0:34:10.00,0:34:12.00,Default,,0000,0000,0000,,about if there's a million elements there and now you don't have any
Dialogue: 0,0:34:12.00,0:34:15.00,Default,,0000,0000,0000,,space you have to copy them. It's like you don't - you can leave the other million elements alone.
Dialogue: 0,0:34:15.00,0:34:18.00,Default,,0000,0000,0000,,You just take the heap, ask for one new element,
Dialogue: 0,0:34:18.00,0:34:20.00,Default,,0000,0000,0000,,and then splice it in.
Dialogue: 0,0:34:20.00,0:34:23.00,Default,,0000,0000,0000,,So the only allocation of the allocation concerns the individual element you're
Dialogue: 0,0:34:23.00,0:34:26.00,Default,,0000,0000,0000,,trying to do something with. You want to take one out of the middle; you just need to delete
Dialogue: 0,0:34:26.00,0:34:30.00,Default,,0000,0000,0000,,that one and close around the gap by wiring the pointers around it.
Dialogue: 0,0:34:30.00,0:34:33.00,Default,,0000,0000,0000,,So all the insert and remove actions, right? Are
Dialogue: 0,0:34:33.00,0:34:35.00,Default,,0000,0000,0000,,only a matter of wiring pointers.
Dialogue: 0,0:34:35.00,0:34:37.00,Default,,0000,0000,0000,,Wiring around something you're taking out,
Dialogue: 0,0:34:37.00,0:34:41.00,Default,,0000,0000,0000,,attaching one to the end or into the middle is splicing a pointer in, and is splicing the pointer
Dialogue: 0,0:34:41.00,0:34:45.00,Default,,0000,0000,0000,,out. So basically you typically have two pointers you need to reassign
Dialogue: 0,0:34:45.00,0:34:46.00,Default,,0000,0000,0000,,to do that kind of adjustment.
Dialogue: 0,0:34:46.00,0:34:49.00,Default,,0000,0000,0000,,If the element has ten members, it has a million members, right? Same amount of work to
Dialogue: 0,0:34:49.00,0:34:51.00,Default,,0000,0000,0000,,put a cell in there.
Dialogue: 0,0:34:51.00,0:34:52.00,Default,,0000,0000,0000,,
Dialogue: 0,0:34:52.00,0:34:57.00,Default,,0000,0000,0000,,No dependency on how big it is, right? Causing those operations to bog down.
Dialogue: 0,0:34:57.00,0:35:00.00,Default,,0000,0000,0000,,The downside then is
Dialogue: 0,0:35:00.00,0:35:02.00,Default,,0000,0000,0000,,exactly the, sort of, opposite of where it came out in the array in the vector,
Dialogue: 0,0:35:02.00,0:35:06.00,Default,,0000,0000,0000,,which is you don't have direct access to the 10th element, to the 15th
Dialogue: 0,0:35:06.00,0:35:09.00,Default,,0000,0000,0000,,element, to the 260th element. If I want to see what that 260 of
Dialogue: 0,0:35:09.00,0:35:13.00,Default,,0000,0000,0000,,my linked list is I've got to start at the beginning and walk.
Dialogue: 0,0:35:13.00,0:35:17.00,Default,,0000,0000,0000,,I go next, next, next, next, next, next 260 times and then I will get
Dialogue: 0,0:35:17.00,0:35:19.00,Default,,0000,0000,0000,,to the 260th element.
Dialogue: 0,0:35:19.00,0:35:20.00,Default,,0000,0000,0000,,So I don't have
Dialogue: 0,0:35:20.00,0:35:22.00,Default,,0000,0000,0000,,that easy access to say
Dialogue: 0,0:35:22.00,0:35:25.00,Default,,0000,0000,0000,,right here at this spot because we don't know. They're all over the place
Dialogue: 0,0:35:25.00,0:35:28.00,Default,,0000,0000,0000,,in memory. Each linked list cell is allocated individually and the only way to get to
Dialogue: 0,0:35:28.00,0:35:29.00,Default,,0000,0000,0000,,them
Dialogue: 0,0:35:29.00,0:35:32.00,Default,,0000,0000,0000,,is to follow those links.
Dialogue: 0,0:35:32.00,0:35:35.00,Default,,0000,0000,0000,,Often that's not as bad a disadvantage as it sounds because
Dialogue: 0,0:35:35.00,0:35:36.00,Default,,0000,0000,0000,,typically, right?
Dialogue: 0,0:35:36.00,0:35:38.00,Default,,0000,0000,0000,,That you're doing things like walking down the array or the vector to look at each of
Dialogue: 0,0:35:38.00,0:35:41.00,Default,,0000,0000,0000,,the elements at the end you would also be walking down the linked list while you did it isn't
Dialogue: 0,0:35:41.00,0:35:42.00,Default,,0000,0000,0000,,really that bad.
Dialogue: 0,0:35:42.00,0:35:45.00,Default,,0000,0000,0000,,So in the case where you happen to be storing stuff in an index and you really want to
Dialogue: 0,0:35:45.00,0:35:46.00,Default,,0000,0000,0000,,reach back in there
Dialogue: 0,0:35:46.00,0:35:50.00,Default,,0000,0000,0000,,is where the linked list starts to be a bad call. Can you take it on, like,
Dialogue: 0,0:35:50.00,0:35:52.00,Default,,0000,0000,0000,,from the list and find something?
Dialogue: 0,0:35:52.00,0:35:55.00,Default,,0000,0000,0000,,Well, it can take - the thing is it - with a question with me like a long time. Like if I were
Dialogue: 0,0:35:55.00,0:35:59.00,Default,,0000,0000,0000,,looking through to see if there was an existence of a particular score in a
Dialogue: 0,0:35:59.00,0:36:02.00,Default,,0000,0000,0000,,vector of integers I have to look at them all from the beginning to the end.
Dialogue: 0,0:36:02.00,0:36:05.00,Default,,0000,0000,0000,,Now, the way I can access them is subzero, subone, subtwo, right?
Dialogue: 0,0:36:05.00,0:36:09.00,Default,,0000,0000,0000,,But if I'm walking down a linked list I'm doing the same sort of work. I have to look at each element
Dialogue: 0,0:36:09.00,0:36:12.00,Default,,0000,0000,0000,,but the way I get to them is by traversing these pointers.
Dialogue: 0,0:36:12.00,0:36:15.00,Default,,0000,0000,0000,,It might be that that's a little bit more expensive relative to the
Dialogue: 0,0:36:15.00,0:36:18.00,Default,,0000,0000,0000,,vector, but they're still gonna be about the same. If there's a million elements
Dialogue: 0,0:36:18.00,0:36:20.00,Default,,0000,0000,0000,,they're all gonna look at a million elements and whether it looked at them in contiguous memory
Dialogue: 0,0:36:20.00,0:36:24.00,Default,,0000,0000,0000,,or looked at them by jumping around it ends up being in the end kind
Dialogue: 0,0:36:24.00,0:36:27.00,Default,,0000,0000,0000,,of a very comparable amount of time spent doing those things.
Dialogue: 0,0:36:27.00,0:36:31.00,Default,,0000,0000,0000,,What would be tricky is if I knew I wanted to get to the 100th element.
Dialogue: 0,0:36:31.00,0:36:34.00,Default,,0000,0000,0000,,Like I wasn't interested in looking at the other 99 that preceded it. I really just wanted
Dialogue: 0,0:36:34.00,0:36:37.00,Default,,0000,0000,0000,,to go straight to the thing at slot 100.
Dialogue: 0,0:36:37.00,0:36:39.00,Default,,0000,0000,0000,,The array gives me that access immediately.
Dialogue: 0,0:36:39.00,0:36:43.00,Default,,0000,0000,0000,,Just doing a little calculation it says it's here. Go to this place in memory.
Dialogue: 0,0:36:43.00,0:36:47.00,Default,,0000,0000,0000,,And the linked list would require this walking of 100 steps to get there.
Dialogue: 0,0:36:47.00,0:36:49.00,Default,,0000,0000,0000,,And so if there are situations, right? Where one of these is
Dialogue: 0,0:36:49.00,0:36:53.00,Default,,0000,0000,0000,,just clearly the better answer because you know you're gonna do that operation a lot, right? You're
Dialogue: 0,0:36:53.00,0:36:54.00,Default,,0000,0000,0000,,gonna definitely prefer this.
Dialogue: 0,0:36:54.00,0:36:58.00,Default,,0000,0000,0000,,If you know you're gonna do a lot of inserting and rearranging within the list,
Dialogue: 0,0:36:58.00,0:37:00.00,Default,,0000,0000,0000,,the linked list may buy you
Dialogue: 0,0:37:00.00,0:37:03.00,Default,,0000,0000,0000,,the ease of flexibility of a kind of rewiring
Dialogue: 0,0:37:03.00,0:37:10.00,Default,,0000,0000,0000,,that does not require all this shuffling to move everything around. Question here? But if you were to
Dialogue: 0,0:37:10.00,0:37:14.00,Default,,0000,0000,0000,,know the size of the linked list? Typically a linked list won't limit the size unless you tell it, but that's actually true about an
Dialogue: 0,0:37:14.00,0:37:15.00,Default,,0000,0000,0000,,array too, right? Which is you
Dialogue: 0,0:37:15.00,0:37:18.00,Default,,0000,0000,0000,,- the vector happens to it on your behalf, but underneath it, right? That the
Dialogue: 0,0:37:18.00,0:37:22.00,Default,,0000,0000,0000,,array is tracking how many elements are in there, so would a linked list. So
Dialogue: 0,0:37:22.00,0:37:25.00,Default,,0000,0000,0000,,you could do a manual count when you needed, which would be expensive, or you could
Dialogue: 0,0:37:25.00,0:37:27.00,Default,,0000,0000,0000,,just track along with that
Dialogue: 0,0:37:27.00,0:37:29.00,Default,,0000,0000,0000,,outer most pointer. Well, how many elements have I put in there?
Dialogue: 0,0:37:29.00,0:37:31.00,Default,,0000,0000,0000,,And then update it as you add and remove. So
Dialogue: 0,0:37:31.00,0:37:34.00,Default,,0000,0000,0000,,you'd likely want to cache that if it was important to you to know that. If
Dialogue: 0,0:37:34.00,0:37:38.00,Default,,0000,0000,0000,,a lot of your operations depended on knowing that size you'd probably want to keep it stored
Dialogue: 0,0:37:38.00,0:37:41.00,Default,,0000,0000,0000,,somewhere. Over here?
Dialogue: 0,0:37:41.00,0:37:42.00,Default,,0000,0000,0000,,Why does
Dialogue: 0,0:37:42.00,0:37:45.00,Default,,0000,0000,0000,,the vector use arrays then instead of linked
Dialogue: 0,0:37:45.00,0:37:46.00,Default,,0000,0000,0000,,list?
Dialogue: 0,0:37:46.00,0:37:49.00,Default,,0000,0000,0000,,That is a great question. It's one that we actually will talk about kind of in about a week.
Dialogue: 0,0:37:49.00,0:37:52.00,Default,,0000,0000,0000,,It's like, well, why? So sometimes array - the vector is kind of taking the
Dialogue: 0,0:37:52.00,0:37:56.00,Default,,0000,0000,0000,,path of, well, it's just presenting you to the array in a slightly more convenient
Dialogue: 0,0:37:56.00,0:37:56.00,Default,,0000,0000,0000,,form.
Dialogue: 0,0:37:56.00,0:37:58.00,Default,,0000,0000,0000,,We will see situations where
Dialogue: 0,0:37:58.00,0:38:01.00,Default,,0000,0000,0000,,then the vector is just as bad as a choice as an array and then we'll
Dialogue: 0,0:38:01.00,0:38:05.00,Default,,0000,0000,0000,,see, well, why we might prefer to use a linked list and we will have - we will build linked
Dialogue: 0,0:38:05.00,0:38:06.00,Default,,0000,0000,0000,,lists instead basically.
Dialogue: 0,0:38:06.00,0:38:10.00,Default,,0000,0000,0000,,It has to make a choice and it turns out that for most usages
Dialogue: 0,0:38:10.00,0:38:11.00,Default,,0000,0000,0000,,the array
Dialogue: 0,0:38:11.00,0:38:15.00,Default,,0000,0000,0000,,is a pretty good match for a lot of ordinary tasks. The linked list happens to be a match
Dialogue: 0,0:38:15.00,0:38:18.00,Default,,0000,0000,0000,,for other tasks, right? And then we will build stuff out of that when
Dialogue: 0,0:38:18.00,0:38:20.00,Default,,0000,0000,0000,,that context comes up. Well, if you just, like,
Dialogue: 0,0:38:20.00,0:38:22.00,Default,,0000,0000,0000,,then you just, sort of, like
Dialogue: 0,0:38:22.00,0:38:25.00,Default,,0000,0000,0000,,in a vector class, like encapsulate all that and I - its final
Dialogue: 0,0:38:25.00,0:38:29.00,Default,,0000,0000,0000,,functionality would be the same. You certainly could. So you could totally build a vector class that
Dialogue: 0,0:38:29.00,0:38:31.00,Default,,0000,0000,0000,,actually was backed by a linked list and we will see how to do that,
Dialogue: 0,0:38:31.00,0:38:34.00,Default,,0000,0000,0000,,right? And then it would have different characteristics in terms of what
Dialogue: 0,0:38:34.00,0:38:36.00,Default,,0000,0000,0000,,operations were efficient and which ones were inefficient
Dialogue: 0,0:38:36.00,0:38:39.00,Default,,0000,0000,0000,,relative to do an array backed one. And
Dialogue: 0,0:38:39.00,0:38:41.00,Default,,0000,0000,0000,,over here was also. Yeah?
Dialogue: 0,0:38:41.00,0:38:43.00,Default,,0000,0000,0000,,Well, I, just to - for using linked
Dialogue: 0,0:38:43.00,0:38:44.00,Default,,0000,0000,0000,,lists, like,
Dialogue: 0,0:38:44.00,0:38:48.00,Default,,0000,0000,0000,,so first in, first out or first in, last out
Dialogue: 0,0:38:48.00,0:38:48.00,Default,,0000,0000,0000,,seems to make
Dialogue: 0,0:38:48.00,0:38:51.00,Default,,0000,0000,0000,,really good sense, but are there - am I
Dialogue: 0,0:38:51.00,0:38:52.00,Default,,0000,0000,0000,,like
Dialogue: 0,0:38:52.00,0:38:55.00,Default,,0000,0000,0000,,missing - You are way ahead of us, but, yeah, you're right on.
Dialogue: 0,0:38:55.00,0:38:57.00,Default,,0000,0000,0000,,The things like the stack and the Q, right?
Dialogue: 0,0:38:57.00,0:39:00.00,Default,,0000,0000,0000,,Seem like they're gonna be natural things that will work very, very well with
Dialogue: 0,0:39:00.00,0:39:01.00,Default,,0000,0000,0000,,a linked list.
Dialogue: 0,0:39:01.00,0:39:04.00,Default,,0000,0000,0000,,Things that required a lot of shuffling in the middle, right? It's a
Dialogue: 0,0:39:04.00,0:39:08.00,Default,,0000,0000,0000,,little unclear because you have to find the place in the middle, which is expensive,
Dialogue: 0,0:39:08.00,0:39:11.00,Default,,0000,0000,0000,,but then the insert is fast. The question is, well, which of these is actually gonna
Dialogue: 0,0:39:11.00,0:39:13.00,Default,,0000,0000,0000,,work out better? They both have
Dialogue: 0,0:39:13.00,0:39:16.00,Default,,0000,0000,0000,,some things they can do well and some things they can't do well. So it will have to have
Dialogue: 0,0:39:16.00,0:39:19.00,Default,,0000,0000,0000,,know maybe a little bit more about the context to be sure which ones seem
Dialogue: 0,0:39:19.00,0:39:22.00,Default,,0000,0000,0000,,like the best solution and maybe in the end it's just a coin toss, right?
Dialogue: 0,0:39:22.00,0:39:25.00,Default,,0000,0000,0000,,Some parts will be fast and some parts could be slow and anyway I can get the inverted form
Dialogue: 0,0:39:25.00,0:39:26.00,Default,,0000,0000,0000,,of that
Dialogue: 0,0:39:26.00,0:39:28.00,Default,,0000,0000,0000,,as an alternative that
Dialogue: 0,0:39:28.00,0:39:32.00,Default,,0000,0000,0000,,doesn't dominate in any clear sense. It's just like, well, they both have advantages
Dialogue: 0,0:39:32.00,0:39:35.00,Default,,0000,0000,0000,,and disadvantages. Question
Dialogue: 0,0:39:35.00,0:39:36.00,Default,,0000,0000,0000,,back here? Why
Dialogue: 0,0:39:36.00,0:39:37.00,Default,,0000,0000,0000,,was
Dialogue: 0,0:39:37.00,0:39:38.00,Default,,0000,0000,0000,,that infused
Dialogue: 0,0:39:38.00,0:39:41.00,Default,,0000,0000,0000,,to be based on a vector instead of a linked list?
Dialogue: 0,0:39:41.00,0:39:44.00,Default,,0000,0000,0000,,So they - I think your question is kind of like, yeah, they likely are built on linked lists.
Dialogue: 0,0:39:44.00,0:39:48.00,Default,,0000,0000,0000,,We're gonna see how we can do it both ways, right? We'll see how we can do it on array, we'll see how we can do it
Dialogue: 0,0:39:48.00,0:39:50.00,Default,,0000,0000,0000,,on a linked list, and then we'll talk about what those tradeoffs look like. Well, which one
Dialogue: 0,0:39:50.00,0:39:54.00,Default,,0000,0000,0000,,ends up being the better call
Dialogue: 0,0:39:54.00,0:39:57.00,Default,,0000,0000,0000,,when we're there? So that will be about a week. So don't worry too much about it now,
Dialogue: 0,0:39:57.00,0:40:00.00,Default,,0000,0000,0000,,but when we get there we'll definitely see kind of both variants and then we'll
Dialogue: 0,0:40:00.00,0:40:06.00,Default,,0000,0000,0000,,talk about them in great detail. Okay.
Dialogue: 0,0:40:06.00,0:40:10.00,Default,,0000,0000,0000,,So I'm gonna show you, just the last operation I want to show you on a linked list
Dialogue: 0,0:40:10.00,0:40:12.00,Default,,0000,0000,0000,,is doing an insert in sorted order and this
Dialogue: 0,0:40:12.00,0:40:15.00,Default,,0000,0000,0000,,is gonna require some pretty careful
Dialogue: 0,0:40:15.00,0:40:17.00,Default,,0000,0000,0000,,understanding of what's going on with the pointers and then we're also gonna
Dialogue: 0,0:40:17.00,0:40:20.00,Default,,0000,0000,0000,,see a recursive form of it that actually is a
Dialogue: 0,0:40:20.00,0:40:22.00,Default,,0000,0000,0000,,really clever
Dialogue: 0,0:40:22.00,0:40:25.00,Default,,0000,0000,0000,,and very elegant way to solve the same problem. So I'm gonna first do it
Dialogue: 0,0:40:25.00,0:40:25.00,Default,,0000,0000,0000,,iteratively
Dialogue: 0,0:40:25.00,0:40:28.00,Default,,0000,0000,0000,,just to kind of talk about. What's the mechanism for doing stuff iteratively on
Dialogue: 0,0:40:28.00,0:40:32.00,Default,,0000,0000,0000,,a linked list? It gets a little bit messy and so just be prepared for that.
Dialogue: 0,0:40:32.00,0:40:36.00,Default,,0000,0000,0000,,That I'm planning on taking my address book and building it up inserted order. So
Dialogue: 0,0:40:36.00,0:40:40.00,Default,,0000,0000,0000,,instead of doing a prepend where I just take each cell and put it on the front I'm actually assume
Dialogue: 0,0:40:40.00,0:40:42.00,Default,,0000,0000,0000,,that I'm gonna keep them all in order by name
Dialogue: 0,0:40:42.00,0:40:45.00,Default,,0000,0000,0000,,and whenever I get a new cell I want to put it in the right position relative to
Dialogue: 0,0:40:45.00,0:40:48.00,Default,,0000,0000,0000,,the other neighbors in the list that are all ready there.
Dialogue: 0,0:40:48.00,0:40:51.00,Default,,0000,0000,0000,,So this is one of those places where it seems like the linked list is actually gonna do very well. I have
Dialogue: 0,0:40:51.00,0:40:53.00,Default,,0000,0000,0000,,to search to find the spot.
Dialogue: 0,0:40:53.00,0:40:55.00,Default,,0000,0000,0000,,Okay? Well, you're gonna have to search to find the spot in a vector, too.
Dialogue: 0,0:40:55.00,0:40:59.00,Default,,0000,0000,0000,,Once I find the spot it should be very easy to just wire it in
Dialogue: 0,0:40:59.00,0:41:02.00,Default,,0000,0000,0000,,without shuffling and rearranging anything around. It should be a pointer
Dialogue: 0,0:41:02.00,0:41:04.00,Default,,0000,0000,0000,,in and a pointer out.
Dialogue: 0,0:41:04.00,0:41:06.00,Default,,0000,0000,0000,,So I'm gonna start this insert sorted.
Dialogue: 0,0:41:06.00,0:41:08.00,Default,,0000,0000,0000,,It's gonna take the
Dialogue: 0,0:41:08.00,0:41:11.00,Default,,0000,0000,0000,,head of the list, right? As a bi-reference parameter because there are
Dialogue: 0,0:41:11.00,0:41:14.00,Default,,0000,0000,0000,,situations, right? Where we're gonna be changing where the list points to when the cells in the
Dialogue: 0,0:41:14.00,0:41:15.00,Default,,0000,0000,0000,,first one
Dialogue: 0,0:41:15.00,0:41:18.00,Default,,0000,0000,0000,,and then the new cell that's coming in is the second parameter.
Dialogue: 0,0:41:18.00,0:41:21.00,Default,,0000,0000,0000,,So we're gonna search to find the place where it goes.
Dialogue: 0,0:41:21.00,0:41:24.00,Default,,0000,0000,0000,,So let's watch this go down it's
Dialogue: 0,0:41:24.00,0:41:28.00,Default,,0000,0000,0000,,loop. I do a four loop here that's like, well, Kerr starts this list while it's not null,
Dialogue: 0,0:41:28.00,0:41:29.00,Default,,0000,0000,0000,,advance by this,
Dialogue: 0,0:41:29.00,0:41:34.00,Default,,0000,0000,0000,,and if the cell that I'm trying to place, which in this case is the cell Rain,
Dialogue: 0,0:41:34.00,0:41:36.00,Default,,0000,0000,0000,,proceeds the one we're currently looking at,
Dialogue: 0,0:41:36.00,0:41:38.00,Default,,0000,0000,0000,,then this must be the place that goes in the list.
Dialogue: 0,0:41:38.00,0:41:41.00,Default,,0000,0000,0000,,So I look at Rain, I compare it to Cullaf
Dialogue: 0,0:41:41.00,0:41:44.00,Default,,0000,0000,0000,,and if Rain goes in front of Cullaf then this is where Rain should go in the list.
Dialogue: 0,0:41:44.00,0:41:47.00,Default,,0000,0000,0000,,Well, it doesn't actually proceed it,
Dialogue: 0,0:41:47.00,0:41:48.00,Default,,0000,0000,0000,,so I advance again. Then
Dialogue: 0,0:41:48.00,0:41:51.00,Default,,0000,0000,0000,,I look at Cullaf - Rain versus Lowery.
Dialogue: 0,0:41:51.00,0:41:54.00,Default,,0000,0000,0000,,Does Rain proceed Lowery? It does not. So I just keep going. So I'm gonna break out of
Dialogue: 0,0:41:54.00,0:41:56.00,Default,,0000,0000,0000,,the loop as soon as I get to
Dialogue: 0,0:41:56.00,0:41:59.00,Default,,0000,0000,0000,,the place I compare Rain to Matt.
Dialogue: 0,0:41:59.00,0:42:00.00,Default,,0000,0000,0000,,Doesn't come out.
Dialogue: 0,0:42:00.00,0:42:03.00,Default,,0000,0000,0000,,I compare Rain to Thomas.
Dialogue: 0,0:42:03.00,0:42:07.00,Default,,0000,0000,0000,,Now, this is the first time when new ones name came up as being less than
Dialogue: 0,0:42:07.00,0:42:08.00,Default,,0000,0000,0000,,Kerr's name.
Dialogue: 0,0:42:08.00,0:42:13.00,Default,,0000,0000,0000,,So that says, okay, well, Rain needs to go in front of Thomas.
Dialogue: 0,0:42:13.00,0:42:15.00,Default,,0000,0000,0000,,Okay. All is well and good
Dialogue: 0,0:42:15.00,0:42:18.00,Default,,0000,0000,0000,,almost.
Dialogue: 0,0:42:18.00,0:42:20.00,Default,,0000,0000,0000,,I have a pointer to Thomas.
Dialogue: 0,0:42:20.00,0:42:23.00,Default,,0000,0000,0000,,That's where my curve points to, right?
Dialogue: 0,0:42:23.00,0:42:29.00,Default,,0000,0000,0000,,And I want to put Rain kind of in the list right in front of Thomas. How do
Dialogue: 0,0:42:29.00,0:42:38.00,Default,,0000,0000,0000,,I get from Thomas to Matt? But it's
Dialogue: 0,0:42:38.00,0:42:41.00,Default,,0000,0000,0000,,not just enough to know Thomas, right? Because Thomas tells me like what's gonna follow
Dialogue: 0,0:42:41.00,0:42:42.00,Default,,0000,0000,0000,,Rain.
Dialogue: 0,0:42:42.00,0:42:44.00,Default,,0000,0000,0000,,So this is the cell where
Dialogue: 0,0:42:44.00,0:42:47.00,Default,,0000,0000,0000,,Rain's next is gonna point to where Thomas is because Rain is kind of gonna replace
Dialogue: 0,0:42:47.00,0:42:51.00,Default,,0000,0000,0000,,Thomas in the list and push Thomas one element down,
Dialogue: 0,0:42:51.00,0:42:55.00,Default,,0000,0000,0000,,but the situation is that I also need to know what proceeds Thomas. The
Dialogue: 0,0:42:55.00,0:42:58.00,Default,,0000,0000,0000,,cell that led into Thomas is the one whose next field needs to get reassigned
Dialogue: 0,0:42:58.00,0:43:00.00,Default,,0000,0000,0000,,to point to Rain.
Dialogue: 0,0:43:00.00,0:43:01.00,Default,,0000,0000,0000,,So the way the loop is going, right?
Dialogue: 0,0:43:01.00,0:43:04.00,Default,,0000,0000,0000,,It has to go kind of one too far
Dialogue: 0,0:43:04.00,0:43:07.00,Default,,0000,0000,0000,,to know that it was there because, like, if I look at Matt I can say, well, does Rain go
Dialogue: 0,0:43:07.00,0:43:10.00,Default,,0000,0000,0000,,after Matt? Yes, it does. Right? But that's not good enough to know that it goes
Dialogue: 0,0:43:10.00,0:43:13.00,Default,,0000,0000,0000,,right after Matt. The only way I can tell if it goes right after Matt is to say,
Dialogue: 0,0:43:13.00,0:43:17.00,Default,,0000,0000,0000,,well, if the cell that comes up next, right? Is behind Rain is that it goes in between
Dialogue: 0,0:43:17.00,0:43:21.00,Default,,0000,0000,0000,,these two.
Dialogue: 0,0:43:21.00,0:43:22.00,Default,,0000,0000,0000,,[Inaudible] Thomas and then
Dialogue: 0,0:43:22.00,0:43:24.00,Default,,0000,0000,0000,,[inaudible] Thomas?
Dialogue: 0,0:43:24.00,0:43:27.00,Default,,0000,0000,0000,,Yes. So at least I can do it by maybe kind of
Dialogue: 0,0:43:27.00,0:43:30.00,Default,,0000,0000,0000,,overwriting Thomas with Rain and then overwriting Rain with Thomas and kind of
Dialogue: 0,0:43:30.00,0:43:31.00,Default,,0000,0000,0000,,wiring them up. I'm gonna try to avoid that.
Dialogue: 0,0:43:31.00,0:43:34.00,Default,,0000,0000,0000,,I'm gonna actually say, well, let's just think about can we do it with
Dialogue: 0,0:43:34.00,0:43:37.00,Default,,0000,0000,0000,,leaving the information in the cells where it is?
Dialogue: 0,0:43:37.00,0:43:40.00,Default,,0000,0000,0000,,I don't know who else might point to Thomas, right? It would seem kind of weird if all of
Dialogue: 0,0:43:40.00,0:43:44.00,Default,,0000,0000,0000,,a sudden Thomas turned into Rain in some other way. That I don't know for sure
Dialogue: 0,0:43:44.00,0:43:47.00,Default,,0000,0000,0000,,who else is using this pointer. So lets assume that I can't do that
Dialogue: 0,0:43:47.00,0:43:50.00,Default,,0000,0000,0000,,variation of it, but I'd like to put Rain in between Matt and Thomas
Dialogue: 0,0:43:50.00,0:43:53.00,Default,,0000,0000,0000,,and the pointer I have is not quite good enough.
Dialogue: 0,0:43:53.00,0:43:56.00,Default,,0000,0000,0000,,The cells as is, right? Have this asymmetry. They know what follows or
Dialogue: 0,0:43:56.00,0:43:58.00,Default,,0000,0000,0000,,not. What precedes them.
Dialogue: 0,0:43:58.00,0:44:02.00,Default,,0000,0000,0000,,So, in fact, what I'm gonna change here is I'm going to run two pointers down
Dialogue: 0,0:44:02.00,0:44:03.00,Default,,0000,0000,0000,,the list,
Dialogue: 0,0:44:03.00,0:44:05.00,Default,,0000,0000,0000,,kind of in parallel,
Dialogue: 0,0:44:05.00,0:44:08.00,Default,,0000,0000,0000,,where they're always one step apart.
Dialogue: 0,0:44:08.00,0:44:11.00,Default,,0000,0000,0000,,Then I'm gonna track what was the one I last looked at
Dialogue: 0,0:44:11.00,0:44:13.00,Default,,0000,0000,0000,,and what is the one I'm currently looking at
Dialogue: 0,0:44:13.00,0:44:16.00,Default,,0000,0000,0000,,and I call this dragging a previous pointer
Dialogue: 0,0:44:16.00,0:44:19.00,Default,,0000,0000,0000,,or trailing a previous pointer behind.
Dialogue: 0,0:44:19.00,0:44:20.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:44:20.00,0:44:24.00,Default,,0000,0000,0000,,each time I'm about to advance Kerr equals Kerr next, the thing I'll do right
Dialogue: 0,0:44:24.00,0:44:27.00,Default,,0000,0000,0000,,before it is to assign previous to be what Kerr is now.
Dialogue: 0,0:44:27.00,0:44:31.00,Default,,0000,0000,0000,,So then it'll advance to the next one, test against null, and keep going. So at
Dialogue: 0,0:44:31.00,0:44:33.00,Default,,0000,0000,0000,,any given state, right?
Dialogue: 0,0:44:33.00,0:44:36.00,Default,,0000,0000,0000,,Previous is exactly one behind where Kerr is
Dialogue: 0,0:44:36.00,0:44:39.00,Default,,0000,0000,0000,,and there's one special case, right? Which is that
Dialogue: 0,0:44:39.00,0:44:44.00,Default,,0000,0000,0000,,at the very first time through the loop, right? Kerr is set to be the list. Well,
Dialogue: 0,0:44:44.00,0:44:48.00,Default,,0000,0000,0000,,what's the previous of the head of the list? There actually is no previous, so actually
Dialogue: 0,0:44:48.00,0:44:50.00,Default,,0000,0000,0000,,initialize previous to be null.
Dialogue: 0,0:44:50.00,0:44:52.00,Default,,0000,0000,0000,,So the first time through, right?
Dialogue: 0,0:44:52.00,0:44:55.00,Default,,0000,0000,0000,,We've assigned previous to null and Kerr gets to go to the first one and then we
Dialogue: 0,0:44:55.00,0:44:57.00,Default,,0000,0000,0000,,say, well, is Cullaf -
Dialogue: 0,0:44:57.00,0:44:58.00,Default,,0000,0000,0000,,does
Dialogue: 0,0:44:58.00,0:45:00.00,Default,,0000,0000,0000,,Rain come before Cullaf? No.
Dialogue: 0,0:45:00.00,0:45:04.00,Default,,0000,0000,0000,,And so I'll advance both so move previous up to where Kerr is and then move
Dialogue: 0,0:45:04.00,0:45:06.00,Default,,0000,0000,0000,,Kerr up to the next one.
Dialogue: 0,0:45:06.00,0:45:08.00,Default,,0000,0000,0000,,So now they're pointing at Cullaf and Lowery together
Dialogue: 0,0:45:08.00,0:45:12.00,Default,,0000,0000,0000,,and, again, I'm comparing Lowery to Rain. Does Rain go in front of Lowery? No. So then I
Dialogue: 0,0:45:12.00,0:45:15.00,Default,,0000,0000,0000,,move up previous and move up Kerr.
Dialogue: 0,0:45:15.00,0:45:17.00,Default,,0000,0000,0000,,Does Rain go in front of Matt?
Dialogue: 0,0:45:17.00,0:45:19.00,Default,,0000,0000,0000,,No. I advance them both, right?
Dialogue: 0,0:45:19.00,0:45:21.00,Default,,0000,0000,0000,,And then I have
Dialogue: 0,0:45:21.00,0:45:22.00,Default,,0000,0000,0000,,
Dialogue: 0,0:45:22.00,0:45:25.00,Default,,0000,0000,0000,,previous at the Matt entry, Kerr at the Thomas entry,
Dialogue: 0,0:45:25.00,0:45:28.00,Default,,0000,0000,0000,,and then Rain does go right in between those, right?
Dialogue: 0,0:45:28.00,0:45:32.00,Default,,0000,0000,0000,,We know that it didn't precede Matt because we all ready made it through the loop.
Dialogue: 0,0:45:32.00,0:45:37.00,Default,,0000,0000,0000,,We know it does precede Thomas and that tells us it goes exactly in between them, right?
Dialogue: 0,0:45:37.00,0:45:41.00,Default,,0000,0000,0000,,That Matt should lead into Rain and Rain should lead into Thomas and that will have
Dialogue: 0,0:45:41.00,0:45:44.00,Default,,0000,0000,0000,,spliced it in the list at the right position
Dialogue: 0,0:45:44.00,0:45:45.00,Default,,0000,0000,0000,,relative to the
Dialogue: 0,0:45:45.00,0:45:47.00,Default,,0000,0000,0000,,other sorted entries. So I
Dialogue: 0,0:45:47.00,0:45:55.00,Default,,0000,0000,0000,,give myself just a little note here. Well, what are the possible values for previous?
Dialogue: 0,0:45:55.00,0:46:00.00,Default,,0000,0000,0000,,If the cell is gonna go anywhere in the list other than the very front,
Dialogue: 0,0:46:00.00,0:46:05.00,Default,,0000,0000,0000,,so as long as Rain follows at least one cell on the list, it's not the
Dialogue: 0,0:46:05.00,0:46:05.00,Default,,0000,0000,0000,,alphabetically
Dialogue: 0,0:46:05.00,0:46:09.00,Default,,0000,0000,0000,,first cell of all the ones I've seen, then previous will be some valid cell
Dialogue: 0,0:46:09.00,0:46:12.00,Default,,0000,0000,0000,,and potentially Kerr could be null,
Dialogue: 0,0:46:12.00,0:46:17.00,Default,,0000,0000,0000,,but there is a non-null prev in all of those cases.
Dialogue: 0,0:46:17.00,0:46:20.00,Default,,0000,0000,0000,,There's also the possibility though that previous is null
Dialogue: 0,0:46:20.00,0:46:23.00,Default,,0000,0000,0000,,in the case where the new cell was the alphabetically first. So if that one actually began
Dialogue: 0,0:46:23.00,0:46:27.00,Default,,0000,0000,0000,,with an A, let's say it was Alena.
Dialogue: 0,0:46:27.00,0:46:30.00,Default,,0000,0000,0000,,Then the first test would be if Alena is less then Cullaf. It is. It would
Dialogue: 0,0:46:30.00,0:46:31.00,Default,,0000,0000,0000,,immediately break and
Dialogue: 0,0:46:31.00,0:46:35.00,Default,,0000,0000,0000,,so previous would be null, Kerr would point to the front most cell,
Dialogue: 0,0:46:35.00,0:46:38.00,Default,,0000,0000,0000,,and I've got a little bit of a special case there
Dialogue: 0,0:46:38.00,0:46:43.00,Default,,0000,0000,0000,,where inserting at the front of the list isn't quite the same thing as inserting
Dialogue: 0,0:46:43.00,0:46:44.00,Default,,0000,0000,0000,,further down.
Dialogue: 0,0:46:44.00,0:46:49.00,Default,,0000,0000,0000,,So let me look at the code that I added to this and I ran out of room to draw pictures, so we'll have to do a little
Dialogue: 0,0:46:49.00,0:46:51.00,Default,,0000,0000,0000,,bit on the board here.
Dialogue: 0,0:46:51.00,0:46:54.00,Default,,0000,0000,0000,,That there are two pointers we need to assign
Dialogue: 0,0:46:54.00,0:46:55.00,Default,,0000,0000,0000,,for that
Dialogue: 0,0:46:55.00,0:47:01.00,Default,,0000,0000,0000,,new cell that's coming in. One is it's outgoing one
Dialogue: 0,0:47:01.00,0:47:06.00,Default,,0000,0000,0000,,and then another is it's incoming one. And so
Dialogue: 0,0:47:06.00,0:47:11.00,Default,,0000,0000,0000,,I have this list and,
Dialogue: 0,0:47:11.00,0:47:16.00,Default,,0000,0000,0000,,let's say, this new cell is going here. So this is like K, L, M,
Dialogue: 0,0:47:16.00,0:47:17.00,Default,,0000,0000,0000,,T, R.
Dialogue: 0,0:47:17.00,0:47:22.00,Default,,0000,0000,0000,,That the first line splices in the outgoing pointer in all cases. It says
Dialogue: 0,0:47:22.00,0:47:24.00,Default,,0000,0000,0000,,that the new ones next field is Kerr.
Dialogue: 0,0:47:24.00,0:47:29.00,Default,,0000,0000,0000,,So Kerr is the first cell, right? That we found that follows the cell we're trying
Dialogue: 0,0:47:29.00,0:47:32.00,Default,,0000,0000,0000,,to insert. It might be that Kerr is null,
Dialogue: 0,0:47:32.00,0:47:33.00,Default,,0000,0000,0000,,but that's totally fine too.
Dialogue: 0,0:47:33.00,0:47:37.00,Default,,0000,0000,0000,,In this case it happened to point - this is where Kerr was and this is where previous
Dialogue: 0,0:47:37.00,0:47:39.00,Default,,0000,0000,0000,,was.
Dialogue: 0,0:47:39.00,0:47:41.00,Default,,0000,0000,0000,,That it will make
Dialogue: 0,0:47:41.00,0:47:44.00,Default,,0000,0000,0000,,R point to T, so that is the outgoing pointer for the new cell
Dialogue: 0,0:47:44.00,0:47:46.00,Default,,0000,0000,0000,,and now there are two cases here.
Dialogue: 0,0:47:46.00,0:47:51.00,Default,,0000,0000,0000,,The ordinary case is that there is some previous cell. In which case the previous
Dialogue: 0,0:47:51.00,0:47:54.00,Default,,0000,0000,0000,,cell's next field needs to get updated to point to the new one.
Dialogue: 0,0:47:54.00,0:47:58.00,Default,,0000,0000,0000,,So we use the pointer to this one. It's next field
Dialogue: 0,0:47:58.00,0:48:00.00,Default,,0000,0000,0000,,no longer points to T,
Dialogue: 0,0:48:00.00,0:48:05.00,Default,,0000,0000,0000,,but instead points to R. And so I inserted R in between M and T with that
Dialogue: 0,0:48:05.00,0:48:06.00,Default,,0000,0000,0000,,adjustment.
Dialogue: 0,0:48:06.00,0:48:09.00,Default,,0000,0000,0000,,In the case where the new cell,
Dialogue: 0,0:48:09.00,0:48:11.00,Default,,0000,0000,0000,,let's say, was the A,
Dialogue: 0,0:48:11.00,0:48:13.00,Default,,0000,0000,0000,,then Kerr would be here
Dialogue: 0,0:48:13.00,0:48:17.00,Default,,0000,0000,0000,,and previous would be null.
Dialogue: 0,0:48:17.00,0:48:20.00,Default,,0000,0000,0000,,I will set A as next field to the Kerr,
Dialogue: 0,0:48:20.00,0:48:23.00,Default,,0000,0000,0000,,which spliced the outgoing pointer of A
Dialogue: 0,0:48:23.00,0:48:25.00,Default,,0000,0000,0000,,to attach to the rest of the list.
Dialogue: 0,0:48:25.00,0:48:29.00,Default,,0000,0000,0000,,But here's the special case. There is no previous next field that's gonna point to A.
Dialogue: 0,0:48:29.00,0:48:32.00,Default,,0000,0000,0000,,A actually needs to get reassigned to be the front most cell of the list. So it
Dialogue: 0,0:48:32.00,0:48:36.00,Default,,0000,0000,0000,,looks like our prepend operation where I'm saying list equals new one
Dialogue: 0,0:48:36.00,0:48:40.00,Default,,0000,0000,0000,,and the list is some reference parameter
Dialogue: 0,0:48:40.00,0:48:42.00,Default,,0000,0000,0000,,to some list elsewhere
Dialogue: 0,0:48:42.00,0:48:46.00,Default,,0000,0000,0000,,that then gets permanently set to the new cell. So I would call insert sorted
Dialogue: 0,0:48:46.00,0:48:49.00,Default,,0000,0000,0000,,from, like, the build address book function
Dialogue: 0,0:48:49.00,0:48:52.00,Default,,0000,0000,0000,,to attach it to the very front in this case.
Dialogue: 0,0:48:52.00,0:48:56.00,Default,,0000,0000,0000,,This is very common in linked list code, right? Is to have there be a bit of a special
Dialogue: 0,0:48:56.00,0:49:00.00,Default,,0000,0000,0000,,case about either the first cell or the last cell or on the empty list, right? But
Dialogue: 0,0:49:00.00,0:49:03.00,Default,,0000,0000,0000,,that there is a large
Dialogue: 0,0:49:03.00,0:49:06.00,Default,,0000,0000,0000,,- all the cells in the interior kind of behave the same. They have a cell in
Dialogue: 0,0:49:06.00,0:49:10.00,Default,,0000,0000,0000,,front of them and a cell in back of them and that insert has certain properties, but
Dialogue: 0,0:49:10.00,0:49:13.00,Default,,0000,0000,0000,,there's a little bit of an oddness with that maybe that first cell is sometimes the
Dialogue: 0,0:49:13.00,0:49:16.00,Default,,0000,0000,0000,,very last cell that requires a little special case handling.
Dialogue: 0,0:49:16.00,0:49:20.00,Default,,0000,0000,0000,,In this case, right? Putting A in the front means somebody doesn't point
Dialogue: 0,0:49:20.00,0:49:22.00,Default,,0000,0000,0000,,into A. It's the listhead that points to A
Dialogue: 0,0:49:22.00,0:49:24.00,Default,,0000,0000,0000,,and so it's not somebody's next field
Dialogue: 0,0:49:24.00,0:49:30.00,Default,,0000,0000,0000,,that we're updating. It really is the listhead pointer itself.
Dialogue: 0,0:49:30.00,0:49:32.00,Default,,0000,0000,0000,,Questions about that one?
Dialogue: 0,0:49:32.00,0:49:35.00,Default,,0000,0000,0000,,So I need to show you the recursive one. I'm not gonna be able to talk about it very much, but
Dialogue: 0,0:49:35.00,0:49:38.00,Default,,0000,0000,0000,,I'm gonna encourage you to take a look at it.
Dialogue: 0,0:49:38.00,0:49:40.00,Default,,0000,0000,0000,,Which is the
Dialogue: 0,0:49:40.00,0:49:41.00,Default,,0000,0000,0000,,
Dialogue: 0,0:49:41.00,0:49:46.00,Default,,0000,0000,0000,,same activity of inserting a cell
Dialogue: 0,0:49:46.00,0:49:48.00,Default,,0000,0000,0000,,into a list that's being kept in sorted order.
Dialogue: 0,0:49:48.00,0:49:53.00,Default,,0000,0000,0000,,Now, not using this iterative, not using this dragging of our previous pointer,
Dialogue: 0,0:49:53.00,0:49:58.00,Default,,0000,0000,0000,,but instead using a strong dense recursive powerful formulation here
Dialogue: 0,0:49:58.00,0:50:01.00,Default,,0000,0000,0000,,that basically has the idea that says, well,
Dialogue: 0,0:50:01.00,0:50:03.00,Default,,0000,0000,0000,,given a list that I'm inserting into,
Dialogue: 0,0:50:03.00,0:50:06.00,Default,,0000,0000,0000,,let's say it's the M through Z part of the list.
Dialogue: 0,0:50:06.00,0:50:11.00,Default,,0000,0000,0000,,I'm trying to insert R is I compare R to the front of the list and I say,
Dialogue: 0,0:50:11.00,0:50:14.00,Default,,0000,0000,0000,,well, does that become the new front of this list? That's what my base case is
Dialogue: 0,0:50:14.00,0:50:18.00,Default,,0000,0000,0000,,looking at. Is the list empty or does this one go in front of it? If so, prepend it.
Dialogue: 0,0:50:18.00,0:50:19.00,Default,,0000,0000,0000,,Otherwise
Dialogue: 0,0:50:19.00,0:50:22.00,Default,,0000,0000,0000,,just insert it in the remainder of this list.
Dialogue: 0,0:50:22.00,0:50:24.00,Default,,0000,0000,0000,,So if it doesn't insert
Dialogue: 0,0:50:24.00,0:50:28.00,Default,,0000,0000,0000,,at the front of M then we pass the N or the O whatever is following it and
Dialogue: 0,0:50:28.00,0:50:31.00,Default,,0000,0000,0000,,have it kind of recursively insert into the
Dialogue: 0,0:50:31.00,0:50:34.00,Default,,0000,0000,0000,,remainder of the list. Eventually it will hit the space case
Dialogue: 0,0:50:34.00,0:50:38.00,Default,,0000,0000,0000,,when it either gets to the end of the list or when there is
Dialogue: 0,0:50:38.00,0:50:40.00,Default,,0000,0000,0000,,the cell we're trying to insert
Dialogue: 0,0:50:40.00,0:50:43.00,Default,,0000,0000,0000,,belongs in front of these remaining cells. In which case, we do a prepend right
Dialogue: 0,0:50:43.00,0:50:44.00,Default,,0000,0000,0000,,there
Dialogue: 0,0:50:44.00,0:50:46.00,Default,,0000,0000,0000,,and stop the recursion.
Dialogue: 0,0:50:46.00,0:50:49.00,Default,,0000,0000,0000,,A dense little piece of code. One I'll
Dialogue: 0,0:50:49.00,0:50:53.00,Default,,0000,0000,0000,,encourage you to kind of trace a little bit on your own to kind of
Dialogue: 0,0:50:53.00,0:50:56.00,Default,,0000,0000,0000,,get an idea of how it's working, but it kind of shows in this case that the recursion is
Dialogue: 0,0:50:56.00,0:50:57.00,Default,,0000,0000,0000,,really buying you something
Dialogue: 0,0:50:57.00,0:51:00.00,Default,,0000,0000,0000,,by making it, I think, a much simpler and more direct way to
Dialogue: 0,0:51:00.00,0:51:02.00,Default,,0000,0000,0000,,express what you want to do and then kind of the
Dialogue: 0,0:51:02.00,0:51:06.00,Default,,0000,0000,0000,,more mechanical means of doing it iteratively.
Dialogue: 0,0:51:06.00,0:51:08.00,Default,,0000,0000,0000,,What we will talk about on Monday
Dialogue: 0,0:51:08.00,0:51:12.00,Default,,0000,0000,0000,,will be algorithms. We'll talk about algorithms, Chapter 7. Start talking about
Dialogue: 0,0:51:12.00,0:51:16.00,Default,,0000,0000,0000,,Big O and formal announcements algorithms and do a little bit of sorting. So I will see
Dialogue: 0,0:51:16.00,0:51:18.00,Default,,0000,0000,0000,,you on Monday
Dialogue: 0,0:51:18.00,0:51:23.00,Default,,0000,0000,0000,,and have a good weekend.