All right time to look at some doubly linked list source code. This is part two of two in the linked list series. So the link for the source code can be found on GitHub and github.com. Slash Williams is a slash data dash structures. Please star this repository if you find the source code helpful so that others may also find it. And also make sure you watch the first part of the linked list series before continuing.

Here we are in the source code, we're looking at the implementation of a double e linked list in Java. So first, notice that I have declared a few instance variables so we are keeping track of the size of the linked list, as well as what the head and the tail currently are. To begin with the head and the tail or no meaning linked list is empty. Furthermore, we will be using this internal node class quite excessively, because it contains the data for our nodes. And it also contains the previous and next pointers for each node since this is a doubly linked list. So we have one constructor for the node, namely the data and the previous and the next pointers themselves.

We need both otherwise we can't do much. So this first method I have declared here is to clear the list. It does so in linear time by going through all the elements and D allocating them one at a time D allocates them by setting them equal to No. So we started traversing the head, we loop while the traverser is equal to no meaning there are still elements in the list and then we do our deallocation business. At the end we set the size to zero and reset the head and tail Perfect. These size and empty methods are pretty self explanatory get the size and check if the size of our linked list is empty.

Okay, so here I have a public method add an element by default we're going to append to the end of the linked list or at the tail, but I also support adding to the beginning of the linked list. So, how we do this, if this is the first element, make a list is empty, then we set the head and the tail to be equal to the new node which has you can see here both previous and next pointers set to no otherwise if the list is not empty, then we say the heads previous pointer is equal to this new node. And then we set the head, the head pointer to be whatever heads previous is. So we backup the pointer in a sense. And we also, don't forget to increment the size. A very similar thing as done when we want to add to the tail the length list, except we're moving the tail pointer around.

Okay, let's move to peak. So peaking is just looking at either the element at the beginning of the linked list or at the end of the linked list. And we throw a runtime exception if the list is empty, because it doesn't make sense to peek an empty list. Okay, now we get to the first more complex method, which is remove first. So this is if we want to remove the head of the length list. So we can't do much if lists Simply otherwise we'd get the data, we extract the head, and then move the head pointer forward, we decrease the size by one.

So if the list is empty, we set the tail to be known as well. So both the head and the tail are now No. Otherwise, we deallocate the memory of the previous node that we just removed. This is especially important if you're in C or c++, make sure to free or delete pointers. Then at the end, we return the data. Very similar thing is done for last except we're using the tail this time to remove from the tail the linked list and not the head.

Okay, and here's a generic method to remove an arbitrary node remember access to private because the node class itself is private, so the user shouldn't have access to the node, that's just something we're using internally inside the linked list data structure to manage the list. So if the node that we're removing is either at the head of the tail, detect that and call our methods either remove first or remove last. Otherwise, we know we're somewhere in the middle of a linked list. And if we are, we make the pointers adjacent to the, to our current node equal to each other. So we're effectively skipping over the current node. And then of course, don't forget to clean up your memory and return the data.

So we have to temporarily store the data. Of course before we delete the node, otherwise we've deleted the node and data is already gone. Now suppose we want to remove a node at a particular index in our linked list. Yes, we can do this. Even though our nodes are not explicitly indexed, we can pretend that they are. So first check that the index is valid.

Otherwise throw an illegal argument exception. So here, we are trying to be a bit smarter than just naively going through the link list. Either we're going to start searching from the front of the link list to find our index or from the back depending on if the indexes closer to the front or to the back, although this method remains linear. So for the Remove method, we want to be able to remove an arbitrary value from our linked list, which is object. So we're going to also support searching for note values in case someone decided that The value of the node should be no, that's fine. So we checked for a special case.

Otherwise we traverse through the link list until we find a null element and then remove that node. And return true we return true if we actually found the element we want to remove. Otherwise we return false down here. In this else statement, we search for the element we want to remove. We use the dot equals method to check if we found the element. If so, remove that node and return true.

Okay, here we have a related method which is index of. So this is not remove at an index, or remove a value but get whatever index this object is at. Again, sports searching for null. So you're going for values No, we're just returned the first place we find an element. So again, First link list. Otherwise search for a non null element and also increment the index as we go.

We can use the index of before our method contains to check if an element is contained within a linked list because we return minus one if the element is not found. Something that's useful sometimes is to have an iterator for the linked list. This is also trivial to implement. Just start a pointer, traverse at the head and traverse until you reach the end. Notice I'm not checking for concurrent modification error, but if you want to, it's pretty easy to do that. And lastly, at the very bottom, we have To the to string method to print a string, or to get rather a string representation of our linked list.

And that's it for the link list. So pretty straightforward stuff, but there's a lot of pointers flying around. So if you're confused about a particular part of the algorithm, look I in more details or comment below, I'll get to you when I have time.