CS50 2021 in HDR - Lecture 5 - Data Structures

This is CS50, Harvard University's Introduction to the intellectual enterprises of computer science and the art of programming. Enroll for free at cs50.edx.org/. Slides, source code, and more at cs50.harvard.edu/x. Playlist at • CS50 Lectures 2021 (HDR) .
TABLE OF CONTENTS
00:00:00 - Introduction
00:01:17 - Data Structures
00:02:25 - Arrays
00:09:41 - Arrays in C
00:23:50 - Realloc
00:26:34 - Arrow Notation
00:28:58 - Linked Lists
00:43:19 - Building a Linked List
00:51:29 - Linked Lists in C
01:10:09 - Linked List Demonstration
01:17:45 - Linked List Time Complexities
01:23:20 - Binary Search Trees
01:30:52 - tree.c
01:37:17 - Searching a Binary Search Tree
01:43:10 - Binary Search Tree Time Complexities
01:44:00 - Hash Tables
01:50:33 - Hash Functions
01:51:40 - Hashing Demonstration
01:53:25 - Buckets and Collisions
01:57:20 - Tries
02:04:04 - Stacks and Queues
02:08:23 - Jack Learns the Facts
02:12:14 - This was CS50
***
This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming.
***
HOW TO SUBSCRIBE
kzbin.info_c...
HOW TO TAKE CS50
edX: cs50.edx.org/
Harvard Extension School: cs50.harvard.edu/extension
Harvard Summer School: cs50.harvard.edu/summer
OpenCourseWare: cs50.harvard.edu/x
HOW TO JOIN CS50 COMMUNITIES
Discord: / discord
Ed: cs50.harvard.edu/x/ed
Facebook Group: / cs50
Faceboook Page: / cs50
GitHub: github.com/cs50
Gitter: gitter.im/cs50/x
Instagram: / cs50
LinkedIn Group: / 7437240
LinkedIn Page: / cs50
Medium: / cs50
Quora: www.quora.com/topic/CS50
Reddit: / cs50
Slack: cs50.edx.org/slack
Snapchat: / cs50
SoundCloud: / cs50
Stack Exchange: cs50.stackexchange.com/
TikTok: / cs50
Twitter: / cs50
KZbin: / cs50
HOW TO FOLLOW DAVID J. MALAN
Facebook: / dmalan
GitHub: github.com/dmalan
Instagram: / davidjmalan
LinkedIn: / malan
Quora: www.quora.com/profile/David-J...
TikTok: / davidjmalan
Twitter: / davidjmalan
***
CS50 SHOP
cs50.harvardshop.com/
***
LICENSE
CC BY-NC-SA 4.0
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International Public License
creativecommons.org/licenses/...
David J. Malan
cs.harvard.edu/malan
[e-mail]

[@dluca182]

my brains goes in segmentation fault like 4-5 times every lesson on pointers...

[@sankalpkumar4490]

Doing problem sets is the only way to understand pointers. When you figure out the solution to a certain problem your are stuck is a pointer. Thats the satisfaction that makes you feel like you understand pointers.

[@novacoax]

nice one 🤣

[@sayori3939]

That's because you forgot to set your brain to NULL before watching the video :3

[@Technoph1le]

@@sayori3939 😂😂😂🤣🤣

[@Technoph1le]

🤣🤣🤣🤣🤣😂😂👍

[@mlv60]

man, watching these series as a self-taught web dev, all these commonly used algorithms and data structures are making a lot more sense, thanks for making the lectures public and free for everyone Harvard && CS50 team

[@hammadazhar4598]

I will never forget the chills of starting and finishing a lecture.

[@RandomGuy-hv7tb]

Same ❤️

[@marvinmoltgen7349]

Especially the great intro and always the ".. and this is CS50" at the end.

[@MitchellRoman97]

Every time I just have a giant smile on my face

[@VicoSotto.]

and the music right?? right!??

[@kvon2108]

The cello is a magical instrument

[@hilsCYBER]

SIR, you are the best lecturer I have personally encountered!!!

[@MrX-nc8cm]

Im not tired of repeating this!

[@codingyoshi]

thank you

[@novacoax]

I agree

[@mengvang396]

He is a Harvard professor.

[@ryadmesbah7281]

Fact

[@epicgameryt4052]

Goosebumps whenever I hear: 'This is CS50!'

[@AriaHarmony]

2:03:37 the Economist Thomas Sowell said "There are no solutions, only trade-offs", memory and time complexity in CS seems like a prime example of this.

[@jathebest2835]

Surely, yes and besides it exists anywhere in our lives. For example, if you want to be free, you don't need to have a job but you suffer the loss of money. However, if you only follow money by working endlessly, you can enjoy affluence of many things but actually you don't have enough time to enjoy all of them...

[@AbhishekKumar-yu1mf]

This is the most innovative and interesting way to teach data structures I have ever seen yet. Thank you, sir.

[@ReyPeon]

The teacher, he is amazing! He leaves me wanting for more. Thank you so much, and every person that make this possible!

[@AetherCS2]

Yoo I never look through my subscriptions on KZbin but I'm glad I did. Definitely going to watch this since it would be a great headstart for next semester

[@SG-J]

Completed week 4 on 2021, 2022 here we go!

[@parsian_korous]

This course is the best CS code I've ever seen.

[@MEBAbhishekKumar]

Best lecture series ever encountered. Thanks CS50....!!!

[@samiulbasir8456]

The best teacher ever !!!!!!!!!!!

[@TJTheEpicGamerGuy]

Amazing! CS50 is truly the best!

[@shariarnurnahin1703]

Watch the 2020 version of this lecture too, if you are having trouble with the linked list real life visualization. Students pointing to each other felt somewhat not so clear as compared to previous years Box/Tools visualization- which I felt was somewhat easy to understand.

[@johnafariogun1076]

This was brilliant, interactive and enlightening. Thank you very much for this wonderful lesson

[@Ak-pr1wg]

Learnt BST in college. Understood it today Thank you

[@ryadmesbah7281]

Much of respect for J.David , thnks boss

[@billionairesbio]

I wish i had a teacher like you while was in school life...

[@Param3021]

Completed more than half in 2021. Only Abstract data structures part is left, which I'll do it now in 2022.

[@YuvrajSingh-sm1rc]

yes me too . 1st sem college workload

[@leetchoy]

Thanks for the course!

[@sayori3939]

I'm glad i quit the lecture at the linked list part when i wasn't understanding anything (I took a break, watched week 4's short on pointers, stack etc) then i was able to understand everything including the loop to iterate the list

[@ItsSchwifty]

finally finished this omg my brain

[@dluca182]

me: " ok, finally, it took me long but i kinda got the theory of this-" david: "ok but there's even another data structure that..." damn.

[@sayori3939]

LoL maybe that's the time you would call his number from week 3? :3

[@Blezerker]

Never thought i'd wake up and have my name featured on a cs50 video :D

[@iftekhar035]

Awsome experience...!🥰🥰🥰

[@abdelrahmansamy5792]

what an epic ending!

[@harikrishna3069]

1:47:10 I like how they used Harry Potter reference to explain the hash table 😁

[@omaradel7867]

Start first of december 2021 and now stuck in pset5 data structures

[@not_amanullah]

thanks ❤

[@user-xq6cl2si2e]

Honestly speaking, i am getting lost after he started to use pointers. Till the third class, i managed to understand but, this one? Uhhhhh I am lost between those pointers and pointees. So frustrating. Maybe i should watch this video again and again repeatedly.

[@user-xq6cl2si2e]

I finally get the concept of freeing the heap, after i watched the previous lesson and this one repeatedly and also did some research on google. This concept was the most confusing one for me so far, but i atlast understand. If there is somebody who is at the same position where i was, am and willbe, just don't give up. Keep learning even it is frustrating. Nobody knows perfectly at the first time.

[@darkeyedwitch]

For anyone else lost, remember to watch shorts on the CS50 site that are included in week 4. Up until that point I was able to follow along without watching the shorts, but for that week the shorts were very important because they dug deeper into the concepts than the main lecture did.

[@manuraghav4500]

@@darkeyedwitch Yea dont overlook the shorts...they are super underrated

[@riflkiller]

Does this playlist have all the actual lectures? David keeps talking about previously mentioning malloc and the "free" function from the previous week, but I only recall him mentioning malloc and not going into it ever, this lecture makes it seem like there was some coding involving malloc already in the previous lectures, but I've watched all four previous lectures, and I don't recall that happening. Am I missing something or are this videos just specific lectures from the entire course?

[@YuvrajSingh-sm1rc]

I guess i am in love with sir

[@Sam-gq1bw]

this is how computer science should be taught in schools.

[@ATOMiiCChicken]

Honestly I took ICT gcse and he just stuck us on scratch and that was the end. Now I'm 25 Ive started this and wish I did an A level or degree in computer science it's so interesting

[@Sam-gq1bw]

@@ATOMiiCChicken Goodluck luck dear and happy learning!

[@ankithans8693]

Why do we use Malloc for linked lists, I mean what’s the point if we are freeing the space in the end anyways, why not just use stack memory instead by not using malloc?

[@varunnayyar3138]

1:24:00 personal bookmark

[@vishalgupta7522]

this lecture is damn difficult i cant understand linked list

[@ricardocorrea9398]

its been 3 months now... do u understand now???

[@vishalgupta7522]

@@ricardocorrea9398 now I am in 2 semester I am learning linked list in data structure and algorithm

[@ricardocorrea9398]

@@vishalgupta7522 im proud of you buddy

[@vishalgupta7522]

@@ricardocorrea9398 thanks

[@sayori3939]

But one thing i don't understand is, maintainable code is something that's always talked about and in the week 3 i believe, he talked about how easy it is to mess up if you used 2 arrays with no relationship with each other, but this one right here isn't something that really messes up everything, like imagine having to keep track of all this and if something went wrong having to figure out where you screwed up, would the extra time to use a "relloc" malloc etc be that harmful to make you risk something like this? I know it's faster but it really felt like the true reason people hate pointers and memory management

[@sayori3939]

Omg what is that binary tree atrocity but it works incredibly well with the binary search :3

[@ethanyen30]

can the buckets of a hash table be in the form of a linked list as well. like what if i want to add another bucket.

[@sankalpkumar4490]

Good Observation. Even I wonder now.

[@aracari2]

You will then lose the speed benefits of the hash table, as you cannot jump directly to a specific place. Instead you will have created an inefficiently laid out variation on a binary tree

[@WicCaesar]

At 54:30, David says it suffices to free list, that is equivalent to n. Why not free n instead, since it's the original malloc variable? What if other node variables had been created and similarly equaled to n, by freeing one of them would all others be freed as well?

[@DavidTastyToad]

In line 26 n was assigned to list, after which both contain the same address. But in line 29 the return value of malloc - address of newly allocated memory, or NULL on allocation failure - is assigned to n. Therefore n and list contain different addresses after line 29. Since the free(list) is in a conditional block if (n == NULL) - malloc failed and n contains NULL - you have to free the original list element by free(list). Using free(n) at this point would not work since n contains NULL.

[@joaoamadeu3659]

does anybody know the music intro?

[@teli4181]

There's only one thing that confuses me in that linked list code.... Why use the temporary *n for allocating new nodes? Can't you just do it directly like node *list = malloc(....); And then list->next = malloc(....); list->next->next = malloc(....); I understand why using temp is necessary for freeing memory at the end (so you can still access and free the next node after you free current one), but is it really necessary for initializing? (without a loop)

[@teli4181]

Update: I tested it, and turns out it works just fine without temps. David probably wanted us to get used to using a temp, because in real life applications we will always construct linked lists using a loop... He didn't mention that tho, so idk

[@abrahamcheung]

You can do that, but you have to make sure that list->next !== NULL or risk losing information. I think he's trying to do it for clarity - in that you get in the habit of first creating a new temporary node THEN making the last node of the list to point to this temporary node (which would be used in adding new nodes and freeing them), rather than malloc()ing the next pointer directly (as you suggested).

[@harshprateek1391]

My brain officially crash anywhere linked list showing up. Is it just me or is it actually hard? I mean what is the point of making a linked list when we can use calloc for contiguos memory location.

[@bikdigdaddy]

well yes, linked list is hard, learning it is a coping mechanism. and well, we need linked list so we can store elements anywhere in the main memory. if you use arrays, then the size is limited, and to add an element to the 1st, you'll have to move each element to incorporate the space for the new element. but using linked list, you can do some address changes and boom, with just 1 major step, you can add element.

[@_Gubi_]

Could someone explain what return 1 does on line 50 1:33:44 (as compared to return 0, for example)? I forgot and going back to where he explained it would be tedious. Thanks!

[@lemonade2196]

return 1 basically tells you something went wrong in the code you wrote, while return 0 means it ran successfully. in our code the if statement checks whether or not n has some garbage value stored in it and if it does, the program stops and returns 1, to signify that something went wrong. i think. hehe 😅

[@ludo3941]

@@lemonade2196 that's about it. When everything goes right in our main function it should return 0, when something goes wrong it should return a non-zero value. If I'm not wrong, it isn't checking for garbage values but rather if we managed to allocate space in the heap properly. The instructor says it a lot of times that we're checking if we have enough memory for the allocation, if it doesn't the program should quit (e.g. 16:23).

[@babulo563]

Can anyone tell me which video has big and small o notations ? It'll be very helpful. thank you.

[@MarkoRely]

Week 3

[@babulo563]

@@MarkoRely thanks man. !

[@bsykesbeats4013]

I've heard that at Microsoft (and other companies) you will be fired if you use recursion, because there is too much possibility of stack overflow (if n is a large number). So, if that is the case, how would you ever use a binary search tree at a real company? Or do most companies not use binary search trees because of this?

[@OfficialSombrero]

Maybe. But I heard you couldn't be fired for writing buggy code unless its in your contract/agreement? Where did you hear that

[@bsykesbeats4013]

@@OfficialSombrero my uncle who worked for Microsoft in the 90s and early 2000s. Its not so much getting fired for writing buggy code, it's more they have a strict rule against recursion and if u can't follow their rules, u gotta go...But I still don't totally understand how they work around using recursion for certain things.

[@bsykesbeats4013]

@@OfficialSombrero yeah I'm assuming the no recursion is in their agreement.

[@OfficialSombrero]

@@bsykesbeats4013 oh well good thing this is just an entry level CS class. I'm sure a lot has changed since then. Hope I can land a nice job like that. Would be fun and then you can pretty much work anywhere else once you have a big company like that on your resume.

[@mobai123]

Maybe they use hash table or something like that?

[@ajay4319]

Lecture 5 completed on 13/06/23.

[@sayori3939]

Moral of the video: create a big enough array/chunk of memory or suffer the consequences to resize it LOL

[@BigBoss-rh8mz]

i wish it were that easy, there are times where you don't know much memory you will need until runtime, and asking for a huge chunk of memory that you don't end up using is pretty inefficient.

[@sayori3939]

@@BigBoss-rh8mz idk man seems like java to me

[@STk0614]

Doubt, why couldn't we just say node *list = malloc(sizeof(node))? Why is there a need to create a temporary variable?

[@sayori3939]

If you're talking about the n pointer I think he did that because that would mean he would write "list->next" fewer times, if you're talking about yhe for loop "tmp" he needs to do that or else the compiler is gonna complain about "shadowing" variables i think About the while loop one, it's like a ninja move, if you free "list" you don't have acess the the node adresses, but that's what tmp is for, keeping the adress of the next list, then "current list" is freed, and the now empty list pointer, is assigned to the next "list"( now that i write it, list a confusing name since ot gives an idea of a lot of things together but it's just the pointer of a node which "happens" to have a pointer to another node) but keep in mind a "list" only points to one node at a time with the whole loop thing in every iteration the list pointer is set to another node with the list = tmp untill it's the last node which has a null pointer then the pointer list is set to null since tmp is null at this certain iteration then the loop ends, and that's why you don't need to free list again since it has been assigned to NULL at the last loop iteration

[@DavidTastyToad]

For adding the first element, what you wrote makes sense, but temporary variable n might be better for consistency in that example program - initializing an element always looks the same (using n, check if n == NULL, n->number and n->next). You could also not use the temporary variable at all, but then you would have to keep using list->next... or list->next->next... on almost every line.

[@docmalc47]

"SEGFAULT"

[@raicyceprine8953]

22:10 they are speaking english but I don't understand a thing 40:28 integers have 4 bytes, pointers have 8 bytes that's true for 32 bit system but 64 bit system prolly makes everthing atleast 8 bytes i don't understand anything at all .. using data structure -> yes ..{ int number struct node *next } -> no .. using that defined function then including a * which might be a dereference -> no .. safety method(if conditional, == NULL, return value of 1) -> no .. malloc(sizeof(node)) -> yes .. n == NULL; -> no .. free(list); - no .. free(list->next); - no .. lastly, i don't understand how that code is the transaltion of that pseudocode, it's so counter intuitive im already at 55 mins 😔 56:25 isn't the student's answer right though?? hahaha his answer and the professor's answer feels the same for me 1:07:22 so far, ito lang nagets ko😭😭😭 1:30:54 yo suddenly i'm understanding eveything from binary search tree. 👁👄👁 iwas completely having a hard time understanding everything else before this timestamp. i would watch only 5 mins then break cause i took lots of notes within 5 mins and im tired hahah 1:52:21 just realized this is a perfect set up for teaching. well-planned and clean and you wouldn't ask for more as if they prepared their whole lives just to have the best teaching environment. harvard is just something else and it's super cool. glad to have an opportunity to these classes for free here in youtube

[@faizannazir5596]

Want to attend these classes physically 🥲

[@immanuelkantholz9033]

I'm honestly thankful that I'm able to pause the lecture if needed. :D

[@N1GHTW4TCH]

Shouldn't linked lists be called linked arrays? I mean, they're technically arrays, just not stored back to back (thus linked) Idk, just makes more sense to me I guess 😂

[@amitbikramroy9099]

Done 23Nov

[@jamesedwards5668]

I think you shoukd explain stacks using magic the gatherings 'stack' ... example.. I attack.. in response to your attack I cast a lightning bolt to kill your creature.. in response to your lightning bolt I cast boomerang to return my creature to my hand ... in response to your boomerang I cast swords to plowshears removing your creature from the game ... swords resolves first creature gets removed ... so the boomerang fizzles.. then the lightning bolt fizzles.. and now you have no attacking creature.. so attack phase ends

[@jamesedwards5668]

A stack could be useful as in magic .. if you have an environment where you have things reacting to input. And you need to resolve them in reverse order... or.. explain that it if it doesn't matter what tray you receive as long as it's clean.. stacks can be useful

[@sayori3939]

What the....? I think I'll go with the week 4's short on stack

[@peerapatj9094]

@1:31:22 your light theme almost kill my eyes

[@duckpilot962]

I think my brain stopped working when he started coding the linked lists

[@anshgujral5175]

love from gujralssssssssssssssss

[@hami4044]

I have to say that some 5 minutes clips took me 30 minutes to understand... It means when I'm about 150 years old, I could go to Harvard!

[@sayori3939]

To be honest that example using people was more confusing than the code example lol

[@j.maginnenu6291]

This is Harvard.

[@sayori3939]

This is my failure juice

[@tGoldenPhoenix]

1:53:33

[@ItsSchwifty]

1:42:38

[@linahussain2838]

1:04:24

[@SimonTheFlash]

I don't understand something. If n == NULL, why do you need to free(list) before return 1. If you are going to exit the program anyhow, isn't memory just freed itself?

[@santiagoa7226]

it's not freeing the actual malloc, but the one that he sued before. If you use malloc 5 times, even with the sme name. You've to use free() 5 times.

[@sayori3939]

The OSes nowadays do reclaim that "wasted" memory back, but that's not the case in some systems and when you close certain programs and the process is still on task manager this may be one of the reasons

[@frankcastellanos]

Pointers and data structures uhhgg

[@savinyupant6227]

22:09

[@razu3717]

why david always sweats during lecture, why Harvard doesn't install air condition?

[@ObaidahNaseer]

Because of mask. The next year and years prior he is doing fine.

[@chasez9257]

47:38

[@shivamseth5262]

Free my guy list, he ain't done nothing

[@UmarFarooq-cq5zb]

Hi

[@vipinritik781]

I don't get that why n variable in node get vanished or free automatically

[@kristofersokk1580]

If you have a stack-allocated variable (aka not allocated with malloc), it gets freed automatically at the of the function by the compiler.

[@sayori3939]

"n" is being assigned to different adresses and then list/list->next is being assigned to the same adress in memory, so in the end what really matters is that adress in memory, the pointer itself is just a 4/8 bytes "variable" so if you free list, n is automatically freed too since both points to a chunk of memory, watch week 4's shorts on pointer it's much clearer but i don't understand why use n if you could just use list = malloc(....) Then list->next = malloc(....) (The same stuff that was used on n), maybe it was to avoid writing list->next, list ->next->nex etc so putting it into n you would only write all those "next" when you were assigning list to n and it would be easier to check for NULL using n

[@sayori3939]

I think i wanna go deep diving tied up....

[@sayori3939]

Yep time to drown myself in the short videos of this lesson lol

[@abrahamtellez592]

If only the lectures could be twice as long...

[@djt6fan]

Theyre already long enough and densely packed with information. I dont get why youd want them to be even longer.

[@padinnya_jepy]

there are additional shorts on the course, related to almost every topic for each lecture

[@alialo5390]

Fmfv

[@BruceNJeffAreMyFlies]

'We will give you a chance to do that in problem set five' Yeah.. You tell us to do it without telling us HOW to do it, so maybe answer the guys question so that we know what we are doing?

[@homeless5913]

Are you serious

[@leopower1093]

Binary search tree walkthrough : kzbin.info/www/bejne/f5WkoJiwfamNgbs

[@Slail]

I am dumb.

[@hamzasehavdic]

why?

[@sayori3939]

If you're feeling like that because of how hard this lesson is you probably want to check the short videos on each week 4(on the edx website) specially the pointer video and the stack one too

[@yassineinsta7731]

The dumbest algorithm I've ever seen, this guy is wondering why the string length is being returned wrong 👇😂 int length (string str) int count = 0; for (I = 0; I < strlen(str); I ++) count ++; Return count;