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
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!
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. 😐
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.
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.
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 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.
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 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!!
“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. 🙄
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.
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.
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?
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.
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.
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.
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.
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
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.
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.
@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 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.
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.
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!
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
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));
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
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
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 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“ 😉
@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?
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.
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.
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?
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?
Easy to understand, please continue Binary Trees and then Graphs 😉👏👏👏. It would be usefull that you explain in which situations you have used those data structures in your projects. Thank you 💪
Sorry I have to disagree. This code is a pure mess and full of serious bugs! Didn't you recognise this? 🥺😮💨 Well, I hope he prepares better next time! ... and I hope he realizes his responsibility to his 156k subscribers to want to teach people something solid here.
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).
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 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.
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.
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.)
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 :/
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
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.
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.
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?
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.
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.
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.
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!
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).
8:22 wouldn't it be possible to have just the second case to handle adding to the start of the list? If the list is empty, then the head node is set to NULL, therefore "new->next = head" would give the same result as "new->next = NULL", although I'm unsure which one gives better performance. EDIT: on my computer after running some tests, the "just the second case" variant gave a performance improvement of about 0.5%, as well as the fact that the code is shorter and there's less repetition.
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.
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.
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 ;)
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--
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.
@15:57. Why you you set a local variable to NULL which is not used anymore in the following program flow? 🤔 the local variable will be destroyed afterwards due to the stack unwinding upon the functions exit... Are you aware of the difference between local and global and parameter values in concern of their lifecycle and visibility? 🙄 Stack, Heap and the global storage (aka as the “data segment”)
this is the video that got me to nearly entirely stop watching this guy I thought it was just a one time thing when he malloced and checked the pointer for null twice for every case of the 'if' statement in the first function he wrote, but turns out that was just the least of the concerns with this video any first year college junkie can write a linked list in C better than this and with no memory leaks
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.
Just questions I m maths but not programmer so can we make in c/c++ this program: List(objectType, Type* nexy){ objectType_data data; List * nextNode; objectType * ()next;}
It would be better if you just explained using words ;-) As far as I understand, you want so list could store some object instead of a integer number? That is possible! ;-) typedef struct { void *next; void object; } Node; The problem with that is so we don't know how much space would that object occupy in space, so we should use a pointer to a object instead of a object itself - all pointers have the same size: typedef struct { void *next; void *object; } Node; After that, code would became a little bit more complicated but still doable!
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
Loving this videos. This one helped me internalize more what I've been learning at 42 School. Could you give a try to lists with void type data? That's where it gets messy real quick for me
I remember this topic was an exercise in my C programming class exam. there were like 11.5/20 points for this exercise, I had 16.5/20 final mark. I don't remember how did I do it, but you refreshed my memory, thank you sir!
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
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.
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. 😐
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.
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.
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 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.
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 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!!
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. 🙄
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!
When you decrement position in the insert function, you aren't moving the current pointer
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.
hey just wanna let u know im watching ur channel since last year and i really appreciate ur content, thx for making quality videos
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...
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?
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.
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.
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'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.
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.
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.
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
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.
Me: Seems easy enough, I'll code it up in Rust real quick.
Rust: Imma about to end this man's whole career.
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.
@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 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.
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.
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.
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
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));
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
Greeting From Venezuela I've learned alot with you through this couple of years. Thx for all
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
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
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!
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“ 😉
could you also store the last node in the stack to make appending O(1)? or is there a reason not to?
@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! ;-)
This new video format is amazing!
Glad to hear it!
Why at 9:00 you repeat the start of both if conditions while you could do it outside the if statement once?
Kudos on the LLL animation! It's really amazing
only took me 5 sweaty hours in adobe after effects LOL
@@LowLevelTV worth it!
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
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.
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)
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...
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?
Adding a tail pointer makes insert at end O(1) complexity
Love the videos bro, keep it up
Thanks, will do!
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?
Can you not use a external script to define main() so you would not need so many parameters and everything else at once?
Is it important to put `return` at the end of the printMenu function, even if it's void?
Easy to understand, please continue Binary Trees and then Graphs 😉👏👏👏. It would be usefull that you explain in which situations you have used those data structures in your projects. Thank you 💪
Sorry I have to disagree. This code is a pure mess and full of serious bugs! Didn't you recognise this? 🥺😮💨 Well, I hope he prepares better next time! ... and I hope he realizes his responsibility to his 156k subscribers to want to teach people something solid here.
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.
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 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.
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 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 ;-)
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.)
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.
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
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.
15:55 I was just screaming at my TV “Memory Leak!”
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.
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!
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.
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.
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.
Amazing . Dont stop making such videos
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!
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 is the difference between linked lists and the list-object? As far as i can see they both have the same funcionality
8:22 wouldn't it be possible to have just the second case to handle adding to the start of the list? If the list is empty, then the head node is set to NULL, therefore "new->next = head" would give the same result as "new->next = NULL", although I'm unsure which one gives better performance. EDIT: on my computer after running some tests, the "just the second case" variant gave a performance improvement of about 0.5%, as well as the fact that the code is shorter and there's less repetition.
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.
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?
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.
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 am kinda confused with the "head" being the latest added item on the list (behaving like a stack maybe?)
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 ;-)
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
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? ;-)
Can we make heterogeneous data structure linked list like :
Object1->object2->…->objectn with void* pointer rather than typed pointer ,
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.
Isn't using the "return" keyword at the end of a void function unnecessary?
hey man, mind telling me what font is your vc code?
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.
I love how the first video that pops up next is titled " Why You Should AVOID Linked Lists"
@15:57. Why you you set a local variable to NULL which is not used anymore in the following program flow? 🤔 the local variable will be destroyed afterwards due to the stack unwinding upon the functions exit...
Are you aware of the difference between local and global and parameter values in concern of their lifecycle and visibility? 🙄 Stack, Heap and the global storage (aka as the “data segment”)
this is the video that got me to nearly entirely stop watching this guy
I thought it was just a one time thing when he malloced and checked the pointer for null twice for every case of the 'if' statement in the first function he wrote, but turns out that was just the least of the concerns with this video
any first year college junkie can write a linked list in C better than this and with no memory leaks
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.
Simple and to the point, nice video.
Just questions I m maths but not programmer so can we make in c/c++ this program:
List(objectType, Type* nexy){ objectType_data data; List * nextNode; objectType * ()next;}
It would be better if you just explained using words ;-)
As far as I understand, you want so list could store some object instead of a integer number? That is possible! ;-)
typedef struct {
void *next;
void object;
} Node;
The problem with that is so we don't know how much space would that object occupy in space, so we should use a pointer to a object instead of a object itself - all pointers have the same size:
typedef struct {
void *next;
void *object;
} Node;
After that, code would became a little bit more complicated but still doable!
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
Loving this videos. This one helped me internalize more what I've been learning at 42 School. Could you give a try to lists with void type data? That's where it gets messy real quick for me
I remember this topic was an exercise in my C programming class exam. there were like 11.5/20 points for this exercise, I had 16.5/20 final mark. I don't remember how did I do it, but you refreshed my memory, thank you sir!