Doubly Linked List Code

Key Takeaways

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 github.com William SL data- 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 link list series before continuing here we are in the source code we're looking at the implementation of a doubly 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 link list as well as what the head and the tail currently are to begin with the head and the tail are null meaning link 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 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 here is to clear the list it does so in linear Time by going through all the elements and deallocating them one at a time it deallocates them by setting them equal to null so we start a traverser at the head we Loop while the the traverser is not equal to null meaning there are still elements in the list and then we do our deallocation business and at the end we set the size equal to zero and reset the head and the tail perfect these size and Mt methods are pretty self-explanatory get the size and check if uh the size of our link list is empty okay so here I have a public method to add an element by default we're going to append to the end of the link list or at the tail but I also support adding to the beginning of the link list so how we do this if this is the first element aka the list is empty then we set the head and the tail to be equal to the new node which has if you can see here both previous and next pointers set to null otherwise if the list is not empty then we say the head's previous point is equal to this new node and then we set the head the the head pointer to be whatever heads previous is so we back up the pointer in a sense and we also don't forget to increment the size a very similar thing is done when we want to add to the tail of the length list except we're moving the tail pointer around okay let's move to Peak so peing is just looking at either the element at the beginning of the link list or at the end of the link list and we throw a runtime exception if the list is empty because doesn't make sense to Peak 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 link list so we can't do much if list is empty otherwise we get the data we extract the data at 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 null as well so both the head and the tail are now null otherwise we uh deallocate the memory of the previous node that we just removed this is a especially important if you're in C or C++ make sure to free or delete your pointers then at the end we return the data a very similar thing is done for last except we're using the tail this time to uh remove from the tail of the link list and not the head okay and here's a me a generic method to remove an arbitrary node remark that I set this 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 link 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 other wise we know we're somewhere in the middle of the length 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 the data is already gone now suppose we want to remove a note 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 in a legal argument exception so here we are trying to be a bit smarter than just naively going through the link list either we're going start searching from the front of the link list to find our index or from the back depending on if the index is 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 n values in case someone decided that the value of the node should be null that's fine so we check that 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 uh in this lse statement we search for the element we want to remove we use the 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 Sport searching for null so even if our value is null just return the first place we find a null element so again Traverse the link last otherwise search for a non-null element and also increment the index as we go we can use the index of for our method contains to check if an element is contained within a link list because we return minus one if the element is not found something that's useful sometimes is to have an iterator for length 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 uh it's pretty easy to do that and lastly at the very bottom we have um two the two 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 at it in more details or comment below I'll get to you when I have time