DAVID MALAN: So how can we now translate this into more useful code? Not just defining what these structures are, but how do we begin building up linked lists? Well, let me propose that a linked list really begins with just a pointer. And in fact, here we have, thanks to the theater's prop shop, just a null pointer, if you will. I'm going to call this variable list. 

And list is currently pointing to nothing. The arrow will say it's just pointing at the floor, which means it's null. It's not actually pointing at anything useful. 

Suppose I now want to start to begin to allocate a linked list with three numbers, 1, 2, and 3. Well, how am I going to do this? Well, at the moment, the only thing that exists in my program is going to be this variable called list. There's no array in this story. That was in week two. Today's all about linked lists. 

So how do I get myself a wooden block that represents one, another wooden block that represents two, and a third that represents three? Well, I need to use our new friend from last week, malloc. Recall that malloc allows you to allocate memory, as much memory as you might want, so long as you tell it the size of that thing. 

So frankly, I think what we could do ultimately today is use malloc to allocate dynamically one struct, and put the number one in it; another struct, put the number two on it; another struct, put the number three in it. And then use these playful arrows here to actually stitch them together, having one point to the other. So thankfully the prop shop has wonderfully created a whole bunch of these for us. 

Let me go ahead and malloc a very heavy node that has room for two values. And you'll see it has a room for a number and a next pointer. So the number I'm going to first install here is going to be the number one, for instance. And I'm going to leave its pointer as just pointing at the ground, indicating that this is a null pointer. It's not actually pointing at anything else. 

But now that I'm starting to instantiate, that is create this list, now I'm going to do something like this and say that, all right, my variable called list, whose purpose in life is to keep track of where this list is in memory, I'm going to connect one to the other by actually having this variable point at this node. When it comes time, then, to allocate another node, I want to insert into this linked list. Back in the world of arrays, I might have to allocate a new chunk of memory, copy this value over into the new values. 

I don't have to do that. In the world of linked lists, I just call malloc for a second time and say, give me another chunk of memory big enough to fit a node. Thankfully, from the prop shop, we have another one of these. So let me go ahead and malloc another node. Here, at the moment, there's nothing in it, just these placeholders. So it's garbage values, if you will. I don't know what's there until I actually say that the number shall be number two. 

And then I go over to my linked list, whose variable name is list. And I want to insert this thing. So I follow the arrow. I then point the next field of this node at this node here. So now I have a linked list of size two. 

There's three things in the picture. But this is just a simple variable. This is a pointer that's pointing at the actual node, which in turn is pointing at an actual other node. Now, suppose I want to insert the number three into this linked list. Recall that malloc is powerful and that it takes memory from wherever it's available, the so-called heap from your computer. 

And that means, by definition, that it might not be contiguous. The next number might not actually be here metaphorically in the computer's memory. It might be way over there. So that might indeed happen. 

The third time I call malloc now and allocate a third node, it might not be available anywhere in the computer's memory except for way over here. And that's fine. It doesn't have to be contiguous, as it did in the world of our arrays. I can now put the number three in its place. But if I want to keep a pointer to that node so that all of these things are stitched together, I can start at the beginning. I follow the arrows. I follow the arrows. 

And now if I want to remember where that one is, I'm going to have to connect these things. And so now that pointer needs to point at this block here. And this visual is very much deliberate. These nodes can be anywhere in the computer's memory. They're not necessarily going to be contiguous. 

The downside of that is that you cannot rely on binary search, our friend from, like, week zero onward. Binary search was amazing in that its big O of log n. You can find stuff way faster than big O of n. That was the whole point of even the phonebook example in the very first week. 

But the upside of this approach is that you don't have to actually keep allocating and copying more memory and all of your values any time you want to resize this thing. And I'm a little embarrassed to admit that I'm out of breath, for some reason, just malloc-ing nodes. Here. But the point is using malloc and building out the structure does come at some price. It's exhausting, frankly. But it's also going to spread things out in memory. 

But you have this dynamism. And honestly, if you are the Twitters of the world, the Googles of the world, we have lots and lots of data. It's going to kill you performance wise to have to copy all of your data from one location into another, as Santiago originally proposed as a solution to the array. So using these dynamic data structures, like a linked list, where you allocate more space wherever it's available, and you somehow remember where that is by stitching things together, as with these physical pointers, is really the state of the art.