[MUSIC] Okay, we're going to continue with our topic of how to build abstract data types, new types, user defined types within the C language. And again, the key idea is the use of Struct's. And as we'll see it's very important to understand and how to use pointers. And this time the abstract data type we're going to use is again, a very canonical one computer scientists, it's call the list. The list is a form of what we call a self-referential type. In other words, to make a list for example is to add an element on the front of a list. So you can see that the definition contains itself as part of its definition. In some sense it's recursive, so we see that a lot in computers. Here's a list, a list has a head, head is typically this pointer. And then it points to an element, which points to an element, which points to an element which points to an element, which points to ultimately the end of the list, a tail, a sentinel, and again with a lot of the sentinels that we use to end strings and to end other things. We use the special value 0 or sometimes sharp defined as null. So an element is some kind of data type and then an arrow to the next element, this is next, next, next. We'll see that it's a singly linked list. Later we'll see that there are doubly linked list which allow you to go backwards inside the list as well as forwards but you're paying a price. You have to add a link, which is previous, as opposed to just next. So the simplest of these types is the singly linked list. Now again we're going to use struct list and data struct list. Star next as the definition. So that's going to be each internal element. So each of these is one of those. So each itself is what you might call a list, it's basically data, and then our next pointer, data and then the next pointer. And the head is simply a pointer to list. And we'll type that struct list as list so we don't have to keep calling it struct list. And then here's a way of constructing a list, a simple one. We'd say list head. So again, that's just head, H, HD if there are multiple lists, we might say h1, h2, we might have an array of them in which case they would be list star, and some kind of array. And justice as a head of the list, there is a tail, the tail is zero otherwise null, it could have been null, and again, think of this abstract data type as a clothesline, and we've just created a first element as a clothesline. And we can draw the clothesline and go to the next element until we're at the end at the tail of the list. Creating the list requires something we haven't used till date, which is malloc. Malloc is a special routine that's found in the standard library, standard library.h, so that must be included. And malloc is a routine that goes to what's called the heap which is a pile of storage available to C routine which is dynamic. So it can be in use anytime in the course of the program. And when we go to malloc and we ask for a particular size, like for four it would be four bytes, four bytes is a word we could store in a word and So we say malloc of some size, and that returns a pointer. And that pointer can be used for example to initialize head. And indeed the way we might do this is head is assigned malloc, namely an address, where we've gotten size of list, number of elements and you should try this in code, size of his a special keyword. In effect, it's a keyword that returns as an unsigned long in number of bytes whatever this object is, and that allows us to construct such an object. So we have dynamically allocated space. And we'll see as well, that when you dynamically allocate space, as a good citizen, you'll want to later return the space when it's no longer useful. Of course, it will return itself automatically at the end of the program, but if for some reason you're going to use large amounts of this space, you would be asked to free up the space that's being pointed at and so just as with malloc, there is a routine called free that allows the pointer to amount of storage to be returned to the stack for reuse. Okay and let's see this in code in our next video. [MUSIC]
