Python Data Structures #2: Linked List

Code below (some minor improvements have been made since the video was released)... In this video we'll begin by discussing the basics of the linked list data structure, and towards the end, we'll move over to a coding editor to implement the ideas in Python code. In this video, as well as the last, I am using Python 2.7. For some reason, I was talking fairly slow in the beginning so you may want to up it to 1.25x speed.
(PYTHON 2)
► Code for this lesson: github.com/bfaure/Python_Data...
(PYTHON 3)
► Code for this lesson: github.com/bfaure/Python3_Dat...
****
► Python Algorithms Series: • Python Algorithms
► GUI development in Python (WIP): • Python GUI Video Tutor...
Further reading: www.cs.cmu.edu/~adamchik/15-1...
In computer science, a linked list is a linear collection of data elements, in which linear order is not given by their physical placement in memory. Each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing efficient insertion or removal from arbitrary element references.

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

[@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!

[@user-eq9zo5vj7c]

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

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

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

[@gabrieldewraj3502]

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

[@alexlencz7346]

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

[@patrickmutuku9579]

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

[@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!

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

[@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!

[@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!

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

[@softwareengineer8923]

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

[@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!

[@nackyding]

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

[@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!

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

[@apalsnerg]

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

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

[@jordonmarchesano9219]

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

[@QVL75]

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

[@surajkumarkabbur2550]

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

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

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

[@b.f.skinner4383]

Fantastic explanation of the topic, thank you!

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

[@WillSmith-ui1pb]

Very clear and concise. Thank 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

[@jingyuchang1885]

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!

[@BrianFaure1]

No problem, thanks for watching Jingyu!

[@akboss4341]

Man !This is so crisp ! Nice tutorial

[@bhavishahadiyal7836]

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

[@dennisearle]

Thanks, Brian. Really helpful.

[@kelliroache2041]

Awesome tutorial! Thank you

[@lamedev1342]

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

[@varunnarayanan6301]

Its 2022 still the best linked list video on python

[@nuandatun]

Thank you so much! Your explanation really helped!

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

[@unclesam997]

Super good explanation!

[@hughg.rection6778]

Simple and clear， great tutorial！！

[@BortSlampson]

This is awesome, thank you!

[@shrikantkarki4966]

Thank you sir.It helped a lot.Keep posting videos

[@denysivanov3364]

Great video! Thanks for your work!

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

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

[@RahulKumar-tu7fm]

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

[@dontworryaboutit17]

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

[@Abhishek-fe3zs]

Your channel is gold

[@jimmorrisshen]

Nice video. Good teacher. Great programmer.

[@glenfernandes253]

Fantastic explanation! Thanks!

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

[@darksoul.0x7]

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

[@vaibhavtiwari2941]

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

[@umerehsan6677]

Great work. Really appreciated

[@polsiv]

Great video dude, it helped me a lot!

[@akashp4863]

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

[@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?

[@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?

[@precisionchoker]

Many thanks , I've learnt a lot :)

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

[@turk-money]

Great video, thanks for the post.

[@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?

[@limtis]

Very helpful, thank you!

[@hsoley]

Best video on the topic

[@vivekkuma1]

Excellent Explanation Sir

[@RishiKumar-zs4vj]

Really Useful keep on doing more videos please

[@intisharalammisbahul9927]

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

[@dark4137]

Thank you much Brian! This was an excellent tutorial!

[@anjalipc8649]

Thank you sir..It was very informative.

[@gabinkundwa7215]

thank you for this tutorial it is simple and helpful

[@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!

[@reynaldoruizflores]

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

[@rensogomez5753]

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

[@pacificknight414]

Thanks, very helpful!

[@urass1765]

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

[@jpchato]

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

[@alixaprodev]

Thank you so much for your help

[@ahzamejaz6241]

Thank you so much this helped me a lot.... :)

[@josephbianchi6976]

great video!!!

[@yulyalim5178]

Thanks for the video. Yes, that would be handy to have the code :)

[@BrianFaure1]

Sure thing, I've added it to this git repository: github.com/bfaure/Python_Data_Structures/blob/master/Linked_List/main.py

[@yulyalim5178]

Brian Faure Thanks! 🖖🏼

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

[@sahajkapoor4718]

Pretty good tutorial for me as a beginner

[@mohammedhelal5778]

Hi Brian. I was wondering, in the erase function, would you have been able to stop at index-1 and set cur_node.next = cur_node.next.next instead of bookkeeping with last_node?

[@BrianFaure1]

Hi Mohammed! I'm pretty sure that would work, just off the top of my head I think you'd need to cover it differently if the user erases the element at index 0 (because index-1 would be -1 in this case). Thanks for the comment!

[@mohammedhelal5778]

Ahh good point. Thanks for the vids man!

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

[@parth_149]

@brian Can you share code for Reversing the linked list? I'm having confusions for it.

[@shankarmuduli1540]

great explaination

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

[@gloriaramlal8027]

Hi Brian: Can the Data field contain different types of data (as in a List or a dict) and can you show how (for both if possible :)). And does the append method in your code refer to what you created or the built-in version?

[@BrianFaure1]

Hi Gloria, the data field can definitely contain different data types including list or dict (as you said) as well as any other built-in or user-defined classes. For example, to insert a list object into an instance of the linked list you would just pass it as the parameter: example=linked_list() example.append(['a','b','c']) example.append([1,2,3]) Then if you were to call the display function (example.display()) to print out the contents of the linked list it would look like: [ ['a','b','c'], [1,2,3] ] The append in the code (being used inside the display function on line 31, not the append method we defined) is the append function the comes with Python list object. Thanks for watching!

[@nokibulislam9423]

is it okay to see the implementation after learning the theory if cant solve myself?I just do it alone

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

[@umarpatel5809]

quick question: whats the point of the get function, like i tried my_list.get(1) and nothing happens, isnt it supposed to show the number at the 1st index?

[@croakinglizard2156]

thanks for your help!

[@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?

[@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)

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

[@user-vr7pm5rx2f]

@Brian Faure. Thanks for your tutorial.

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

[@CowCow5354]

For the length method, can't you just initialise a length variable and +/-1 to it everytime u add/delete a node?

[@BrianFaure1]

Yes, and that would certainly be more efficient in most use cases. Thanks for watchin!

[@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)