CPE 102 Program 2b - A Basic array-based List

Ground Rules

No collaboration is allowed on this program assignment. Your program must be an individual and original effort. Except for any situations explicitly identified in this assignment, if any, you may only receive help from your instructor or the tutors provided by the Computer Science Department. See the Syllabus for the significant consequences for disallowed collaboration and/or plagiarism.


   None so far - updates and corrections, if any, will show up here (be sure to refresh this page as necessary).

Due Date and Submission Instructions

Submit the following file(s) on one of the CSL servers using handin as follows:

    File(s): BasicList.java BasicArrayList.java

    touser: eaugusti

    assignment/subdirectory: 102-program02b

  1. To gain experience working with arrays.
  2. To gain experience working with Interfaces.
  3. To gain experience working with exceptions.
  4. To begin understanding the concept of an Abstract Data Type (ADT).
  5. To gain insight into the internal workings of the Java Standard Library java.util.ArrayList<E> class.

You will be implementing a class that represents a simple list like, for instance, a list of numbers, a shopping list, or a todo list. Common things one does with a list include adding stuff, removing stuff, seeing if somthing is on a list. In programming lingo, a list is an example of an Abstract Data Type (ADT). An ADT is a data type whose logical operations are defined independently of the physical (concrete) implementation. As you know, a Java interface specfies method signatures but no method logic - an excellent choice for defining an ADT! You will implement the methods specified by the interface (plus a few more) using an array of Object references to support the list operations. Later in the quarter you will implement that same ADT a completely different physical implementation to experience, once again, how the logic associated with a methods can be achieved in different ways.

  1. Your source code must meet the Coding Style Guidelines.

  2. Your solution must pass all tests of the provided test driver (link and instruction provided below) when compiled and run on vogon.
  3. Do not suppress any compiler warnings. If you do, your submission may be rejected for grading or your grade marked down at your instructor's descretion.

  4. You may implement any private methods you wish to make your implementation easier and/or better. 

  5. Write a Java interface called BasicList to this specification.

    1. Be sure to read the detailed method descriptions as there is often addtional and necessary information there.

  1. Write a Java class called BasicArrayList to this specification. This class is not a generic class like the Java Standard Library's ArrayList class. Instead, it will be built upon a array of Object references. Remember, due to polymorphism, a reference to any object of any type is also an instanceof Object. This means your BasicArrayList class can store a reference to any and all Java class types - even ones that have not even been written yet!

    1. Be sure to read the detailed method descriptions as there is often addtional and necessary information there.

    2. Notice that this class in not generic.
    3. This class must be written using an array of Object references to store and retrieve values.

    4. This class distinguishes between the size of the list and the capacity of the list. The "size" of the list is the number of elements in the list (stuff added but not removed) at a specific point in time. The "capacity" of the list is the current length of the private array of Object references. For example, a newly consructed BasicArrayList has a size of zero and a capacity of ten. In Java you can use the .length property (not a method) on any array reference to find out is length/capacity at runtime - useful!
    5. In the spirit of minimal necessary instance variables, your class is limited to two instance variables, an Object[] to hold references to the items added to the list and an int to keep track of the number of items in the list (its size). Be sure you don't confuse the size of a list with its capacity.

    6. Note that a list never has any gaps (holes) between the values in contains. This means all indexes between zero and size-1 contains things added (and not removed) from the list by the user of the list.
    7. You must only allocate a new array when it is necessary to grow or shrink the capacity of the array.

    8. Recall that arrays are fixed in size. For any method that increases the size of the array (adds stuff) you must grow the private array, as and when necessary, to support the operation. When attempting to add to an array that is full you must make a new, larger array, copy all the old arrays stuff into it, and add the new element. You must use this algorithm when growing the array - the new larger array must always be exactly twice as large as the old (full) array.

    9. Several of the methods in this class throw exception when certain errors occur. Be sure to read the detailed method descriptions to see which methods and what specific exceptions. You will have to write the conditional logic to determine when to throw the exceptions. Exceptions are Java classes - just contstruct the type you want to throw and throw it. Here is an example of how to throw an IndexOutOfBoundsException (don't forget that you may need to import the exception if it is not in java.lang):

                            throw new IndexOutOfBoundsException();
Testing With the Provided Test Driver
  1. You should develop and use your own tests prior to using the provided test driver.
  2. Do not use the provided test driver until your solution is complete and you believe it is correct.

  3. Using the save-as feature of your browser, not cut-and-paste, save P2bTestDriver.java (to be published on the first due date) in the same directory as all of the source files (.java files).

  4. Compile the P2bTestDriver.java, all of your source files (.java files), and run P2bTestDriver (see How to Compile and Run From the Command Line, as necessary). Remember that your code will be graded on one of the CSL servers so, to avoid unpleasant grading surprises, be sure to test on any one of those machines at least once after all changes and just before handing in!

Program courtesy of Kurt Mammen.