By Levels

Library

All right, thank you all for volunteering.
 
Current Time 0:00
Duration 5:00
Loaded: 0.00%
 
All right thank you all for volunteering

All right, thank you all for volunteering.

x1.00


Back

Games & Quizzes

Training Mode - Typing
Fill the gaps to the Lyric - Best method
Training Mode - Picking
Pick the correct word to fill in the gap
Fill In The Blank
Find the missing words in a sentence Requires 5 vocabulary annotations
Vocabulary Match
Match the words to the definitions Requires 10 vocabulary annotations

You may need to watch a part of the video to unlock quizzes

Don't forget to Sign In to save your points

Challenge Accomplished

PERFECT HITS +NaN
HITS +NaN
LONGEST STREAK +NaN
TOTAL +
- //

We couldn't find definitions for the word you were looking for.
Or maybe the current language is not supported

  • 00:00

    All right, thank you all for volunteering.
    All right, thank you all for volunteering.

  • 00:01

    Let's go ahead and do this.
    Let's go ahead and do this.

  • 00:02

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

  • 00:05

    So if you could maybe all back up over here just
    So if you could maybe all back up over here just

  • 00:08

    to where we have some available space.
    to where we have some available space.

  • 00:10

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

  • 00:13

    Siobhan was it?
    Siobhan was it?

  • 00:14

    AUDIENCE: [? Siobhana. ?]
    AUDIENCE: [? Siobhana. ?]

  • 00:14

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

  • 00:15

    you want to go ahead and represent list.
    you want to go ahead and represent list.

  • 00:17

    And to represent our actual list, we have--
    And to represent our actual list, we have--

  • 00:21

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

  • 00:25

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

  • 00:28

    represents the linked list itself.
    represents the linked list itself.

  • 00:30

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

  • 00:33

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

  • 00:35

    So you're not pointing at anything.
    So you're not pointing at anything.

  • 00:37

    But you represent list.
    But you represent list.

  • 00:38

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

  • 00:40

    What was the next step?
    What was the next step?

  • 00:41

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

  • 00:49

    what lower level operation to get 2 in there?
    what lower level operation to get 2 in there?

  • 00:52

    What was the first line of code?
    What was the first line of code?

  • 00:53

    AUDIENCE: malloc.
    AUDIENCE: malloc.

  • 00:54

    DAVID MALAN: malloc.
    DAVID MALAN: malloc.

  • 00:55

    So we want to malloc a node for 2.
    So we want to malloc a node for 2.

  • 00:57

    So let's go ahead and malloc.
    So let's go ahead and malloc.

  • 00:58

    OK, come on up.
    OK, come on up.

  • 00:59

    So malloc.
    So malloc.

  • 01:00

    And what's your name again?
    And what's your name again?

  • 01:01

    AUDIENCE: Ethan.
    AUDIENCE: Ethan.

  • 01:01

    DAVID MALAN: Ethan.
    DAVID MALAN: Ethan.

  • 01:01

    OK.
    OK.

  • 01:02

    And what do we need to give Ethan?
    And what do we need to give Ethan?

  • 01:03

    Ethan has two values or two fields.
    Ethan has two values or two fields.

  • 01:06

    The first one is the number 2.
    The first one is the number 2.

  • 01:08

    Thank you.
    Thank you.

  • 01:10

    The next one is a pointer called next.
    The next one is a pointer called next.

  • 01:13

    Now, you're not pointing at anyone else.
    Now, you're not pointing at anyone else.

  • 01:15

    So you'll put it behind your back.
    So you'll put it behind your back.

  • 01:16

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

  • 01:18

    AUDIENCE: Point to--
    AUDIENCE: Point to--

  • 01:19

    DAVID MALAN: Point to?
    DAVID MALAN: Point to?

  • 01:20

    AUDIENCE: 2.
    AUDIENCE: 2.

  • 01:21

    DAVID MALAN: Him, yes, number 2.
    DAVID MALAN: Him, yes, number 2.

  • 01:22

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

  • 01:26

    but the null pointer as well.
    but the null pointer as well.

  • 01:28

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

  • 01:30

    How do we go ahead and do this?
    How do we go ahead and do this?

  • 01:31

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

  • 01:33

    malloc, all right.
    malloc, all right.

  • 01:35

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

  • 01:38

    What do we want to do with your pointer?
    What do we want to do with your pointer?

  • 01:40

    AUDIENCE: Not point it.
    AUDIENCE: Not point it.

  • 01:41

    DAVID MALAN: Not point at anything.
    DAVID MALAN: Not point at anything.

  • 01:43

    Now, it's a little more work.
    Now, it's a little more work.

  • 01:44

    And I need a temporary variable.
    And I need a temporary variable.

  • 01:46

    So I'll play this role.
    So I'll play this role.

  • 01:47

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

  • 01:49

    at in sort of unnaturally this way.
    at in sort of unnaturally this way.

  • 01:51

    That's OK.
    That's OK.

  • 01:51

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

  • 01:54

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

  • 01:56

    You're both pointing at 2.
    You're both pointing at 2.

  • 01:57

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

  • 02:00

    AUDIENCE: If it's greater than.
    AUDIENCE: If it's greater than.

  • 02:01

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

  • 02:03

    So I'm going to check.
    So I'm going to check.

  • 02:04

    Well, 4 is greater than 2.
    Well, 4 is greater than 2.

  • 02:06

    So I'm going to keep going.
    So I'm going to keep going.

  • 02:06

    And your name was Eric?
    And your name was Eric?

  • 02:07

    AUDIENCE: Ethan.
    AUDIENCE: Ethan.

  • 02:08

    DAVID MALAN: Ethan, sorry.
    DAVID MALAN: Ethan, sorry.

  • 02:08

    So, Ethan, what are you pointing at?
    So, Ethan, what are you pointing at?

  • 02:10

    Nothing.
    Nothing.

  • 02:10

    So that's an opportunity.
    So that's an opportunity.

  • 02:11

    There's nothing to his right.
    There's nothing to his right.

  • 02:13

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

  • 02:15

    AUDIENCE: Athena.
    AUDIENCE: Athena.

  • 02:16

    DAVID MALAN: Athena.
    DAVID MALAN: Athena.

  • 02:17

    Also, unnaturally, but that's fine.
    Also, unnaturally, but that's fine.

  • 02:19

    And so now does Athena need to update her pointer?
    And so now does Athena need to update her pointer?

  • 02:22

    No, she's good.
    No, she's good.

  • 02:22

    She represents the end of the list.
    She represents the end of the list.

  • 02:24

    So her pointer can stay behind her back.
    So her pointer can stay behind her back.

  • 02:25

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

  • 02:27

    You want to be our 5?
    You want to be our 5?

  • 02:28

    So now we need a 5.
    So now we need a 5.

  • 02:30

    So we need to hand you the number 5.
    So we need to hand you the number 5.

  • 02:32

    And what's your name again?
    And what's your name again?

  • 02:34

    AUDIENCE: Sarika.
    AUDIENCE: Sarika.

  • 02:34

    DAVID MALAN: Sarika.
    DAVID MALAN: Sarika.

  • 02:35

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

  • 02:37

    She also is going to get a pointer called next.
    She also is going to get a pointer called next.

  • 02:39

    What should Sarika be pointing at?
    What should Sarika be pointing at?

  • 02:41

    AUDIENCE: Nothing.
    AUDIENCE: Nothing.

  • 02:42

    DAVID MALAN: Nothing.
    DAVID MALAN: Nothing.

  • 02:42

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

  • 02:44

    Well, I have to do the same thing.
    Well, I have to do the same thing.

  • 02:46

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

  • 02:48

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

  • 02:51

    which is Ethan.
    which is Ethan.

  • 02:51

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

  • 02:53

    he's actually pointing at someone else.
    he's actually pointing at someone else.

  • 02:55

    So I'm going to follow that.
    So I'm going to follow that.

  • 02:56

    It's still number 4.
    It's still number 4.

  • 02:57

    So I want to keep going.
    So I want to keep going.

  • 02:58

    Oh, wait a minute.
    Oh, wait a minute.

  • 02:58

    Athena is not pointing at anyone.
    Athena is not pointing at anyone.

  • 03:00

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

  • 03:03

    But are you going to change your pointer yet?
    But are you going to change your pointer yet?

  • 03:05

    No.
    No.

  • 03:06

    Now things get a little more interesting.
    Now things get a little more interesting.

  • 03:08

    Could we go ahead and malloc 1?
    Could we go ahead and malloc 1?

  • 03:10

    And what's your name again?
    And what's your name again?

  • 03:11

    AUDIENCE: Emma.
    AUDIENCE: Emma.

  • 03:11

    DAVID MALAN: Emma.
    DAVID MALAN: Emma.

  • 03:12

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

  • 03:14

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

  • 03:18

    And now we have a couple of steps involved here.
    And now we have a couple of steps involved here.

  • 03:21

    What do we want to do first?
    What do we want to do first?

  • 03:25

    What's your proposal?
    What's your proposal?

  • 03:26

    AUDIENCE: Temporary pointer.
    AUDIENCE: Temporary pointer.

  • 03:26

    DAVID MALAN: Temporary pointer.
    DAVID MALAN: Temporary pointer.

  • 03:27

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

  • 03:29

    which is Ethan here.
    which is Ethan here.

  • 03:31

    But I see that 2 is greater than 1.
    But I see that 2 is greater than 1.

  • 03:33

    So what do I actually want to do?
    So what do I actually want to do?

  • 03:34

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

  • 03:37

    you point at number 1?
    you point at number 1?

  • 03:38

    What have we just done wrong?
    What have we just done wrong?

  • 03:39

    We've orphaned everyone else.
    We've orphaned everyone else.

  • 03:41

    And even more visibly now, no one is pointing
    And even more visibly now, no one is pointing

  • 03:43

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

  • 03:47

    to be recovered or free.
    to be recovered or free.

  • 03:48

    So we don't want to do that.
    So we don't want to do that.

  • 03:49

    Undo, Control-Z.
    Undo, Control-Z.

  • 03:50

    What do we want to do instead?
    What do we want to do instead?

  • 03:51

    What's your name again?
    What's your name again?

  • 03:52

    AUDIENCE: Emma.
    AUDIENCE: Emma.

  • 03:53

    DAVID MALAN: Emma.
    DAVID MALAN: Emma.

  • 03:53

    What do you want to point at?
    What do you want to point at?

  • 03:55

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

  • 03:57

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

  • 03:59

    is pointing at, which is equivalent then to Ethan.
    is pointing at, which is equivalent then to Ethan.

  • 04:03

    So go ahead and do that with your--
    So go ahead and do that with your--

  • 04:04

    OK, sort of like Twister now.
    OK, sort of like Twister now.

  • 04:06

    That's OK.
    That's OK.

  • 04:07

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

  • 04:09

    Perfect.
    Perfect.

  • 04:10

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

  • 04:13

    depending on which pointers we want to update.
    depending on which pointers we want to update.

  • 04:15

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

  • 04:17

    And your name was again?
    And your name was again?

  • 04:18

    AUDIENCE: Anurag.
    AUDIENCE: Anurag.

  • 04:18

    DAVID MALAN: Anurag.
    DAVID MALAN: Anurag.

  • 04:19

    So then we have a 3 for you from Brian.
    So then we have a 3 for you from Brian.

  • 04:21

    We have a pointer for you.
    We have a pointer for you.

  • 04:22

    It's initialized initially to null.
    It's initialized initially to null.

  • 04:24

    So you can put that behind your back.
    So you can put that behind your back.

  • 04:25

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

  • 04:29

    1 is smaller.
    1 is smaller.

  • 04:30

    2 is smaller.
    2 is smaller.

  • 04:31

    4 is larger.
    4 is larger.

  • 04:32

    So let's get this right.
    So let's get this right.

  • 04:34

    And who do we want to point at whom first?
    And who do we want to point at whom first?

  • 04:38

    AUDIENCE: 3 points at 4.
    AUDIENCE: 3 points at 4.

  • 04:40

    DAVID MALAN: 3 should point at 4.
    DAVID MALAN: 3 should point at 4.

  • 04:42

    So go ahead and do that.
    So go ahead and do that.

  • 04:43

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

  • 04:46

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

  • 04:49

    Number 3.
    Number 3.

  • 04:50

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

  • 04:53

    We have wonderful souvenirs for each of you.
    We have wonderful souvenirs for each of you.

  • 04:55

    We just need the numbers back.
    We just need the numbers back.

  • 04:55

    Thank you to our volunteers here if we could.
    Thank you to our volunteers here if we could.

All phrase
all for
//
phrase
strongly in favor of.

CS50 2019 - Lecture 5 - Linked Lists

1,953 views

CS50

Video Language:

  • English

Caption Language:

  • English (en)

Accent:

  • English (US)

Speech Time:

98%
  • 4:55 / 5:00

Speech Rate:

  • 247 wpm - Fast

Category:

  • Education

Tags :

Intro:

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

Video Vocabulary

pointing

/ˈpoin(t)iNG/

noun verb

cement or mortar used to fill joints of brickwork or masonry. To indicate something with your finger to others.

initially

/iˈniSH(ə)lē/

adverb

At first; originally.

initialize

/iˈniSHəˌlīz/

verb

set to value or put in condition appropriate to start of operation.

operation

/ˌäpəˈrāSH(ə)n/

noun

Medical procedure involving surgery.

represent

/ˌreprəˈzent/

verb

be entitled to act for someone.

available

/əˈvāləb(ə)l/

adjective

Able to be used at a scheduled time.

rectangle

/ˈrekˌtaNGɡəl/

noun

plane figure with four straight sides and four right angles.

numbers

/ˈnəmbər/

noun other verb

arithmetical value expressed by word, symbol, or figure. Particular songs or dances performed during shows. To put numbers on things.

nothing

/ˈnəTHiNG/

adjective adverb noun pronoun

of no value. not at all. Number or value of zero. Not anything, not a single thing.