Data Structures: Linked Lists
HTML-код
- Опубликовано: 26 сен 2016
- 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.
Yeah
It’s been 4 years, what are you doing now?
Nice
@@alfonsocanady7564 he is still trying to solve linked list problems,… haha ask me what I’m doing in 4 years!!
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!!!
Thanks so much for putting the algorithm and the coding together on the same page, that's the best way to learn any coding language.
This is probably the best video you can find on RUclips that talks about LinkedList. Great job!
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.
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.
Excellent, easy to digest explanations and 0 ads. Thank you for your content
Great video! I was so confused with Linked Lists in my CS class, but this makes it so simple to understand!
The wrapper class of LinkedList dynamically changes the head by prepending to inform other "lists" pointers. This is really neat! Thank you!
This is one of the few videos that I found does not make the topic more confusing. Thanks so much
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.
For anyone interested in a simple Python implementation, feel free to peep my recent lesson: ruclips.net/video/JlMyYuY1aXU/видео.html
Any conversation about linked lists should BEGIN with the following warning:
"You probably shouldn't be using a linked list for this."
@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)
Wonderful explanation. Textbook for my class gets confusing sometimes since its not step by step so these videos help explain further
of all the "LinkedList" videos I've watched, None can be compared to this. Thank you for this explanatory video 🥳🥳🥳🥳🥳🥳🥳🥳🥳
your explanations are so smooth I'm so thankful to you ma'am.
thank you!! you explained this so beautifully clear. kudos
I've never watched a programming video from beginning to end before. A truly class explanation. Thank you!
SIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIMPHHHHH
Jehrili Paad couldn’t agree more
I re-watched this video several times, thank you for posting this!
understood this way better the way you explained it compared to how my professor did. thank you so much.
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.
great explanation!! right from the scratch. this helped me a lot, thanks!!
omg someone i can understand!! amazing, thank you for speaking clearly! that is hard to come by in this area!!
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.
You know that moment of satisfaction when you finally understand something? I got it from this video.
Great vid! I understand it faster than 100x times thanks to you
This girl is amazing. Thanks for the fantastic tutorial :D.
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.
This video is very helpful. Thank you!
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++.
delete head;
head=head->next;
@@xCwieCHRISx Whoops, my bad!
head=head->next;
delete head->previous;
Dope! I was watching this from a C++ background and was thinking to myself, "java doesn't have to explicitly free memory?" xD
@@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 ;)
Reallly thank you for explaining!!! I learned a lot from it!
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!
snaps out for you, this is such a great explanation.
a video from 2016 gave me the info i needed, thank you
Thank you very much.
You just lifted a load off me head
Great tutorial, easy to understand! Thank you!
Excellent emphasizing. Thanks a lot.
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!!
is that not just doubly linked?
@@saveerjain6833 no.
@@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.
if you talk about the usage of this structures.Such as where can we use this structures and where can not. I think this video will be much better.
thank you so much for the video. now i understand the linked lists.
This is otherworldly explanation technique, amazing. "Actionpacked supercoder blockcuster" ! :)
i just loooove you , and your explanations
Gayle is awesome, I got her book, only read 1st chapter so far .
i love this channel :) it's so good!
Thank you so much, this was very easy to follow.
She is SUCH A GENIUS
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 ?
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
in link lists can you have different types of data at the same time? such as intergers and strings at a same time
I wished she was my lecturer.. so fluent and to the point 😀
Awesome job Gayle!
Thank you, Chris Gayle!
your voice is so sweet i grasped everything u said
thanks for this. I'm trying to find problems that would fit LinkedList best
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
She could also change the if statement that checks if the head needs to be deleted to a while statement.
she has mentioned the requirement of the function - delete only the first node having data same as the given data
Very understandable, thank you! Subscribed!
That’s a nice way to explain Linked list!
Thank you ! Very nice explanation !
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?
This video is very helpful! Thanks a lot !!!!
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) ?
Thanks for the explanation !
So, do I understand correctly, that with this linkedlist we're only adding values and re-routing instead of actually removing values? If so, would this mean that the size will increase over time? If so, is there any way to access the values that have been 'ignored'?
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.
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..
My God, that keyboard click sound is erotic. What keyboard is that?
iMac keyboard
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.
Get yourself a mechanical keyboard and the sound of this keyboard will make you cringe.
Abd-Elrhman Rizk dude, if sounds like that are your thing, search ASRM audio or something like that...
omg thanks, i searched and i'm listening to it like 1 hour or something. this is great. like braingasm
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?
Great explanation of the linked list.
Thank you for the video, I am preparing for the following interview question. When searching for the element in the list, what if the list is too big, then what would you do? I am really struggling how to answer this question. Could you please help me?
Awesome Video! Can you please include insert at position also.
Put the return at the end so if you there are any duplicates in the (DeleteWithValue) it wont skip them over.
You made it so easy!!!
If you keep a tail variable along with the head, appending to the list should be 0(1) since you won't have to traverse the whole list to the end
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.
Nice video, But I am confused about the dot operator . Since current and next are node type variable, how can we use current.next? because all I know is only object.( method/data) can be used.
Loved it! thanks
On deleting of data, do head element will be updated? As we are assigning head to current node variable and delete operation is performed on it.
while appending an element does the head node keep changing and we add a new node after the head node? , is that the meaning of the append code in the video
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?
you are fired
Which coding platform did you use? Thank you this was very helpful!
Amazing explanation 👨🔬
I dont understand deleteWithValue(). Dont you just create current as a temporary list that copies the data of head, and then works through the data until value is found. So I understand that you manipulate the pointers in current to ignore the node you need to, but dont you need to change in head (the original link list) to match what current now has? How do you do so? That block of code is left at current = current.next
We can't have two public classes in the same file though right?
The best lecture I have ever listened
seriously! This is the best one I've seen. She's hella good
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).
Hey, @HackerRank. There was only one thing i did not understand : "If we preappend we have a issue because we change the Head..." Only with preappend ? i guess we always need a Wrapper/class and a "stamp" on one node to navigate and do operations and always know which one is the first. To not miss a single node. Is this correct ?
Anyway, thanks for the free learning :)
Great Explanation
What if we wanted to show the elements of the linked list? Like a show method?
Thank you
At 5:31, it is stated that current is a method. Isn't it an instance variable of type Node?
but what if I want to delete what's inside a node, taking as a parameter a reference to the data inside said value, and not the number of node itself, how would you approach that?
is there a better way to remove the head? since you aren't able to access it wouldn't that cause a memory leak? or is it different in java
So linked list are actually objects that point to another object? And at 2:30 when you write 'Node next' does the program already know what 'next' does? Is 'Node next' like a method that is predefined within the program??
Question! Why the data's type is int, we can store any data type in node right? so why (int data)
Won't the delete function only delete the first instance of a node with matching data? Not every instance?
Hi guys, Please which tool are they using to create explanation visuals? I want to create some for a class I'm teaching
you are theeeeeee best.. I love this
The class node has only 2 fields, Node next and int data. What if I want to add a String to my LinkedList, to which field is the string allocated??
Would nesting the class node under linked list make a difference?