Let's go ahead and do this.

You for the moment represent a heap of memory, if you will.

So if you could maybe all back up over here just

to where we have some available space.

We're going to need one of you to represent the list.

Siobhan was it?

AUDIENCE: [? Siobhana. ?]

DAVID MALAN: [? Siobhana, ?] come on up. [? Siobhana, ?] do

you want to go ahead and represent list.

And to represent our actual list, we have--

or Brian-- yeah, we have a name tag, hello, my name is list.

So you're going to represent the rectangle on the left that

represents the linked list itself.

And now initially we're going to go ahead initialize you to null.

So you can just go ahead and put that behind your back.

So you're not pointing at anything.

But you represent list.

And there's nothing in the list, no numbers in the list.

What was the next step?

If the goal at hand is to insert 2, 4, 5, 1, 3, we want to do what first,

what lower level operation to get 2 in there?

What was the first line of code?

AUDIENCE: malloc.

DAVID MALAN: malloc.

So we want to malloc a node for 2.

So let's go ahead and malloc.

OK, come on up.

So malloc.

And what's your name again?

AUDIENCE: Ethan.

DAVID MALAN: Ethan.

OK.

And what do we need to give Ethan?

Ethan has two values or two fields.

The first one is the number 2.

Thank you.

The next one is a pointer called next.

Now, you're not pointing at anyone else.

So you'll put it behind your back.

And now what do we want to do with? [? Siobhana, ?] what do we have to do?

AUDIENCE: Point to--

DAVID MALAN: Point to?

AUDIENCE: 2.

DAVID MALAN: Him, yes, number 2.

OK, so this now represents the picture where we have list here, 2 here,

but the null pointer as well.

All right next we wanted to add 4 to the list.

How do we go ahead and do this?

Well, with 4, we're going to go ahead and malloc.

malloc, all right.

And now, Brian has a lovely number 4 for you and a pointer.

What do we want to do with your pointer?

AUDIENCE: Not point it.

DAVID MALAN: Not point at anything.

Now, it's a little more work.

And I need a temporary variable.

So I'll play this role.

I'm going to go ahead and point at wherever Siobhana is pointing

at in sort of unnaturally this way.

That's OK.

We couldn't get hands that point the other way physically.

So we're going to point at the same thing here.

You're both pointing at 2.

And what am I looking for in order to decide where to put 4?

AUDIENCE: If it's greater than.

DAVID MALAN: If it's greater than some value.

So I'm going to check.

Well, 4 is greater than 2.

So I'm going to keep going.

And your name was Eric?

AUDIENCE: Ethan.

DAVID MALAN: Ethan, sorry.

So, Ethan, what are you pointing at?

Nothing.

So that's an opportunity.

There's nothing to his right.

So let me go ahead and have Ethan point at-- what's you're name again?

AUDIENCE: Athena.

DAVID MALAN: Athena.

Also, unnaturally, but that's fine.

And so now does Athena need to update her pointer?

No, she's good.

She represents the end of the list.

So her pointer can stay behind her back.

All right, let's go ahead and malloc 5.

You want to be our 5?

So now we need a 5.

So we need to hand you the number 5.

And what's your name again?

AUDIENCE: Sarika.

DAVID MALAN: Sarika.

All right, so Sarika's holding the number 5.

She also is going to get a pointer called next.

What should Sarika be pointing at?

AUDIENCE: Nothing.

DAVID MALAN: Nothing.

And now how to do I insert her into the right place?

Well, I have to do the same thing.

So I'm going to get involved again and be a temporary variable.

I'm going to point at the same thing [? Siobhana ?] is pointing out,

which is Ethan.

I'm going to follow this and see, ooh, wait a minute,

he's actually pointing at someone else.

So I'm going to follow that.

It's still number 4.

So I want to keep going.

Oh, wait a minute.

Athena is not pointing at anyone.

This is an opportunity now to have Athena point at 5 and voila.

But are you going to change your pointer yet?

No.

Now things get a little more interesting.

Could we go ahead and malloc 1?

And what's your name again?

AUDIENCE: Emma.

DAVID MALAN: Emma.

OK, Emma, we have the number 1 for you from Brian.

You have a pointer, which should be initialized as well to null.

And now we have a couple of steps involved here.

What do we want to do first?

What's your proposal?

AUDIENCE: Temporary pointer.

DAVID MALAN: Temporary pointer.

So I'm going to point at the same things [? Siobhana ?] is pointing at,

which is Ethan here.

But I see that 2 is greater than 1.

So what do I actually want to do?

Well, let me incorrectly for a moment-- [? Siobhana, ?] could

you point at number 1?

What have we just done wrong?

We've orphaned everyone else.

And even more visibly now, no one is pointing

at Ethan or beyond, which means we've just leaked that memory, never

to be recovered or free.

So we don't want to do that.

Undo, Control-Z.

What do we want to do instead?

What's your name again?

AUDIENCE: Emma.

DAVID MALAN: Emma.

What do you want to point at?

AUDIENCE: I want to point at [? Siobhana. ?]

DAVID MALAN: At that the same thing, [? Siobhana ?]

is pointing at, which is equivalent then to Ethan.

So go ahead and do that with your--

OK, sort of like Twister now.

That's OK.

And then [? Siobhana, ?] what I do want to point at?

Perfect.

So again a bunch of steps involved, but it really is just two or three steps

depending on which pointers we want to update.

And then lastly, let's go head to malloc 3.

And your name was again?

AUDIENCE: Anurag.

DAVID MALAN: Anurag.

So then we have a 3 for you from Brian.

We have a pointer for you.

It's initialized initially to null.

So you can put that behind your back.

I'm going to point at the same thing as [? Siobhana. ?] And here we go.

1 is smaller.

2 is smaller.

4 is larger.

So let's get this right.

And who do we want to point at whom first?

AUDIENCE: 3 points at 4.

DAVID MALAN: 3 should point at 4.

So go ahead and do that.

And you can step a little forward just so it looks a little less awkward.

And then lastly, big finale, Ethan, who do you want to point at?

Number 3.

And thankfully, all these steps later, we have a linked list.

We have wonderful souvenirs for each of you.

We just need the numbers back.

Thank you to our volunteers here if we could.