Objectives

• To provide practice implementing and using a doubly linked list.
• To provide practice implementing and using the Postion interface.

Problem Statement

Complete the implementation of the NodePositionList class given on pages 239-241 in Goodrich and Tamassia. This class uses a doubly linked list for its underlying implementation. You will be given an implementation of the DNode class, which implements the Position interface.

NodePositionList is an implemention of the PositionList ADT, which consists of the following methods::

• size():int --- Return the number of elements in D.
• isEmpty():boolean --- Determine if D is empty.
• first():Position --- Return the first position
• last():Position --- Return the last position Not Implemented
• prev(Position p):Position --- return the Position that precedes p
• next(Position p):Position --- return the Position that follows p Not Implemented
• addFirst(Object o) --- Insert o in the first position
• addLast(Object o) --- Insert o in the last position Not Implemented
• addBefore(Position p, Object o) --- Insert o before position p
• addAfter(Position p, Object o) --- Insert o after position p Not Implemented
• remove(Position p):Object --- Remove the object at position p
• set(Position p, Object o):Object --- Replace the element at position p

Except for the marked methods, all of these methods have been correctly implemented. You must implement and test the marked methods.

Note that any method that involves a Position parameter must call the private checkPosition() method to check that the position is valid. For example, see prev().

Note that some of the above methods throw exceptions. There are three types of exceptions used in NodePositionList, the InvalidPositionException, EmptyListException, and BoundaryViolationException. You are given complete implementations of the first two of these, but the third one is left as a lab exercise. You should model your implementation after the first two and you should develop code to test the new exception.

The toString() Method

Write a recursive NodePositionList method named toString(). This method should construct and return a string containing each element of the list, from first to last.

Testing Your Implementation

You will also need to develop a main program, which will be used to test your implementation of the NodePositionList class. You can either implement the main() method in the NodePositionList class or in a separate class, say NodePositionListTester.

Your main program should perform whatever tests are needed to prove that the methods you wrote are correct. At a minimum you should test that you can insert an unlimited number of elements into the list and then remove all the elements. Your should also test that exceptions are thrown in the proper places. For example, try removing an element from an empty list or try referring to a nonexistent position. After you test the exception, you will have to comment out that line of code to continue your testing. Here's some code to get you started:

   NodePositionList list = new NodePositionList();
   Position p;
   System.out.println(list.toString());    // Print the empty list
//        p = list.first();                // Should throw exception
   p = list.addFirst( new Integer(8) ); // Insert an element
   System.out.println(list.toString());    // Print the list with 1 element

Downloads

• NodePositionList.java, an incomplete implementation of the List interface
• DNode.java, a complete implementation of the DLNode class.
• PositionList.java, a complete implementation of the List interface
• Position.java, a complete implementation of the Position interface
• BoundaryViolationException.java, an incomplete implementation of this exception
• InvalidPositionException.java, a complete implementation of this exception
• EmptyListException.java, a complete implementation of this exception

Step-wise Refinement

Documentation

Programming Assignment