In the previous lecture, we created our List abstract class with all pure virtual methods making it essentially an interface. It does exactly what the List ADT does. It tells us the method that a  List has to implement but it doesn't tell us how to provide the functionality for those methods. That goes for both the backing data structure as well as the algorithms. That's up to us to decide. In this lecture, we'll implement the List ADT using a very different technique from the ArrayList implementation. We'll be using a linked chain of nodes thus, giving us a  LinkedList. Our first step is to create a new project in Visual Studio called LinkedListApp. So, I will create that. And once that's done, we're going to copy over our List.h from the  ArrayList implementation and then, include it in our project. So, let me go over to our  ArrayList. Over here, I'm going to just grab this. I can copy this right here, List.h and I'm going to go into our LinkedListApp project and paste it, first of all. Then, I'm going to import it here by adding an existing item. Here we go. List.h. That's exactly what we needed. And of course, I'm going to create a main.cpp with which to test it eventually. Here we go. So, once that is done, we need to create a new file for the implementation called LinkedList.h. So, in the Header Files, I'm going to create a new item, Header File and we will call it LinkedList.h. Let's call this LINKED_LIST_H, LINKED_LIST_H. And of course, endif. Before we write some code though, let's quickly revisit what a linked chain is going to look like. So, our LinkedList is going to maintain a pointer to the first note in the chain called the Head of The Chain. Then, each node maintains a pointer to the next node in the chain until the last node which has its next pointer set to nullptr. Now, we can write some code. So, let's include of course, <iostream> <iostream> <iostream> and we're also going to include the List.h. And we need a node. So, we have a Node class and then, we have the actual Linked List class. So, our node is going to look like this. We have class Node. And the public portion,  we're going to have a public portion, and also a private portion. The private portion is going to have data which will just be an integer again. Continuing with that and then a pointer to the next node in the chain. We're going to have the constructor here. So, we can have this->data=data; and this->next=next;. And then of course, we can have getData() which is const since it doesn't modify anything. And we're also going to have setData(int data) which does modify things. So, we don't want to make that const. So, this ->data=data;. Then, we have Node* getNext(). Also, this does not modify the private data members. And of course, we're going to also have setNext, in case we need that. Now, some of these we may use, some of these we may not. This is just to fully give us a good node class here. So, that's the Node that just represents a single node in the chain. The next thing we're going to code is going to be the LinkedList itself. So, this represents the full  List. LinkedList publicly inherits from the  List interface essentially. We're going to have a public section and a private section as well. And with the private section, unlike the ArrayList implementation, we're going to just hold a Node, which is the head of the node and then num, well, we'll call it mNumElements;, so that will hold the number of elements. And then, of course, we're going to have a nice little constructor that's going to get our LinkedList started. So, we'll do that. And all we're going to do, we're going to set mNumElements=0 and then, the head of the  List to nullptr because it's empty. We might also want to do this. I'm going to make it virtual. That's actually preferred to make your destructors virtual especially if they were going to be inherited from because it's considered good programming to use the virtual destructor just in case you might delete an object of a derived class through a polymorphic pointer later on. Now, we're not actually going to be doing this but it's a good habit to get into that I didn't really reinforce earlier in the course. void add(). So, what happens when we have a new entry and it's not specified where it goes. Now, with the  ArrayList implementation, we put it at the end of the array because that's the most convenient place to put it. We don't have to move elements over. However, the ADT, in this case, the method from the ADT doesn't specify where you have to add it. So, we're going to put it where the most convenient location is for the linked chain and in this case, it's going to be the front. Since we're pointing to the front with mHead, consistently is where we're going to be putting stuff and it's growing from the front. So, we're going to create our new Node and it's going to hold the newEntry and as its next, it's going to point to the current head of the  List. Now, if this is our very first node, the head is just nullptr. On subsequent occasions, the head will be, as you'll see in a second, the head will be the current head of the List but it will become the previous head and the second item in the  List upon calling it again. So, well I guess first things first, we've got the mHead set to next and we've also got the data set. If you did not have the ability to do this with the constructor, you could say newNode -> setNext (mhead). That would be the other thing you could do. Well, it's actually capitalized like that. But since it's already set, we're good and we just need to reset the head here. So, we're going to set the head equal to our new node. So, it's the newHead. Now, mNumElements++;. So, we're increasing the number of elements since we just added. Now, we have another implementation of add. In fact, I'm actually going to do what I did before and copy over the rest of these things just to make it a little bit easier from the interface file and we're going to delete that, the virtual keyword on these and give them all bodies like I did before. That will just make it a little bit easier. And let me see here. We'll delete that and give that a body. Delete that. Give that a body. We'll do return false; on this one. We'll return 0; on this. Just sort of compile. And of course, let me see your make empty. It can be empty. return 0; on size as we did before. The bool isEmpty. We can return false or true. It doesn't really matter. We're about to override all the behavior anyway and then printList is void so we don't need to do anything with that. We could try a Build right now. I guess one other thing we should do is go over to main and include the "LinkedList.h". Now, let's do another build. Just to make sure everything looks good. date is not a member of node, data. There we go. See, exposed a little bug there. I like taking care of bugs as they happen if possible. Now what we're going to do, go back to our implementations here. We got the first add done. The second add, the one that specifies the position, we have a couple of cases here. We could add at the beginning. So, add at the beginning that means position 0, or we add somewhere that's not the beginning. So, the first thing we need to do is that newNode = new Node. And again, we do what we did before. The head is the next in line. And now we're going to say mNumElements +  1 or the position < 0. So, we have to see we allow adding at the end. So, the mNumElements itself, we have to make sure that we're able to add at the end. So, one more past the number of elements, which we wouldn't really have the option with an array list unless we made it dynamic. So, this one is actually making it pretty easy for us. We can just add at the end, one past the end or up to one past the end. So, are up to that element at the end, if we go beyond that element i.e 1, one past the end, if we get the position greater than, it's not going to let us do that. But we can add at the end, which is a at nNumElements, if that makes sense. So, "Cannot add at specified position" and then we're of course going to return, so let's get out of here. Another thing we're going to do here is we have to specify the different cases. Remember it's either at the beginning or some other that's not the beginning. Now, there's many ways to do this. So, it's not beginning. But if it's at the beginning, we're going to do it this way. So, we'll say a newNode->setNext(mHead); we've actually already done that, but we'll just keep the because of the constructor up here. But I'll keep this code here to make it explicit what we're doing. And then mHead = newNode. You could technically come at that part up. Now, if it's not at the beginning, we have to actually find the location. So, this is one of the disadvantages of our linked chain is that we can't do random access because the nodes are all over the heap. They're not contiguous in memory. So, we're going to take, we're basically going to inch our way up until we find the location that we need to add at, and then, we'll be able to. So, we've got nodeBefore where we want to add it and nodeAfter. So, what we're going to do is use a little for loop here. So, we're going up to the basically the location before the position and that's the end of the for loop. And all we're doing is we're setting nodeBefore = nodeBefore->get next(); So, we're just inching our way up. And once we get out of this loop, we know that we're going to be at the position we want. So, we set nodeAfter, we need to not break the rest of the chain, so we need to set nodeAfter = nodeBefore   where we want to add it, getNext(); So, we don't break the chain. So, we've got nodeBefore, nodeAfter, and we're going to splice in our node, if that makes some sense. We're going to splice the node in between the nodeAfter and the nodeBefore. So, we're going to say newNode. We're going to setNext to nodeAfter, so that's why we don't break the chain. And now what we have to do is we set nodeBefore, which did have after as its nextNode. Now, we're basically just setting next on the newNode. So, this is carefully splicing it into position. And that's not too bad. We also need, irrelevant as to whether it was added at the beginning or somewhere else, we need to increment mNumElements. The next thing we're going to do is we're going to do set. So, set isn't too bad. We're going to say Node* walker = mHead, because we need to walk the chain to find the location where we want to change the data. We're going to set int index =  0. Again, if the position is greater than or equal to, in this case, mNumElements or position < 0, so in this case it has to be an existing elements so we don't do mNumElements + 1. And again, you could also use exceptions here, but "Cannot set at specified position" and return. Now, we're going to walk int i =  0, i  < position that we're looking for, and of course, we're going to say walker = walker next. And then, we have to do set the data when we find the our position. So, basically we found the location that we want to update, and we didn't have to create any brand new nodes. We just found the position, and all we did was update the data. We didn't update the actual node, we didn't change the node itself to a different node. contains, we're going to leave alone for a second here. We've stubbed this out just for compilation, but that we'll see what we do with that later. For find int foundIndex = -1 will assume that means not found, kind of like what we did with the array. We're kind of treating it like it has indices even though the list does not actually, the LinkedList doesn't actually have indices. indexCounter, okay. So, now what we're going to do is we're going to set the Node* walker  = mHead again. And as long as the walker is not equal to null pointer, so we're basically going to walk the whole list. And if we ever get to know pointer, we know that it wasn't ever found. So, if walkers data is ever equal to the entry, then we know that we have the foundIndex equal to, we're going to call this the indexCounter; indexCounter++. So, indexCounter's always being incriminated inside of this loop. And then, if we ever find it, we set the foundIndex equal to the counter and then break. Perfect, perfect. That one's done now. Now, what we're going to do is we're going to move on to remove. remove will allow us to again check the position. We have to make sure that they're not trying to remove out of range, because that doesn't make sense. "Cannot remove at specified position." We'll just return 0, just add something to return. Now, we're going to set dataToReturn = 0. Eventually, return that dataToReturn. In between these two things, if(position == 0) in the case that it's the first node, what we need to do is we set a temporary Node pointer to the head, because if we just delete the head, the head's pointing to the next element of line. So, it's just going to lose the whole list. We don't want that. So, we get dataToReturn = temp's data. At this point, you could say mHeads data, it doesn't really matter. We progress the actual chain. So, you set mHead = mHead Next, and then delete temp. So, once we have that, we also have an else situation here, and we have nodeBefore = mHead, and then Node* nodeToRemove right there, nodeToRemove and the nodeAfter. So, we're kind of doing the same thing we did before when we were finding it. So, we find the location of the position that they have indicated. So, position - 1 in this case, so we want the element before, nodeBefore = nodeBefore->getNext() And then, once we're out of this loop, we have the nodeBefore where we want to remove. So, nodeToRemove itself is obviously nodeBefore next element. That makes sense. But we have to not lose the rest of the chain. That's why we need this nodeBefore, and then we'll also need the nodeAfter. Let's get data to return first. So, dataToReturn is going to be set to the nodeToRemove its data. Then we're going to set nodeAfter = nodeToRemove->getNext() So, this is basically broken it out of, we've got this set to the nodeBefore is next. That's the one we're removing. Keeping track of it, we've already got nodeBefore, obviously we've got nodeAfter. So, we want to basically we've spliced them together. And once we have everything we need we have after this spliced out of there and then, the nodeToRemove kept in an address here with the node pointer variable, we can actually do this. We can say nodeBefore, this is the bypass right here. Set next to node after. So node to remove is going to get deleted and it won't destroy the rest of the chain. There you go. Perfect. And of course, before anything else happens we have mNumElements--. We, of course, have to keep track of the number of elements. Make empty, now this one we don't need a walker we just want to destroy all nodes on the list. We use a walker to avoid destroying the actual list. In this case, we want to destroy the list because we want to make it empty. We want to get the all the nodes deleted and we want to eventually get mHead equal to pointer. So, temp is equal to mHead to start off with, mHead equals mHeads next. And then we delete temp. Okay. So, we keep going until the head is actually no pointer and then we have an empty list again. The other thing you should do is set your mNumElements to zero and there you go. The size is pretty easy. We just returned the mNumElements that looks pretty familiar, right? IsEmpty is pretty simple. Also, here's a one liner. We could use the list itself to determine this but we're just going to do that and then we have print list. Print list uses a walker to walk the list because if we use the head directly, it's a member. Members, if you remember scope, it's a member of the linked list, so it's going to update and then it will lose the entire list in our wake, if we don't use a walker. The walker is going to start just by pointing to the current head and then it can walk down the list without disturbing the head itself. So, we're just interested in getting data here, right there, and then, we progress the walker, right there. Good. So that just prints it. Now, of course we might want to test out main, to test out our list using main. So here, I am going to create a linked list which I will call myList. I know I'm very creative with those names and we'll create an int data. So, I can test out our remove that's what we're gonna do. So myList.add(15), myList.add(22), a 100. You can do whatever you want. You can even, if you want to just put this in a loop. You can use a random number generator and generate some integers for you. It doesn't really matter. 505. MyList.add(22). If you need to pause the video and wait it for a second. That's fine too. I'm also going to test out set. So, let's see if these work. So those are to try to get them to stick out. I have made them large and then we're going to call print on this. I am going to add another element at index eight. Maybe do a little bit of in-line there and then print it again. Okay? And maybe another in-line and this time what we're going to do is we're going to just go through whatever remains in the list just to do some more testing. So, while not myList.isempty. Great way to test isEmpty. We're going to set data equals myList.remove the element at zero, so it will remove the front and we're just going to say just removed and then data. And then what we're going to do is do another indel. And then I'm going to try mylist.print list. And of course, let's run it and see the output. Make sure we don't have any bugs. We have some bugs. Cout undeclared, that tells me I'm not using namespace std. I thought I did that but apparently not. There we go, succeeded. Now let's run main and here we go. We can see that the elements are printed out and that was from the first run. With the 15, 15 and the 22, 52 changed at either end. Then we and we printed the list. Then we added 1500. So that goes to the end because we said added at position eight which is outside the current boundaries but we allowed for that. We allowed it to go up one more to the actual size. Then we printed it and then we went through and we did just removed and it removed all of these elements and then at the very end we call print list but you'll notice nothing is happening. There's nothing printed, right? Because there's nothing in the list anymore. Perfect. Amazing. So, we've fully implemented our first real link to data structure of the linked list. As you can see there are quite a few cool things that it can do. While it lacks random access, like an array so that's a negative of course, we can add and remove elements without shifting any elements over to make room or close gaps like you do with array-based implementations. Before moving on, I have a challenge for you. You may have noticed again and I even mentioned it so hopefully you noticed that I didn't implement the contains member function. I'd like you to implement it. You can implement it completely from scratch if you'd like, but there's actually a bit of a cool shortcut implementation if you use one of the other methods that the linked list provides. So, think it through and see if you can figure that out. There's a very big hint in the slide of course, pause the video come back when you're done or if you need some help. How did that go for you? Were you able to finish the challenge? Let's work on the contains method together. So, in this case, what we're gonna do is I'm just going to set a bool result equal to false. We actually don't have to do this but we could just set it directly. But here's really where the magic happens. So, if we call find which is a method that's already implemented and this will return true if it is found. So find, we're actually using a bool in here. If the find is not negative one, that means it found it. So, it's going to set result to true. If it is equal to -1, it's going to set result to false. That's pretty awesome. If you want to test it out, feel free to add some code to the main file and try it out. But in the next lecture, we're going to take a look at another abstract data type. The Stack ADT. I'll see you over there.