ITI 1121. Introduction to Computer Science II

Laboratory 11

Winter 2014



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.



  1. Create an implementation for the interface OrderedStructure. This implementation, called OrderedList, will use doubly-linked nodes and should have a head and a tail pointer. Furthermore, the implementation should throw exceptions where this applies. See OrderedStructure.

    1. Here is a step-by-step approach for implementing the class OrderedList. This will be a top-down approach, focusing on the general organization of the class first (adding the variables, the nested class, as well as empty methods). Once, the overall implementation is complete, we will implement the methods one by one.

      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.

      throw new UnsupportedOperationException( "not implemented yet!" );

      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().


    2. Implement the method size(), i.e. replace the throw statement by an iterative implementation that traverses the list and counts the number of elements. Add a test to the test class, simply to check that the method size works for the empty list. We will check the other cases when the method add has been completed.


    3. Implement the method boolean add( Comparable obj ); adds an element in increasing order according to the class’ natural comparison method (i.e. uses the method compareTo ). Returns true if the element can be successfully added to this OrderedList, and false otherwise.
    4. Add test cases for the method add. It will be difficult to thoroughly test the implementation, but at least the size of the list should change as new elements are added.
    5. Implement Object get( int pos ). It returns the element at the specified position in this OrderedList; the first element has the index 0. This operation must not change the state of the OrderedList;
    6. Add test cases for the methods add and get to the test class. You are now be in a better position for testing all three methods, add, get and size. In particular, you should be able to add elements, use a while loop to get all the elements of the list, one by one, using the method get. Make sure that all three methods are fully debugged before continuing.


    7. Implement void remove( int pos ); Removes the element at the specified position in this OrderedList; the first element has the index 0.
    8. Add test cases for the method remove to the test class. Make sure that the method remove (as well as all the other methods) is fully debugged before continuing.



      We now have a complete implementation of the interface OrderedStructure.

  2. Write an instance method, void merge( OrderedList other ), that adds all the elements of the other list to this list, such that this list preserves it property of being an ordered list. For example, let a and b be two OrderedLists, such that a contains “D”, “E” and “G”, and b contains “A”, “C”, “D” and “F”, the call a.merge( b ) transforms a such that it now contains the following elements “A”, “C”, “D”, “D”, “E”, “F” and “G”; b should not be changed by the method call. The class String implements the interface Comparable and could be used for testing.

    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!


  3. (Advanced and optional topic) Use your implementation of the class OrderedList as a starting point for creating a parametrized implementation of the following interface.
    public interface OrderedStructure< T extends Comparable<T> > {  
        public abstract int size();  
        public abstract boolean add( T elem ) throws IllegalArgumentException;  
        public abstract T get( int pos ) throws IndexOutOfBoundsException;  
        public abstract void remove( int pos ) throws IndexOutOfBoundsException;  

    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.

Quiz (1 mark)

For the ArrayList implementation of the interface List.

  1. Insertions at intermediate positions are always fast.
  2. Adding an element at the first position is always fast.
  3. Removing an element is always fast.
  4. Reading the value of an intermediate position is always fast.

Last Modified: March 19, 2014