Doubly-Linked Lists

The goal of this lab period is to give you an opportunity to implement a doubly-linked list with Iterators that allow you to traverse the list backwards and forwards.

Tasks

1. Make a new folder for this week's project.
2. Copy your LinkedList class from last week. Show Stephanie the output your test code to convince her it is working. Fix any bugs.
3. Re-implement your LinkedList class as a doubly-linked list with a head and a tail pointer and prev/next pointers at each node. It should have the same functionality as the original LinkedList.
4. Test your doubly-linked list. It will be graded as part of your project, so be sure to test it well. This means you should test (at a very minimum) adding to an empty list, a list with one item, and a list with multiple items, clearing a list, then adding to it again.
5. Add support for a backwards iterator.
   • Create another private class called LLBackwardIterator modeled on LLIterator:

         private class LLBackwardIterator implements Iterator<T>
         

     It should begin at the tail and iterate through the backwards links.

   • Add a method to the LinkedList class to access the iterator:

         // Return a new LLBackwardIterator pointing to the head of the list
         public Iterator<T> backward_iterator() {
             return new LLBackwardIterator( tail );
         }
         

   • Then add the following to the end of your main test function.

             System.out.println( "iterating backward" );
             Iterator bi = a.backward_iterator();
             while (bi.hasNext()) {
                 System.out.println( bi.next() );
             }
         

6. Test your code again. :)

Once you have completed the lab, go on to the project.