Lists, Linked Lists, and Memory - Python Tutorial

- [Narrator] The Python list, despite its lowercase spelling in Python, this is actually a class, the list class. Each list that we create is an instance of the list class, it's a list object. Now, most classes in Python, like say a datetime class, have a limited amount of data they will ever hold in them. Python knows exactly how much memory it needs to store it, but what about a list? How big is a list? Well, it can be any size. It can be zero elements long, it can be 500 million elements long, there's just no telling. The problem is that all the elements of a list, or rather pointers to them, need to be stored in the same contiguous block of memory. This allows us to jump to a particular index of the list by taking the starting point, multiplying the index by the block size, and then adding the two together. Then you go and jump to that spot in memory. So when we create a list, Python needs to find an empty chunk of memory that can comfortably accommodate a list that will potentially grow. Let's say we assume our list will hold no more than eight items, so we find a chunk of memory that's big enough to hold those eight items. Every time we add something to the list, not a big deal, it's super fast. We have room for it. But what happens when we keep adding to that list and it gets too big for its current space? Well, the list needs to be moved. This requires moving every single value from the old list to the new and bigger list, and this operation takes a lot of time. The eighth item added to the list is fast. The ninth item takes a very, very, very long time, longer than if we had just allocated the right amount of space for our list in the first place. Now, some programming languages get around this problem by forcing you to declare the maximum number of things your list will hold upfront. For example, this array declaration in Java. This is declaring a new integer array, the Java version of a list, that is 20 integer long. That way, it never has to reallocate memory or move it around. You can tell upfront how big the list is going to be, but even then, you run into issues if you delete items from the middle of a list. If an item is deleted, you have to take all of the following items and move them one by one. And this is a problem that the Python tuple has solved very nicely. Simply never let people add or remove items. You declare exactly how big it will ever be, and then you can only modify the values inside of it, but you can't add or remove them. But what if there is another way to solve this problem? Going back to our list expansion problem, what if when you ran out of memory, you just added a little note that said hey, the list continues over here in this block, and then you continue on with your list. Now, one problem is that if you want to jump to the the last element of the list, you have to jump to the end of this one first, read the address where it continues, and then jump to the next list. You can't just jump straight to the segment of memory that you want. Now, what if that's not a problem for us? What if we're always reading lists in order anyway? What if we don't want to jump around and let's take this idea to its extreme conclusion. What if every single element simply had a pointer to where the next element was? When you declare a new list, then you never need to allocate more than one chunk of memory because the next item could be stored over here, over there, over there, you can use up all these little bits and pieces of memory. You can trivially, add and delete items from the list without having to rearrange anything else. You just skip over the node you want to remove, and everything else can stay in place. The only thing you give up is your ability to jump to any random index in the list. For some applications, it may be a Faustian bargain, an untenable position, or it may not matter at all. This is a list with linked elements, the linked list.