David prefixes * to the variable/field name in lectures, but you add * as a suffix to the data type. It would be AWESOME if you guys used the same style.
Everytime I finish the current week's PSET, I feel so smart. And then there's another higher wall that is waiting for you for the next week's PSET. Lmao
I really wish they would compliment these shorts/sections with more code examples. Visualization isn't enough. It's the biggest barrier in this course in my opinion. You get to the problem set and you have VERY limited exposure to the new syntax. It feels like shooting in the dark.
Thanks a lot teacher Lloyd for this great explanation. In the lecture we learned inserting nodes to end of list as follows. list -> next = node; list -> next -> next = node; But in this video you gave us another idea. Bless you.
I definitely see the similarity between the recursive functions in call stacks and deleting linked lists. It's... probably the only thing I really understood in this video :-
To delete an entire linked list... 1. In your video, you used recursion; 2. In the class video, a while loop was used: while (list != NULL) { node *tmp = list->next; free(list); list = tmp; } Which is preferred?
Personally, I would prefer using the while loop as it makes the code look more readable. If I were to come across a piece of code that began with a while loop, I could use that as a base and build up my understanding as I continue reading. If I came across a piece of code that used recursion, I feel like it would take me a little longer to understand it as I'll only know what it's accomplishing when I finish reading it.
Hi, I don't understand how at 8:50 the `create` function returns a pointer. I understand that we need a pointer that is pointing to the single node, so that later we can use that pointer to link the node to other nodes, but where does this pointer get stored? Into sllnode * new? I guess??
14:00 Why do you have to return a pointer for the insert function? i.e., instead of: sllnode* insert(sllnode* head, VALUE val); why note just do: void insert(sllnode* head, VALUE val); Since it's a pointer, any changes made in the porotype will carry over to the stack, no?
At 5:10 , this is weird, because some of the code used in for example Speller is this: // Represents a node in a hash table typedef struct node { char word[LENGTH + 1]; struct node *next; } node;
@@anuraghooda8439 because from the video it looks like you must have different names for the temporary struct name and the definitive one. He uses "sllist" twice and then "sllnode". This got me confused as well.
It could be done either way. The following would still work the exact same way. You can think of the first two instances of tempnode just being needed for your code to compile properly before ultimately defining the new structure as a "node". // Represents a node in a hash table typedef struct tempnode { char word[LENGTH + 1]; struct tempnode *next; } node;
I have the same confusion. Seems to be saying that saying struct x, and then using struct x as the self referenced data type, refers to this struct, not to the name given to the struct data type, so it has a different name at the end than x, ie sllist(the temp variable that refers to this struct, and sllnode, the final name given. It makes the "self referential" part even more confusing because the name changes, but if it works then the understanding changes. Also the placement of the * seems like a typo, like it should be one to the right.
Gotta be honest, this may be an unpopular opinion but from what is expected from the homework versus how much worked examples/exploration of these data structures are given in the lecture/shorts, there feels to be quite a gap: essentially all of c memory manipulation felt rushed like maybe there should have been an extra lesson in order to give more guided exploration with such a core and all important concept as data structures :/
I tried to write the code and the Insert function seems to work fine for adding nodes but also to create new linked lists. So what's the need of a "create" function? Maybe I am missing something.
No I don't think he said you CANNOT use the same name, he just used another name, and David clearly said in the lecture that you can name it whatever you want but he chooses to name it the same name because it makes more sense.
Because you're supposed to come up with the code yourself that's the entire point. You have to learn how to think algorithmically. If you can't tell a machine the exact steps to execute these commands, than you must not really understand the commands yourself. Draw pictures do whatever you have to do to figure it out. It takes a long time!
I could see this trend in the lecture and it keeps going in the shorts, they really don't wanna show any code this week do they? It's like trying to learn recursion in pseudocode without seeing any code. Don't really get the point, but whatever. I'm not asking for the code for speller, I'm just asking to be taught concepts in C not in pseudocode, why all the dodging with showing code this week?
// Free memory node *ptr = numbers; while (ptr != NULL) { node *next = ptr->next; free(ptr); ptr = next; } Here the bit of code from "list2.c" from lecture 5. So, the deletion starts in that code from the very begining. But it was mentioned in the video that we have to go till the NULL pointer and then we delete all the containers. Is it the second way of how to clean memory?
The term itself. Because sllist is used after the curly braces, in the rest of the video, and by extension, the code, sllnode is used to refer to that structure. Therefore, the term struct sllist* is temporary as it doesn't need to be used again.
The further I get into this class the more obvious the problem becomes. There's a huge disconnect in what we're shown vs what we're expected to code. I might just be dumb, but looking at speller is a kick in the pants.
@@WanderingNasi I feel the same way, there should be problems that build up to the final level of any given problem set! Grind out and learning the codes from class is simply not enough, you have to do completely different things for the problem sets.
The video is great, but I don't understand the dogma around only working from front to end or reverse depending on scenario... If I want to be able to append to the end of the list, why not have a global variable just like the one for head, that simply points there (and gets updated accordingly)? And why not avoid a stack overflow by not destroying recursively, but instead storing ->next in a temporary variable (say "sllnode *tmp"), destroy the current node and continue with destroy(tmp) until tmp==NULL? This would seem so much more memory efficient for large lists! EDIT: I just realized he talked about setting up a global variable sllnode *head, but still passes it to his functions - why? The functions automatically have access to all global vars! This does not even compile properly (Wshadow gives an error that we have already defined head)!!!
UPDATE: I just coded the whole thing. Good practice! I still stand by my words. Everything works out fine the way I described it. It's a few more lines of code and maybe a slightly higher risk of messing up somewhere (remembering to keep head AND tail updated), but versatility is higher when you know where the tail is - and I suspect linear freeing is faster, too. EDIT: I never passed the head node to a function btw! (...except when calling recursive destruction, because there you always have to pass the next node in line.)
@@hejhejmonika9787 What do you mean? No matter what you do to the middle of the list, the address of the tail doesn't change, does it? There's nothing to keep track of...
@@rautermann Bit of a necro comment, but.. The function he writes passing in the root is hypothetical sudo code for example purposes, implemented it would have more specific names. As for WHY he passes it in, even though the CS problem sets have a small scope, you still want to use best practices, in this case a "pure function." That is it is independent of its environment. If you look at the way a full project is structured, the image filter problem for example, where functions are declared as helper function in separate files, you can see why referencing global scope is dangerous.
@@georgegriffin3834 Hey, thanks for taking the time! I understand that referencing globals might lead to problems - but if I remember correctly, the head of the list is itself global. Are you sure that's the reason? Or did you just mean to reduce global variables to an absolute minimum - so while the head is necessary, the benefits of having a tail is not worth a global var?
Just a small doubt I had while watching. Which is more economical to have, Strings based on Linked Lists, or based on Character Arrays, as we usually learn?
Yes and that's the point, you create the node as you need them since you don't know how many of them you will need and that's why you would use that structure instead of an array .... so you would need some kind of loop or question the user or any function that would suite the program you're writing and each time you find some memory with malloc, create your node and like your node with the one before so you have a chain ... hopefully it is correct ...
Awesome vid and explanation. I find myself getting a bit confused about syntax with de-reference operators... Should asterisk be attached to TYPE? Or to the NAME? (I can't format the example correctly)... char * s = "mystring"; or bool find(sllnode * head, VALUE val); Maybe it doesn't matter - this seems to be a matter of style, they haven't really covered this in CS50 (or I missed it).
Yeah it's just a style choice. However, using the asterisk with the name makes it clearer that the name of the variable is a POINTER. For example, int *n = malloc(sizeof(int)); shows clearly that a "n" is a pointer to an integer.
Me: This C thing is getting kinda complicated
Doug: *MOOOOAAAR!*
I love that in the last few seconds he cheekily drops the bombshell of doubly-linked lists!
what a cliff hanger!
A tip for anyone who is struggling: USE A PAPER AND PENCIL TO DRAW ROUGH DIAGRAMS OF DATA STRUCTURES.
100% a great recommendation. Drawing out what's happening in the code for visualization is much easier to grasp initially.
I also 100% agree. Having a notebook helps me so much
Holy sheet i understand it now. thank you!
we learnt alot of the basics of c, we could do more right?
me: here we go again
@Blaine Bethurum no
David prefixes * to the variable/field name in lectures, but you add * as a suffix to the data type.
It would be AWESOME if you guys used the same style.
Everytime I finish the current week's PSET, I feel so smart. And then there's another higher wall that is waiting for you for the next week's PSET. Lmao
"Alright, Doug, enough already, I get it!"
-Me watching the video for the 3rd time and finally understanding :)
I really wish they would compliment these shorts/sections with more code examples. Visualization isn't enough. It's the biggest barrier in this course in my opinion. You get to the problem set and you have VERY limited exposure to the new syntax. It feels like shooting in the dark.
Thanks Lloyd for your great way of explaining things. This is helpful in consolidating the concepts explained in the lecture.
YOUR TEACHING STYLE IS AWESOME
THANKS
Thanks a lot teacher Lloyd for this great explanation.
In the lecture we learned inserting nodes to end of list as follows.
list -> next = node;
list -> next -> next = node;
But in this video you gave us another idea. Bless you.
ugh , he explained how the code to do each of those should act .
the thing is how to write that code xD
Thanks for these beautiful shorts, to the all staff. u.u
cs50 shorts the best
Your explanation is awesome!
I definitely see the similarity between the recursive functions in call stacks and deleting linked lists. It's... probably the only thing I really understood in this video :-
The only bad thing in this whole course is that stupid extremely high intro :"D
Does anyone else feel way over their head on speller? Like I feel like an idiot for how clueless I am on that problem...
after every pset you feel comfortable until you. get to the next one and yea its a whole new very unfamiliar experience
To delete an entire linked list...
1. In your video, you used recursion;
2. In the class video, a while loop was used:
while (list != NULL)
{
node *tmp = list->next;
free(list);
list = tmp;
}
Which is preferred?
Personally, I would prefer using the while loop as it makes the code look more readable. If I were to come across a piece of code that began with a while loop, I could use that as a base and build up my understanding as I continue reading. If I came across a piece of code that used recursion, I feel like it would take me a little longer to understand it as I'll only know what it's accomplishing when I finish reading it.
Loops are definitely better. Recursion requires additional memory for each iteration.
I've got this one on repeat
Hi, I don't understand how at 8:50 the `create` function returns a pointer. I understand that we need a pointer that is pointing to the single node, so that later we can use that pointer to link the node to other nodes, but where does this pointer get stored? Into sllnode * new? I guess??
poland
@@dasupaking ok😂😂😂
is it just me or do you guys also see the inverted Germany flag @ 20:08 and it says destroy destroy destroy inside it...
14:00
Why do you have to return a pointer for the insert function?
i.e., instead of:
sllnode* insert(sllnode* head, VALUE val);
why note just do:
void insert(sllnode* head, VALUE val);
Since it's a pointer, any changes made in the porotype will carry over to the stack, no?
At 5:10 , this is weird, because some of the code used in for example Speller is this:
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}
node;
What's weird exactly?
@@anuraghooda8439 because from the video it looks like you must have different names for the temporary struct name and the definitive one. He uses "sllist" twice and then "sllnode". This got me confused as well.
It could be done either way. The following would still work the exact same way. You can think of the first two instances of tempnode just being needed for your code to compile properly before ultimately defining the new structure as a "node".
// Represents a node in a hash table
typedef struct tempnode
{
char word[LENGTH + 1];
struct tempnode *next;
}
node;
I have the same confusion. Seems to be saying that saying struct x, and then using struct x as the self referenced data type, refers to this struct, not to the name given to the struct data type, so it has a different name at the end than x, ie sllist(the temp variable that refers to this struct, and sllnode, the final name given. It makes the "self referential" part even more confusing because the name changes, but if it works then the understanding changes. Also the placement of the * seems like a typo, like it should be one to the right.
Thank you for this awesome video!
Gotta be honest, this may be an unpopular opinion but from what is expected from the homework versus how much worked examples/exploration of these data structures are given in the lecture/shorts, there feels to be quite a gap: essentially all of c memory manipulation felt rushed like maybe there should have been an extra lesson in order to give more guided exploration with such a core and all important concept as data structures :/
I tried to write the code and the Insert function seems to work fine for adding nodes but also to create new linked lists. So what's the need of a "create" function? Maybe I am missing something.
I wish there was more code examples of how this looks. I get it when looking at the diagram, but still don't understand what it looks like in code.
cmon C and Doug, playback speed x0.75 still no node found on my brain for these things to relate it with C.
Wait... In David's lecture he uses the same name in his struct call. You're saying we CANNOT do this? @4:56
No I don't think he said you CANNOT use the same name, he just used another name, and David clearly said in the lecture that you can name it whatever you want but he chooses to name it the same name because it makes more sense.
Why dont they give us the code to do all this?
Because you're supposed to come up with the code yourself that's the entire point. You have to learn how to think algorithmically. If you can't tell a machine the exact steps to execute these commands, than you must not really understand the commands yourself. Draw pictures do whatever you have to do to figure it out. It takes a long time!
Hey, they do give us the code. Check out CS50 page and look at the source code/PDF topic. Voit la!
@@gabriell.gabriel it's "Et, voilà!"
Thanks Doug, awesome explanation, but the last part "Delete a single element" confused me
I could see this trend in the lecture and it keeps going in the shorts, they really don't wanna show any code this week do they? It's like trying to learn recursion in pseudocode without seeing any code. Don't really get the point, but whatever. I'm not asking for the code for speller, I'm just asking to be taught concepts in C not in pseudocode, why all the dodging with showing code this week?
exactly!
i wrote a fancy array (linked list) with 2 nodes that holds nothing but 2 ints in 80 lines...lmao. im completely drained
The hardest part is how to 'destroy' the list.
Agree
// Free memory
node *ptr = numbers;
while (ptr != NULL)
{
node *next = ptr->next;
free(ptr);
ptr = next;
}
Here the bit of code from "list2.c" from lecture 5. So, the deletion starts in that code from the very begining. But it was mentioned in the video that we have to go till the NULL pointer and then we delete all the containers. Is it the second way of how to clean memory?
Дмитрий Бакулин use github and forum communities u wont get any response here
That is not recursive... Not the same approach
void destroy(node *list)
{
if (list == NULL)
{
return;
}
destroy(list->next);
free(list);
}
Try this recursive version. Both approaches are true.
What makes struct sllist* "temporary"? 5:28
The term itself. Because sllist is used after the curly braces, in the rest of the video, and by extension, the code, sllnode is used to refer to that structure. Therefore, the term struct sllist* is temporary as it doesn't need to be used again.
show us actual code please
The further I get into this class the more obvious the problem becomes. There's a huge disconnect in what we're shown vs what we're expected to code. I might just be dumb, but looking at speller is a kick in the pants.
@@WanderingNasi I feel the same way, there should be problems that build up to the final level of any given problem set! Grind out and learning the codes from class is simply not enough, you have to do completely different things for the problem sets.
@@WanderingNasi Well this is a course aimed at Harvard students so... the difficulty is probably reasonable to them.
You're supposed to come up with an implementation yourself, it's part of the learning process.
They give you enough code and pseudo-code that they expect you to figure it out yourself.
The video is great, but I don't understand the dogma around only working from front to end or reverse depending on scenario...
If I want to be able to append to the end of the list, why not have a global variable just like the one for head, that simply points there (and gets updated accordingly)?
And why not avoid a stack overflow by not destroying recursively, but instead storing ->next in a temporary variable (say "sllnode *tmp"), destroy the current node and continue with destroy(tmp) until tmp==NULL? This would seem so much more memory efficient for large lists!
EDIT: I just realized he talked about setting up a global variable sllnode *head, but still passes it to his functions - why? The functions automatically have access to all global vars! This does not even compile properly (Wshadow gives an error that we have already defined head)!!!
UPDATE:
I just coded the whole thing. Good practice!
I still stand by my words. Everything works out fine the way I described it. It's a few more lines of code and maybe a slightly higher risk of messing up somewhere (remembering to keep head AND tail updated), but versatility is higher when you know where the tail is - and I suspect linear freeing is faster, too.
EDIT: I never passed the head node to a function btw! (...except when calling recursive destruction, because there you always have to pass the next node in line.)
As for tail good luck managing that tail variable when an element is deleted from between the list or added between the list.
@@hejhejmonika9787 What do you mean? No matter what you do to the middle of the list, the address of the tail doesn't change, does it? There's nothing to keep track of...
@@rautermann Bit of a necro comment, but..
The function he writes passing in the root is hypothetical sudo code for example purposes, implemented it would have more specific names.
As for WHY he passes it in, even though the CS problem sets have a small scope, you still want to use best practices, in this case a "pure function." That is it is independent of its environment. If you look at the way a full project is structured, the image filter problem for example, where functions are declared as helper function in separate files, you can see why referencing global scope is dangerous.
@@georgegriffin3834 Hey, thanks for taking the time!
I understand that referencing globals might lead to problems - but if I remember correctly, the head of the list is itself global. Are you sure that's the reason?
Or did you just mean to reduce global variables to an absolute minimum - so while the head is necessary, the benefits of having a tail is not worth a global var?
Just a small doubt I had while watching. Which is more economical to have, Strings based on Linked Lists, or based on Character Arrays, as we usually learn?
so how do you connect the node? u need to assign every node one by one?
Yes and that's the point, you create the node as you need them since you don't know how many of them you will need and that's why you would use that structure instead of an array .... so you would need some kind of loop or question the user or any function that would suite the program you're writing and each time you find some memory with malloc, create your node and like your node with the one before so you have a chain ... hopefully it is correct ...
Awesome vid and explanation. I find myself getting a bit confused about syntax with de-reference operators... Should asterisk be attached to TYPE? Or to the NAME?
(I can't format the example correctly)... char * s = "mystring"; or bool find(sllnode * head, VALUE val);
Maybe it doesn't matter - this seems to be a matter of style, they haven't really covered this in CS50 (or I missed it).
Yeah it's just a style choice. However, using the asterisk with the name makes it clearer that the name of the variable is a POINTER. For example, int *n = malloc(sizeof(int)); shows clearly that a "n" is a pointer to an integer.
doug's mouth sounds pretty prominent here
Hi Douglas!
i mean you could ve showed us that in code
Thanks
well this is easy...
thank you!