Learn the basics of Linked Lists. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell. www.hackerrank.com/domains/tut...
You know that moment of satisfaction when you finally understand something? I got it from this video. I've spend so much time watching my lectures, looking at tutorials and explanations of LinkedLists and never really understood it. I decided to write you the code and try to explain to myself what each line meant and when I got stuck, listened to you explain it with the little diagrams and finally(!) understand what on earth this node and head and next thing means. THANK YOU.
@Ella Blun spot on. It's called removal of bias Very effective tool. Sad how we humans are literally built to doubt every damn thing unless reinforced by multiple sources But it's the reality we must live with.
Gayle, if you ever see this, I really love the way this mini lesson is organized and delivered. Very helpful I thank you I am passing a class because of you!!!
Thank you so much. The visual representation that changes with each new line of code is so helpful for a concept like this. Code for nodes can often look kind of cryptic without a visual representation of how things move.
@Peterolen i have no idea why that person said that. linked lists absolutely have their place. this is like saying "You probably shouldn't be using a _hash table_ for this." Well, if you just need to store a list of things, then yes, you dont need a hashtable. But if you need a quick mapping, 100% use a hashable. All data structures have their uses and strong points
@Peterolen But an ArrayList is just an implementation of a linked list. I don't really see it as different. However, if we treat them as different, I agree with you. I can only remember using LinkedList (the data type) like once lol. Most of the time i used ArrayList. But to me both of these are linked lists (the concept, not the data type)
I have been looking for crystal clear explanation to algorithms such a long time. Finally I landed up on right place. What a diligent explanation. Learned a lot. Splendid. No words to appreciate further.
Really amazing tutorial on Linked lists, thank you!! Just want to add why accessing array is faster because its elements are always stored in contiguous memory locations this is kind of its disadvantage also as you need to have in advance that contiguous chunk of memory in advance. Feel free to correct me if I am wrong.
The one thing I have come to find out about all these data structure explainations on youtube is that only a hand few will ever give you an actual REAL life damn example of where and HOW it is used so you can actually make sense of it all. It makes a HUGE, a HUUUUUUUGE difference.
Linked lists are one data structure I really understand with not much of a problem. Although pointers are still a struggle for me, the linked list makes a lot of sense.. I guess practice, practice, practice will help!
Great videos, I have been watching some and I really like the way you draw at the same time you show the code. They are short and straight to the point. I would just like to point out for future viewers that in C/C++ if you do not explicitly delete those nodes memory will be leaking.
Yes. While using C/C++, after deleting a node you also need to free the memory which was allocated to the node. The programmer is required to handle memory management in C/C++.
@@TheKhakPakflyest Java has the garbage collector and any time it sees that an object can't be reached, like in the video where we skip over that Node object, it automatically deletes the object and frees up the space. Something C++ doesn't offer ;)
Thanks for the lesson! It really helped me understand the code much better. Also, I do believe you have a problem with your append method. Your linked list will end up adding the first element twice.
The deleteWithValue(int data) function will throw NullPointerException when the element does not exist in the LinkedList. For Example, LinkedList: 7 (List has only one Node, I.e. only head node with value 7) And, you try to delete the node with value 5.
Appending a node to a linked list doesn't have to be O(n) if we keep track of the `tail` node as well as the `head` node. But very well done explanation as usual, Gayle! Your content are always such confidence boosters!!
@@saveerjain6833 It's not doubly because doubly linked lists have a pointer to the previous and next nodes. To Append at O(1) all we'd need is for the linked list to have both a head var and a tail var. By keeping track of a tail node, we make appending at the end O(1) because we have instant access to the tail node as well as allowing us to assign the new tail node and set it to keep track effectively. Then by making it into a doubly linked list this makes searching faster do to our doubly linked list allowing us to search both ends of the entire set to quicken searching. so having a tail node by the linked list definition does not make it a doubly linked list. It's the nodes themselves that have a pointer to before and after nodes that makes it doubly linked. I hope this makes sense.
Appending and displaying both recursively or just with a loop I practically have down. It’s the destructor and the delete() methods in c++ where the struggle kicks in a bit
Minor correction with the function: deleteWithValue (int data); Change: Move the special case if statement completely to the end of the while loop. Reasoning: If the head and the next node has the same value and equals the data value. The next element won't be deleted. So the special case should be after the while loop. Correct me if I'm wrong. Example data for the original function to fail : 10, 10, 20, 39, 48, ... data = 10
Hey, great video! I was just wondering, however, when is using a linked list actually useful? Since for most operations it requires linear time, versus an array which requires constant time for most operations, what is the main advantage of using a linked list versus an array?
My main appeal is that it's dynamic and the memory isn't assigned when compiled, like an array. An array has to be whatever length you initialize it to, but you can continually add to Linked Lists. The reason is that arrays use memory locations right after each other, so the computer needs to know how far to go before stopping. The Linked List uses the a memory address, so as long as it knows where to go, it doesn't need consecutive memory locations, and be continuously added to without overflow.
This is super clear to me, and I'm briefly flipping through data structures since someone told me I should learn them to apply for work. I understand how it's set up in Java, but how would these be implemented in Javascript outside of DOM?
That is an amazing explanation. I have two questions 1. Does the deleted node garbage collected? 2. How to delete a node with duplicate data. I.e.If there are multiple nodes with same data and we want to delete the last data Node. ? How do we differentiate the two nodes with same data ?
Abd-Elrhman Rizk lmfao. I thought the same thing and wondered if i was the only one who enjoyed that sound until I went to the comments section and saw this. I'm glad i wasn't the only one. Lol.
Thanks for the video. Just wondering, would it be fine to have a contructor in LinkedList, that would take a node as a parameter, and allow you to create LinkedList objects? Or maybe it's useless?
I've seen other implementations that have a tail Node that points to the end of the linked list, making appending an O(1) operation. Why is this not taught in this video?
Can you introduce another node in the Linked List class that will remember the last member we add, something like tail, and when adding you just add to the tail and make it O(1) instead of O(n) ?
Linked list are used on existing objects like Bags or even implemented in the bag itself. Is there a name for things like Linked List? I think they are called sorting algorithms..
Nice tutorials. Just a small note, maybe for prepend method, you should check for null head and assign it the new value, rather than creating a new node and point it to null. Again, it totally depends on scenario, but you considered it for other methods, so thought to point.
One question. if I make use of a temporary object to store current node in append function, then I won't need the LinkedList class containing head separately. I can implement it using just one class. I will use that temporary object to reach the end of linked list while the head will remain the same. Is this correct?
Simple question about creating the LinkedListClass. In oracle when creating a class its needs to have the same name as the CLASS FILE name. So how to circunvent this problem.
It's a very good video. The method deleteWithValue ... when you have a LinkedList with headvalue0 | linkedToNextValue1 -- value1 | linkedToNextValue2 -- value2 | linkedToNextValue3 -- value3 | linkedToNull and you want to delete value2, you go to value1 and set the former "linkedToNext2" variable to "linkedToNextValue3", so basically you work around as said in the video. But this does not delete Value2, right? Because value2 is still linkedToNextValue3, so it should not be collected, should it? headvalue0 | linkedToNextValue1 -- value1 | linkedToNextValue3 -- value3 | linkedToNull value2 | linkedToNextValue3 --^ So, basically you have information hanging around, haven't you? To really delete value2, wouldn't it be necessary to set the link of "value2 | linkedToNextValue3 --^" to "value2 | linkedToNull", so that this element can be collected, like this: headvalue0 | linkedToNextValue1 -- value1 | linkedToNextValue3 -- value3 | linkedToNull value2 | linkedToNull so, this would be: ... while(current.next != null) { //if data of the next element of the current element //equals the data we want to delete if(current.next.date == data) { //set the next-variable of the current element //to the value safed in the next-variable of next element (so it's next next) current.next = current.next.next; //and set the next-variable of the next-element to null //current.next.next = null; } } NullPointerException should in this case not occur, as next-element exists (because we found it and want to delete it), so there is a variable that can be set to a certain value, in this case it's null. And we have an exception for the last element. And only the last element can contain null in the next-variable. And considering that LL are used for many elements, because that's why they are so practical (better than arrays with specific length), plus the operations that can be used over a longer period of time, this looks to me like the outcome is something like a christmas tree/one data string with information hanging around. Is there somewhere an explaination how java's LinkedList is structured/built? I think you cannot actually get the actual Node (Node current = ...), but have to work through with methods such as element(), ... So, I am actually looking for something that can be used for a Node variable (as I would do it in the LL that I built on my own).
You noted that when calling the remove method, if the is to be removed, then the node is never really "destroyed." This was in contrast to the case where the node was in the middle, where there was no such note. I assume you're talking about a Java implementation, so are you saying Java's garbage collector can't detect such a deletion? If this is the case, how would I fix this bug?
I was thinking the same thing! We could fix it by having the head.next point to null before "deleting" it. Java's linkedlist implementation does this to apparently help gc - android.googlesource.com/platform/libcore/+/refs/heads/master/ojluni/src/main/java/java/util/LinkedList.java#176
once you remove the node, you are essentially removing the reference to it. if you haven't referenced that node directly elsewhere outside some local scope, which you likely haven't, the garbage manager will detect it and delete it. this is true for managed languages such as java and c#. for c and c++, you would need to manually delete most times unless you are using smart pointers and such.
I think that comment only applies to languages without garbage collection or am I wrong? Why wouldn't the garbage collection collect that? There would be no reference to the old head...
