Python Tutorial - Organize data with LINKED LISTS

Similar to an array, a linked list is a linear data structure. However, the elements of a linked list are not stored at contiguous locations. Instead, we link the elements using pointers. Let's break this down. Imagine a train. A train is made up of a series of cars, where each car contains a piece of data. In this case, we'll be keeping track of how many crates are in a given train car. In the first train car, we have five crates. In the second, we have 12. And in the last, we have 20. In addition to the number of crates, we are also storing a chain or link to the next train car. We call this link our next pointer. And we are pointing to the next train car on the train. You'll notice for the last train car's next pointer, we point at nothing. That's how we know this is the last element in the linked list. Now, because each link is a pointer, or in other words, holds an address to a memory location, this data structure does not have to be stored at contiguous locations in memory. We can link to any location in memory. In our diagram from before, a linked list appears to be a linear data structure. And it is. But since we have the pointers, our data can be anywhere in memory. We just need the memory address, or in other words, the next pointer. This means if we have access to the first train car, we can get access to the second train car and its data by looking at the first train car's next pointer to see where the second train car is located in memory. Finding the second train car, we can follow its next pointer to find the third train car and its data. Now, the third train car has a null next pointer. So that means this is the end of the trail for our linked list. And we are at the last train car. Notice we can't jump from the first train car to the last. And that's because we must follow each individual train car's next pointer to find the following train car. Introducing some terminology here, we call each train car a node. A node contains data and a pointer to the next node. The first node in a linked list is called the head of the list. Through the head of the list, the first node in the list, we can access every other item in the list by following the pointers. This gives you another way to store your data.