In this part of the lab, we will add functionality to our MyLinkedList class to insert and retrieve items from our data structure. We will also continue to practice using unit tests to debug and validate our implementation.
The first main operation we will work on programming is adding items to our data structure since we cannot do anything unless it is storing data. Given how linked lists store data, we need to first create a private helper method that will simplify the processing of adding data to our doubly linked list.
Implementing the getNth Method
To be able to both insert and retrieve data at given indices within the linked list, we first need to be able to get the DoublyLinkedNode object that is stored at nearby indices. To help with this process, we will create a private DoublyLinkedNode getNthNode(int index) method that traverses the linked list from its beginning to find the n-th DoublyLinkedNode in the list. More specifically, this method should:
this.firstNode.count variable that counts how many DoublyLinkedNodes that you have visited so far.while loop (similar to what you used in Part 1 of the Warmup), keep following the next instance variable of the DoublyLinkedNode until you either reach the n-th node or you reach the end of the list (i.e., when the current node is null).
If you reached the n-th node, return it. If you reached the end of the list before the n-th node, throw an IndexOutOfBoundsException with a meaningful error message (like in Lab 3 Part 2).Our next method public void add(int index, T item) will be responsible for adding a given T item into a desired index in the linked list. 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 makes sense given the current number of items in the array list. If the index is negative or too large, we should throw an IndexOutOfBoundsException with an appropriate error messagesize == 0), then we need to create a new DoublyLinkedNode that contains the given item and make it both the firstNode and lastNode of the linked listindex is the start of our list (i.e., index == 0), then we need to add the item to the beginning of the linked list. This will involve creating a new DoublyLinkedNode that contains the given item with the correct next node, updating the previous instance variable of its next node, and saving the new node at the beginning of the list.index is the end of our list (i.e., index == size), then we need to add the item to the end of the linked list. This will involve creating a new DoublyLinkedNode that contains the given item with the correct previous node, updating the next instance variable of its previous node, and saving the new node at the end of the list.DoublyLinkedNode that contains the given item with the correct previous and next instance variables (your getNthNode method should be really helpful here), and saving the new node’s order in the list by changing the appropriate instance variables of its previous and next nodes.size of the list by 1.ReadMe
This order of operations within each of Steps 3-6 is very important so that all of the nodes in the linked list will be linked in the correct order both forwards and backwards. It will likely be very helpful to draw out what the list will look like after the additions in each of the Steps 3-6 to help guide your implementation – it definitely helps us professors!
Before we continue, we should test some of the behaviors of our add(index, item) method. Unit tests that we want to consider at this point include:
NullPointerException is thrown when you try to insert a null item into the linked list.IndexOutOfBoundsException is thrown when you try to insert into a negative index or an index that is too large.get method below).Hint
Many of your unit tests from Lab 3 will also be useful for the linked list since both data structures implement the List interface. Please feel free to reuse your unit tests from Lab 3 where ever you think it will be helpful – simply copy them from your MyArrayListTest.java file into MyLinkedListTest.java and change any instances of MyArrayList to MyLinkedList.
Note: we can also update our earlier unit test for the size method from Part 1 of this lab to check whether the size instance variable is properly increased each time we add a new item to our linked list.
Our second approach for adding items to the linked list is the method public boolean add(T item) that always adds an item to the end of the list. Because we already did all of the necessary work in the previous method (adding to the end of the list was the special case in Step 5), our second add method can simply call the first add method with the appropriate index.
The only other instruction needed in the second add method is to always return true since we successfully added the item to the linked list.
Don’t forget to create unit tests so that you can be sure that this method is working as intended. Your unit tests from the first add method can help us know what to put here.
We will only have one method for retrieving items from the linked list: public T get(int index). Recall that we created a stub of this method while testing our code so far at the end of Part 1. We should change this method to:
index argument is valid, given the current number of items in the array list. If index is out of range, once again throw an IndexOutOfBoundsExeception with an appropriate error message.DoublyLinkedNode at the given index. Again, your getNthNode method you created above might be very helpful here!Instead of creating new unit tests for the get method, we can instead retrieve items from our lists in the unit tests created above for the two add methods to make sure that the correct items are stored in the correct index. If there are any errors, hopefully the type of error will help you know which method needs debugging and hints at what might be the problem. Remember that the debugger from lab 3 Part 2 could be very helpful here.
Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.