Python Data Structures #2: Linked List




[ad_1]

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: https://github.com/bfaure/Python_Data_Structures/blob/master/Linked_List/main.py

(PYTHON 3)
► Code for this lesson: https://github.com/bfaure/Python3_Data_Structures/blob/master/Linked_List/main.py

****

► Python Algorithms Series: https://www.youtube.com/playlist?list=PLEJyjB1oGzx2h88Tj90B5_HadLq339Cso

► GUI development in Python (WIP): https://www.youtube.com/playlist?list=PLEJyjB1oGzx2t9tB-59_BIG4oNolUFHX4

Further reading: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html

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.

Source


[ad_2]

Comment List

  • Brian Faure
    January 2, 2021

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

  • Brian Faure
    January 2, 2021

    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

  • Brian Faure
    January 2, 2021

    Very helpful, thank you!

  • Brian Faure
    January 2, 2021

    Really Useful keep on doing more videos please

  • Brian Faure
    January 2, 2021

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

  • Brian Faure
    January 2, 2021

    Thank you sir..It was very informative.

  • Brian Faure
    January 2, 2021

    sir brian. how did you learn oop? i am looking for resource for learning oop. Thank you.

  • Brian Faure
    January 2, 2021

    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.

  • Brian Faure
    January 2, 2021

    everything went over my head. sorry.

  • Brian Faure
    January 2, 2021

    hi

  • Brian Faure
    January 2, 2021

    Great video Brian! Thank you so much!

  • Brian Faure
    January 2, 2021

    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.

  • Brian Faure
    January 2, 2021

    Thanks, very helpful!

  • Brian Faure
    January 2, 2021

    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

  • Brian Faure
    January 2, 2021

    I think there might be a bug if the user tries to access an index that is of negative number then it will bypass the error, correct me if I am wrong though ?

  • Brian Faure
    January 2, 2021

    Hey I don't think you're print method is correct. Please correct me if I am wrong but shouldn't the loop condition be while cur_node ! = None? It seems like your method won't print the very last element. cur_node.next! = none is the correct behavior for the append function because you need to make sure you don't fall off the list.

  • Brian Faure
    January 2, 2021

    linked list menu

  • Brian Faure
    January 2, 2021

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

  • Brian Faure
    January 2, 2021

    The erase function is hard to tap my head around

  • Brian Faure
    January 2, 2021

    Very clear and concise. Thank you.

  • Brian Faure
    January 2, 2021

    Make sure to not call your append function insert! Insert apparently is a keyword for lists in python and can give you errors!

  • Brian Faure
    January 2, 2021

    sir i please you to make a video on graph data structure and some of its
    related algorithms especially in python.please.because i searched all
    over the internet but no one has explained like you.i have covered all
    the data structure in python except this graph.so i beg you to make the
    video on it. and i will be waiting for you response as a video.sir i am
    stuck. i cant move foreword without learning it.so please upload it as
    soon as possible…..

  • Brian Faure
    January 2, 2021

    Thank you so much this helped me a lot…. 🙂

  • Brian Faure
    January 2, 2021

    I want to know how .next iterates the code

  • Brian Faure
    January 2, 2021

    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.

  • Brian Faure
    January 2, 2021

    Hey Brain, I have a question, why we need to use linked list as we already have list in python?

  • Brian Faure
    January 2, 2021

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

  • Brian Faure
    January 2, 2021

    Great video, and thanks for the Github. It means I can focus solely on understanding the content, rather than typing.

  • Brian Faure
    January 2, 2021

    Are you using ubuntu or mac?

  • Brian Faure
    January 2, 2021

    do you need a nose tissue?

  • Brian Faure
    January 2, 2021

    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?

  • Brian Faure
    January 2, 2021

    What is the purpose of self.head=node(), in line no 9?

Write a comment