Linked memory stores data together with a link to the next location in memory instead of searching all of the data sequentially in memory. By utilizing the link, we can get several advantages over an array. Let's explore how this works and then we'll talk about the advantages and disadvantages of using this. In C++, we're going to call each list a sequential list of nodes. These ListNodes have both the data stored on this left-hand side and a pointer that points to the next piece of the list. So, for example, if we look at a ListNode class, we're going to see that the ListNode class will be a templated class because we want to store integers, and characters, and strings, and cubes, and anything else, so it's going to have a template type T, the class ListNode, and in the public section we'll have both the data. So, this is the data piece here on the left, and then we'll have a next pointer that points to the next element in our list. I went ahead and included a simple constructor. This constructor is a ListNode constructor that takes in data and it includes data, data and a next to null. We'll link together zero or more of these ListNode elements to form what we call a linked list. We'll have two special properties is linked list. We'll have a head pointer that's going to denote the beginning of our list. This is going to point to the very first element, this will point to effectively index zero. Then, we'll have a pointer to the null pointer that marks the end of the list. So, as long as our pointer doesn't point to null, we know we have not yet reached the end. So, looking at a head pointer, if we start at the head, we see index zero is two, index one is going to contain three, index two is going to contain five, and so forth, simply by following the pointers to the next location each time. Looking at the implementation of this in code, we have our listed each file here. Notice that we have a templated class in this class' class list. In this class, we have a public section that's going to denote a ampersand operator. So, this operator ampersand is C++'s syntax to say that we can access a list L. So, if we have a list of integers named L, we can say L at zero, and L at zero is going to call this function. Line 14 is a second member function called Insert up front. So, we need some way to go ahead and insert elements into list. In our private area of the class, we have a ListNode class that's part of the list itself, so is in the list class internally contains ListNodes, and this ListNode contains our data, our next, as well as our constructor, and the very last thing that's part of the list class itself. So, notice this list node pointer head is part of the list class, so list class itself has the add operator, insert a front, a ListNode class internally to it, as well as the pointer to the head. So, all four of these things make up a list itself. Let's think about how we might implement that get operation. If we want to find out what is at index four or index K. I'm going to think about Index four right now, and then we'll generalize now to index K. So, to access index four, we need to start at the head and advance to index zero, and then continually advance to index one, to index two, to index three, and then to index four. Only once we've reached index four, can we go ahead and return that value. Notice that we have to go through every single node in between, there's no arrow that directs us directly to index four. This doesn't exist, we have to follow the path of next pointers. So, implementing this looks like a simple loop. So, implementing this operator square bracket function, retrieving a particular index until loop, we're going to go ahead and define a thru pointer. This is the thing that's going to allow us to advance through the linked list starting at the head. While our index is greater than zero, and while we haven't reached the end of the list, we want to continually go through the list. What does it mean to go through the list? Well, the first thing is it means the thru pointer should go to the next element. So, if we want this first element, we want to follow the next pointer and set thru to be equal to thru at next. So, this is thru its next pointer, so thru no longer points to the first node, but thru now points to the second ListNode. The second thing we want to do is decrement index. So, if we start index at four, after we visited one node, we want to remove one from that, and make it equal to three. So, as we advance through this loop four times, we'll eventually get to thru pointing to the actual data that we're interested in, and we don't want to return the ListNode to the user, because the user doesn't even care about ListNodes. The user wants to know what's the data at index four, so we go ahead and return thru arrow data. So, we're accessing the ListNodes data element. If we think about the runtime of this algorithm, this algorithm is going to take a lot longer to run than an array. So, remember an array, we could calculate the exact offset to a given element. So, if we want to find out what's at element 10,000, we would do 10,000 times the size of the element, for example four for integers, and we know to just advanced 40,000 bytes in memory. On our list, we can't do it in one operation. If we want to access a 10,000 element in the list, we have to follow 10,000 next pointers. So, as the list grows, the time it takes to access a particular element rose with the size of the list. That's scary. But that may also provide some advantages. We'll do some formal analysis in one of the very next videos. Before we actually run the entire code, we need one other thing we need to know how to insert into a list. So, now I have another linked list, this is just a list of cubes instead of a list of integers. But because this is a template class, the exact same code for integers works for cubes. So, suppose I want to insert a red cube at the beginning of the list. So, inserting at the beginning of the list is going to be a particularly easy operation. So, here at head, I don't want to add your point to the orange cube, instead I want to just change head to point to my new red cube. So, the very first element in the list is now the red cube. All I need to do is with the red cube, I need to update its next pointer to be to the orange cube. Suddenly, just like that, I changed where head was located, and made sure I reattach the rest of list, and by doing that, I've created a bigger linked list, and I did that without even looking at any of the elements in the list. So, let's see how we might do that with code. It's as simple as we just described. We're going just to do three things. We're going to create a new node for our linked lists in heap memory. We want to do this the heap memory because the LinkedList may live well beyond this function. So, we don't want it on the stack because we're going to be using it beyond the scope of this function, so we need to do in the heap. Doing this in the heap, we see that we're going to create a new list node right here, and the new ListNode is going to contain our data. Then, we're going to say our new ListNodes next pointer is going to point to wherever the head was pointing to. So, our head was pointing to this element right here, and now our new node's next pointer points to the head, and now we want to update the head to point to our new element. Now, notice by doing that, our head now points to data, and our data now points to what head used to point to. So, we've kept this intact, we've just added a new element in the front of the list. Unlike an array, the capacity of a list is only bounded by the amount of memory you have on your computer. In contrast, we saw an array has a fixed capacity, we saw that an array had to be resized. Not so with the list. In fact with a list, we can just keep adding elements again, and again, and again, to the beginning of the list, and it just keeps growing. It's an awesome ability that we don't have with an array. However, similar to an array, a list is going to have every element being of the same type. So, an integer list can only contain integers, a string list can only contain strings, this is true with an array analysts. So, in both data structures, we're going to be fixed in the way that we store data in the sense of they have to both contain elements of the exact same type. So, let's write a main function and actually see how this works. Here on line nine, we create a new list. This is a list of integers, and we're going to insert elements with data three at the front. So, I'm going to have a list that's initially empty, and now on line 12, I'm going to insert fronts, so I'm going to insert a new node that has value of three, and our next pointer points to null, and then we output what's at list of zero. So, list of zero contains data three. So, we expect list of zero at this point to be equal to three. The next thing is we're going to insert 30 at the front. So, by inserting 30 at the front, we're now changing the head pointer to point to 30, it's next pointer is going to point to where head originally pointed to, which is three. So, here on line 17, we're going to print out list of zero at this point. So, list of zero after this insert, is going to be the first element in list which is 30. Then, list of one is going to be three. We expect to insert three, then print out three, expect to insert 30 then print out 30, then print out three again. Let's see if this works. Moving into linked memory directory, I'm going to run make, and./main. We see we're inserting element three at the front, list of zero is three, inserting the element 30 at the front, list of zero is 30, and list of one is three. It's exactly what we expected. So, to summarize, linked to memory stores data in nodes that are linked together by links or pointers. The basic structure that we have in linked memory, is a linked list which consists of zero more linked nodes linked together, and a LinkedList provides a more flexible alternative to an array, but with some runtime disadvantages. We're going to formally explore what that means coming up. I'll see you then.
