Replacing and Removing Items

Overview

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.

Replacing Items in MyLinkedList

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:

1. First check whether item is null – we do not want to be adding any null items to our linked list. If so, throw a NullPointerException.
2. Next verify that the 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.
3. Save the prior item that was in the node at index to a new variable so it can be returned after the replacement is finished in Step 5 (otherwise it will be forgotten)
4. Assign the item argument to the DoublyLinkedNode at position index in the linked list
5. Return the prior item that you saved to a new variable in Step 3

Testing

You 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.

Removing Items from MyLinkedList

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:

1. First verify that the 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.
2. Save the current item from the 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)
3. Remove the DoublyLinkedNode at position index from the linked list by updating the previous and next instance variables of its own previous and next nodes.
4. Reduce the size instance variable of the ArrayList by 1
5. Return the former item that you saved to a new variable in Step 2

Importantly, 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.

Testing

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.

Methods about the State of the MyLinkedList

We have two final methods that we want to implement that are both related to the overall state of the array list.

1. The first method 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.
2. The second method public void clear() should remove all of the DoublyLinkedNodes from the list and reset the size to 0.

Testing

Once again, you should create unit tests to test these two methods. Don’t forget to use the debugger if needed.

Committing Your Progress

Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.