DAVID MALAN: All right, this is CS50.

And this is our look today at data structures.

You'll recall last week that we gave ourselves

a few new ingredients and some new syntax in C.

We introduced pointers, the ability to address chunks of memory

by actual addresses--

0, 1, 2, 3 and on up.

And we introduced the star notation and a few other functions,

malloc among them, free among them, so that you can actually

manage your computer's memory.

Just to hammer this home, let's take a look

at just this small example that from the outset is buggy.

This code is buggy.

And we'll see in just a moment why.

But let's just walk through it step by step.

This first line highlighted in yellow in English

is doing what as you understand it now?

If you're a little rusty since last week, what's that first line of code

doing in English?

Anything?

Yeah.

AUDIENCE: It's creating a point to an int named x.

DAVID MALAN: Perfect.

It's creating a pointer to an integer and calling

that pointer or that variable x.

And let me propose that the next line is doing the same thing giving us

another pointer to an integer but this time calling it y.

The third line of code, someone else, what's

happening in English with this line here?

Yeah.

AUDIENCE: It's creates a memory of size of int and assigns it to x,

but it's more difficult to execute if it's not a pointer, I don't know.

DAVID MALAN: This is not the bug.

But the first part is correct.

malloc is the function we introduced last week

that allocates memory for you.

It takes one argument, the number of bytes that you want to allocate.

Even if you don't recall how many bytes you need for an integer,

you can call this other operator, sizeof,

that we saw briefly last week, that will return, in this case, 4 most likely

depending on the computer that you're on.

So this is saying, hey, computer give me 4 bytes of memory.

And it returns that chunk of memory to conventionally

by way of the first address, so ox something,

wherever those 4 bytes happen to star.

And then it stores that address in x, which is in fact OK,

because as you noted initially, x is in fact a pointer.

That is an address.

So all this is doing is it's declaring a variable called

x and storing in it ultimately the address

of a legitimate chunk of memory.

You wouldn't typically allocate an int like this.

You would allocate an int with just int and semicolon just like in week 1.

But now that we have the ability to allocate addresses and allocate memory,

you could achieve the same idea here.

This line here now, the fourth line of code, says what in English?

Star x equals 42 semicolon.

What's going on there?

Yeah.

AUDIENCE: It goes to the address in the x and then sets it to 42.

DAVID MALAN: Good goes to the address in x and sets it to 42.

So the star operator is the dereference operator,

which is a fancy way of saying go to that address.

And what do you want to do?

Well, per week 1 when we discussed the assignment operator,

it just says put the number 42 there.

So wherever malloc found 4 bytes of available memory for me,

this fourth line of code says, go there and put the number 42

by putting the appropriate zeros and ones.

This last line here--

and here's the bug, if we finally reveal it here--

this line is buggy.

Does anyone see why?

Yeah, over here.

AUDIENCE: You haven't allocated memory for that variable yet.

DAVID MALAN: Exactly.

I haven't allocated memory for that variable yet.

And because up here I've just said int star y semicolon.

You can only assume safely that has some garbage value, some unknown value,

maybe remnants from some other part of the program,

that might not necessarily be true here at the beginning of the program.

But for safety's sake assume that if you don't give a variable

a value, who knows what it contains.

It's got some bogus address, such that if you

say star y go to that bogus address something bad is going to happen.

And maybe you experienced this already in P Set 4 or prior,

some kind of memory problem with your code,

or a segmentation fault or seg fault, bad things

happen when you go to addresses that don't exist

or that you don't even know where they are.

So this line of code is bad.

But we can do a little better.

What if instead I do something like this?

I actually assign to y x.

So that just says put in y the same address that's in x.

And then with this last line of code, what if I now say star y equals 13?

What is that-- you're nodding your head.

What am I doing correctly now?

AUDIENCE: Now there's memory allocated for y.

DAVID MALAN: Good.

Now, there's memory allocated for y.

So you're saying go to that address and put 13 there.

However, what did we just need to the 42, just to be clear?

We clobbered it.

We overwrote it with the 13.

Because if x and y are the same address, both this says go to that address

and put 42 there, but then two lines later, we say, no, no, no,

go there and put 13 there instead.

But long story short, bad things happen when you don't necessarily

anticipate what is in memory and you don't allocate it yourself,

so thanks to one of our friends at Stanford,

allow us to take a moment here to hit Play on a short film, a claymation

if you will, that paints the same picture

in a more memorable way perhaps.

If we could dim the lights.

[VIDEO PLAYBACK]

NARRATOR: Hey, Binky, wake up.

It's time for pointer fun.

BINKY: What's that?

Learn about pointers?

Oh, goody.

NARRATOR: Well, to get started, I guess we're going to need a couple pointers.

BINKY: OK, this code allocates two pointers, which can point to integers.

NARRATOR: OK, well, I see the two pointers.

But they don't seem to be pointing to anything.

BINKY: That's right, initially pointers don't point to anything.

The things they point to are call pointees.

And setting them up is a separate step.

NARRATOR: Oh, right, right.

I knew that.

The pointees are separate.

So how do you allocate a pointee?

BINKY: OK, well, this code allocates a new integer pointee.

And this part sets x to point to it.

NARRATOR: Hey, that looks better.

So make it do something.

BINKY: OK, I'll dereference the pointer x to store the number

42 into its pointee.

For this trick, I'll need my magic wand of y dereferencing.

NARRATOR: Your magic wand of dereferencing.

That-- that's great.

BINKY: This is what the code looks like.

I'll just set up the number.

And--

NARRATOR: Hey, look, there it goes.

So doing a dereference on x, follows the arrow

to access its pointee, in this case, the store 42 in there.

Hey, try using it to store the number 13 through the other pointer, y.

BINKY: OK.

I'll just go over here to y and get the number 13 set up

and then take the wand of dereferencing and just--

[BUZZER SOUND] oh.

NARRATOR: Oh, hey, that didn't work.

Say, Binky, I don't think dereferencing y is a good idea, because, you know,

setting up the pointee is a separate step.

And I don't think we ever did it.

BINKY: Oh, good point.

NARRATOR: Yeah, we allocated the pointer y.

But we never set it to point to a pointee.

BINKY: Mm, very observant.

NARRATOR: Hey, you're looking good there, Binky.

Can you fix it so that y points to the same pointee as x?

BINKY: Sure.

I'll use my magic wand of pointer assignment.

NARRATOR: Is that going to be a problem like before?

BINKY: No, this doesn't touch the pointees.

It just changes one pointer to point to the same thing as another.

NARRATOR: Oh, I see.

Now y points to the same place as x.

So, wait, now y is fixed.

It has a pointee.

So you can try the wand of dereferencing again to send the 13 over.

BINKY: Uh-- OK, here goes.

NARRATOR: Hey, look at that.

Now dereferencing works on y.

And because the pointers are sharing that one pointee, they both see the 13.

BINKY: Yeah, sharing, whatever.

So are we going to switch places now?

NARRATOR: Oh, look, we're out of time.

BINKY: But--

[END PLAYBACK]

DAVID MALAN: All right, so now that we do

have this power of pointers and addresses

where we have low level access to the computer's memory,

we can actually solve problems a lot more powerfully

and in a lot more interesting ways.

But first, let's motivate some of these problems.

So back in Week 2, we introduced arrays, which

was the first of our data structures, if you will.

Before then in Week 1, all we had was variables for things

like ints and chars and floats and so forth.

In Week 2, we introduced arrays, which meant

you could store two ints altogether or three or 10 or 100.

So you can kind of encapsulate lots of data together.

So unfortunately, though, arrays aren't quite as powerful as might be ideal.

So, for instance, if we have an array with size 3 and we actually want to go

ahead and store three values in it-- one, two, three--

suppose that we actually want to now store a fourth value,

but we didn't anticipate that from the get go.

Recall after all that with arrays you have to declare their size upfront.

So you've got to hard code the number 3 or a variable containing the number 3.

But suppose that we want to store the number 4.

You might think that, well, just give me another box

of memory just to the right of the number 3,

so that I can keep all of my numbers together.

But unfortunately, per last week, that's not really

a reliable assumption, because in the context

of the rest of your computer's memory, that 1, 2, 3,

might be here surrounded by other bytes.

And per last week those bytes might be mostly filled with other data

from some other parts of your program.

And yet you would think that in seeing that 1, 2, 3

is kind of painted into this corner, so to speak,

that there's just no room for the number 4,

and therefore you can't add the fourth number to your array,

is there a solution visibly to this problem nonetheless?

Where else could we put it?

Yeah.

AUDIENCE: Move it to off of other memory.

DAVID MALAN: Say that a little louder.

AUDIENCE: We can move it off to other memory.

DAVID MALAN: Yeah, so maybe we can move it off to other memory.

So there's a lot of EMMAs in my memory per last week, but there is still,

it would seem, based on this picture, some unused memory.

So maybe we could resize our array, grow it, not by just moving all of the EMMAs

because frankly that would seem to take a lot of time

if we had to shift all of these characters,

why don't we just relocate the 1, 2, 3 down here,

and that gives us an extra space for at least a number 4.

So indeed even if you're using arrays, you

can achieve this outcome by actually moving memory around.

But consider what's involved in that.

So if you've got our old array at top left,

and we've got our new array at bottom right, that is of size 4.