Python: Linked Lists (fast)

[@Alarmedtiger]

Thank you for being straight to the point and concise and not dragging this on for 20 minutes!

[@pablomora3233]

All I see on youtube are half-hour or 40 minute videos about Linked Lists. Thanks for such a brief and clear explanation!

[@qazizaahirah4168]

I actually liked the speed of the video. It was like a final nail to my understanding. Thanks :)

[@akaakaakaak5779]

sometimes something explained fast is clearer than something explained longer because the waffle is filtered out

[@oggiai]

I have a slow version of Linked Lists too.

[@morenomt27]

Thank you for this!! It is easy to understand, it didn't need a 40 minute video to explain the concept!

[@oggiai]

See code on my GitHub repository here, github.com/joeyajames/Python

[@hajerLK]

best video ive ever seen so far about the linked lists ;)

[@hserdarkuyuk]

Thank you so much, I studied and wrote my own code with your instructions and even found a bug which is Line 31 has to be self.root = this_node.get_next() Otherwise, if you want to remove root, it can not .... Thank you so much...

[@danielswonderland6783]

Bingo

[@cesarvigario]

I agree. If we are removing the root node, we will fall on that condition. We can't set the root node to be the same, because we are removing it. That way we should assign the root of the list to be the next node, as you say "self.root = self.root.get_next()". For example, if we have this: ``` list = LinkedList() list.add(1) list.add(2) list.add(3) print(list.root.get_data()) # prints 3 list.remove(3) print(list.root.get_data()) # prints 3 ...it should print 2 ``` we will see that in both cases we print "3", which is wrong for the second case, once we have removed the node(3).

[@ryanzkp]

Agreed…

[@tamertamertamer4874]

the fast part of the video is very descriptive because 10 seconds into the video I remembered what a linked list is 10/10 not clickbait

[@arsalali69]

My exam is in a hour, thank you for making it fast, other videos were half an hour long

[@oggiai]

Glad I could help!

[@darkthrongrising5470]

You are very good at breaking these things down, one of the biggest challenges Ive come across is finding someone who can explain these things. I give this video 99 thumbs up, had you applied this in a real world scenario I would be willing to consider 100 thumbs up(perfect score by my scale). This comment is in no way meant to be incendiary or critical, a mere observation. I think you do a fine job and I sense your employer feels the same way.

[@oggiai]

+Robert Williams thanks!

[@ibnislam9237]

The perfect video I was searching for.

[@edd7676]

Thank you very much, Sir Joe James! The martinis are on me!

[@_inetuser]

Good Video, wouldn't be able to program it on my own but got a good understanding of linked lists

[@lautaroborrovinsky2701]

Hi Joe, in the Remove function, shouldn't it be "self.root = this_node.get_next()" instead of ""self.root = this_node" in case there is no previous node? Thank you.

[@oggiai]

+Lautaro Borrovinsky yes, another commenter already mentioned that. I fixed the code on github.

[@AbhishekBalani93]

Every viewer might not be able to realize of the problem and will get even more confused. Maybe you can show correction with annotations.

[@_fcs999]

First of all, big thanks to +Joe James for the great tutorial. I really appreciate the effort of breaking down the code in a step-by-step fashion. It is more than helpful! I would second +Abhishek Balani that making an annotation for the correction while we remove the element at root position. For least effort, probably leave a note on the description saying the unintended typo. For new learner like me, I would merely go through the youtube to gain some flavor/idea (linked list) and move forward without digging into seems-to-be-scary GitHub code at the moment.

[@ceciliaw1065]

Thank u!!!

[@rounakvyas9713]

What should I do to print all the values of the list using a loop? How do I add a node at a specific place? How do I add a node at the tail of the list? How do I reverse a linked list?

[@PoeLemic]

Very impressive content. I really liked it. Didn't really need to watch, but I just used to see the concept of how to do it. Probably just use a quick array instead. More complex than needed, at moment.

[@raduandreicosmin]

Great video ! I'm pretty new to programming but I didn't mind the speed as I could just pause the video whenever. If I'd change anything, I'd explain the find function first, before the remove function

[@sajibarafatsiddiqui9077]

Best Tutorial ....I am satisfied

[@phillipuchen]

Thanks! It's really easy to understand, and with reasonable time to watch the whole video.

[@michaelashkenazi1234]

Hello, in line 31 you wrote: self.root = this_node, and I think it should be: self.root = this_node.get_next() . Am I right or did I miss something?

[@bexterinat]

Thank you! This helped me so much!

[@DCentFN]

How would you modify this code to add to the end of the list rather than the beginning?

[@fernandozapateroarriaga7926]

2:29 How does he type that instantly?

[@samridhshubham8109]

seriously?

[@hashiramasenju6058]

The video is edited bro

[@fernandozapateroarriaga7926]

@@hashiramasenju6058 Oh...

[@lupitaalvarado4744]

Excellent! Tank you so much!

[@morekaccino]

The speed is so cool.thanks

[@fancylad2006]

Great tutorial!

[@hrvojekelcec8539]

I think your remove() method has a bug. Code line 31: self.root = this_node. In my opinion, it should be "self.root=this_node.get_next()" - that is a case for a first node.

[@leo.y.comprendo]

just watched this video and I completely agree

[@debadridutta]

Sir, I'm having a problem, when i type the code, it says "'LinkedList' object has no attribute 'root'". But when i copy paste your cod, it runs. Also I have noticed that for my class programs, I always have to call the _init_() function

[@oggiai]

+Debadri Dutta post your code

[@GAGANDEEPSINGH-jx4ky]

It happened to me too..Plz update if this was resolved

[@aparnamahalingam1595]

I am facing the same issue; I'm very new to OOPs in Python, and so am not able to debug it either.

[@nizarkadri3109]

code starts at @ 2:28

[@dhavalbhimani5242]

Hi Joe, this implementation looks more like a stack. if you were to remove the last element it will be O(1) and if you traverse and print the list it will be in reverse order

[@connorcoultas9629]

Stack, Queues, Vectors, Dequeues are all implementations of a linked list. All of the above (and lists) are linked lists but not all linked lists are lists.

[@RiteshKumar-lh1xn]

How are you getting all the autocompletes for all your class's getters and setters

[@mchristos]

Hi Joe - thanks for this video. I feel like if the data you are removing is at the root node (or, the node that the root node "points to"), it does not get removed. This is because, at the first occurrence of 'else' you have written 'self.root = this_node' . Should it not instead be 'self.root = this_node.get_next()' ? This way the root node now points to the second node, so that the data at 'this_node' gets removed?

[@oggiai]

+Chris Marais thanks for the feedback. I'll take a close look at that as soon as I get time. I'm pretty buried in work and school projects right now.

[@oggiai]

+Chris Marais Yes, I just tested it, and you're right. The else statement at line 43 should be self.root = this_node.get_next() Without that change you are unable to delete the last node added (root node). Thanks a lot for catching that!

[@mchristos]

+Joe James Cool, no problem!

[@MrGQ]

+Joe James Great video, helps a lot! I think you should add a comment in the video showing a correction to this error. It would've went over my head if not for reading the comments. Thanks again for taking the time to make such a helpful video :)

[@oggiai]

Yeah, sorry, I plan to as soon as I get time. I think I already corrected the code on github.

[@DCentFN]

How would one modify this so rather than adding to the front of the list it adds to the back?

[@crateofloot1772]

idk if im reading this wrong, but the remove function, wouldn't it just remove it from the linked list, not memory, meaning after a while youd have a bunch of useless nodes in memory

[@prithvikapoor7606]

Nice video. the add function is really Neat and simple!!

[@backitdev]

I don't understand that part, where you define your LinkedList constructor like this: def __init__(self,root=None): because if you can set the root, but you didn't increase the size. Do I misunderstand something?

[@rajreeta2485]

Best 💯

[@rajat0610]

straight to the point and very clear thanks for the video! i have one question though i don't understand how line #31 works here's my question in detail - line #31 will be executed if prev_node is None, which means, it will be executed only in case of root node, right? so, if we want to remove the root node, we will set the root node as "self.root = self.root.get_next()" or in this case, "self.root = this_node.get_next()" as this_node has been initialised as self.root on line #24 according to my understanding, it should not work, but it works perfectly and i'm going crazy thinking about why it works

[@cesarvigario]

I agree. If we are removing the root node, we will fall on that condition. We can't set the root node to be the same, because we are removing it. That way we should assign the root of the list to be the next node, as you say "self.root = self.root.get_next()". For example, if we have this: ``` list = LinkedList() list.add(1) list.add(2) list.add(3) print(list.root.get_data()) # prints 3 list.remove(3) print(list.root.get_data()) # prints 3 ...it should print 2 ``` we will see that in both cases we print "3", which is wrong for the second case, once we have removed the node(3).

[@pchebbi]

Hi Joe, how to find out sum of values in a linked list? Thank you.

[@gloriaramlal8027]

Hi Joe, in the Data field of the Node you use one element, an integer. Is it possible to use a List with different data types (or a dict) in the Data field and how would you input and access the data? Thanks

[@oggiai]

My linked list here is a simple one for educational purposes. In practice you can put any object into the Node. For example, you could put a Student who has an age, id_number and Class_schedule. It would not require much change to the code, but I'm not going to rewrite it.

[@RuslanSkiraUkraine]

in remove function prev_node will always None? and why do we need check if prev_node ? line:25

[@iMAFIAo]

Just a heads up your remove function does not remove the first element in a list.

[@oggiai]

Thanks, I’ll take a look at my code

[@MuhammadHamdan91]

Correction: In the remove method. self.root = this_node.get_next()

[@proshlok1]

Exactly, idk no one is pointing that out

[@OmkaarMuley]

thanks for making the video

[@GaneshManika]

Thank you Joe!!

[@playcorner2474]

wow, this was faster than speed of light

[@maobufei4986]

Very helpful! Thank you!

[@vaishnaves1723]

I don't get the prev_node part of the remove function. Could you please explain that? (Why even have a function which checks if prev_node is not none when you're setting it to none in the previous line?)

[@Simeon1337]

Its used because in a situation where a list can have only 1 node, and if that condition is met ( previous is none ) after itterations, you just change the root to be none, otherwise you re-link the list so it excludes the current node

[@Julia-rq7uj]

So for the add function, you add the new data to the beginning of the list?

[@oggiai]

Right.

[@charanpuladas1891]

Hey Joe! I have a a couple of doubts. Can I declare the Linkedlist class as a child class of Node class? Like Class Likedlist(Node) and declare the Node constructor in Class Likedlist()? The other one is I don't completely understand the add() method. new_node = Node (d, self.root) // This creates an object of Node with 2 attributes data and next_node self.root = new_node // Then you assign new_node object to self.root but how is the program returning the address of new_node?

[@oggiai]

+Charan Puladas No, a LinkedList is not a Node. A LinkedList has nodes. So you cannot do LinkedList(Node). I think you could make Node an inner, or nested class of LinkedList though. That should work. You can read up more on nested classes, or just try it out. Basically that just means you put the code for the Node class inside the LinkedList class, indented. Inner/outer class is not the same thing as sub-class/super-class. Sub-class requires an "is-a" relationship between the classes, which is not the case between Node and LinkedList. For add, the new Node becomes the new root since you add it at the beginning. The old root becomes Node #2 in the list. So you set new_node's next pointer to point at root, then you set the root pointer to point at the new_node.

[@charanpuladas1891]

+Joe James Got it! Thanks for the videos and code on GitHub!

[@markkoenig1590]

Hi Joe, A couple of questions... Say I had nodes that represented people with a name and age. What if I wanted to find a person with a specific name or specific age? How is it possible for me to sort nodes in a linked list using algorithms like Bubble Sort, Merge Sort, Radix Sort, Insertion Sort, and Quick Sort? Also, could I implement a Binary Search Tree to organize data from a linked list?

[@oggiai]

Good questions. If you need to do a lot of sorting you should choose a different data structure. For example, in Python you could use a list of Person objects, then it would be very easy to sort them by name or age. Or in Java you could use an ArrayList of Person objects, which would also be quite easy to sort using a custom Comparator. However, if you just need to occasionally iterate the objects to locate one with a specific name or age then yes, a Linked List would work fine for that, and it's easy to iterate the linkedlist. A binary search tree is a different data structure than a LinkedList. They both use a Node to store the data. A tree would have left and right children instead of just having a Next node. And inserting or removing from a BST is more complicated than with a LinkedList, since order matters in the BST. I have a good Python BST video that might help you, and code is posted on my github site.

[@pk_1320]

Or use dictionary - chimera.labs.oreilly.com/books/1230000000393/ch01.html#itemgetter It's Neater as it uses Python's default data structure

[@saivenkat1409]

In order to display entire list We use loops And This_node=get_node() To link to next node

[@antarasargam6299]

Sorry, new to programming here. I did a lesson on Linked Lists in C/C++ where they create a Node using the data field and a pointer to next node. In C/C++, we use a struct Node* to create a "Pointer" to the next node so that it contains the "address" field of the next node. In Python, I don't see that happening. It's just like any other variable (self.next_node), so does it even store the address of the next node? If not, what exactly does it store?

[@oggiai]

+Antara Sargam unlike C, Python takes care of a lot of the grit for you behind the scenes. A variable is a pointer to the memory address where the object is stored. Every variable also has meta data.

[@antarasargam6299]

Thanks a lot for replying Joe. So if i'm not wrong, the reason we're getting the memory address of the next Node in the self.next_node is because the "instance" is created as the variable. So it's a variable of type class Node. If it were any other variable, eg, type integer, we wouldn't get the same result.

[@hujake5406]

sir, why do we need to have object in "class Node(object)" and "class Linkedlist(object)" ? is object parent class of Node and Linkedlist? but I don't get what object is.

[@oggiai]

Everything is an object in Python, so every class is a subclass of the object class. You don't really have to put object in the parentheses because Python knows that it is implied even if you don't write it there. In other words, a Node is an object, but the code will still work if you remove the word 'object'.

[@shelbygt5004]

Great tutorial! Which editor are you using?

[@oggiai]

shelbygt5004 Thanks. I did this in PyCharm, but I usually use Notepad++ for Python development. I'm trying to use PyCharm more.

[@svitlanaripa6294]

super video! Thank you!

[@mansamusa-el4705]

Could you explain the difference in implementation between a normal Python list and this linked list that you have created in one sentence please?

[@oggiai]

+Mansa Musa-El a Python list is similar to a Java array in that it uses a contiguous block of memory, and any item can be accessed instantly using its index. In a Linked List the items are stored in different areas of memory, and the items can only be accessed by iterating (use each item to get to the next item using its 'next' link).

[@mansamusa-el4705]

Joe James Thank you much, sir. May the LORD bless you bountifully for clarifying this subject for me.

[@nirbhaykumarsingh7727]

Hello Joe; I am New to Python and your videos were quite helpful to me. I was wondering what does "object" in the Parenthesis after both the class name signify ? i.e. "object" in "class Node (object): " and "class Linkedlist (object):". Thanks in advance...

[@oggiai]

+Nirbhay Kumar Singh that is how Python handles inheritance. If a class is a subclass of (or inherits from) another class then you put the super-class in parenthesis. By default, all classes in Python are subclasses of the object class. Putting object in parenthesis is optional since it is already implicit, and it just means that these classes are subclasses of the object class.

[@diegoiruretagoyenaoliveri6050]

Hi ! What do you use to record your screen and voice ?

[@oggiai]

+Diego IRURETAGOYENA OLIVERI I use Camtasia for screen and voice recording, and Sony Vegas for video editing. I know a lot of people at my work (Cisco) also use Camtasia, so it seems to be widely used. Most of my content is in Power Point, but I also use the Notepad++ text editor in many of my videos, and I use the ConEmu command line console. Camtasia can capture screen video from any of those sources -- whatever's on the screen.

[@jhicinternational]

Good explanation+++

[@robincchauhan]

what editor are you using here for python coding ?

[@oggiai]

Notepad++

[@cplearners9244]

It would be better if a light theme is used for better understanding. Thanks a lot.

[@AnnaProgramming]

Hi, very good work,very interesting, good visualization. (Also I think that for beginners(I will take it upon myself to decide that you made it for them) it's hard to understand what is going on in your programm coz your explanation isnt very detailed.)

[@oggiai]

+Беллатрисса Лестрейндж Thanks. I realize I rush through the explanation. Average view time on my videos is 4 minutes, so my fear is that I produce a great 15 minute explanation and nobody watches it. In any case, I'm doing my best. I hope it helps you.

[@rounakvyas9713]

+Joe James Can you explain the add() function again? Explain the function line by line if possible? Thanks

[@oggiai]

+Rounak Vyas to add a new node you must pass in a data value. And we will add the new node to the beginning of the list. Since you called Tree's add function, we first create a new node by calling Node's constructor. We pass two parameters to The Node constructor: the data and the next node. Since we're adding this new node to the beginning we pass the root node as the next parameter. Then we set the tree's root pointer to the new node we just created. Lastly, we increment the counter for the list length.

[@halcyonramirez6469]

don't get the add method for the LinkedListClass how come the new nod becomes the root node? wouldn't that mean everytime you add a node then the root becomes that node?

[@oggiai]

+Halcyon Abraham Ramirez yes, that's right. The "root" is just a pointer to the first node. When you add a new node you add it at the beginning, and update the root to point to the new node. The other alternative - adding the new node to the end of the list - would require either traversing the entire list to get to the end (very bad idea) or maintaining another pointer to the last node in the list.

[@halcyonramirez6469]

Wait so when you insert something on a linked list you insert at the beginning? and not to the end like a regular list?

[@halcyonramirez6469]

+Joe James subbed thanks for the videos i kinda sorta get it now

[@oggiai]

+Halcyon Abraham Ramirez right. Like I said, if you want to maintain a pointer to the end of the list you could add to the end, but in most cases there's no benefit to that, so it's more common to add to the beginning. The nice thing about linked lists is that you can modify them to do what you want. If you want new nodes to be added at the end that's easy to implement using a tail pointer, and there are also bi-directional (doubly) and circular linked lists. I have another video on doubly linked lists.

[@oggiai]

+Halcyon Abraham Ramirez don't think of it as an array. It's not an array. Think of it as a treasure hunt. You're looking for a gold coin, and the first place you look is under the couch. Instead of finding the gold coin there you find a note that says go look in the dresser. In the dresser you find no gold coin, but another note that says go look in the mailbox. Eventually you find the gold coin. When you add another hiding spot to the list it doesn't matter whether it's added at the start or end. Linked lists are very rarely in sorted order, and its impractical to sort them. And a linked list does not have a contiguous block of memory like an array does. Each node may be in a different area of memory.

[@anon-sl4vp]

am i rite in thinking a double link list has 3 boxes [ prev | data | next ]

[@oggiai]

Just watch my doubly linked lists video. But yeah, that’s right.

[@baothg]

Thanks you very much !!

[@omssw]

Good expalnation, but too fast for me. I'm new in programming so please explain it in details if possible.

[@oggiai]

+Omar sorry this one is kinda fast paced, and linked lists is not a simple concept for beginners. I don't have any easier videos on linked lists, but many of my videos go at a slower pace and are easier to follow.

[@vaibhavmathur8804]

should be self.root = this_node.get_next() i.e root (to be remove which have no previous link ) should change to next node of this_node(root) ???

[@oggiai]

yes, I already fixed that a year ago. Please see latest code on my github site at GitHub.com/joeyajames/Python

[@origanem8250]

Hey Joe, put a comment in the video so you don't have to explain everytime

[@Kingofqueers1]

how come you pass in the word "object" in both classes

[@oggiai]

That’s not a parameter. For functions, anything inside the parentheses is a parameter, but for classes it means inheritance/subclass.

[@tammyton]

You explained this way too quickly

[@SequoiaAlexander]

I thought it was great! I just wanted an overview.

[@segreyfurt]

myList.remove(12) - doesn't work. Problem in 31 line, fix to: self.root = this_node.get_next()

[@segreyfurt]

oh, shi... lots of comments about that))

[@diolaoyeyele774]

Lifesaver

[@jaiveekshah1232]

Hey Joe, Even after removing the node from the list the get_size() gives the same number of nodes which was prior to remove(). It still counts the node even after it is removed. Please have a look. Thanks. Its a great video though. :) (y)

[@oggiai]

+Jaiveek Shah I tested it and it worked fine for me. Make sure you don't have line 44 self.size -= 1 indented too far. That line has to execute every time the if statement in line 39 executes, if this_node.get_data() == d: Line 44 should NOT be part of the else block in line 42. The code as I have it on github should work fine.

[@jaiveekshah1232]

+Joe James Thanks for the quick response. I was doing the code from this video and so i was getting an error but your github code is perfect. The only difference between your video tutorial and github code was in line 31, where the self.root = this_node in video but on github its self.root = this_node.get_net(). It works fine for me now. Thank you so much for the explanation and i really appreciate your valuable time.

[@luhar9669]

joe, how to get code orderd linked list??

[@oggiai]

+rahul macharla linked lists are not really intended for sorting. If you need to sort items then you should use a List in Python. Of course you can write a sorting algorithm for Linked List, but it will be much slower than sorting a List.

[@oggiai]

Rahul, I added the Linked List sorting code to my GitHub site, and will post the sorting video to KZbin in a week or so.

[@astheshooter]

this goes crazy on 2x speed and im not joking

[@abc_cba]

I just got a sapiosexual crush on you. Thanks for such a lucid explanation !

[@KolaIL]

well he did say fast

[@oggiai]

Yeah, I have another similar video (same topic) that’s at slow speed.

[@mihirkumar8832]

What is with that intro music :/

[@27Football27]

so fast D:

[@charlesjsescoto]

i was watching 2x

[@sebwebio]

is your intro Beethoven Virus?

[@meepmeep3874]

Way too fast. Like you're teaching people who already understand?

[@oggiai]

+Not Name I know. I was experimenting with tempo in my videos, and this one is too fast. I may re-do it at a normal pace when I get time.

[@meepmeep3874]

Thank you, sorry I was a little rude. Internet attitude took over for a moment. The content was very helpful with some pausing. :)

[@TheWonderJr]

it's true though. I'm learning python right now and this just seemed like a video made for people who already use python

[@TheWonderJr]

also what program do you use?

[@oggiai]

Done in Notepad++. Sorry about the speed, I was late for the bus.

[@hadithpoint]

Thank you but you are a little too fast for someone explaining complex topics like data structures.

[@oggiai]

I have a different video on same topic that is much slower. I think I put a link in the comments.

[@nevikgnehz368]

What a dramatic intro

[@jennilithgow7924]

Why is this so ridiculously fast? Most people's minds don't work at this speed. If yours does, congratulations, but if you want to teach others, you need to slow it waaaaayyyyyy down.

[@oggiai]

+Jenni Lithgow you're right. I know. But haven't re-recorded it yet. You can play it at slower speed.

[@nzstr]

go slower and explain everything you are doing

[@oggiai]

+nzstr thanks for the feedback. I have some very clear slow paced Python videos and some fast ones. This one is quite fast and assumes you already have a firm grasp on Python. I'm happy to hear more feedback on which style people prefer. I'll keep that in mind for future videos.

[@ashfernandes7327]

Sorry, but this is really confusing.

[@oggiai]

This one is fast. I have a much slower version that’s easier to follow

[@philippecolin151]

Sorry useless explanation, too fast or most likely my brain is too slow

[@oggiai]

That’s why it says Fast in the title. I have a separate much slower paced video on Linked Lists.

[@TalkswithJinesh]

Very fast, disliked it!

[@oggiai]

That's why the title says (fast). I have a much slower version that is linked in the description.

[@proshlok1]

there is a mistake at def remove(self,d) It should be self.root = this_node.get_next