Inserting and Retrieving Items

Overview

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.

Adding Items to MyLinkedList

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:

1. Start with the beginning of the linked list, available as this.firstNode.
2. Also create an integer count variable that counts how many DoublyLinkedNodes that you have visited so far.
3. Using a 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).

Implementing the add(int index, T item) Method

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:

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 check whether 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 message
3. If we currently have an empty list (i.e., size == 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 list
4. If index 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.
5. Instead, if 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.
6. Otherwise, we need to add the item somewhere else that is inside the linked list. Again, we will need to create a new 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.
7. Increase the size of the list by 1.

Testing add(int index, T item)

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:

1. Making sure that a NullPointerException is thrown when you try to insert a null item into the linked list.
2. Making sure that an IndexOutOfBoundsException is thrown when you try to insert into a negative index or an index that is too large.
3. Making multiple additions to the list so that you test each of Steps 3-6 above and make sure the code doesn’t crash (we will verify each case made a correct addition after we implement the get method below).

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.

Implementing and Testing the add(T item) Method

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.

Retrieving Items from MyLinkedList

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:

1. First verify that the 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.
2. Return the item stored in the DoublyLinkedNode at the given index. Again, your getNthNode method you created above might be very helpful here!

Testing

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.

Committing Your Progress

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