Okay. We're going to do more list implementation. This is such a critical topic and the past experience with people who are beginning programmers is they need a lot of practice to try and understand what pointers are, how they get used, and the use of dynamic memory, heap-based memory. This is among the most sophisticated things you'll learn in this class. Without really practicing the basics, it can be a big hurdle. So we're going to see some of the same material we already talked about and we're going to extend it. Again, keep in mind that it's critical to understand these idioms. So if you master these idioms that we're giving you even though they're for very basic cases, they still will let you do very much of the same thing and more advanced instances. So let's look at this code. Again, a typedef shows it's self-referential nature, a list appears inside the list. So it's a piece of data with a link to next. Then we have things that operate on such a construct. For example, we can tell if a list is empty by seeing whether the current pointer at the list is null. That's the sentinel for being empty. Let's look at creating a list. We can create a list out of a piece of data. So this would be data. Notice that when I say int d, if you're doing this with some other data type, you have to again just use the same thing, the same idiom. You just change what's being deposited in the list element. So we take the list and create its head. The way we create its head is we go to the heap using malloc out of the standard library and we create an element size of list we saw on a previous case that's 16 bytes. Then inside the data member, we store d and inside the head next, we store the null pointer. So in effect, when we initialize a list to a single element, the single element has as its next pointer the tail or null. Then what you return from creating that list is the head that you found dynamically. Now if we want to build the list, that we're going to do by adding to the front of the list. So remember the list is like a close line, you can't just put things into the middle, it's not like an array. So it has limitations but it has features that it takes advantage in certain algorithms. So not every algorithm wants to use an array, but certain algorithms would benefit by using list access even though you don't get to randomly look at elements inside a list. So searching a list can be what's called order n, the size of the list. So look and find something as opposed to order one, which is how you go and look something up in an array. So we add to the front of the list, we give it that current head of the list. We give it the data that we want. With that piece of data, we create a list. Remember what that does, that goes off and gets malloc. Makes up an element, sticks d in it, and then what was the current head is now going to point at next. Then, this newly created element will be the new head of the list. So we had a list of how many ever elements, we create a new one with its head, we link its next pointer to the old list, and the head is now the head of the whole list. That's add to front. Now, let's say we have an array which is another data structure, and we want to take an array and convert it into a list, how would we go about doing that? Well, we can do array to list. An operation that we want to use often. Again, we have some array of data. We have the size of the array or even a sub-array. We start by creating the list using the first element of the array. Then, until the size of the array, we keep adding to the front. So we have to update the head, keep adding to the front one by one, and we get a list created. We return head at the end of this. We've already seen how print list works. So again, a lot is going on. These things remain idioms for how to process things one by one. Remember in our print list, we're using the sentinel head null and then we stop when the head is null. Otherwise, we keep doing something and in here it would be print. So that was our print list. Now, we're going to take a data array of six elements, 2, 3, 5, 7, 8, 9. We're going to create a list from them using that data array, then we're going to print it. What we're going to notice is 2 is the first element, then 3 becomes the first element, then 5. So in the end, because we're heading on to the beginning of the list, 9 will be ultimately the beginning of the list, 8, 7, 5, 3, 2. That will be the order in which elements were placed on the list. So let's leave that. Try that code. Now, execute it. Sure enough, we print single. So I did something. I used an old thing that gave the heading as single element list and it isn't, 9, 8, 7, 5, 3, 2. Let's go and correct that program. Though we found a little bug. That's always useful. So I'm going to go and correct that. So that title shouldn't be a single element list. So that's going to be data of six made into a six-element list. Okay. Let's recompile this, and now run it. Data of six made into a six-element list. 9, 8, 7, 5, 3, 2. Okay. So again, study that program carefully along with the other beginning material, make sure you understand how malloc fits in. How is malloc producing an element of the list? Make sure to understand how next works, how you have this linkage that gets you a linear list. That should get you familiar enough that you can start handling lists and even more complex data structures that involve pointers.
