For this laboratory, you will create a (doubly) linked list implementation of the interface OrderedStructure, which declares the following methods.
Implementations of this interface should be such that the elements are kept in increasing order. The order of the elements is defined by the implementation of the method compareTo( Object obj ) declared by the interface Comparable. The classes Integer and String both implement the interface Comparable, you can use these for the tests. Objects of any other classes that implement the interface Comparable can be stored in an OrderedList.
IMPORTANT: Since the main objective of the laboratory is to study doubly linked lists, generics will not be used. Since generics are not used, 1) some warnings will be issued when compiling the source code. But also, 2) the type of the return value of the method get( int pos ) will be Object. Hence, the users of the class will be forced to use a type cast when accessing the content of an OrderedList. There is an optional exercise at the end of the laboratory consisting of rewriting the implementation using generics. A solution will be posted next week.
First, let’s create a template for the class. At this point, we are ignoring details such as the implementation of the body of the methods, we are focusing on the necessary variables and the need for a static class called Node. This template needs to contain a static nested class called Node, the necessary instance variables, and empty definitions for all the methods of the interface OrderedStructure.
The compiler will not allow us to have empty declarations for the methods that return a result. To circumvent this problem, we could add a “dummy” return statement, such as returning the value -99 for the method size. Knowing that later we will give it a proper implementation.
However, we may later forget to change the implementation, and this will cause all sorts of problems. Because of this, I prefer creating an initial method that consists a throw statement.
I can now compile the class and start working on the implementation of the methods one by one. Any attempt at using a method that has not been implemented yet will be signaled with the proper exception to remind us that we still have to implement that method. You can ask your TA for further information if needed.
Create a test class called OrderedListTest, at this point it will contain only a main method that declares an OrderedList and creates an OrderedList object. (I leave it up to you to JUnit or not for implementing the test cases.)
Make sure that your implementation is correct, i.e. has all the elements presented above and compiles. When you are done compiling all the files, proceed with the next step, implementing the method size().
We now have a complete implementation of the interface OrderedStructure.
The objectives are to learn how to traverse and transform a doubly linked list. Therefore, you are not allowed to use any auxiliary or existing methods, in particular add, for your implementation!
Your implementation should traverse both lists and insert the elements (values) of the other list, in order, into this list. Remember that it is better to practice now than at the final examination!
The added benefit of using generics will be that all the elements of a list will be of the same type. Therefore, the method compareTo( other ) will always be passed an object of the same type as the instance.
For the ArrayList implementation of the interface List.
Last Modified: March 19, 2014