Doubly Linked List Iterator

Overview

In this part of the lab, we will create a ListIterator called MyLinkedListIterator for our MyLinkedList class that will allow us to iterate through our data structure without accessing any item by its index, similar to how we looped in Part 3 of the Warmup. Given the way a linked list is organized, this type of access is faster than using the get method whenever we want to loop over successive items in the list.

Since our MyLinkedList is a doubly-linked list, our MyLinkedListIterator object will be able to iterate both forwards and backwards through our MyLinkedList one item at a time. You can think about the iterator as always being positioned before and/or after an item in the list. It will start in front of the firstNode of the linked list, as pictured here:

Iterating once forward then returns the first item (0) of the linked list (since the first item was to the right of the iterator) and moves the iterator to be between the first and second items, as pictured here:

Iterating forward once again will then return the second item (1) of the linked list (since the second item was now to the right of the iterator) and moves the iterator to be between the second and third items, as pictured here:

Iterating backwards would then return the second item (1) of the linked list (since the second item was now to the left of the iterator) and moves the iterator back to be between the first and second items, as pictured here:

In summary, each time the iterator moves forward, it returns the item to its right, whereas each time the iterator moves backwards, it returns the item to its left.

Implementing MyLinkedListIterator

We will start implementing our MyLinkedListIterator class by defining another inner class within the MyLinkedList (similar to MyLinkedListIterator in Part 1 of the Warmup). It should implement the ListIterator<T> interface.

Your MyLinkedListIterator will have one constructor that sets up the MyLinkedListIterator to be positioned in front of the first DoublyLinkedNode of your MyLinkedList (as in the first diagram above). You should also think about what instance variables you will need in your MyLinkedListIterator class (think about how you will keep track of the current position of the iterator within your doubly-linked list) and how you will assign values to those instance variables in your constructor.

Before implementing the rest of the iterator, you should add two public methods to your MyLinkedList class (both from the List interface) so that you an create and test your iterator:

1. public ListIterator<T> listIterator returns a new MyLinkedListIterator for iterating through your list.
2. public Iterator<T> iterator also returns a new MyLinkedListIterator for iterating through your list (e.g., by simply calling the first method).

Next, you will want to create the four public methods that implement the functionality of the iterator that we described in the Overview above:

1. public boolean hasNext() returns either true if there is another item to the right of iterator in the linked list, else false
2. public T next() implements the idea of moving forward through the linked list. The next method should return the item to the iterator in the linked list if one exists and shifts the iterator to be after the next item to the right. If there is no next item to the right, then the method should throw a NoSuchElementException with a meaningful error message
3. public boolean hasPrevious() returns either true if there is another item to the left of iterator in the linked list, else false
4. public T previous() implements the idea of moving backward through the linked list. The previous method should return the item to the left of the iterator in the linked list if one exists and shifts the iterator to be before the previous item. If there is no previous item to the left, then the method should throw a NoSuchException with a meaningful error message

As you create each of these four methods, do not forget to add unit tests to your MyLinkedListTest file to help debug and verify that everything was implemented correctly. A useful strategy in your tests might be to create a new MyLinkedList with a few elements, then call the listIterator method to get a copy of your iterator, then test the methods of your iterator by comparing what each returns vs. what you expect based on the items you initially added to the linked list. You might need to create stubs for each of the methods before you can run a unit test since we are implementing the ListIterator interface that requires several methods.

        public int nextIndex() {
            throw new UnsupportedOperationException();
        }

        public int previousIndex() {
            throw new UnsupportedOperationException();
        }

        public void add(T item) {
            throw new UnsupportedOperationException();
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public void set(T item) {
            throw new UnsupportedOperationException();
        }

Committing Your Progress

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