@Brian Faure. Thanks for your tutorial. I really appreciate for your efforts to make this tutorial. After watching your vedio , I am confused by one thing. The append function doesn't show the great advantage of the linked list. Could you give us more explanation about this. I think one great merit for linked list is: when we want to insert a node into the list, it just need to change the pointer instead of moving the items in the list to create an gap and then inserting the new item into the list. In the linked list, when we want to insert an node, we just need to change two pointers, which helps us save time, especially the list contains millions of node. But your append function, it needs to iterate to find the last node and then add a new node. This doesn't show the virtue of the linked list. So I am think about the append function whether we could just add the new node at the end of the linked list without iteration. Thanks for your help.
Hi Xiufeng, thanks for the nice words! Yes the way the append function works currently is O(n), and is not the most efficient. By adding in an extra class member variable, we can call 'tail' for example, we can reduce the complexity of the append function down to constant time, or O(1). A possible implementation could be as follows: > def append(self,data): > new_node=node(data) > self.tail.next=new_node > self.tail=new_node Take note that for this to work, we will need to declare this 'tail' variable in the constructor of the class: > def __init__(self): > self.head=node() > self.tail=self.head If you wish to take this approach, you'll also need to be careful to set the 'tail' correctly inside of the 'erase' function (for example, if you try to erase the last element in the list, you'll need to set the tail to the _new_ last element). The following 'erase' function includes a single 'if' statement which should achieve this: > def erase(self,index): > if index>=self.length() or index print "ERROR: 'Erase' Index out of range!" > return > cur_idx=0 > cur_node=self.head > while True: > last_node=cur_node > cur_node=cur_node.next > if cur_idx==index: > last_node.next=cur_node.next > if last_node.next==None: self.tail=last_node ## *Here is where we set the tail* > return > cur_idx+=1 I've done some simple tests with this new implementation and it seems to be working, but feel free to let me know if you find any issues or have any other questions! I'm going to pin this comment so any others with the same question can see it.
Hello, I have a question about the way you append new object with self.tail: why setting both self.tail and self.tail.next equal to next_node. Does this mean you set the last element (after the tail) equal to the new node and then set the tail of the list to that node?
I was a beginner and struggled a lot for the right content and pace which suited me. I have started watching your videos and I must say the concepts are taught very well. At most places I see people just giving presentation through slides and your videos teach us how to implement them. My request to you is to please put more videos in this very playlist covering topics such as Heaps, Recursion etc . Basically the topics which you have'nt uploaded here. You're doing a great job sir. Your efforts can make someone's career. Someone like me. Thank you and have a nice day !
I know this is more geared to beginners but a better way to do length for an object is by levying your own dunder method or "magic method". You can do this by defining your function as: def __len__(self): this will let you leverage the length of your linked-list by using len(your_linked_list) rather than using your_linked_list.length(), which will be more pythonic and user friendly. You could also use def __getitem__(): for yor get function.
I love you dude thanks for explaining this stuff so clearly. So many other channels explain this stuff so badly, but you make it so easy to understand.
Thank you for making this great tutorial, it's very helpful! I've been struggling with understanding the linked list structure and finally find answers from your video, thank you very much!
Good job making this video. - append() method and elems.append() might be confusing if you create a method to insert at end with name other than append().
I found the concept interesting, I'm not sure where I'd use it over a list. I must say that your code can be made much more efficient by adding a _length variable and incrementing it when you append and de-incrementing it when you erase. No need to iterate when you can store it in an integer. Also __repr__() could be used vs display or perhaps a __str__(). so you could just print(linked_list) __getitem__() or perhaps __get__() could be used so you could linked_list[0] magic methods are kinda cool.
Thank you for making such a great tutorial! It really helps me aces the linked list, which I kept avoiding before. Finally found your clear step by step tutorial! It is so cool and excellent, thank you!
Thank You Brian. this video was very helpful. i watched other tutorials and they were confusing. one thing I discovered about algorithm and data structure is that the teacher's use of plain english and well outlined variable is fundamental to understanding the concept easily. i grasped everything you taught in this video but the challenge i face is that once i try to implement it on my own, i run into errors because i don't like the idea of copying people's code rather than either interpreting in a paper or typing them on my own. i have fundamental knowledge of programing and am a web developer. i want you to help me master OOP, DSA and Iterations. Thank You
It would be simpler if when you append a new node, you simply point it to the head node and set the head as the node you just added. Saves you from iterating through all the nodes you've added (could be a large number) to add one to the end.
I have a doubt. In the "append" method, new_node = node(data), each time The append method is called, an object of node class is created with the same name (new_node). Why doesn't this produces an error? wouldn't the object be garbage-collected?
Hi, this isn't an issue because the Python garbage collector uses reference counting to decide what to remove from memory and since we are setting the 'next' node pointer of the prior node equal to this node there will always exist some reference to it (until it is deleted from the list).
Really dumb question, but in the display method why is cur = cur.next before elems.append? In my head you would want to append to elems first and then move the pointer
Instead of doing another costly iteration through the linked list to find the size of it. We can add a self.length variable to the init() with an initial size of 0, and then add a 1 in the append() and a subtract a 1 in the remove method
I have a doubt.. If there is only one element say 5... Self. Data is 5 and self.next= none right?.. When you run "length" loop..the cur.next is equal to none, so it comes out and gives the length as 0...but the length should be 1 right?
You use function naming convention for your classes which would become very confusing eventually especially for new people. For example instantiating a class would look identical to assigning a function to a variable.
I had the same error. It's possible that in your length() function you are printing the total, instead of returning it. self.length() needs to RETURN a value, not PRINT
Awesome! But in method for calculate length I see some sort of problem. If counting start from 0 - head will not count. I understand, that list index start from 0, but in length method 0-element must counting like another 1. Or this is mistake?
I think it works. In the len function it is technically counting the head which doesn't have data and not counting the last node. I believe it works as he intended though.
For the length method, should total + 1 not be returned since the last node won't be added to the total (because it doesn't satisfy the condition of the while loop)?
At 11:50 I think it should be if index > self.length() instead of index >= self.length() This will ignore the last element and it cannot be accessed. I am still a newbie, correct me if I am wrong. Anyway, great series, thank you sir
Thanks for this video, you've explained the code and data structure really thoroughly and I'm starting to understand the implementation of LinkedLists. However, I found a bug with the length method that you wrote in the video. I found that if you try to access the last element of LinkedList it will raise the error due to the count starting at 0 rather than 1. The fix is simply start the count at 1 because it counts the empty node and makes the final element inaccessible via the get method that you defined. Also, with the change above, you want to move the `if cur_index == index: return cur_node.data` statement to the top of the while loop or you'll get an error stating cur_node.data is None (the get method)
It's the default Ubuntu terminal color scheme with some extra background opacity ( askubuntu.com/questions/941734/whats-the-rgb-values-for-ubuntus-default-terminal-unity ). If you're on Windows 10 you can actually install the Ubuntu terminal directly and take advantage of all it's sweet features (and also the color scheme), there's some info on that here docs.microsoft.com/en-us/windows/wsl/install-win10 . Otherwise if you're on a lower version of Windows you can install Cygwin and customize the color scheme to look like this in the appearance settings. Similarly if you're on OSX or another Linux distro you'll have to tweak the appearance settings to match.
This gets the idea of a linked list. However, it's not a very efficient implementation. With that append method you'd be iterating the WHOLE linked list before each insertion, and avoiding that kind of insertion is the very reason of using a Linked List. This could be easily fixed by keeping track of the Linked List's tale node.
@Brian Faure. Thanks for your tutorial. I really appreciate for your efforts to make this tutorial. After watching your vedio , I am confused by one thing. The append function doesn't show the great advantage of the linked list. Could you give us more explanation about this. I think one great merit for linked list is: when we want to insert a node into the list, it just need to change the pointer instead of moving the items in the list to create an gap and then inserting the new item into the list. In the linked list, when we want to insert an node, we just need to change two pointers, which helps us save time, especially the list contains millions of node. But your append function, it needs to iterate to find the last node and then add a new node. This doesn't show the virtue of the linked list. So I am think about the append function whether we could just add the new node at the end of the linked list without iteration. Thanks for your help.
Hi Xiufeng, thanks for the nice words! Yes the way the append function works currently is O(n), and is not the most efficient. By adding in an extra class member variable, we can call 'tail' for example, we can reduce the complexity of the append function down to constant time, or O(1). A possible implementation could be as follows:
> def append(self,data):
> new_node=node(data)
> self.tail.next=new_node
> self.tail=new_node
Take note that for this to work, we will need to declare this 'tail' variable in the constructor of the class:
> def __init__(self):
> self.head=node()
> self.tail=self.head
If you wish to take this approach, you'll also need to be careful to set the 'tail' correctly inside of the 'erase' function (for example, if you try to erase the last element in the list, you'll need to set the tail to the _new_ last element). The following 'erase' function includes a single 'if' statement which should achieve this:
> def erase(self,index):
> if index>=self.length() or index print "ERROR: 'Erase' Index out of range!"
> return
> cur_idx=0
> cur_node=self.head
> while True:
> last_node=cur_node
> cur_node=cur_node.next
> if cur_idx==index:
> last_node.next=cur_node.next
> if last_node.next==None: self.tail=last_node ## *Here is where we set the tail*
> return
> cur_idx+=1
I've done some simple tests with this new implementation and it seems to be working, but feel free to let me know if you find any issues or have any other questions! I'm going to pin this comment so any others with the same question can see it.
Hello, I have a question about the way you append new object with self.tail: why setting both self.tail and self.tail.next equal to next_node. Does this mean you set the last element (after the tail) equal to the new node and then set the tail of the list to that node?
Can you make more I love yours do you have stuff on graphs or heaps or merge sort
So Chinglish
3:40 node class, 5:00 linked list class, 6:12 linked list-APPEND method, 7:55 linked list-get LENGTH method, 9:22 linked list-DISPLAY LIST method, 11:31 linked list-get DATA method, 14:50 linked list ERASE method
THANK YOU
Thanks for the timestamps man! It was really helpful!
I struggled a lot with DSA until I found this channel. Now I struggle a lot less thanks to you.
I was a beginner and struggled a lot for the right content and pace which suited me. I have started watching your videos and I must say the concepts are taught very well. At most places I see people just giving presentation through slides and your videos teach us how to implement them. My request to you is to please put more videos in this very playlist covering topics such as Heaps, Recursion etc . Basically the topics which you have'nt uploaded here. You're doing a great job sir. Your efforts can make someone's career. Someone like me. Thank you and have a nice day !
5 years later and this is still a great video! Awesome in-depth explanation.
+ 5 months! Stil great
i must say, this is the simplest coding of linked list i've seen so far on the internet
Lolll, this is the most general and common code for linked list.
This man deserves an award for how well he broke down every concept!
I have searched through UA-cam to find someone to explain Linked lIsts and I gotta say, your video was the most helpful. Thank you so much!
Glad to hear it helped you, thanks for watching Austin!
First dsa video! the keyboard sound was just 🤩
Your explanation is too clean and lucid.Thanks for a great video!
I know this is more geared to beginners but a better way to do length for an object is by levying your own dunder method or "magic method". You can do this by defining your function as: def __len__(self): this will let you leverage the length of your linked-list by using len(your_linked_list) rather than using your_linked_list.length(), which will be more pythonic and user friendly. You could also use def __getitem__(): for yor get function.
I love you dude thanks for explaining this stuff so clearly. So many other channels explain this stuff so badly, but you make it so easy to understand.
Agree. The current appending solution is O(n) not O(1). Your solution should be O(1), which is the benefits of using Linked List
.
Excellent video, really clear, direct, concise and easy to follow. Amazing, so many people on UA-cam need to learn a thing or two from you.
I'm a beginner at coding and this was very helpful. I also liked the cadence of your voice, it helped me from not zoning out. Keep it up!
Extremely helpful tutorial! Clear, concise presentation. And Python is also my favorite language!
beleive me you are one of the greatest teacher of coding. oh its true ,,,its dammmnnn true... keep it up.
Thanks so much!
yes its good
What Kurt Angle would say if he was a developer haha
Thank you for making this great tutorial, it's very helpful! I've been struggling with understanding the linked list structure and finally find answers from your video, thank you very much!
I love your tutorials. I wish I could have discovered them before starting CS110 three months ago. Keep up the great work
Thank you so much for this! This is just what I needed to understand linked lists properly!
You're a great tutor! This feels like it brings me closer to where Python will finally "click" with me.
Thanks so much!
I searched for python linked list and watch many tutorials but I found this tutorial is best.
expect more python tutorials from this channel.
my_list = LinkedList()
my_list.append('3 years later but still great, thanks Brian')
my_list.display()
Good job making this video.
- append() method and elems.append() might be confusing if you create a method to insert at end with name other than append().
Its 2022 still the best linked list video on python
I have an error on display function it's say that 'None type' object has no attribute 'data'
I found the concept interesting, I'm not sure where I'd use it over a list. I must say that your code can be made much more efficient by adding a _length variable and incrementing it when you append and de-incrementing it when you erase. No need to iterate when you can store it in an integer. Also __repr__() could be used vs display or perhaps a __str__(). so you could just print(linked_list) __getitem__() or perhaps __get__() could be used so you could linked_list[0] magic methods are kinda cool.
Thank u for making this video, neat code and clear explanation, 10/10. I really hope one day I can be as intelligent as you are.
Thank you for making such a great tutorial! It really helps me aces the linked list, which I kept avoiding before. Finally found your clear step by step tutorial! It is so cool and excellent, thank you!
Thanks needed a quick refresher on linked list. Going to see if you have double linked list now...thanks again
Best explanation ever please never stop making great videos, we will subscribe
Thank You Brian. this video was very helpful. i watched other tutorials and they were confusing. one thing I discovered about algorithm and data structure is that the teacher's use of plain english and well outlined variable is fundamental to understanding the concept easily. i grasped everything you taught in this video but the challenge i face is that once i try to implement it on my own, i run into errors because i don't like the idea of copying people's code rather than either interpreting in a paper or typing them on my own. i have fundamental knowledge of programing and am a web developer. i want you to help me master OOP, DSA and Iterations. Thank You
I love your tutorial video. Excellent presentation. Very clear explanation. 2 thumbs up.
awesome man thank you. Been having trouble with data structures but this seriously helped a lot.
Your channel is gold
i just wasted 2 hours too complete this get method finally thanks
I looked for copper but found diamond. Loved the video, will help me with my exam.
Just wanted to add that the Doubly Linked List also has access to the last node, or the tail. Where the Singly Linked List doesn't.
Best video on the topic
Great content Brian. Thank you.
thank you for explaining the erase method, I was confused from another video on how the element gets deleted by just assigning the last node
@Brian Faure, Your explanation is pretty awesome. But, I think you have missed the "insert" operation.
antipop to the mic and this is gold. thanks a lot.
The length function is wrong, you need to add 1 to account for the last node.
The head node(empty node at the start) will count towards the total so it kinda cancels out
Thgank for the tutial as suggestion for future video. How to choose a Data structure? Pros vs Cons. Speed Big O notation
Thank you. i know i can watch the video again and understand it
Great video. On your erase, I think it is essential to reassign the self.head for when erase is called at index= 0 so that it does not stay as None
This makes sense. My prof should not be teaching, haha. Thanks for explaining while making it so concise.
It would be simpler if when you append a new node, you simply point it to the head node and set the head as the node you just added. Saves you from iterating through all the nodes you've added (could be a large number) to add one to the end.
Pretty silly statement. I think in general terms when you "append" to a list, you are specifically adding to the end of the list not to the beginning.
@Brian Faure. Thanks for your tutorial.
I have a doubt. In the "append" method, new_node = node(data), each time The append method is called, an object of node class is created with the same name (new_node). Why doesn't this produces an error? wouldn't the object be garbage-collected?
Hi, this isn't an issue because the Python garbage collector uses reference counting to decide what to remove from memory and since we are setting the 'next' node pointer of the prior node equal to this node there will always exist some reference to it (until it is deleted from the list).
@@BrianFaure1 Thank you. That clears my doubt.
Really dumb question, but in the display method why is cur = cur.next before elems.append? In my head you would want to append to elems first and then move the pointer
Very useful, I'm in gr 11 and learning this it was well explained!
Instead of doing another costly iteration through the linked list to find the size of it. We can add a self.length variable to the init() with an initial size of 0, and then add a 1 in the append() and a subtract a 1 in the remove method
Fantastic explanation of the topic, thank you!
Very clear and concise. Thank you.
I have a doubt.. If there is only one element say 5... Self. Data is 5 and self.next= none right?.. When you run "length" loop..the cur.next is equal to none, so it comes out and gives the length as 0...but the length should be 1 right?
Great video, thanks for the post.
Thanks, Brian. Really helpful.
Man !This is so crisp ! Nice tutorial
Thank you very much Brian! You videos are really amazing and helped me a lot! i really appreciate for all your effort! Just can't thank you enough!
No problem, thanks for watching Jingyu!
Oh, it's like a snake game. Coded that yesterday.
Watching in 2021... Very Cool....
Quick and short recap.
Awesome video..👌👌
One of the best I've seen for python tutorials.👌
Awesome tutorial! Thank you
This video is very helpful for me to understand the linked list. I thought it would be very complicated 🤔
bro posted the biggest DSA bang and left
Really Useful keep on doing more videos please
@Brian Faure You did great tutorial. I really enjoyed the tutorial.
You use function naming convention for your classes which would become very confusing eventually especially for new people. For example instantiating a class would look identical to assigning a function to a variable.
Thank you so much! Your explanation really helped!
hi @brian,
getting error on if check
if index >= self.length():
TypeError: '>=' not supported between instances of 'int' and 'NoneType'
I had the same error. It's possible that in your length() function you are printing the total, instead of returning it. self.length() needs to RETURN a value, not PRINT
Super good explanation!
Great video! Thanks for your work!
Thank you sir.It helped a lot.Keep posting videos
Awesome!
But in method for calculate length I see some sort of problem.
If counting start from 0 - head will not count. I understand, that list index start from 0, but in length method 0-element must counting like another 1. Or this is mistake?
for the len function, i think u should use curr instead of curr.next for the loop. Your code will give len -1 for the result
I think it works. In the len function it is technically counting the head which doesn't have data and not counting the last node. I believe it works as he intended though.
Great work. Really appreciated
Great video dude, it helped me a lot!
For the length method, should total + 1 not be returned since the last node won't be added to the total (because it doesn't satisfy the condition of the while loop)?
At 11:50
I think it should be
if index > self.length()
instead of index >= self.length()
This will ignore the last element and it cannot be accessed.
I am still a newbie, correct me if I am wrong.
Anyway, great series, thank you sir
thank you for this tutorial it is simple and helpful
Simple and clear， great tutorial！！
Thanks for this video, you've explained the code and data structure really thoroughly and I'm starting to understand the implementation of LinkedLists.
However, I found a bug with the length method that you wrote in the video. I found that if you try to access the last element of LinkedList it will raise the error due to the count starting at 0 rather than 1. The fix is simply start the count at 1 because it counts the empty node and makes the final element inaccessible via the get method that you defined.
Also, with the change above, you want to move the `if cur_index == index: return cur_node.data` statement to the top of the while loop or you'll get an error stating cur_node.data is None (the get method)
Thanks for the video. Yes, that would be handy to have the code :)
Sure thing, I've added it to this git repository: github.com/bfaure/Python_Data_Structures/blob/master/Linked_List/main.py
Brian Faure Thanks! 🖖🏼
This is awesome, thank you!
Fantastic explanation! Thanks!
Nice video. Good teacher. Great programmer.
Thank you sir..It was very informative.
Pretty good tutorial for me as a beginner
Excellent Explanation Sir
What colour scheme did you use for your command line? I'd like to switch my terminal to that colour scheme
It's the default Ubuntu terminal color scheme with some extra background opacity ( askubuntu.com/questions/941734/whats-the-rgb-values-for-ubuntus-default-terminal-unity ). If you're on Windows 10 you can actually install the Ubuntu terminal directly and take advantage of all it's sweet features (and also the color scheme), there's some info on that here docs.microsoft.com/en-us/windows/wsl/install-win10 . Otherwise if you're on a lower version of Windows you can install Cygwin and customize the color scheme to look like this in the appearance settings. Similarly if you're on OSX or another Linux distro you'll have to tweak the appearance settings to match.
Very helpful, thank you!
Thanks for your wonderful tutorial.
I was stuck in the linked list part from about a week .
You were awesome
This gets the idea of a linked list. However, it's not a very efficient implementation. With that append method you'd be iterating the WHOLE linked list before each insertion, and avoiding that kind of insertion is the very reason of using a Linked List. This could be easily fixed by keeping track of the Linked List's tale node.
for get you can just have display return elems instead of print that way you can just return self.display()[index]
Many thanks , I've learnt a lot :)
Can't we just say while current != None (or while current)? we dont necessarily need to make sure we have 2 nodes before null right?
Lisr length to.. just keep track when add new node