In the last lecture, we discussed how the array and the linked chain of nodes are two of the most fundamental data structures available. With these two data structures in our toolkit of data structures, we will begin building more complex data structures, and we could even use the more complicated data structures that we build as underlying data structures for even more data structures. It's important to see how to use the tools that are at our disposal in case you find yourself needing to implement a custom data structure or some variation on an existing data structure. Furthermore, understanding and building with data structures helps you to know what data structures are more appropriate for certain tasks. In this lecture, we're going to build an Array List, that is the List ADT built using an array.

While some languages like Java provide an entity called an interface, C++ does not have these explicitly. An interface simply provides the list of functions or methods that need to be implemented by any inheriting classes. We can simulate this behavior by creating a class with only pure virtual functions or pure virtual methods. A pure virtual function is a virtual function, like those we learned about earlier in the course, but that has absolutely no implementation whatsoever. It's basically just a return type and signature of a method. In languages like Java, we would call this an abstract method. It's entirely up to the derived classes to implement these functions to provide behavior. So, we'll start by creating a class with only pure virtual functions, which we'll name List. Like the ADT, this class will only tell us what a list is supposed to do, not how it's supposed to be done.

Then in this lecture, we'll inherit from the List class with an ArrayList class, which will provide the list functionality using an array as the underlying data structure. In the next lecture, we'll provide a linked chain based implementation of the same List class and that will be our LinkedList. Cool, huh? Before we dive into code, it's important to note that not every author or instructor is going to provide the same exact set of behaviors that they think a List should provide. But there are several common functions that Lists typically provide, and I've tried to stick mostly to those. Another important thing to keep in mind is there are many different ways to do these implementations once we get to those. We could do implementations with different security and validity checks. We could use templates, and create Lists of template types in order to allow for many different data types.

For example, we're going to just create Lists of integers in order to keep things simple, and focus more on lists and implementations themselves as data structures rather than focusing on the type which they hold. Let's start by creating our List class with only pure virtual functions in it. First, we'll create a new project in Visual Studio called ArrayListApp. So, I've got ArrayListApp here. I'm going to create the project. And then we're going to create a source file main.cpp. And we will also have a header file called List.h to start with.  List.h For LIST.H, I'll just put include guards here. Sorry, define LIST_H, endif, and then in main. I think I'll leave that off for now because we're not going to use it just yet. And we're actually going to use an implementation, so I won't put List.h in there. All right. So, List.h, inside here we're going to have class List, right? We'll have a public section, and we'll also have a private section. Actually for this one, we won't have a private section. Sorry about that. No private for that one because there's no data. So, we'll have our pure virtual functions and nothing but pure virtual functions. So, this will act again as an interface. It'll be simulating what we would be doing, say in Java, if we actually had something with the keyword interface instead of class. newEntry. So, that's how you make a pure virtual function with the = 0 at the end. To avoid a different overload, add new entry and then a position and basically it looks like you're setting the whole function to zero. That basically is telling you that I don't have any implementation, not even an empty implementation with curly braces. So, there's just literally no implementation.

We also have set. So, that will replace an element at a given position. We also want things like contains(), and that just asks- does it exist? entry const = 0. remove() at a particular position. And then we want to makeEmpty method, so all this should be able to make themselves empty, right? You also want to get the length of the List, so that's the size. And then this will say- is it empty? And a little nice helpful method that will print the List. All right. So far, so good. So, clearly, we're going to have to flush main out a little bit once we use it and we also need an implementation to our interface as well. So, since our List has all pure virtual methods, it self cannot be instantiated. We can't say List l = newList or whatever. That would actually give us a compiler error if we tried to do that in main. In fact, if a class has even one pure virtual method, it cannot be directly instantiated.

So, if you try to put something like List myList in main, it will even tell you something along the lines of object of abstract class List is not allowed." Okay, so whether you try it with pointers like List* l = newList, or if you try it with list myList directly, it won't let you do either of those. So, our List class is the perfect interface for the implementations we will write shortly. Again, note that we could add other methods that are common or useful as well. One particular would be a get method to get a member of the list in particular position. But later in the course, that would make one of your projects a little too easy. So, I've actually left this out of the interface right now. This interface is a great first step to implementing our ArrayList, and later our Linked List. List is a C++ version of our ADT List, essentially. It tells us what a List is supposed to do, such as add, remove items, tells us its size, etc., but not how we're supposed to provide the functionality or even how we store it.

So, let's create an ArrayList implementation of the List abstract class. So, I'm going to create, we'll put all of our code actually in a .h file. Just to keep things simple, we could split it up but we're going to put it in a .h file and we'll call this ArrayList. So, with ArrayList, we want our include guards- #ARRAY_LIST_H, #endif And we're going to include iostream because we're going to do some output. We need to include List.h because we have to have access to that class in order to implement this one. And here we go. It inherits from public list. Now, that means that it is promising to implement those methods. I do want to have a constructor in a public section. Let's make the public section first and a private section here. For the private section this time, that's where I started to jump the gun before, we do need some data.

So, the actual array, I'm starting with a pointer because I have to dynamically create it based on the size. There's going to be a MAX_SIZE and then there's a number of elements. That's the actual number of elements. And the MAX_SIZE represents the capacity. All right. So, now we're going to get this a constructor, and this time I'm just going to temporarily use this. This is the way you can initialize constants in a constructor. So, this uses almost like a functional syntax, but it allows you to do this even if it's a constant. So, you should be able to do that, that will initialize it to size s. And notice this is a default parameter, 16. So, if they do not pass anything to it, it will be 16. If they pass value to ArrayList, then that  s takes on that value. So, here we go. We're creating an array of MAX_SIZE, and then mNumElements, which I think I goofed here. Let's make that mNumElements for member, just on this one to keep it clear. You don't have to do that. There's going to be an add method. Actually you know what we will do?  This will make it easier.

I'm going to go over to class, List, and copy all these, and then in the ArrayList, I'm actually going to paste them, but I'm going to get rid of virtual off of all of these. This may save us a little bit of time typing here. Now, I have to give them bodies. So, I take off the = 0; and then I give them bodies. The void ones, we don't have to worry, we just give them bodies but any of that return any kind of data, we need to at least put, what we would call, a stub method, so it should return something. This right here actually contains,  that has a const also. So, I think I goofed. Here we go. That one should still keep its const. Did I miss any other ones? Nope.  This one... remove. So, these both return integers. So, I'm just going to return a 0 for now. So, the compiler won't be angry with me. makeEmpty( ) doesn't have a const because it modifies the internal data clearly. size( ) will return 0 by default here until we fill it in with actual implementation, isEmpty( ) will return false just for now  and then printList is const.

So, now at least, it would compile if we go over into main ArrayList.h, actually, I forgot using namespace std; and if we tried to compile this, we'll see if there's any problems, and it says it's succeeded. So, I think we're pretty happy there. Oops. ArrayList. Back over here, we've got the implementation for the constructor already. If we think about how does this regular add method work? You might think, where would be the best place to put it in an array if they don't specify where it should go? And the answer to that is, so as long as or if rather the elements goes above the MAX_SIZE and we're going to say, we're going to just print out, "Cannot add any more elements. List is full." And then just return to get out of there. Beyond that, if that's not satisfied, it will go over it. So, we don't really need an else. Otherwise, we set at [mNumelements] = newEntry; and then increase our NumElements. So, it starts at zero. So, that's the perfect thing to use for the index here. And it's kind of playing double duty because it's acting as the index. And then, we immediately say, "Okay. Well, now we have an element". So, we increase elements by one. And remember, this array is bigger than this as long as we know the mNumElements >= MAX_SIZE, as long as it's less than MAX_SIZE, then we can put it anywhere we want in that array. We're just adding it to the end because that's an easy place to put it for an array, it's the easiest place to put it. Now, if they specify the position, this time just going to do a little copy paste. It's not too many lines, so it's not that bad. We're going to also now, when they specify position, we have to actually check the range. So, if we've got past the num elements >= size, we know that we're not trying to go over capacity or outside the capacity. So, if the position they're trying to add in is less than zero or greater than the number of elements then we know, that would be out of range. So, we're going to print out, "Out of range with position" and then do a return. Now, we could also throw exceptions here. So, that's another thing you could do. But here, I'm just trying to keep it really simple, and we're just printing out something to count. But if you were using this professionally, you would probably want to go with exceptions, that would probably be a little bit better.

All right. So, the next thing we need to do, if it gets past all of these, we know it's in of range and the position and range and also that were not full, then we need to move the elements over and then add the new elements. So, we have to move elements over to make room for it if the order of the list essentially matters. So, this is us moving the data over. We actually start at the end as long as i is greater than the position and then go down. So, what we're doing is we're starting at the end, we're going to take mArray at,  so mArray[i]  is going to be such that mArray[i - 1].  So, I put myArray, it was supposed to be mArray[ ], sorry about that. And what this is doing is it's starting at the end. Whatever the number element is it's staring at that value and it's moving the previous one over. Then mArray[position] is just set to the newEntry after we've moved and made a room for it. Now we set... There, I did it again, should be mArray of course.  And now, mNumElements++. All right. Pretty cool.  So, now set, what do we do with set? So, set just replaces the value. So, for set, we don't need to check the allocation of the array but we do need to check to see if the position is in range,  so I just copied that part. So, I'll say, "Out of range for setting at position" and if it gets past that, it's in range. And then all we do is we replace, not going to do it again,  we replace the mArray value at that position with the newEntry. That was past step. So, this one's a replacement. So, contains, we're moving on to this; contains is just going to return true or false. So, we'll start assuming it's false and then we return this variable found. So, we assume that the list doesn't contain the entry they're looking for until proven otherwise. So, how do we do that? Well, to even see if we're proven otherwise, we go into this for loop here and if at any point we find mArray[ ] == entry, so they're integers, so we can just compare them like this, it's very easy. If at any point we do that, we set found = true and then we immediately break out of the loop because we found it. We know that it contains the value they were looking for. If it goes through this whole loop and never enters here, that means that value was never in that array. Now, find. Right here, we'll do something similar. We're going to set foundIndex = -1. So, we assume at first that it's not found at all and -1 is a special value to indicate that. And now, we're going to loop through. It's a little more intensive than the just contains because we need to keep track of where, not just, did we find it? So, here we'll do that less than or equal to numElements; i++, now we're in the loop. If again, we find the entry, which is very similar, we set foundIndex = i and then we break. So, it's very similar to contains. It's just in this case, we have to make sure we keep track of where we found it. If we go through the whole thing and never find it, then it'll be a -1. So, what about remove?  So, given a particular position, what about remove? So, if I have right here, we'll say int value = -1. But that is a valid value. So, we have to be a little careful. This is returning an integer because there are integers in the underlying array that we're containing. So, that means that we have to allow it to remove the value before totally removes it,  "totally removes it." We want to give it an option of returning what that value was. Now, I could have just copied this and modified it but we'll just do this, I'll do cout<<"The position to remove is out of range" and then we'll just return value immediately, which is -1. So, if they get this output, you just have to know not to use the value which is again, why an exception would probably be better in this case but right here, I'm going to set value. If it gets pass that then we know it's valid. So, I'm going to set the value = mArray[position];. And then what we got want to do is //close the "gap" and reduce mNumElements. So, if you can picture the array, the values are actually being, it's opposite of making room when we tried to do the add in a particular position. We're actually closing this gap or the gap that will be made. So, we're copying over it and then just pretending like the end of the array doesn't exist even though there may be values actually living there. So, closing the gap looks like this for( int = position; i < mNumElements -1; i++), We'll see that in a second here. mArray[i] = mArray[i + 1];. That's why we're allowing for the -1 here. That doesn't even say i, does it? There you go. So, in i=position and I did it again, mArray. I'm used to naming a lot of arrays myArray. if it doesn't have a specific meaning. So, that's bad habit and then what we want to do is we want to do mNumElements --; and then return. We already got returned the value, so I'll leave that. So, I hope this makes sense what this part's doing. You're starting at the position that we want to remove the stuff from where we're actually copying the element to it's right over. So, then you actually have two copies of it and then you iterate and it scoots over to the one that made the double copy, then it copies the thing to it's right and it keeps on going until we get to the end. At the very end, for the mNumElements, the last element will actually have two copies. But since we reduce mNumElements by 1, that's going to invalidate or make it so that we don't pay attention to whatever values sitting around at the end. So, hopefully that makes sense. So, even though the data is there, you're not actually "removing it". You're treating it as if it doesn't exist. So, in that respect, you are getting rid of it. makeEmpty is actually quite easy. We don't have any memory management to do so I'm just going to set mNumElements = -1 which if we go back up to our. Some implementations might choose to use a -1 but in our case, it is zero. So, mNumElements is zero and the size is fairly straightforward. We just return mNumElements; There we go. That's easy. Is empty. Now this one's really, really cool. This one's one liner also mNumElements = =0, because that's what we've defined our empty as. Now printList is also pretty easy. for (int i = 0; i < mNnumElements; i++). And then you're going to say cout << mArray[i] << endL; and there we go for that. Now we have to actually use this thing. So, we have to go over to main () and inside of main, we're going to create ArrayList. This time I'll call it myList; and then for (int i = 0; i < 25; i++), I'm going to say myList.add (i * 10);. So, it doesn't really matter. Just arbitrarily adding some values. Then myList.printList();. So, it'll print the whole list and maybe we'll just additionally print some spacing and to test out the size, we'll say cout<<"Size is "myList.size() << endl; Here you go. myList.add (555, 15);. So, in this case we're adding the value 555 at location 15. So, that will have to scoot stuff over. Now, what we're going to do, I said 25 up here. That should be 15. I'm sorry. So, change that, if you put 25, that should be 15 because since we're using the default here, that'll be values enough to hold 16. So then what we do, if we try to add an element here, well, think about what happens. So, we're not setting it. We're trying to add it. So, I'm going to print the list say cout<< "Size is now" << endl;. And then finally this one we'll do myList.set(978, 3);. And then, print the list again. Great. So of course, you know that was a lot of coding. If you need to pause at any point to catch up, that's totally fine. Just go back to wherever you need to and let's run it and see what happens. So, we're going to just, good habit is build, run. Oh, looks like cout undeclared. Oh yes. We need to do using namespace std;. That's why we test it. See how that made so many errors? Now it succeeded. Just one little line of code can really change things. Now I'm going to run it. Let's start without debugging. And as you expected, we've got the values printed. So, it's basically i * 10 all the way down, up to 14 from zero to 14 inclusive multiplied by 10. And then, you'll notice that since we allowed for 16 values. So, this was 15 and this one now allows us to add something at index 15. That's why we were one less over here. Because it did allow us to add the 555 at the end and then we set the 987 on index 3. So, 0123, we have index 987. And that's exactly what we expect. So, that's pretty cool. We've been able to make this list. You might think why is this better than a regular array? When we're adding object oriented functionality in it, it can tell us things about its size, if we wanted to we could reimplement it to do dynamic resizing, we get to size it as we wanted at the beginning, which we could do. There's all kinds of things that we could do. So, that's pretty cool. So, we've created our first data structure, the ArrayList implementation of the list ADT. Before moving on, I have a challenge for you. It's pretty simple. I'd like you to add code to the main function that will cause the program to print out an error when you try to add an element beyond the capacity of the ArrayList. So, pause the video and give this one your best shot. Come back when you're done or if you need some help. How did that go for you? Were you able to complete this challenge? Let's work on it together. So, the end of the main function, what we're going to do is we're going to see if our out of range stuff works. So, myList.add(1000);. And of course, let's run it again. It's very simple. Build, run, and you'll notice that after the 555, we do get a printout that says we can't add any more elements. The list is full. All right. So, pretty simple. Nice work, everyone. In the next lecture, we'll implement the list ADT again but this time with a linked chain. Get ready to implement our first link to data structure, the linked list. I'll see you there.