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!!!
@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)
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.
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.
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.
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.
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.
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 ;)
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.
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.
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
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'?
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..
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?
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!
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?
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??
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
I might be wrong but doesn't this code have a memory leak? You are never destroying an element, so the original value entered is still there, but now there isn't a pointer to it. Its just gonna hand out there and every time you delete an element, another chunk of memory becomes unaccusable.
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.
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).
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.
Just curious trying, probably that statement in line no. 45 is not necessary, right? The while loop will accomplish the task I guess. Correct me if I am wrong kindly. And the video is too good. Thank you.
None of the nodes you delete are destroyed with your method (not only the head). You have two nodes pointing to the subsequent node because the link of the "deleted" node is never removed (garbage collection won't pick this up). Although you can't access deleted nodes anymore since it's not doubly-linked, your memory grows without bound, which is bad.
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...
I think there is a problem in the deleteWithValue-method of the example. Because the while is checking for current.next it won't be able to delete the value if it is in the last node of the list.
I don't think there's a problem: it's not 'current' that gets deleted, it's current.next. If the value is in the last node, then when current == the second-to-last node, the code will set current.next = current.next.next, which is null
yiani31 yes you are right. The real problem is NullPointerException when you set current = current.next while deleting last node. A small null check should be placed before setting value for current
There is no Exception. When you call current.next=current.next.next, and current is the second to last node, current.next.next will be null. This means that current.next will be null after the deletion, and this is not only fine, but desired. NullPointerException is trown when you actually try to use the null value somehow, like accessing it.
@Ella Blun well Java is also object oreinted where c isn't. So it might be harder wrapping your head around imperative languages if you've only had practice with oop
Also Java does garbage collection where C does not. This means that, in Java, if nothing is pointing to an object, then it will automatically be deleted. In C, you have to do this deletion your self or you might get memory leaks.
the if statement handles the situation when the head is null. If they leave the code without the return on line 17 it'll add the node where its supposed to and then it'll run the code below it (since we don't have an "else" at the end of the if statement bracket) and it'll add the same node a second time
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.
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 :)
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 ?
I think there is a problem with this code, both the Node class and LinkedList classes are declared public whereas we can have only one public class per file
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?
If you just walk around an item in a linked list, isn't that item still stored in memory, since we haven't actually deleted it? On a large scale, can that cause problems?
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
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) ?
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?
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?
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?
ok, let's suppose that I declare my class Node. It has inside itself a declaration of another class Node, that is Node next. so, when I declare an instance of my Node class, e.g. Node node, it should initialize his Node next, who should initialize his Node next, who should initialize his Node next, who should initialize his Node next, who should initialize his Node next, who should initialize his Node next, who should initialize his Node next, (.......) and this loop should get us to a memory overflow soon or later, meaning the portion of memory that was planning for the program execution can't contain all my Node instances. I'm curious to know why this doesn't happen, cause I feel there is something big I still can't get about these data structures.
I really don't understand why we need to walk through all nodes in the list to append a new node. Just define a first/head and last/tail pointer in the list class. l.append() will then be in constant time.
In a singly linked list or doubly? For singly: l.delete() is not l.append(). l.append() can be in constant time, deleting the first element constant time, deleting the last element O(n), deleting an element in the middle O(n-distance to end) SLL can be useful if you want to save memory on a list that will only be added to / checked, and rarely deleted from the end of it. Priority queues for example, if implemented as SLL, will always delete first (constant), appended to end (constant). DLL allows constant modifications anyway, except for adding/removing non-first or non-last elements. And even those times could be improved by for example, binary searching if list is ordered - log n Or if not ordered, you could start your search at first or last depending on where the element is expected to be (if known), or, intuitively, start + 1 and end - 1 ... till start + n/2 and end - n/2 in O(2n/2), which will be better than to left-to-right list traversal in O(n - distance to end) if the element is in the second half. Basically, if the element then is closer to start or end than the middle, it'll be better.
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!!
This is probably the best video you can find on RUclips that talks about LinkedList. Great job!
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!!!
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)
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.
You know that moment of satisfaction when you finally understand something? I got it from this video.
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've never watched a programming video from beginning to end before. A truly class explanation. Thank you!
SIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIMPHHHHH
Jehrili Paad couldn’t agree more
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.
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.
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.
The wrapper class of LinkedList dynamically changes the head by prepending to inform other "lists" pointers. This is really neat! Thank you!
Excellent, easy to digest explanations and 0 ads. Thank you for your content
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.
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 ;)
I re-watched this video several times, thank you for posting this!
This is one of the few videos that I found does not make the topic more confusing. Thanks so much
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
She is SUCH A GENIUS
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.
This girl is amazing. Thanks for the fantastic tutorial :D.
Great video! I was so confused with Linked Lists in my CS class, but this makes it so simple to understand!
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
of all the "LinkedList" videos I've watched, None can be compared to this. Thank you for this explanatory video 🥳🥳🥳🥳🥳🥳🥳🥳🥳
a video from 2016 gave me the info i needed, thank you
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'?
Will the delete implementation work for the last node on a list?
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.
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..
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?
Exactly what I was thinking.
thanks for this. I'm trying to find problems that would fit LinkedList best
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!
Gayle is awesome, I got her book, only read 1st chapter so far .
your explanations are so smooth I'm so thankful to you ma'am.
Is there a course like this but in Go?
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
Great vid! I understand it faster than 100x times thanks to you
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??
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
Good video but noob question, where do you specifically put the main driver code(public static void main(String[] args)) ? Thanks
I was wondering the same
I might be wrong but doesn't this code have a memory leak? You are never destroying an element, so the original value entered is still there, but now there isn't a pointer to it. Its just gonna hand out there and every time you delete an element, another chunk of memory becomes unaccusable.
Java has a garbage collector
This is otherworldly explanation technique, amazing. "Actionpacked supercoder blockcuster" ! :)
omg someone i can understand!! amazing, thank you for speaking clearly! that is hard to come by in this area!!
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.
understood this way better the way you explained it compared to how my professor did. thank you so much.
At 5:31, it is stated that current is a method. Isn't it an instance variable of type Node?
Wonderful explanation. Textbook for my class gets confusing sometimes since its not step by step so these videos help explain further
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).
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
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.
Just curious trying, probably that statement in line no. 45 is not necessary, right? The while loop will accomplish the task I guess. Correct me if I am wrong kindly. And the video is too good. Thank you.
None of the nodes you delete are destroyed with your method (not only the head). You have two nodes pointing to the subsequent node because the link of the "deleted" node is never removed (garbage collection won't pick this up). Although you can't access deleted nodes anymore since it's not doubly-linked, your memory grows without bound, which is bad.
link TO the deleted node is changed. Thus, there remains no reference assigned to access it, hence it will be garbage collected.
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.
referenceless memory which is left undeleted in c++ causes memory leak..
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...
What model of keyboard are you using? it sounds so satisfying
I think there is a problem in the deleteWithValue-method of the example. Because the while is checking for current.next it won't be able to delete the value if it is in the last node of the list.
I don't think there's a problem: it's not 'current' that gets deleted, it's current.next. If the value is in the last node, then when current == the second-to-last node, the code will set current.next = current.next.next, which is null
yes it can't delete the last node
yiani31 yes you are right. The real problem is NullPointerException when you set current = current.next while deleting last node. A small null check should be placed before setting value for current
There is no Exception. When you call current.next=current.next.next, and current is the second to last node, current.next.next will be null. This means that current.next will be null after the deletion, and this is not only fine, but desired. NullPointerException is trown when you actually try to use the null value somehow, like accessing it.
like when you create the first node (head) then only the data variable is set, but not the next variable, so maybe it goes automatically null
Why do we need to create current＝head?
What does it do??
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.
Great video but i am expecting the coding in C but u r doing in it java. I am not familiar with it.... anyways nice explanation for the core concept
@Ella Blun well Java is also object oreinted where c isn't. So it might be harder wrapping your head around imperative languages if you've only had practice with oop
Also Java does garbage collection where C does not. This means that, in Java, if nothing is pointing to an object, then it will automatically be deleted. In C, you have to do this deletion your self or you might get memory leaks.
Ella Blun really bad analogy. it’s more like cursive vs print and not really being able to decipher cursive.
what actually gets returned in the public void append(int data) method? I'm confused as to why you need the return statement on line 17?
the if statement handles the situation when the head is null. If they leave the code without the return on line 17 it'll add the node where its supposed to and then it'll run the code below it (since we don't have an "else" at the end of the if statement bracket) and it'll add the same node a second time
This video is very helpful! Thanks a lot !!!!
1:15 Correction. If you implement a linked list with a tail variable pointing to the last node, appending to the end of a list will take 0(1) time.
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.
totally agree with you :D
Just changing the pointer, wouldn't that create trash in memory? Is there a way to clear the object from the memory?
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 :)
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 ?
I think there is a problem with this code, both the Node class and LinkedList classes are declared public whereas we can have only one public class per file
The best lecture I have ever listened
seriously! This is the best one I've seen. She's hella good
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??
This video is very helpful. Thank you!
thank you!! you explained this so beautifully clear. kudos
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?
If you just walk around an item in a linked list, isn't that item still stored in memory, since we haven't actually deleted it? On a large scale, can that cause problems?
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
why do you need to walk through a linked list for delete? is not linked list have o(1) for insert and delete?
Great explanation of the linked list.
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
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) ?
We can't have two public classes in the same file though right?
I wished she was my lecturer.. so fluent and to the point 😀
Won't the delete function only delete the first instance of a node with matching data? Not every instance?
But what if you want to delete the head and if the head is the only node in the linked list?
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?
snaps out for you, this is such a great explanation.
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?
your voice is so sweet i grasped everything u said
Can `current.next.next` be null.empty? Ie, what if we are trying to remove the last element?
Question! Why the data's type is int, we can store any data type in node right? so why (int data)
in link lists can you have different types of data at the same time? such as intergers and strings at a same time
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?
great explanation!! right from the scratch. this helped me a lot, thanks!!
Put the return at the end so if you there are any duplicates in the (DeleteWithValue) it wont skip them over.
Append is also constant if you keep a reference of your tail.
What if we wanted to show the elements of the linked list? Like a show method?
Reallly thank you for explaining!!! I learned a lot from it!
ok, let's suppose that I declare my class Node.
It has inside itself a declaration of another class Node, that is Node next.
so, when I declare an instance of my Node class, e.g. Node node, it should initialize his Node next, who should initialize his Node next, who should initialize his Node next, who should initialize his Node next, who should initialize his Node next, who should initialize his Node next, who should initialize his Node next, (.......) and this loop should get us to a memory overflow soon or later, meaning the portion of memory that was planning for the program execution can't contain all my Node instances.
I'm curious to know why this doesn't happen, cause I feel there is something big I still can't get about these data structures.
Would nesting the class node under linked list make a difference?
That’s a nice way to explain Linked list!
Which coding platform did you use? Thank you this was very helpful!
i just loooove you , and your explanations
I really don't understand why we need to walk through all nodes in the list to append a new node.
Just define a first/head and last/tail pointer in the list class.
l.append() will then be in constant time.
Deagan Otterspeer what if you want to delete the last node
In a singly linked list or doubly?
For singly: l.delete() is not l.append().
l.append() can be in constant time, deleting the first element constant time, deleting the last element O(n),
deleting an element in the middle O(n-distance to end)
SLL can be useful if you want to save memory on a list that will only be added to / checked, and rarely deleted from the end of it. Priority queues for example, if implemented as SLL, will always delete first (constant), appended to end (constant).
DLL allows constant modifications anyway, except for adding/removing non-first or non-last elements.
And even those times could be improved by for example, binary searching if list is ordered - log n
Or if not ordered, you could start your search at first or last depending on where the element is expected to be (if known), or, intuitively, start + 1 and end - 1 ... till start + n/2 and end - n/2 in O(2n/2), which will be better than to left-to-right list traversal in O(n - distance to end) if the element is in the second half. Basically, if the element then is closer to start or end than the middle, it'll be better.
MapleStory For Life baby!