CSci 2101 Takehome exam 2.

Due Monday, November 7th at 11:59pm

You may not take more than 8 hours on this test.

40 points

You may use the textbook, your lecture notes, in-class examples, and other materials for this class. You may use any Java textbook. General online Java resources may be used with preapproval only (send me an e-mail if you plan to use any). You may not google for any problem-specific keywords.

The work is strictly individual. You may ask me questions in person or by e-mail, you may not ask anyone else any questions about any material on the test. Any exceptions to this rule (such as discussions with a TA) will be announced in class.

Please include your name in comments in each file and comment the program appropriately.

Implementing a doubly linked list

Overview

A doubly linked list is a linked list in which a node has a link not just to the next node but also to the previous one (called previous). In addition to the firstNode reference, a doubly linked list has a reference lastNode to the last node. The list has the flexibility of being able to be traversed forward and backward. It cuts down traversal time by accessing elements close to the end of the list by starting at the last node and traversing the previous references.

You will also need to write an iterator that traverses the list backward, starting at the last node and following the previous references. You need to change get method so that it traverses the list backward if the element is in the second half. The purpose of the iterator is to check that references to the previous node are correct.

Write tests for each of your methods before you write the actual method, this will help you better understand the intended behavior. Feel free to use JUnit if you so prefer.

Step-by-step instructions

Write an implementation of a doubly linked list called DoublyLinkedList. Use OurLinkedList as a starting point (make sure to rename all necessary elements appropriately). Just like OurLinkedList<E>, it implements OurList<E> interface, and via it Iterable<E>.

Please follow this sequence of steps below, starting at the class that's identical to the final version of OurLinkedList class. This sequence of steps allows you to develop incrementally, testing after each step. A different order would make incremental development difficult.

  1. Add a previous variable to the Node inner class.
  2. Add the lastNode reference to the linked list class.
  3. Modify the add and remove methods so that they correctly set not just the next references but also the previous ones. Be especially careful with adding to an empty list (both firstNode and lastNode need to be set) and removing the last element from the list (both firstNode and lastNode must become null).
  4. Add an inner class LinkedListBackwardIterator that implements Iterator<E>. It starts at the last element and iterates backward traversing the previous references. The iterator must not use get.
  5. Change any other methods in the linked list that need to change to work correctly with the double linking.
  6. Add an instance variable 
    
  private boolean iterateBackward = false;
    to the DoublyLinkedList class and write a method 
    
public void iterateBackward(boolean back)
    that sets iterateBackward to back. If back is true then the backward iterator is used, otherwise the forward one (the one we developed in class) is used.
    Note that you will also have to add the method to the interface in order to call it in your testing code.
  7. Change the iterator method to return the usual iterator when iterateBackward is false and LinkedListBackwardIterator<E> when the variable is true.
  8. Test your backward iterator and all other methods that use previous references by setting iterateBackward to true and running a for-each loop. It should print the list backward. If it doesn't, a mistake can be in the iterator or in add/remove methods. Fix the errors (if any); test with both forward and backward iterators.
  9. Change the get method so that when the element is in the second half of the linked list, you access it from the last element going backward. Test your get method.
  10. Test everything carefully. In particular, make sure to test iterating forward and backward after a combination of add and remove calls. This way you are more likely to notice if some of your methods are not setting some of the references correctly.
  11. Submit both all your Java file, including your testing code. Make sure to include all of your tests. If any of your tests are not working correctly, write a comment about it. Remember that an error in functionality and no test for it will result in points taken off twice: once for the error and once for a failure to test for the case.

How to submit

Please submit it by e-mail to me with the subject 2101 Midterm II.

CSci 2101 course web site.