This is okay for how a first year CS student would code it, but I'd like to see you do a tutorial that shows the more experienced method of turning the code into a generic library. Also, using void* for the structure was a bad idea for type checking purposes as well as introduces the possibility on some older, but potentially still relevant, platforms of pointer size mismatch. Better is to do typedef struct node_s node_t; struct node_s { int data; node_t *next; }; // While reusing the structure name in a typedef is allowed in C, as in typedef struct node_t node_t; I personally dislike the practice for various reasons.
@@anon_y_mousse Para el caso también podría hacer: typedef struct node_t { node_t *next; int data; } Node; y no tienes que separar la definición en dos lineas. De todas formas usar node_t* o void* en este contexto es lo mismo: Un puntero, sea del tipo que sea tiene un tamaño fijo, por lo que no cambia el tamaño de la estructura. Por otra parte en este tipo simple de estructura el puntero no va a tener aritmética ni se va a usar con notación de de array, por lo que no le afecta de que tipo sea. Lo único que debe hacerle el cast cada vez que quiera dereferenciarlo.
@@Ak4n0 If I'm understanding you based on an automated translation, on older platforms where you had near and far pointers they were indeed multiple sizes, and void * was allowed to be the largest size possible if the implementation desired. It's less relevant on modern computers, but the type checking argument is still valid, and your struct is actually invalid. If you want to define it in one statement it would be typedef struct node_s { struct node_s *next; int data; } node_t; That's a semi-acceptable method too, but I prefer a separate statement because if you deal with more links you don't need to repeat the struct keyword that many times.
For those interested in fundamental data structures and algorithms, I highly recommend "Algorithms + Data Structures = Programs" by Niklaus Wirth. It is the seminal authority on the the topic.
@@leninalopez2912 If you think reading books is efficient for your learning then you don't know what is efficient learning at all and haven't ever been learning efficiently yourself. Reading books is the LEAST (time) efficient way of ALL to learn stuff. It is thorough, yes, but that's all there is to it. Reading can *never* be more efficient than watching a video(Audio+Visual input) if we assume both have the same quality content. When you read you do indeed go into more theory and detail, but what is the purpose of that if you can't apply 80% of stuff that you read in practice("Tutorial Hell" from reading books is *magnitudes* worse than "tutorial hell" from videos, I can explain the reasoning if you are interested). You can't really say "books" and "efficient use of your time" in one sentence as this is just a contradiction because of the reasons above. I am 100% sure that I can outlearn(have better learning results than) *every single person* who studies by reading books, by studying using a video material with the same quality instead, for example. I really dislike people who haven't really been competitive or (really) care about efficiency, yet talk like they tried every single thing and know the best. No, you just went with what first worked for you(or preference), blindly thinking it is "efficient", without ultimately seeking for what is actually most efficient in reality. Efficiency is not about optimizing your own preferences, it is about being competitive and adapting to the best environment possible. You can say fast walking is more efficient than normal walking, but I am saying that I will rather run, even if I never ran in my entire life, if in the end it will be more efficient, that is the difference.
@@twothreeoneoneseventwoonefour5 it's not about efficiency, that's simply a dumb perspective. Learning is about seeing what you already know in a new light and not running ahead to something else. For good reason the advice is "_stop_ and think!". In order to really think, it's best to first stop and reconsider if it's a good idea at all. Wirth was a mathematician first, and I see that in his writing. It has proofs of fact, mathematical proofs, not just proofs of concept. The kind of sloppiness of "just hacking away at it" and "being efficient and productive" without evaluating the goals of your own enterprise is exactly why the tech industry is at the point where it is today: stalled for ideas, producing buggy messes and completely separated from any critical understanding of it's own creations
Due to caching linked lists are usually slower than a simple contiguous vector. Bi-directional Linked lists typically require 3x the number of bytes as a simple vector structure, so they hurt performance for even medium sized lists.
I wonder if it would be worth it to first copy all of the data into a contiguous array from a linked list before operating on it with a complicated algorithm, and then copying it back at the end. Somehow this sounds better than running an algorithm (like sort) on the list itself.
@@softwarelivre2389 but to remove from the middle (at least by index), you must traverse the whole list. The cache thrashing that results makes it so much worse than an array/vector that uses memcpy.
@@colejohnson66 good point, but sometimed you have to merge two linked lists at a position (put one in the middle of the other), which can be very fast in the case of linked lists
I left a PR that fixes a couple issues with the code. As Alistair Foggin said, there is a memory leak in removeNode, and the call to malloc() in addNode only needs to occur in one place. Additionally, as noted by Mohammad Salman, the insertNode() function does not interate through the list each time the position variable is decremented. This means that insertNode only ever inserts into the second position.
@@user-dp3zr1qe3s I totally agree! Can't believe it either! 😳This video should not be recommended how to learn to implement a single linked list in C. It's a big mess, riddled with serious bugs and reveals a totally sloppy attitude towards clean working... The only thing that is of any use is the graphic explanation. Sorry to say that. 😐
In removeNode, you only free the removed node if it is in the middle or the end of the list. If it is the head, it is not freed so there is still a memory leak. Other than that, this is a fantastic tutorial! Keep up the good work!
My favourite implementation of a linked list is a circular doubly linked list. Here the nodes have 2 references, previous and next. The head of the list is not a part of the list (its data is unimportant), instead it points to the first node and the last node as its next and previous references, respectively. If the list is empty, then the head points to itself on both previous and next. The reason why I like this is because, being circular, there are no edge cases. Removing the first element is the same as removing an element in the middle of the list or the end. Inserting an element is the same regardless if the list is empty, you are inserting at the start, end or middle. This simplicity makes fixing bugs and adding more functionality to the list much easier.
You don't need to branch if head points to NULL, just assign head to the new node, if its NULL so be it. Also position 0 should semantically mean "before the first", it seems now you can only insert after the first element (you can add though but add can be implemented in terms of insert as a simplified function)
I would definitely agree that a programmer should know and be able to implement a linked list but that being said, linked lists are almost never the best solution to a problem. Due to the expensive heap allocations, CPU cache, deref iterations and a bunch of other things linked lists are generally "slow as shit" except in a few very rare cases
Depends if performance is your goal. One major advantage of linked lists is that they're dead simple and can be optimized for all kinds of tasks. If I'm in a language that has a decent set of data structures*, then I don't usually use lists. I tend to use them in C because they're quick to write and debug. * Besides Lisp languages, which usually have a full set of data structures but use lists for all kinds of stuff
@@jeffspaulding9834 A linked list is definitely not simpler than a Array based list / vector. As long as you don't have a rather large list where you constantly remove elements from the middle, a vector is probably faster
@@darkfire2703 Depends what you're doing with the list. If you're adding and removing from both ends, a linked list is simpler than an array. As far as faster, I don't debate that.
I think to append a node in constant time, we can maintain a tail pointer. So in push() we push new node into head pointer if it's null and make tail equal to heads next, else we push new node into tail and make tail equals to tails next.
Doesn't matter how long I've been programming, there's something about implementing and viewing the code for a linked list that's just fascinating. Great stuff. I was taught to always have a head and tail node. So I always code that out of habit. It does complicate the code just a little bit though.
@@MECHANISMUS I believe that a doubly linked list. Which as the other user stated, gives you access to more efficient opporations because you know the end and beginning of the list. So you can trace inwards with both at the same time, cutting any O(N) time down and as he said, insert into list O(1) time.
@@zenverak having a head and tail node doesnt always imply having a double linked list. But it will make implementing a queue or stack easy because you will always have access to the head or tail with O(1) time.
im learning how to code using the cs50 course on youtube and the section about linked lists absolutely stumped me. After watching this tutorial i realized my understanding of the syntax in C was wrong and i finally figured it out. thank you so much.
I use technology every day, and in the background; all of this code is running. Someone sat for hours, days, weeks, even months and years in some cases, to create the code for all of it to happen and work without bugs. It's crazy to think about it in terms like that and I guess programmers are really sort of the unsung hero's of the technological age. Thank you!
I use extra pointers. One for the last and one for the previous. It allowed me to walk forward or backward and I didn't have to walk the list to get to the end. It was especially helpful for large lists. The code to keep the pointers current is less than one might expect.
If you have very large lists you should either: a) Consider using a different data structure, maybe a map or self-balancing BST. It really depends on what you're doing b) Doubly linked skip list, requires a sorted list of course.
When is it useful to add a pointer to the previous node as part of the node structure? Also, should we, or when should we create another structure for the list that links to the functions we created that are exclusively designed to work with the list instead of using a node pointer as the list?
There's an issue with the insertion code, it's missing an instruction on the initial loop to update the `current` reference, just like that: while (current != NULL && position != 0) { position--; current = current->next; } Without this, the code will just run down the position, but the item will always be inserted as the next from the head, since the current never changes. Other than that pretty cool video, thank you!
I noticed your new use of transitions since I’m a part time videographer as well. Your production quality is up from last year! Keep it up. I’m loving the consistency!!
In the insertNode function, the while loop doesn't update current node so when insert you will all way insert into position 0 (right after the head node). I think you should add current = current->next inside that loop. Edit: It should be like this while(current != NULL && --position != 0){ current = current->next; }
This is true. I was wondering about it and cross checked w GitHub code. Seems same there and updating the current makes it perfect! Thanks for putting that up.
17:20 Can you please tell my how this while loop change current from point to head, and end up pointing to the node at position, when something like current = current->next is not explicitly defined? Thank you for the great vid.
Theres an issue in the insertnode function! You move position but dont update the new current so you will always insert data into position 1 (after current) You need a prev node to update prev and current along with position--
@@kingbababouille That's what I thought would happen, but interestingly, the code provided in the video works exactly as it should. In fact, when I explicitly add the current = current->next line, the code breaks. I don't understand how the head pointer changes still.
Man this content takes me back to first year of college, having to create all these different data structures from scratch. Good times. A lot of people using high level languages dont realize how important it is to have a good grasp on how all this works behind the scenes.
To anyone reading the head pointer is the front of the list. He said it correctly at first then when testing the add function he switched his definition implying the head pointer was at the end, and then switched it back correctly when testing the insert function. This might be confusing for people trying to learn.
Hi, one question why arent you changing *current in the while loop of the "insertNode" function? I think that the function is inserting the node in the same place every time, after the *head. Havent ran the code before but i think this is the way of doing it: while (current != NULL && position != 0) { current = current->next; position--; } Thanks for the video.
I have a task manager app that I implement in any new language i learn. It uses doubly linked lists with sub-lists available for any task. It puts me through tha paces of multiple features of any language: Data structures, pointers, memory allocation, functions, classes (if OOP), file I/O, user interface.
With how horrendously bad linked lists are for cache efficiency and auto vectorization the thumbnail is actual clickbait. I thought I was about something interesting
“Clean”? Are you serious? 😳It’s a whole mess mixed with pretty serious Bugs in it! Almost every rule of good software development is violated in this course! It contains wrong semantics, memory leaks and shows a ridiculous bad style of coding habits! Such a basic thing as a common Data container has to be robust. My advice: You should better watch videos from people who work clean and are aware of their responsibility for their big count of subscribers. 🙄
why are we appending to the front? why are we using void pointers? why are we nesting if + switch instead of using a guard clause or just letting the menu default? we are duplicating mallocs in different branches of addNode, we have a memory leak in removeNode, we're not handling negative values for position NOR EVER MOVING THE CURRENT NODE in insertNode (no wonder it literally doesn't work) this implementation is borderline insane and it's even crazier that you had the balls to upload this
Never in my programming career have I ever used/needed a linked list. These pointer structures are super slow. Maybe good for teaching, but useless in practice. Unlike the linked list, I was not taught in school that accessing an array instead is >1000x faster, and accessing an array on GPU adds another 100x. If in a job interview I would get asked how to write a linked list or other leetcode crap, I would just leave the room and not waste any more time.
There are real world use cases for linked lists like LRU caches. They also use a hash table to lookup the nodes of the linked list in constant time in order to avoid the slow linked list traversal. The linked list is used for fast removal and insertion.
@@jeffspaulding9834 You're right, who am I to judge about the usefulness of linked lists. I don't even have any formal education on CS. I'm just the one solo developer who writes the answers on Stack Overflow, and whose software is somehow ranked at the very top in GitHub topics. I guess I should go back learn linked lists and leetcode to be able to write super slow code like everyone else.
@@psychoinferno4227 I know. But linked lists and other data structures are taught in a way as if they always were the superior choice, without ever considering performance. What then happens is that people use them in places they don't belong, and end up with poor software without even a clue what's wrong. I've once had an assessment center challenge to write Conway's game of life in a couple minutes. I was the only one who got it working in time, and the employee seriously suggested I should have used linked lists instead of arrays. You can't make this up.
Theres an issue in the insertnode function! You move position but dont update the new current so you will always insert data into position 1 (after current) You need a prev node to update prev and current along with position--
1:11, If you do this with offset pointers instead you can also keep the benefits of a buffer (access by index), something like: link = head + link->next will get you the next link in this scenario. UX side you still need to loop through the remaining list items to update their positions (not their indices, the ordered positions as far as the user is concerned) when you add/remove items but that's still much cheaper than actually moving every item in the list. Since both index and position can be attached to UX elements and only the position reported to the user you can just grab the index/offset (depends which you stored, both can be converted to the other using sizeof(link)) and add that back to the head element to get the intended link. Comes at the cost of memory but I'd argue speed is more worthwhile in all cases for this particular case.
Linked lists are a great exercise on how to use pointers, but they are also old data structures that do not work very well in modern computer architectures. They are relics of the past and have very few remaining use-cases where they are superior to vector-style arrays, even taking into account the reallocation+move times.
Linked List is the Latin of data structures. It exists by being dissolved into other, more complex and useful data structures like LFU caches for example.
That is a pointer to a pointer to a char. Meaning it stores the address of a pointer to char which itself stores the address of a char. It is used to store an array of strings that can be accessed using only a single variable. The ammount of strings is stored in the first argument. char *argv[] would be equivalent (since the compiler turns it into the other version automatically), but shows better what is happening. In case you don't know those strings are usually what you write behind the name of the executable which looks about like this: executable arg1 arg2 arg3 ... argN The name and path of the executable are usually given as the first argument automatically.
I used to use single linked lists that were bidirectional with a single pointer (to save memory, you xor the current and next values, and you can go through the list in either direction. I used that on a device with less than 64K to save memory.)
at 8 minute, you allocated a new Node object, and then later on set the "next" variable to NULL. It works in your case, but for real life cases it is strongly suggested (at least from my view) that you do a memset(new, 0x00, sizeof(Node));
Just discovered this channel as a CS student that loves linked lists since he learned about it at the beginning of the year. Talking about addNode, isn't it just better to straight up declare the list as a NULL then just adding nodes from there ? Like this : list_t *addNode(list_t *list, int data) { list_t *newNode = malloc(sizeof(list_t)); newNode->data = data: newNode->next = list; return newNode; } int main(int ac, char **av) { list_t* list = NULL; list = addNode(list, x); list = addNode(list, y); ... return 0; } I've been taught that way and it avoids checking if head is NULL bc you'll always have NULL at the end of the list and there is no need to really manage the head pointer
Currently having to do a .cpp paper for an engineering degree and I find everything you've done in c very helpful. I learn best from seeing functional examples with explinations and your channel is great for it. I do have a code example from my course that I would appreciate an explination for though, as I can't make heads nor tails of what it is actually doing. If you want a picture I can send it to you, basically it is allocating information in a table structure, but in the book (learning through correspondence) it isn't clearly outlined.
haha love that realization at 11:23 that your code is gonna crash, then being surprised that you actually wrote the correct code the first time around. Relatable feeling.
one should probably use array instead (i know only 2 very specific cases where linked lists are better, sort of). arrays are also quite flexible: you can have a "fat pointer" or store header directly on the array, you can have capacity variable to reduce allocations or you can have no extra capacity and prioritize space efficiency. arrays are far better than linked lists for pushing a new element to the end and popping last element (because they normally don't need new allocations for that), they have fast access and sorting and so on. even insert in the middle of array is often faster than insert in the middle of a linked list (modern chips are good at copying contiguous chunks of memory).
What's the point of the 'while' loop in the 'insertNode' function? It just decreases the position until it reaches 0, you never modify the 'current' pointer and you don't cover this in your test. Also, the signed integer is not a right choice here - passing '-1', for example, can be very bad.
1:08, the last node doesn't have to point to NULL, NULL is just an easy exit condition but you can also just check the pointer you have does not match the one you started with, this allows the option of a semi-permanent loop that doesn't check for said match since it only needs to process the nodes, this is particularly useful if you 're making a multiplayer game or even just physics, the players/"actors" would be nodes that need their position constantly updated even if they're not rendered during the update, a linked list of nodes that circles on itself would allow the loop to be optimised to just check for game exit instead of both that and a NULL pointer
6:20, nope, not necessary, you can maintain 2 types of lists for the same nodes, one is a simple array of pointers to nodes int the order they are declared to be, the other is the linked list, when you want to append a node you select the last node pointer in the array and just set it's next value to the new pointer and add the new pointer to the end of the list (increasing the count while you're at it), when removing by index you load the node from the pointer list and make the nodes it's linked to link to each other instead, then you shift the pointers in the list up 1 and iterate through them all to correct their stored index, when inserting you likewise load the node already stored at said index and set the new pointers next to that node and update the previous node it was connected to, sure this method is a little more memory hogging but in most cases that is less an issue than the speed
A fun challenge to expand on this video is indexing the list. Give the node struct an index integer. Makes it easier to reach a certain element n by just reading the index. It also completely changes how you add, remove or insert elements into the list, since all indexes from that point on have to be adjusted.
This is a good reason to allocate it contiguously, then the pointer for the index becomes: root node pointer + size of node * index. This is much faster than jumping through the links, but of course, it goes against the point of having a linked list to begin with (why have next-pointers at all if the nodes are already right next to each other in memory, AKA an array).
Though if you want a thing with dynamic size, you could make a dynamic array. It isn't that hard to do. You just need a structure with a pointer, the count, and the max size, and if you want to add to the array and the new size will be larger than the allocated space, you just use realloc and decide on how much to increase it (you could double it until you have enough, you could add some number to it until you have enough, or you could do some clever math, it's up to you.) Then maybe consider shrinking it if you don't need all that space anymore. The advantage of using a dynamic array instead of a linked list is that you have all the data in one place instead of scattered all over the place (unless you use an arena allocator or something), also the data will be easier to traverse, and you may need less allocations if you do it right. Though the linked list has one advantage... you can quickly and easily remove a single element in the middle of the list. If you want to try it out, try making a string that you can print, append to, remove stuff from, etc.
Back in the days in the year 2000, I learned that in 11. grade at high school using Turbo Pascal. We had a really good computer science teacher then. We also learned to make tree structures in similar way....including sort and search functionality. I suppose such things are not tought in high school anymore since very few teachers know that stuff.
Also you could use `typedef struct node { struct node *next; int data; } Node;` to make life much, much easier when going certain number of nodes forward (`some_node->next->next->next`) without casting it to `Node` every time
While all the other physicist were specializing in their field, Einstein was specializing in none but watching all. It resulted in general relativity. To see someone so good that they can deduce so many coding disciplines reminds me of what Einstein did there.
while (current != NULL && position != 0) { position--; } shoudln't this loop also move current to current->next ? Otherwise we keep inserting the node to the head right? unless i'm mistaken
@8:45: Lines 19 and 27 (among others) are redundant. So this violates the DRY (Don't repeat yourself) rule! Why don't you separate the piece of code to allocate a new node (malloc) and first fill it with data and next to NULL and *then* just ask if head is NULL and if it is just assign this to the new created node?🧐 Sorry, couldn't resist - I'm German. 🥺
I was once forced to implement a cyclic singly linked list for a game I made in a fairly new language called freebasic. It was in its beta stage so you pretty had to code everything. It was a nice mind exercise too.
Red-black tree best data structure >.> I've always liked how understanding singly-linked lists is essential to implement most other data structures, tbh. A lot of them are extremely similar in concept to a linked list.
In AddNode, the malloc, NULL check and data assignment should all be above the if statement. Code duplication can lead to errors if one copy is changed and the other is not.
nice! but I have to say there is an error in the function insert node function. the current node pointer is not changed in the while loop. one line should be added into the while loop to update the current pointer to the position where to add the new node: current = current->next;
I don't understand the insertNode function. In the first loop, position goes to 0, so haven't we lost the actual position where we were supposed to insert the element? Also, the current pointer is always at the head is it not? So how can we accurately insert the node at the required position?
Yep youre right, he forgot to add current=current->next after position--. Also in that case you need to change while current->next not null because it can get to null if its the same number of nodes as psotion
you're right, he doesn't interate the current node when he decrements the position. He just doesnt notice the bug because he only tries inserting into position 0. I tried running the code myself and it doesn't work properly :/
Usually when I make my linked lists I make a struct representing the entire list with a pointer to both the head and the tail, allows for o(1) adding and removal from both ends of the list ;)
Ironically I think that doubly linked lists are faster if you have a pointer to a specific node, since you can do it in O(1) time by simply connecting node->prev with node->next and updating the heads, rather than having to go through the whole list again to find the previous element which points back there. Addition to both heads is also O(1) if you keep track of them. *By O(1) I mean that their execution time is constant as the data set's size increases, since they're operations where you don't need to create any loops, instead simply manipulating a few pointers.
So much of the data structure education I got in school went out the window when I got into embedded where node count (or maximum node count) is part of the design so it just becomes predefined array
Good for theoretic implementation and understanding of pointers, bad for practical applications minus few isolated edge cases. Even the creator of C said that arrays are better in any way as you don't need to traverse them to get to a certain element.
You are doing an amazing videos! I would just suggest that if you want to append element in the list you could do it in complexity of O(1) by creating a pointer named “tail” which points to the last node. 😊
Yes at least this video indeed is amazing... ...amazing because of the abundance of serious bugs! Honestly - I don't want to be harsh - but this video is not really a good example to learn software development conscientiously. 🤨See I'm a senior embedded Software Engineer and such (actually simple) code would not have survived a code-review. Seriously! In my opinion this is *not* a good example of how to do clean software development. I'm sorry to say that. Hope he prepares better next time! Remember - a good preparation is 90% of success.
@LowLevelLearning Thank you very much for all the amazing content you make. I would like to point out that the insertNode function in your example does not work as intended, below is the corrected implementation: Node* insertNode(int value, int position){ Node* new = malloc(sizeof(Node)); if (new == NULL) { printf("Memory allocation failed "); return NULL; } new->value = value; new->next = NULL; if (position == 0) { new->next = head; head = new; return new; } Node* current = head; Node* previous = NULL; while (current != NULL && position > 0) { previous = current; current = current->next; position--; } if (position > 0) { printf("Requested position too far into the list "); free(new); return NULL; } new->next = current; previous->next = new;
They are also a fantastic way for people to get comfortable with recursion, as any algorithm for a recursive data strucutre can be implented with a recursive algorithm.
@2:35 why is this a void* and not a Node* ? I mean the Poster pints to the next Node which is not an anonymous (void) reference but an concrete namely Node?
Sorry I'm just watching the video and checking the code and I'm a bit confused.. On the InsertNode method, inside the while loop u're decrementing position without setting current to current->next, in this way whatever position you receive, current just points to head without moving... or am I wrong?
When trying to see if you can get your code to run the first time, you get an error and say, "Go ahead and include standard libs." Then you copy the text . Then you open a new terminal and are able to run the command again but without the errors. What are you doing here? I don't know how you got it running without an error and that's where I'm stuck at.
(A bit late, but for those curious) He used: #include This command tells the compiler to include another file in compilation. The one in question being stdlib.h. often called the "Standard Library". Without it you don't have easy access to commonly used stuff like memory allocation, random numbers and converting variables. There are also other libraries like which gives you mathmatical functions like cos, sin, floor, log, etc. Libraries are an important element of coding stuff you don't know how to do from scratch yourself and provide many shortcuts. Especially in embedded systems do we use libraries a LOT to make interacting with certain things a lot less headache inducing!
I like the use of the void*. In the past, I have always typedef a Node ahead of defining it and used Node* in the Node. However, the void* makes more sense.
For the add method, is it really necessary to separate between and empty list and a non-empty list? Is it not enough to do what you do for the non-empty case in both of the cases, since head == NULL, and therefore new->next = head is the same as new->next = NULL?
0:07 If I were to give a wild guess, I'd assume that a singly linked list is a linked list but where only the next node is stored for each node instead of both next and previous nodes being stored. How close was I?
I love these kind of videos from you keep on going. I try to recreate everything you do myself and I leave every of your videos a bit smarter. Thank you a lot keep on going!
...that said and hopefully you realized, that his code is full of (partial serious) bugs? 🙄😳 Furthermore, the presence of a lot of *redundant* (with its rendundant bugs) code reveals that this guy has no real practice about programming and hence as an total novice he should not try to teach others in this matter... we’re here in Germany are used to say: “Schuster, bleib‘ bei Deinen Leisten“ 😉
Super tutorial, I am now learning to handle frees with new best friend Valgrind.I have a question: what are the actual use cases for linked lists in a real world program? I am only learnig the basics now but I would like to know when Is the best and optional situation for when to use them, especially considering performance and fastness of the program one is writing. Probably It would make a nice video this topic, but thanks in advance for the answer!
Hi! in real world, it is quite rare to use a real linked list as it is quite slow (huge allocation overhead). However, you can cheat to remove this slowness. In c++, if I remember correctly, the std::deque is a linked list of enormous arrays, meaning you have to allocate array after array without having a really big allocation issue. I think of it more of a way to extend an existing array rather than being the sole container. same language, still c++, std::vector (allocated array) is almost always faster than std::list. However, when you have to keep references (or pointers) to the object, linked list are actually the best. if you remove a node from the list, it only invalidates the pointers (or iterators) to the specific node. same goes if you ever add a node. If you ever need to keep huge quantity of pointers to members of an array which could reallocate at anytime, I would suggest using a linked list if the array is not in a critical chokepoint. Still the same pattern though, one allocation for a pool of nodes I would pick from to reduce performances drop. You could still have better performances with an array, however the code required to make it work would probably require way more memory. In production code, I actually never used linked list in its pure form (std::list) but used them in the hidden form (std::deque).
I think knowing how to use a LL is vital, but for environments that care about performance? Just use an array. Far less memory overhead, random access, and faster iteration.
Go check out the code here: www.github.com/lowlevellearning/singly-linked-list and let me know if you want more data structure videos!
This is okay for how a first year CS student would code it, but I'd like to see you do a tutorial that shows the more experienced method of turning the code into a generic library. Also, using void* for the structure was a bad idea for type checking purposes as well as introduces the possibility on some older, but potentially still relevant, platforms of pointer size mismatch. Better is to do typedef struct node_s node_t; struct node_s { int data; node_t *next; }; // While reusing the structure name in a typedef is allowed in C, as in typedef struct node_t node_t; I personally dislike the practice for various reasons.
Dynamic stacked structures? I know it's more for general compute, but I have never seen anyone discuss it.
@@anon_y_mousse Para el caso también podría hacer:
typedef struct node_t {
node_t *next;
int data;
} Node;
y no tienes que separar la definición en dos lineas.
De todas formas usar node_t* o void* en este contexto es lo mismo: Un puntero, sea del tipo que sea tiene un tamaño fijo, por lo que no cambia el tamaño de la estructura. Por otra parte en este tipo simple de estructura el puntero no va a tener aritmética ni se va a usar con notación de de array, por lo que no le afecta de que tipo sea. Lo único que debe hacerle el cast cada vez que quiera dereferenciarlo.
@@Ak4n0 If I'm understanding you based on an automated translation, on older platforms where you had near and far pointers they were indeed multiple sizes, and void * was allowed to be the largest size possible if the implementation desired. It's less relevant on modern computers, but the type checking argument is still valid, and your struct is actually invalid. If you want to define it in one statement it would be typedef struct node_s { struct node_s *next; int data; } node_t; That's a semi-acceptable method too, but I prefer a separate statement because if you deal with more links you don't need to repeat the struct keyword that many times.
For those interested in fundamental data structures and algorithms, I highly recommend "Algorithms + Data Structures = Programs" by Niklaus Wirth. It is the seminal authority on the the topic.
Link pls
@@elitearmedforce Here you go: en.wikipedia.org/wiki/Algorithms_%2B_Data_Structures_%3D_Programs
Agreed. Reading books is a more efficient use of your time, and the best way of not loosing time with this kind of inefficient clickbait.
@@leninalopez2912 If you think reading books is efficient for your learning then you don't know what is efficient learning at all and haven't ever been learning efficiently yourself. Reading books is the LEAST (time) efficient way of ALL to learn stuff. It is thorough, yes, but that's all there is to it. Reading can *never* be more efficient than watching a video(Audio+Visual input) if we assume both have the same quality content. When you read you do indeed go into more theory and detail, but what is the purpose of that if you can't apply 80% of stuff that you read in practice("Tutorial Hell" from reading books is *magnitudes* worse than "tutorial hell" from videos, I can explain the reasoning if you are interested). You can't really say "books" and "efficient use of your time" in one sentence as this is just a contradiction because of the reasons above.
I am 100% sure that I can outlearn(have better learning results than) *every single person* who studies by reading books, by studying using a video material with the same quality instead, for example.
I really dislike people who haven't really been competitive or (really) care about efficiency, yet talk like they tried every single thing and know the best. No, you just went with what first worked for you(or preference), blindly thinking it is "efficient", without ultimately seeking for what is actually most efficient in reality.
Efficiency is not about optimizing your own preferences, it is about being competitive and adapting to the best environment possible. You can say fast walking is more efficient than normal walking, but I am saying that I will rather run, even if I never ran in my entire life, if in the end it will be more efficient, that is the difference.
@@twothreeoneoneseventwoonefour5 it's not about efficiency, that's simply a dumb perspective. Learning is about seeing what you already know in a new light and not running ahead to something else. For good reason the advice is "_stop_ and think!". In order to really think, it's best to first stop and reconsider if it's a good idea at all. Wirth was a mathematician first, and I see that in his writing. It has proofs of fact, mathematical proofs, not just proofs of concept. The kind of sloppiness of "just hacking away at it" and "being efficient and productive" without evaluating the goals of your own enterprise is exactly why the tech industry is at the point where it is today: stalled for ideas, producing buggy messes and completely separated from any critical understanding of it's own creations
Due to caching linked lists are usually slower than a simple contiguous vector.
Bi-directional Linked lists typically require 3x the number of bytes as a simple vector structure, so they hurt performance for even medium sized lists.
Truth hath been spoken
I wonder if it would be worth it to first copy all of the data into a contiguous array from a linked list before operating on it with a complicated algorithm, and then copying it back at the end. Somehow this sounds better than running an algorithm (like sort) on the list itself.
@@MrSephirothJenova The best use for a linked list is when you need to add or remove an element in the middle of the list, then it is great!
@@softwarelivre2389 but to remove from the middle (at least by index), you must traverse the whole list. The cache thrashing that results makes it so much worse than an array/vector that uses memcpy.
@@colejohnson66 good point, but sometimed you have to merge two linked lists at a position (put one in the middle of the other), which can be very fast in the case of linked lists
I left a PR that fixes a couple issues with the code. As Alistair Foggin said, there is a memory leak in removeNode, and the call to malloc() in addNode only needs to occur in one place. Additionally, as noted by Mohammad Salman, the insertNode() function does not interate through the list each time the position variable is decremented. This means that insertNode only ever inserts into the second position.
This guy is so bad at coding I can't believe the support he's receiving.
@@user-dp3zr1qe3s Mistakes are made.. smh.
I read the insertion loop over and over again trying to understand what was I missing, to finally realize that there was an error
@@ignacio_falco lol. So did I. Thought I was going nuts and almost called in to quit my job as a coder lol
@@user-dp3zr1qe3s I totally agree! Can't believe it either! 😳This video should not be recommended how to learn to implement a single linked list in C. It's a big mess, riddled with serious bugs and reveals a totally sloppy attitude towards clean working... The only thing that is of any use is the graphic explanation. Sorry to say that. 😐
In removeNode, you only free the removed node if it is in the middle or the end of the list. If it is the head, it is not freed so there is still a memory leak. Other than that, this is a fantastic tutorial! Keep up the good work!
Crap. Feel free to put in a PR on the github! :D
@@LowLevelTV Also forgot to free the list on exit.
@@kuroikenjin7652memory is no longer used when process exits
Nice flex 💪😎 🤓
@@xBZZZZyt Still a memory leak.
My favourite implementation of a linked list is a circular doubly linked list. Here the nodes have 2 references, previous and next. The head of the list is not a part of the list (its data is unimportant), instead it points to the first node and the last node as its next and previous references, respectively. If the list is empty, then the head points to itself on both previous and next. The reason why I like this is because, being circular, there are no edge cases. Removing the first element is the same as removing an element in the middle of the list or the end. Inserting an element is the same regardless if the list is empty, you are inserting at the start, end or middle. This simplicity makes fixing bugs and adding more functionality to the list much easier.
You don't need to branch if head points to NULL, just assign head to the new node, if its NULL so be it.
Also position 0 should semantically mean "before the first", it seems now you can only insert after the first element (you can add though but add can be implemented in terms of insert as a simplified function)
I would definitely agree that a programmer should know and be able to implement a linked list but that being said, linked lists are almost never the best solution to a problem. Due to the expensive heap allocations, CPU cache, deref iterations and a bunch of other things linked lists are generally "slow as shit" except in a few very rare cases
Sadly true, depending on language 95% of this kind of thing should be array or vector.
Sure and agreed. But is an easy exposition and serves equally well as material for clickbait...
Depends if performance is your goal. One major advantage of linked lists is that they're dead simple and can be optimized for all kinds of tasks.
If I'm in a language that has a decent set of data structures*, then I don't usually use lists. I tend to use them in C because they're quick to write and debug.
* Besides Lisp languages, which usually have a full set of data structures but use lists for all kinds of stuff
@@jeffspaulding9834 A linked list is definitely not simpler than a Array based list / vector. As long as you don't have a rather large list where you constantly remove elements from the middle, a vector is probably faster
@@darkfire2703 Depends what you're doing with the list. If you're adding and removing from both ends, a linked list is simpler than an array.
As far as faster, I don't debate that.
I think to append a node in constant time, we can maintain a tail pointer. So in push() we push new node into head pointer if it's null and make tail equal to heads next, else we push new node into tail and make tail equals to tails next.
Doesn't matter how long I've been programming, there's something about implementing and viewing the code for a linked list that's just fascinating. Great stuff. I was taught to always have a head and tail node. So I always code that out of habit. It does complicate the code just a little bit though.
What's the use of the tail?
@@MECHANISMUS so when you do an insert at the end of the linked list you do it in O(1).
@@MECHANISMUS I believe that a doubly linked list. Which as the other user stated, gives you access to more efficient opporations because you know the end and beginning of the list. So you can trace inwards with both at the same time, cutting any O(N) time down and as he said, insert into list O(1) time.
@@zenverak having a head and tail node doesnt always imply having a double linked list. But it will make implementing a queue or stack easy because you will always have access to the head or tail with O(1) time.
Having a tail is essential for FIFO
im learning how to code using the cs50 course on youtube and the section about linked lists absolutely stumped me. After watching this tutorial i realized my understanding of the syntax in C was wrong and i finally figured it out. thank you so much.
I use technology every day, and in the background; all of this code is running. Someone sat for hours, days, weeks, even months and years in some cases, to create the code for all of it to happen and work without bugs. It's crazy to think about it in terms like that and I guess programmers are really sort of the unsung hero's of the technological age. Thank you!
I use extra pointers. One for the last and one for the previous. It allowed me to walk forward or backward and I didn't have to walk the list to get to the end. It was especially helpful for large lists. The code to keep the pointers current is less than one might expect.
That’s not singly linked.
If you have very large lists you should either:
a) Consider using a different data structure, maybe a map or self-balancing BST. It really depends on what you're doing
b) Doubly linked skip list, requires a sorted list of course.
@@thev01d85 I first worked with linked lists in the early 80s in a business environment. They served most purposes.
@@glennmiller394 So... you're telling me linked lists are good for large sets of data because you used them a long time ago?
@@thev01d85 I wrote my first linked list in C in 1986. I haven't written one lately using C++. It provides functionality to avoid that.
When you decrement position in the insert function, you aren't moving the current pointer
When is it useful to add a pointer to the previous node as part of the node structure? Also, should we, or when should we create another structure for the list that links to the functions we created that are exclusively designed to work with the list instead of using a node pointer as the list?
There's an issue with the insertion code, it's missing an instruction on the initial loop to update the `current` reference, just like that:
while (current != NULL && position != 0)
{
position--;
current = current->next;
}
Without this, the code will just run down the position, but the item will always be inserted as the next from the head, since the current never changes. Other than that pretty cool video, thank you!
Thank you for making sure I am not crazy! I was thinking that. He doesn't ever check any other positions other than the case it works.
Adding a tail pointer makes insert at end O(1) complexity
I noticed your new use of transitions since I’m a part time videographer as well. Your production quality is up from last year! Keep it up. I’m loving the consistency!!
In the insertNode function, the while loop doesn't update current node so when insert you will all way insert into position 0 (right after the head node). I think you should add current = current->next inside that loop.
Edit: It should be like this
while(current != NULL && --position != 0){
current = current->next;
}
This is true. I was wondering about it and cross checked w GitHub code. Seems same there and updating the current makes it perfect! Thanks for putting that up.
Thanks I was wondering how it went over the list. It only worked when pos = 0 which was the only thing tested.
17:20 Can you please tell my how this while loop change current from point to head, and end up pointing to the node at position, when something like current = current->next is not explicitly defined? Thank you for the great vid.
Theres an issue in the insertnode function!
You move position but dont update the new current so you will always insert data into position 1 (after current)
You need a prev node to update prev and current along with position--
@@kingbababouille That's what I thought would happen, but interestingly, the code provided in the video works exactly as it should. In fact, when I explicitly add the current = current->next line, the code breaks. I don't understand how the head pointer changes still.
Man this content takes me back to first year of college, having to create all these different data structures from scratch. Good times.
A lot of people using high level languages dont realize how important it is to have a good grasp on how all this works behind the scenes.
To anyone reading the head pointer is the front of the list. He said it correctly at first then when testing the add function he switched his definition implying the head pointer was at the end, and then switched it back correctly when testing the insert function. This might be confusing for people trying to learn.
Hi, one question why arent you changing *current in the while loop of the "insertNode" function? I think that the function is inserting the node in the same place every time, after the *head.
Havent ran the code before but i think this is the way of doing it:
while (current != NULL && position != 0)
{
current = current->next;
position--;
}
Thanks for the video.
I have a task manager app that I implement in any new language i learn. It uses doubly linked lists with sub-lists available for any task. It puts me through tha paces of multiple features of any language: Data structures, pointers, memory allocation, functions, classes (if OOP), file I/O, user interface.
With how horrendously bad linked lists are for cache efficiency and auto vectorization the thumbnail is actual clickbait. I thought I was about something interesting
This was so good. i really have to learn to code. Lists look like a lot of fun. This comment section looks like its about:set to cache on fire
}
I love how clean this tutorial is. Keep it up 👍
Thank you! Cheers!
“Clean”? Are you serious? 😳It’s a whole mess mixed with pretty serious Bugs in it! Almost every rule of good software development is violated in this course! It contains wrong semantics, memory leaks and shows a ridiculous bad style of coding habits! Such a basic thing as a common Data container has to be robust. My advice: You should better watch videos from people who work clean and are aware of their responsibility for their big count of subscribers. 🙄
A fun followup to this is a fibonacci heap, which heavily uses linked list concepts but is O(1) for many of its operations!
Please continue with this series.
why are we appending to the front? why are we using void pointers? why are we nesting if + switch instead of using a guard clause or just letting the menu default? we are duplicating mallocs in different branches of addNode, we have a memory leak in removeNode, we're not handling negative values for position NOR EVER MOVING THE CURRENT NODE in insertNode (no wonder it literally doesn't work)
this implementation is borderline insane and it's even crazier that you had the balls to upload this
Why not use void pointer?
@@paradoxicalcat7173 it is unsafe and unnecessary. he already has a struct to represent the allocated memory with...
Never in my programming career have I ever used/needed a linked list. These pointer structures are super slow. Maybe good for teaching, but useless in practice. Unlike the linked list, I was not taught in school that accessing an array instead is >1000x faster, and accessing an array on GPU adds another 100x.
If in a job interview I would get asked how to write a linked list or other leetcode crap, I would just leave the room and not waste any more time.
There are real world use cases for linked lists like LRU caches. They also use a hash table to lookup the nodes of the linked list in constant time in order to avoid the slow linked list traversal. The linked list is used for fast removal and insertion.
I don't know if you intended it to sound this way, but it sounds like you're bragging about how limited your programming career has been.
@@jeffspaulding9834 You're right, who am I to judge about the usefulness of linked lists. I don't even have any formal education on CS.
I'm just the one solo developer who writes the answers on Stack Overflow, and whose software is somehow ranked at the very top in GitHub topics. I guess I should go back learn linked lists and leetcode to be able to write super slow code like everyone else.
@@psychoinferno4227 I know. But linked lists and other data structures are taught in a way as if they always were the superior choice, without ever considering performance. What then happens is that people use them in places they don't belong, and end up with poor software without even a clue what's wrong.
I've once had an assessment center challenge to write Conway's game of life in a couple minutes. I was the only one who got it working in time, and the employee seriously suggested I should have used linked lists instead of arrays. You can't make this up.
@@ProjectPhysX, I agree completely.
Theres an issue in the insertnode function!
You move position but dont update the new current so you will always insert data into position 1 (after current)
You need a prev node to update prev and current along with position--
i made this comment
1:11, If you do this with offset pointers instead you can also keep the benefits of a buffer (access by index), something like: link = head + link->next will get you the next link in this scenario. UX side you still need to loop through the remaining list items to update their positions (not their indices, the ordered positions as far as the user is concerned) when you add/remove items but that's still much cheaper than actually moving every item in the list. Since both index and position can be attached to UX elements and only the position reported to the user you can just grab the index/offset (depends which you stored, both can be converted to the other using sizeof(link)) and add that back to the head element to get the intended link. Comes at the cost of memory but I'd argue speed is more worthwhile in all cases for this particular case.
Linked lists are a great exercise on how to use pointers, but they are also old data structures that do not work very well in modern computer architectures.
They are relics of the past and have very few remaining use-cases where they are superior to vector-style arrays, even taking into account the reallocation+move times.
Linked List is the Latin of data structures. It exists by being dissolved into other, more complex and useful data structures like LFU caches for example.
"they are also old data structures that do not work very well in modern computer architectures."
Cache locality issues ?
Sometimes they're still the right tool my man. E.g. what do you do if the list items are not movable or copyable?
What does the double asterisk mean in the second parameter of main and why does main need parameters here?
That is a pointer to a pointer to a char. Meaning it stores the address of a pointer to char which itself stores the address of a char.
It is used to store an array of strings that can be accessed using only a single variable. The ammount of strings is stored in the first argument.
char *argv[] would be equivalent (since the compiler turns it into the other version automatically), but shows better what is happening.
In case you don't know those strings are usually what you write behind the name of the executable which looks about like this: executable arg1 arg2 arg3 ... argN
The name and path of the executable are usually given as the first argument automatically.
@@janb.9425 Well I can't believe I never knew that, there's always more than one way to skin a cat...
Me: Seems easy enough, I'll code it up in Rust real quick.
Rust: Imma about to end this man's whole career.
I used to use single linked lists that were bidirectional with a single pointer (to save memory, you xor the current and next values, and you can go through the list in either direction. I used that on a device with less than 64K to save memory.)
at 8 minute, you allocated a new Node object, and then later on set the "next" variable to NULL. It works in your case, but for real life cases it is strongly suggested (at least from my view) that you do a memset(new, 0x00, sizeof(Node));
I've never done a huge amount of C so I was secretly proud of myself that I spotted the bug you found at ~20:08, when you originally typed it.
Just discovered this channel as a CS student that loves linked lists since he learned about it at the beginning of the year.
Talking about addNode, isn't it just better to straight up declare the list as a NULL then just adding nodes from there ?
Like this :
list_t *addNode(list_t *list, int data)
{
list_t *newNode = malloc(sizeof(list_t));
newNode->data = data:
newNode->next = list;
return newNode;
}
int main(int ac, char **av)
{
list_t* list = NULL;
list = addNode(list, x);
list = addNode(list, y);
...
return 0;
}
I've been taught that way and it avoids checking if head is NULL bc you'll always have NULL at the end of the list and there is no need to really manage the head pointer
I know i didn't check my allocation but i mean, just for the example
Currently having to do a .cpp paper for an engineering degree and I find everything you've done in c very helpful. I learn best from seeing functional examples with explinations and your channel is great for it. I do have a code example from my course that I would appreciate an explination for though, as I can't make heads nor tails of what it is actually doing. If you want a picture I can send it to you, basically it is allocating information in a table structure, but in the book (learning through correspondence) it isn't clearly outlined.
hey just wanna let u know im watching ur channel since last year and i really appreciate ur content, thx for making quality videos
haha love that realization at 11:23 that your code is gonna crash, then being surprised that you actually wrote the correct code the first time around. Relatable feeling.
one should probably use array instead (i know only 2 very specific cases where linked lists are better, sort of). arrays are also quite flexible: you can have a "fat pointer" or store header directly on the array, you can have capacity variable to reduce allocations or you can have no extra capacity and prioritize space efficiency. arrays are far better than linked lists for pushing a new element to the end and popping last element (because they normally don't need new allocations for that), they have fast access and sorting and so on. even insert in the middle of array is often faster than insert in the middle of a linked list (modern chips are good at copying contiguous chunks of memory).
What's the point of the 'while' loop in the 'insertNode' function? It just decreases the position until it reaches 0, you never modify the 'current' pointer and you don't cover this in your test. Also, the signed integer is not a right choice here - passing '-1', for example, can be very bad.
1:08, the last node doesn't have to point to NULL, NULL is just an easy exit condition but you can also just check the pointer you have does not match the one you started with, this allows the option of a semi-permanent loop that doesn't check for said match since it only needs to process the nodes, this is particularly useful if you 're making a multiplayer game or even just physics, the players/"actors" would be nodes that need their position constantly updated even if they're not rendered during the update, a linked list of nodes that circles on itself would allow the loop to be optimised to just check for game exit instead of both that and a NULL pointer
This is also how Linux kernel organizes tasks
6:20, nope, not necessary, you can maintain 2 types of lists for the same nodes, one is a simple array of pointers to nodes int the order they are declared to be, the other is the linked list, when you want to append a node you select the last node pointer in the array and just set it's next value to the new pointer and add the new pointer to the end of the list (increasing the count while you're at it), when removing by index you load the node from the pointer list and make the nodes it's linked to link to each other instead, then you shift the pointers in the list up 1 and iterate through them all to correct their stored index, when inserting you likewise load the node already stored at said index and set the new pointers next to that node and update the previous node it was connected to, sure this method is a little more memory hogging but in most cases that is less an issue than the speed
A fun challenge to expand on this video is indexing the list. Give the node struct an index integer. Makes it easier to reach a certain element n by just reading the index. It also completely changes how you add, remove or insert elements into the list, since all indexes from that point on have to be adjusted.
This is a good reason to allocate it contiguously, then the pointer for the index becomes: root node pointer + size of node * index. This is much faster than jumping through the links, but of course, it goes against the point of having a linked list to begin with (why have next-pointers at all if the nodes are already right next to each other in memory, AKA an array).
@@theRPGmaster Yup. Although one could argue that the point of linked lists in C in the first place is simply to have dynamic arrays.
Though if you want a thing with dynamic size, you could make a dynamic array.
It isn't that hard to do. You just need a structure with a pointer, the count, and the max size, and if you want to add to the array and the new size will be larger than the allocated space, you just use realloc and decide on how much to increase it (you could double it until you have enough, you could add some number to it until you have enough, or you could do some clever math, it's up to you.) Then maybe consider shrinking it if you don't need all that space anymore.
The advantage of using a dynamic array instead of a linked list is that you have all the data in one place instead of scattered all over the place (unless you use an arena allocator or something), also the data will be easier to traverse, and you may need less allocations if you do it right. Though the linked list has one advantage... you can quickly and easily remove a single element in the middle of the list.
If you want to try it out, try making a string that you can print, append to, remove stuff from, etc.
Back in the days in the year 2000, I learned that in 11. grade at high school using Turbo Pascal. We had a really good computer science teacher then. We also learned to make tree structures in similar way....including sort and search functionality. I suppose such things are not tought in high school anymore since very few teachers know that stuff.
Also you could use `typedef struct node { struct node *next; int data; } Node;` to make life much, much easier when going certain number of nodes forward (`some_node->next->next->next`) without casting it to `Node` every time
While all the other physicist were specializing in their field, Einstein was specializing in none but watching all. It resulted in general relativity. To see someone so good that they can deduce so many coding disciplines reminds me of what Einstein did there.
while (current != NULL && position != 0)
{
position--;
}
shoudln't this loop also move current to current->next ? Otherwise we keep inserting the node to the head right?
unless i'm mistaken
I saw this and the 5 value issue causing it to close and the reuse of the same code in the add like right away.
yes this loop is useless, he forgot to update current
@8:45: Lines 19 and 27 (among others) are redundant. So this violates the DRY (Don't repeat yourself) rule! Why don't you separate the piece of code to allocate a new node (malloc) and first fill it with data and next to NULL and *then* just ask if head is NULL and if it is just assign this to the new created node?🧐 Sorry, couldn't resist - I'm German. 🥺
I was once forced to implement a cyclic singly linked list for a game I made in a fairly new language called freebasic. It was in its beta stage so you pretty had to code everything.
It was a nice mind exercise too.
Red-black tree best data structure >.> I've always liked how understanding singly-linked lists is essential to implement most other data structures, tbh. A lot of them are extremely similar in concept to a linked list.
In AddNode, the malloc, NULL check and data assignment should all be above the if statement. Code duplication can lead to errors if one copy is changed and the other is not.
nice! but I have to say there is an error in the function insert node function.
the current node pointer is not changed in the while loop.
one line should be added into the while loop to update the current pointer to the position where to add the new node:
current = current->next;
I don't understand the insertNode function.
In the first loop, position goes to 0, so haven't we lost the actual position where we were supposed to insert the element?
Also, the current pointer is always at the head is it not? So how can we accurately insert the node at the required position?
@@lennonmclean Nope, the function is just plainly wrong. We are not iterating through the list, we're just decrementing the position variable.
Yep youre right, he forgot to add current=current->next after position--. Also in that case you need to change while current->next not null because it can get to null if its the same number of nodes as psotion
We always insert at the start of the list.
you're right, he doesn't interate the current node when he decrements the position. He just doesnt notice the bug because he only tries inserting into position 0. I tried running the code myself and it doesn't work properly :/
@@lennonmclean Yeah, kind of funny that he only tried position 0. What a weird coincidence.
Love the videos bro, keep it up
Thanks, will do!
Usually when I make my linked lists I make a struct representing the entire list with a pointer to both the head and the tail, allows for o(1) adding and removal from both ends of the list ;)
You could do that but that costs additional memory - everything ha it's costs ;-)
Kudos on the LLL animation! It's really amazing
only took me 5 sweaty hours in adobe after effects LOL
@@LowLevelTV worth it!
Ironically I think that doubly linked lists are faster if you have a pointer to a specific node, since you can do it in O(1) time by simply connecting node->prev with node->next and updating the heads, rather than having to go through the whole list again to find the previous element which points back there. Addition to both heads is also O(1) if you keep track of them.
*By O(1) I mean that their execution time is constant as the data set's size increases, since they're operations where you don't need to create any loops, instead simply manipulating a few pointers.
Why at 9:00 you repeat the start of both if conditions while you could do it outside the if statement once?
So much of the data structure education I got in school went out the window when I got into embedded where node count (or maximum node count) is part of the design so it just becomes predefined array
He said it 7 seconds into the video, that's impressive.
Usually titles like that wait until the 75% mark to do that :_D
(love the content btw)
could you also store the last node in the stack to make appending O(1)? or is there a reason not to?
Is it important to put `return` at the end of the printMenu function, even if it's void?
Good for theoretic implementation and understanding of pointers, bad for practical applications minus few isolated edge cases. Even the creator of C said that arrays are better in any way as you don't need to traverse them to get to a certain element.
This new video format is amazing!
Glad to hear it!
You are doing an amazing videos! I would just suggest that if you want to append element in the list you could do it in complexity of O(1) by creating a pointer named “tail” which points to the last node. 😊
what about doing it like this:
```
void ft_lstadd_back(t_node **lst, t_node *new)
{
t_node *temp;
if (!lst || !new)
return ;
if (!*lst)
{
*lst = new;
return ;
}
temp = *lst;
while (temp->next)
temp = temp->next;
temp->next = new;
}
```
Yes at least this video indeed is amazing... ...amazing because of the abundance of serious bugs! Honestly - I don't want to be harsh - but this video is not really a good example to learn software development conscientiously. 🤨See I'm a senior embedded Software Engineer and such (actually simple) code would not have survived a code-review. Seriously! In my opinion this is *not* a good example of how to do clean software development. I'm sorry to say that. Hope he prepares better next time! Remember - a good preparation is 90% of success.
Oh right, my suggestion made no sense, this would not be O(1)
@@hanspeterbestandig2054 brother it’s possible to come across significantly less arrogant than you did here
@@LoveChaac Not only that, but he didn't even bother pointing out what was wrong...
@LowLevelLearning Thank you very much for all the amazing content you make.
I would like to point out that the insertNode function in your example does not work as intended, below is the corrected implementation:
Node* insertNode(int value, int position){
Node* new = malloc(sizeof(Node));
if (new == NULL) {
printf("Memory allocation failed
");
return NULL;
}
new->value = value;
new->next = NULL;
if (position == 0) {
new->next = head;
head = new;
return new;
}
Node* current = head;
Node* previous = NULL;
while (current != NULL && position > 0) {
previous = current;
current = current->next;
position--;
}
if (position > 0) {
printf("Requested position too far into the list
");
free(new);
return NULL;
}
new->next = current;
previous->next = new;
return new;
}
Ok, now try this structure in Rust. It is a really challenge xD
They are also a fantastic way for people to get comfortable with recursion, as any algorithm for a recursive data strucutre can be implented with a recursive algorithm.
@2:35 why is this a void* and not a Node* ? I mean the Poster pints to the next Node which is not an anonymous (void) reference but an concrete namely Node?
Yep - I think that would be a smarter idea!
There is always room for improvement! ;-)
Can u help us how to set C on Vs studio? I am a new programmer and i am learning, but i am lost using VS studio
Sorry I'm just watching the video and checking the code and I'm a bit confused.. On the InsertNode method, inside the while loop u're decrementing position without setting current to current->next, in this way whatever position you receive, current just points to head without moving... or am I wrong?
Very helpful! Everything i see a video from you i will save it so watch is again and again when i need it. Thanks!
You are welcome!
When trying to see if you can get your code to run the first time, you get an error and say, "Go ahead and include standard libs." Then you copy the text . Then you open a new terminal and are able to run the command again but without the errors. What are you doing here? I don't know how you got it running without an error and that's where I'm stuck at.
(A bit late, but for those curious)
He used: #include
This command tells the compiler to include another file in compilation. The one in question being stdlib.h. often called the "Standard Library".
Without it you don't have easy access to commonly used stuff like memory allocation, random numbers and converting variables. There are also other libraries like which gives you mathmatical functions like cos, sin, floor, log, etc.
Libraries are an important element of coding stuff you don't know how to do from scratch yourself and provide many shortcuts. Especially in embedded systems do we use libraries a LOT to make interacting with certain things a lot less headache inducing!
What is the issue at 8:36 that you need to move node * x = NULL, before malloc?
The issue is that you can't "return new;" because it's out of scope.
Try and you will se by yourself ;-)
what is the difference between linked lists and the list-object? As far as i can see they both have the same funcionality
Amazing . Dont stop making such videos
i am new to c. Shouldnt head in the add function be a pointer to a pointer as its equal to new, which is a pointer?
Can you not use a external script to define main() so you would not need so many parameters and everything else at once?
I like the use of the void*. In the past, I have always typedef a Node ahead of defining it and used Node* in the Node. However, the void* makes more sense.
For the add method, is it really necessary to separate between and empty list and a non-empty list? Is it not enough to do what you do for the non-empty case in both of the cases, since head == NULL, and therefore new->next = head is the same as new->next = NULL?
15:55 I was just screaming at my TV “Memory Leak!”
0:07 If I were to give a wild guess, I'd assume that a singly linked list is a linked list but where only the next node is stored for each node instead of both next and previous nodes being stored. How close was I?
This comment was both a wild guess and a way for me to find this video again so I can watch it later, assuming someone replies to it!
Greeting From Venezuela I've learned alot with you through this couple of years. Thx for all
Simple and to the point, nice video.
What do you use to draw on screen? Are you using a touch screen laptop or a separate wacom tablet thing?
What about just using a mouse? ;-)
I am kinda confused with the "head" being the latest added item on the list (behaving like a stack maybe?)
I love these kind of videos from you keep on going. I try to recreate everything you do myself and I leave every of your videos a bit smarter. Thank you a lot keep on going!
...that said and hopefully you realized, that his code is full of (partial serious) bugs? 🙄😳 Furthermore, the presence of a lot of *redundant* (with its rendundant bugs) code reveals that this guy has no real practice about programming and hence as an total novice he should not try to teach others in this matter... we’re here in Germany are used to say: “Schuster, bleib‘ bei Deinen Leisten“ 😉
If you're going to make bigger projects, did you c++ and and C++ std::vector because vector doesn't sig fault if you are handed invalid user input.
Super tutorial, I am now learning to handle frees with new best friend Valgrind.I have a question: what are the actual use cases for linked lists in a real world program? I am only learnig the basics now but I would like to know when Is the best and optional situation for when to use them, especially considering performance and fastness of the program one is writing. Probably It would make a nice video this topic, but thanks in advance for the answer!
Hi! in real world, it is quite rare to use a real linked list as it is quite slow (huge allocation overhead).
However, you can cheat to remove this slowness.
In c++, if I remember correctly, the std::deque is a linked list of enormous arrays, meaning you have to allocate array after array without having a really big allocation issue.
I think of it more of a way to extend an existing array rather than being the sole container.
same language, still c++, std::vector (allocated array) is almost always faster than std::list.
However, when you have to keep references (or pointers) to the object, linked list are actually the best. if you remove a node from the list, it only invalidates the pointers (or iterators) to the specific node. same goes if you ever add a node.
If you ever need to keep huge quantity of pointers to members of an array which could reallocate at anytime, I would suggest using a linked list if the array is not in a critical chokepoint.
Still the same pattern though, one allocation for a pool of nodes I would pick from to reduce performances drop.
You could still have better performances with an array, however the code required to make it work would probably require way more memory.
In production code, I actually never used linked list in its pure form (std::list) but used them in the hidden form (std::deque).
I think knowing how to use a LL is vital, but for environments that care about performance? Just use an array. Far less memory overhead, random access, and faster iteration.
hey man, mind telling me what font is your vc code?
I love how the first video that pops up next is titled " Why You Should AVOID Linked Lists"
Isn't using the "return" keyword at the end of a void function unnecessary?
What if i add two identical data and try to remove it from the list