In this lecture, we'll implement a linked list. In practice, you should just use the linked list that's available in the system collections generic namespace but implementing our own linked list gives us additional practice both in our programming and in our algorithm analysis. We'll start by looking at each node in the linked list which I've called LinkedListNode and our linked list node is a generic so we can store any data type we want. There are two fields, we have a value that we're storing in our linked list node and we're storing a reference to the next node in the linked list. So we're implementing something called a singly linked list here where each node only points to the next node in the list. There's also something called a doubly linked list which you'll get to implement if you do the exercise that doubles the links and in that particular implementation each linked list node has a reference to the next node in the list and a reference to the previous node in the list. And it'll turns out that having that link back to the previous node is particularly helpful if you need to traverse the list from the tail, the end of the list to the head. We have a constructor that simply sets the value of the node and next to whatever node is passed in. And of course, we have properties that access the value so we can only get the value of the linked list node but the next property lets us both get the next property which we need to be able to do if we ever want to walk the list or traverse the list from the beginning to the end. And we also provide the set accessor for this property because we may need that, we will need that if we are going to add and remove nodes from the list which of course we need to do for it to be a useful data structure. This is one of the building blocks of a linked list, each node is a piece of the linked list and then we just hooked them all together to form our linked list. Speaking of our linked list, here's the class for that, it is an abstract class because the add method is abstract but really this linked list pairing class for the sorted and unsorted linked lists contains most of the functionality for the linked list. We have the head, the front, if you want to think of it that way but it's regularly called the head of the linked list and that's a reference to a particular node, the node at the very front of the linked list. And for convenience, we'll keep track of the count of the number of nodes in the linked list. We could in fact, walk the list every time somebody wanted to know the count but this is a quicker and more convenient way to actually keep track of the count. The constructor sets head to null and count to zero because when we construct a linked list, it starts as empty. We have the count property that returns how many nodes are in the list and we have the head property that returns the head of the list. Anyone who actually wants to use our linked list will start at the head and walk along processing the different nodes in the list. Here's that abstract, the add method because an unsorted list can do this much more easily than a sorted list can. Clearing is more complicated than we saw with the dynamic arrays. Here's the issue, we have references to all the linked list nodes in our linked list and the way garbage collection works is if an object in memory has a reference to it that means it can't be garbage collected. So we can't just set the head to null and set the count to zero because all those nodes that are hooked together in our linked list will have references to them and so they can't be garbage collected. So as long as we have something, at least one node in our linked list, we will release or disconnect all those nodes and we'll see this pattern again and again for how we actually walk a list. We'll set previousNode to head and currentNode to head.next. Now, we're holding the first two nodes in the list and if this list has only one node then current node is null at this point. This is not a standard piece of how we traverse a linked list. At this point, we are disconnecting previousNode from currentNode and while the currentNode isn't null and so currentNode will be null when we get to the end of the list. We make previousNode currentNode so we jump one node forward with previousNode. We set currentNode to currentNode.next. We jump currentNode one node forward and then we disconnect currentNode from previousNode. And this is the way we disconnect all those references for the nodes in our linked list and once we've done that, we set head to null and count to zero just like we did in the constructor to indicate that we now have an empty linked list. To remove something from the list, first thing we check is, is the list empty because we can't remove anything from an empty list so we return false in that case. The next thing we check is to see if we're removing the head of the list because remember, for consumers of this class, the head is kind of the only way that they can get at the other nodes in the list. They started at the head and they walk along the list. So if we remove the head, we need to make sure that the linked list still has a head and the way we do that is we set head equal to head.next. We're removing this node head but before we do we'll grab the next node that the head currently references and set head to that instead and we reduce count by one as well. And of course if this was a linked list of only one link list node, setting head to head next makes head null and reducing count from one to zero is essentially saying, now we have an empty list. You'll find as you deal with linked list that you have to check for special cases all the time so this was checking for special case and this was checking for special case. Now, we can go to the normal traversal and this is really the normal pattern for traversing a singly linked list. So previousNode get set to head, currentNode get set to head.next. And we'll see why we actually needed this previousNode later and the reason is when we get to currentNode if we haven't saved the previousNode in a singly linked list, we can't find the predecessor of the currentNode so we have to keep track of both in a singly linked list. Okay. While the currentNode isn't null and while we haven't found the item we're looking for, we advance along the list. We jump the previousNode to currentNode and we jump currentNode to currentNode.next. This moves both of those things forward one node. When we're done, we either found what we were looking for and it's in currentNode or we exhausted the list and currentNode is null. We have to check this and if currentNode is null it means we didn't find it so we return false. Otherwise, here is where we're actually removing that node. The way this linkage works is before we execute this line of code previousNode.next is currentNode. And if we set previousNode.next to currentNode.next, we've just made that reference jump over currentNode which means currentNode no longer has a reference to it. It's not part of the list anymore and of course we decrement count. If this piece doesn't seem clear to you, you should actually write down an example on a piece of paper and see how this actually does remove that node. You might wonder why the remove method is here in the parent class because in our dynamic array remove was in the unordered dynamic array and the ordered dynamic array classes because they worked differently and they work differently because removing from an unordered dynamic array, we just copied over the place where we wanted to remove but removing from an ordered dynamic array, we had to shift things around. Remove works exactly the same for both unsorted linked lists and sorted link lists. We have to find the node to remove and then removing it works exactly the same way whether the list is sorted or not. Similarly, Find is also here in the Parent class. Remember, in the unordered dynamic array, we had to do a linear search for the item we were looking for, but in the ordered dynamic array, we could do a binary search which was Order log n instead of Order n. We could only do that because arrays are something called a random access data structure, right? We can get any particular element in the array with an index directly. A linked list doesn't work that way. We start at the beginning at the head and we work our way forward. So, there is no way to do a binary search on a linked list. So, Find Also is here in the Parent class. This time we don't need to keep a reference to the previous node because we're not going to unlink anything, we're just looking for the current node. So, we can start the current node at the head and while it's not null, and while we haven't found the item we're looking for yet, we just jump current nodes to the next node until we either exhaust the list or find the item we're looking for. If we haven't exhausted the list, that means we found the item so we returned that node, otherwise, we return null because we couldn't find that item in the list. This toString method simply starts at the head of the list, making sure we haven't reached the end and while we haven't, we add the value to the string and then bump current node along to the next node. And we just walk along from the head to the tail or the end of the list, adding information to the string that we then return. That's it for the Parent class. Luckily, the child classes are pretty simple because they only implement a constructor in the add method. The constructor just calls the base constructor, the add method for an unsorted linked list. If we're adding to an empty list, then we just make the head be a brand-new node with the value we wanted to add, and null for the reference to the next node in the list because there is no next node in the list, we're adding to an empty list. Otherwise, we can simply add to the front of the list, and the way we do that is we say that the head is a new LinkedListNode with the value we're trying to add and the next node is the existing head. So, remember, what happens is the right-hand side of this assignment gets evaluated before we assign it to the left-hand side. So, this is the old head that is now going to be referenced as the second node in the list by the new head once we do that assignment. And of course we increment count because we just added something to the list. The SortedLinkedList, again, requires whatever type we're using as values in our LinkedList, implement the IComparable interface so that we can make sure we keep the order correct. We have our constructor, we have our add method. Again, adding to an empty list, same as before. If we're adding before the front of the list because the head value is greater than the item we're adding, then we do this which is just what we did with the unsorted linked list, but usually in a sorted linked list, we actually have to find out where to place the node and that's what this code does. So again, standard previous node, current node, while we haven't reached the end of the list and we still haven't found the right place, then we bump previous node and current node forward, one node each, and then we link in the new node between the previous node and the current node because that's the place we wanted to put it. So, previous node now refers to as the next node on the list. The new one that holds the item, and that new node we're creating now references the current node as its next node. So, we're basically inserting this node with the value we wanted to insert between previous node and current node, which is exactly what we need to do to keep this linked list sorted. And we increment count because we just added an item to the list. In this lecture, we learned how to implement linked lists and linked list node. We learned how to walk a linked list from the head to the end, often called the tail of the linked list. We learned about the difference between linked lists and random access structures. And we saw how we could support garbage collection when we cleared our linked list.
