In this part of the lab, we will add the remaining functionality to our MyLinkedList class to replace and remove items from our data structure, as well as a few methods for affecting the current state of the data structure. We will also continue practicing using unit tests to debug and validate our implementation.
To allow us to replace the item at a given index of the linked list, we will use the public T set(int index, T item) method. This method should:
item is null – we do not want to be adding any null items to our linked list. If so, throw a NullPointerException.index argument is valid, given the current number of items in the array list (reminder: this is a different range of valid values than earlier in your add method). If not, once again throw an IndexOutOfBoundsExeception with an appropriate error message.index to a new variable so it can be returned after the replacement is finished in Step 5 (otherwise it will be forgotten)item argument to the DoublyLinkedNode at position index in the linked listYou should create unit tests to verify that this method works properly. One approach might be to create a new MyLinkedList<Integer> object, add some items, replace one of them, then check if (1) the correct item is now stored in the updated index, (2) none of the other items were affected, and (3) the correct prior item was returned.
You should also create a test to make sure that the NullPointerExeception and IndexOutOfBoundsExeception are thrown at the proper times. Don’t forget to use the Debugger to help you debug.
Sometimes we also want to remove an item outright without replacing it. For this, we will use the public T remove(int index) method, which should:
index argument is valid, given the current number of items in the array list. If not, once again throw an IndexOutOfBoundsExeception with an appropriate error message.DoublyLinkedNode at position index to a new variable so it can be returned in Step 5 after the removal is finished (otherwise it will be forgotten)DoublyLinkedNode at position index from the linked list by updating the previous and next instance variables of its own previous and next nodes.size instance variable of the ArrayList by 1Importantly, remember the idea of edge cases that we introduced in Lab 3. We have two very important edge cases for our remove method here. We should make sure that we can remove a node correctly when it is (1) at the beginning of the list, and (2) when it is at the end of the list. Updating the connections between the nodes in Step 3 above will be different if the node is at the beginning or end, as opposed to when it is somewhere in the middle of the list.
Hint
Once again, drawing a picture of what is happening as we remove a DoublyLinkedNode and how we need to update its neighbors could be really helpful!
Our unit tests for this method will be very similar to what we used for the set method above and for our MyArrayList‘s remove method in Lab 3. Make sure to test for the edge cases of removing nodes at the beginning and end of the list.
We have two final methods that we want to implement that are both related to the overall state of the array list.
public boolean isEmpty() should return whether or not the linked list is currently empty (i.e., contains no items). Question: there are actually two different ways to properly check whether a linked list is empty – can you think of both? You only need to implement one.public void clear() should remove all of the DoublyLinkedNodes from the list and reset the size to 0.Once again, you should create unit tests to test these two methods. Don’t forget to use the debugger if needed.
Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.