Placeholder Image

字幕列表 影片播放

  • All right, thank you all for volunteering.

  • 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.

All right, thank you all for volunteering.

字幕與單字

影片操作 你可以在這邊進行「影片」的調整,以及「字幕」的顯示

A2 初級

CS50 2019--閱讀5--鏈接列表 (CS50 2019 - Lecture 5 - Linked Lists)

  • 0 0
    林宜悉 發佈於 2021 年 01 月 14 日
影片單字