Python Data Structures #2: Linked List

[@Noooname945]

@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.

[@BrianFaure1]

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.

[@hoangminhnguyen2191]

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?

[@skillfulactor09]

Can you make more I love yours do you have stuff on graphs or heaps or merge sort

[@JF-di5el]

So Chinglish

[@LemesaElias]

I struggled a lot with DSA until I found this channel. Now I struggle a lot less thanks to you.

[@domss1174]

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

[@AbdulSamad-qv4tr]

THANK YOU

[@seanli75]

Thanks for the timestamps man! It was really helpful!

[@code4code857]

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 !

[@MCMB29]

5 years later and this is still a great video! Awesome in-depth explanation.

[@printdaniel]

+ 5 months! Stil great

[@austinbao]

I have searched through KZbin to find someone to explain Linked lIsts and I gotta say, your video was the most helpful. Thank you so much!

[@BrianFaure1]

Glad to hear it helped you, thanks for watching Austin!

[@gabrieldewraj3502]

This man deserves an award for how well he broke down every concept!

[@Julia-rq7uj]

i must say, this is the simplest coding of linked list i've seen so far on the internet

[@sauravraj1085]

Lolll, this is the most general and common code for linked list.

[@yunsizhang3847]

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 .

[@tguigz]

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.

[@djlazer1]

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.

[@MrBloodshadow323]

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!

[@softwareengineer8923]

Your explanation is too clean and lucid.Thanks for a great video!

[@mouseen92]

Excellent video, really clear, direct, concise and easy to follow. Amazing, so many people on KZbin need to learn a thing or two from you.

[@zulfiqarali1212]

beleive me you are one of the greatest teacher of coding. oh its true ,,,its dammmnnn true... keep it up.

[@BrianFaure1]

Thanks so much!

[@Teachjarunjoshi]

yes its good

[@bernardo013]

What Kurt Angle would say if he was a developer haha

[@mr-engin3er]

I searched for python linked list and watch many tutorials but I found this tutorial is best. expect more python tutorials from this channel.

[@patrickmutuku9579]

I love your tutorials. I wish I could have discovered them before starting CS110 three months ago. Keep up the great work

[@varunnarayanan6301]

Its 2022 still the best linked list video on python

[@alexlencz7346]

Extremely helpful tutorial! Clear, concise presentation. And Python is also my favorite language!

[@EugeneMillerErm]

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.

[@collintech057]

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

[@yajingli1990]

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!

[@C-Swede]

You're a great tutor! This feels like it brings me closer to where Python will finally "click" with me.

[@BrianFaure1]

Thanks so much!

[@sanjiblamichhane]

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().

[@apalsnerg]

Thank you so much for this! This is just what I needed to understand linked lists properly!

[@ETR12935]

First dsa video! the keyboard sound was just 🤩

[@grifmang]

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.

[@commandprompt7171]

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

[@PrinceAdom]

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

[@reynaldoruizflores]

Thgank for the tutial as suggestion for future video. How to choose a Data structure? Pros vs Cons. Speed Big O notation

[@GoldPlatedINDIAN]

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.

[@dannyskillet7315]

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.

[@zwj808]

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!

[@jpchato]

my_list = LinkedList() my_list.append('3 years later but still great, thanks Brian') my_list.display()

[@bhavishahadiyal7836]

Best explanation ever please never stop making great videos, we will subscribe

[@motheotreasurepuso0724]

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

[@YorkshireSpud]

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)

[@brniesenders4288]

Thanks for the video. Linked Lists are making sense thanks to your teaching! Question: When we erase(index) a specific node, I understand how we are simply bypassing the specified index and assigning the node on the left of the specified index to the node on the right of the specified index. What happens to the specified index that gets "erased()" Is it erased from memory ? Below is just the erase method that was defined inside the linked_list class and then calling the erase() on an instance of linked_list def erase(self,index): if index >= self.howManyInThere(): print("ERROR: 'Erase' Index out of range!") return None 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 return cur_idx += 1 my_list.erase("The node that gets erased") What happens to the node that gets erased()? Hope this isn't a dumb question, I'm just curious.

[@nackyding]

Thanks needed a quick refresher on linked list. Going to see if you have double linked list now...thanks again

[@chandragirivishnuvardhan7654]

@Brian Faure, Your explanation is pretty awesome. But, I think you have missed the "insert" operation.

[@darksoul.0x7]

I have an error on display function it's say that 'None type' object has no attribute 'data'

[@intisharalammisbahul9927]

I looked for copper but found diamond. Loved the video, will help me with my exam.

[@jonassteinberg3779]

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.

[@charlielin188]

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.

[@QVL75]

I love your tutorial video. Excellent presentation. Very clear explanation. 2 thumbs up.

[@vipinamar8323]

The length function is wrong, you need to add 1 to account for the last node.

[@clashgamers4072]

The head node(empty node at the start) will count towards the total so it kinda cancels out

[@谢生-b2g]

@Brian Faure. Thanks for your tutorial.

[@hemanthkumarar]

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

[@vortsynx3151]

Python list index start from 0 while .length() return how many data is inside the list. Say I have this list... list = [1, 2, 3, 4, 5] The max index is 4, because the first address started from 0. list[0] = 1 list[1] = 2 list[2] = 3 list[3] = 4 list[4] = 5 See how the last index is 4. If you try to print the same list using list.length(), it will return 5 as there is a total of 5 data inside the list. If you do index > self.length(), it would make it possible for the user to try to return list[5], which is non-existent as the max index is only 4.

[@rensoagomez]

antipop to the mic and this is gold. thanks a lot.

[@dontworryaboutit17]

This makes sense. My prof should not be teaching, haha. Thanks for explaining while making it so concise.

[@jordonmarchesano9219]

awesome man thank you. Been having trouble with data structures but this seriously helped a lot.

[@Abhishek-fe3zs]

Your channel is gold

[@ch33ze0g]

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

[@quangnhat-uc4ri]

yeah the same question and he also wrote in the same style in the get fuction . It has been 4 years and do u know why ?

[@nostestwu8689]

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

[@bakerct90]

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.

[@lamedev1342]

Very useful, I'm in gr 11 and learning this it was well explained!

[@hsoley]

Best video on the topic

[@Skeeb04]

i just wasted 2 hours too complete this get method finally thanks

[@GuitarreroDaniel]

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.

[@ameynaik2743]

Hi Brian, Thanks for this video where you code as you explain. I have one question, to maintain appending to be O(1) operation, why can't we append to the head of the linkedlist. This way we need not need track of its tail (as you explained in @Xiufeng Shi post) def appendfront(self,val): new_node = Node(val) curr_node = self.head new_node.next = curr_node.next curr_node.next = new_node

[@BrianFaure1]

Hey Amey, looks like a good O(1) solution to me (I think appending to the front is actually called prepend but it doesn't really matter)! And, like you say, you could implement a similar approach to append to the end if you maintained a self.tail variable and updated that after each insertion. Edit: oh, actually I'm not sure if the function works as you have it, I would write it as follows: def append(self,val): new_node=Node(val) new_node.next=self.head self.head=new_node

[@ad2894]

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)?

[@surajkumarkabbur2550]

Awesome video..👌👌 One of the best I've seen for python tutorials.👌

[@ComSci-student]

Great content Brian. Thank you.

[@nestoriyagamongerto7881]

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?

[@vortsynx3151]

>> cur = self.head it started from head >> while cur.next!=None: > idx+=1

[@akashp4863]

Thank you. i know i can watch the video again and understand it

[@dennisearle]

Thanks, Brian. Really helpful.

[@rembautimes8808]

Good video but with dynamically typed language like Python how would a linked list be of use? Maybe in a distributed environment where the objects are stored in different machines

[@yolamontalvan9502]

Thank you I was wondering how do you create pointers in Python. My favourite languages are C++, C#. It took me three years to learn them. I think I’m going to give Python a try, it looks easy. Thank you.

[@pratiknalage1666]

This tutorial is great. Thumbs Up! I was just wondering if there is any built-in package for linked list, just like in many other languages.

[@BrianFaure1]

There isn't one built-in that I know of but you could easily install a package such as this one: pythonhosted.org/llist/ . On the other hand, the built-in regular list object in Python is fantastic and can do most of what you could do in a linked list, but faster. Thanks for the nice comment!

[@sarvesh_k]

hi @brian, getting error on if check if index >= self.length(): TypeError: '>=' not supported between instances of 'int' and 'NoneType'

[@BessedDrest]

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

[@b.f.skinner4383]

Fantastic explanation of the topic, thank you!

[@JohnDoe-rr8uf]

Oh, it's like a snake game. Coded that yesterday.

[@akboss4341]

Man !This is so crisp ! Nice tutorial

[@urass1765]

This video is very helpful for me to understand the linked list. I thought it would be very complicated 🤔

[@Sreekanthraja7]

@Brian Faure, Thank you for your videos. I have a doubt in linked list implementation,why are we not checking if head is None while appending Data(like in if else statement below). I can see that you are not inserting any data in Head node def append(self,data): if self.head==None: self.head=node(data) else: current=self.head while current.next!= None: current=current.next current.next=node(data)

[@wangnan173]

THANK YOU really!!! The only thing I can't understand is the % right before my_list.get(). What does it do exactly?

[@ad2894]

You mentioned that the list object in python can be thought of as an array type data structure. I thought lists in python could be changed but arrays could not. If you could clarify this that would be really appreciated! Awesome content by the way!

[@BrianFaure1]

Hi Adam, yes the list in Python isn't technically a traditional array because, like you say, it's mutable and its length can be changed. It also allows for different objects to be slotted in next to each other (for example; a string, an integer, and a float) and this wouldn't be possible if each element was assigned a fixed size in memory. Python lists _are_ however similar to arrays in that they accessed using integer indices and this was pretty much the reason I included that comparison in the video. Thanks for the nice comment!

[@ad2894]

Thanks!

[@aamirmomin669]

Hi, thank you for taking the time to create this video. I had a question surrounding the implementation of the get method for linked list. Isn't a linked list different from an array in that you cannot reference a certain index and grab it, rather you have to jump through every item in the linked list O(N) time complexity. So why do we have a get item specific to an index added?

[@mizzzile]

Quick and short recap.

[@RishiKumar-zs4vj]

Really Useful keep on doing more videos please

[@ROC4Life96]

What colour scheme did you use for your command line? I'd like to switch my terminal to that colour scheme

[@BrianFaure1]

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.

[@gate7689]

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?

[@BrianFaure1]

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).

[@gate7689]

@@BrianFaure1 Thank you. That clears my doubt.

[@RahulKumar-tu7fm]

@Brian Faure You did great tutorial. I really enjoyed the tutorial.

[@soundwaves1752]

I don't know if I am not the one getting it, but it's like the length method doesn't include the last node. is that meant to exclude the head.

[@zusm]

for get you can just have display return elems instead of print that way you can just return self.display()[index]

[@indranildutta4252]

Watching in 2021... Very Cool....

[@shibajichatterjee3190]

Brian .. thanks for the nice tutorial. I have one question.. as I learned in python once you assign an object to another variable like here last_node = cur_node, both are basically pointing to the same object. when you traverse through the list by cur_node = cur_node.next, should not that already change the last_node also.. then how the last_node remebers the prior node ?

[@BrianFaure1]

Hi Shibaji. It can certainly get confusing sometimes working with references to objects in Python because of how little information is shown to the programmer. In this case when we call 'last_node=cur_node' this will indeed cause both 'last_node' and 'cur_node' to point to the same object, though, when we call 'cur_node=cur_node.next' this actually only changes the object 'cur_node' is pointing to while leaving 'last_node' pointing to the original object. If you'd like you could prove this to yourself and make it a bit easier to understand by printing out the 'last_node' and 'cur_node' on each iteration so you can see the objects they point to change as the loop proceeds. Thanks for watching and let me know if you have any other questions!

[@shibajichatterjee3190]

Brian Faure thanks for explanation..I tested by printing the variable memories and understood it now.

[@vaibhavtiwari2941]

Thanks for your wonderful tutorial. I was stuck in the linked list part from about a week . You were awesome

[@Neha_H46]

Thank you for the videos in python. Can you please do a video on detecting a cycle in linked list with input/test case?

[@mouseen92]

Quick question Brian, the way that you wrote the append function it seems like it places the new node at the end of the Linked List, so the time complexity will be O(n), why would you not simply add the new node at the head and then have new_node.next point to cur_node. If I am correct this time complexity will be reduced to O(1), let me know what you think.

[@BrianFaure1]

Hi Ely, using the method you lay out would certainly be O(1) but normally when I think think of 'append' it's as adding something to the end rather than the front. I actually answered a similar question asked by Xiufeng (it should be the pinned comment) and was able to come up with another approach which would achieve a O(1) append using an extra 'tail' variable (we attach the new node to the 'tail' then update the 'tail' with our new node), so check that out if you're interested. Thanks for the comment and for watching!

[@anjalipc8649]

Thank you sir..It was very informative.

[@nabiljada413]

Can you create a video on Python's GIL(Global interpreter lock)??

[@turk-money]

Great video, thanks for the post.

[@maanupurisai398]

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?

[@vortsynx3151]

cur = self.head cur.next = None

[@umerehsan6677]

Great work. Really appreciated

[@akshatdhiman8819]

Make videos on stacks and queues implementation in python.

[@jax911123]

Hey Brian, I am novice at python and would like to understand in more details following code plz while True: last_node = cur_node cur_node = cur_node.next if cur_idx == index: last_node.next = cur_node.next return cur_idx += 1

[@daramgk4877]

Hi, I'm not a CS student and I am trying to learn the stuff from the internet. I'm fairly new to 'class' and I was wondering why the node class and linked_list class are separated. Thanks

[@kewtomrao]

The video was really helpfull.I have one doubt.In c the head pointer points at the first node.Here too it does that but it is also a node right?So the first node of the linked list will be the head?Am i correct?

[@vivekm4945]

Hey Brian. The append method in your code is traversing to the end of the list for each append. I think it is O(n) to add a new node based on the code. Can you explain how it is O(1)?

[@BrianFaure1]

Hi Vivek, in this implementation the 'append' method is certainly O(n) as you say. You could improve this to O(1) if you always maintained a reference to the last node in the list and simply appended onto the end of that inside the 'append' function. Some further improvements could be made beyond this, such as maintaining an integer size attribute which was updated when you append/erase to optimize the 'length' function from O(n) to O(1). Thanks for the comment!

[@pedrocalaisguerra]

​@@BrianFaure1 I think this is the flaw of the video: you say inserting is O(1) but present a O(n) implementation.

[@BrianFaure1]

@@pedrocalaisguerra Yes, looking back I can see now that is an issue. I apologize for the confusion here Pedro.

[@RishabhGKoenigseggRegera]

Hey Brian, this was a great video. I was wondering if there is any danger associated with not deleting the data from memory? The way I understand it is that we just "skip" the erased node, but that node remains in memory. Would it be better to erase this node?

[@BrianFaure1]

Hi Rishabh, thanks for watching! In Python when an object is no longer referenced anywhere it will automatically be erased without us having do anything ourselves.

[@emilyli6763]

16:42 and a few of other spots, shouldn't we be incrementing the cur_idex by one before the if statement?

[@codeityourself4847]

no, becuase if you increment the index before the if statement the index will always start at 1 not 0 so the my_list.get(0) will be None, but if you increment it after the if statement, it will check the index 0 first and the get(0) method will return the first elem if it makes sense. basically if you have it before the if statement, your linked list will always start with index 1 not 0

[@emilyli6763]

@@codeityourself4847 thank you so much!

[@codeityourself4847]

@@emilyli6763 you are welcome