Due at the start of class on Monday September 24
In this prelab, you will tackle some of the non-programming issues related to the second full lab assignment. Please write or type up your solutions, and hand in a paper copy by 10 am on Monday. Sign the Honor Pledge somewhere on the paper. Late prelabs are not accepted.
Note that there are 5 numbered questions here.
In this week's lab, you will construct your own implementation of the ArrayList data structure, which we will call MyArrayList. You will likely be using this data structure frequently. It has a fairly simple interface and behaves similarly to the Python list structure.
list.add(x)- adds x to the end of the list (like Python's
list.add(i,x)- adds x at index i in the list moving items down by 1 (like Python's
list.set(i)- gets or replaces item at index i in the list (like Python's
list.remove(i)- removes the item at index i in the list moving items down by 1 (like Python's
list.size()- returns the number of items in the list (like Python's
MyArrayList implements the Java List
interface. That is, you have to provide implementation for all
of the (abstract) methods contained in the interface. There are
more than 20 such methods, however, which is more than we want
to do in a single lab. Fortunately, java.util contains an
abstract class AbstractList
that implements many of the required methods. Some of the
methods still aren't implemented (that is, they are abstract)
and some of them may have an inefficient implementation (that
is, you'll want to override them), but it's useful
nonetheless. Thus your MyArrayList class should extend
AbstractList in order to take advantage of this.
You'll be using generics for your implementation, and taking advantage of the fact that List and AbstractList are similarly parameterized. Given the information above, give the declaration (i.e. "public class...") for MyArrayList. Remember to properly indicate the parent and that we'll be using Generics to handle the storage type. (Refer to Weiss 4.7 for information on generics.)
Skim through the documentation for AbstractList
(specifically the description at the top of the web
page). What methods must you implement to
create a concrete child class? What methods do you need
to override so that the list is modifiable?
As you might expect from the name, the underlying storage for
an ArrayList is an array. That is, an ArrayList is an
object with an array as a data member. Thus, the number of
slots in the array (its capacity; i.e., its length)
might be different than the number of items currently in the
MyArrayList (its size). The size must always be
less than or equal to the capacity -- otherwise we're not
storing everything. (Note: you don't need to make things
smaller after removing items.)
Which of the methods that you identified in question 2 might require that you resize the array in order to be sure all the data can fit?
When you add an item to a MyArrayList, you may need to resize the underlying array. Otherwise, you might not being able to fit all of your data into your structure. Let's consider how much larger we should make the array each time we resize.
You will write a private resize() method that increases the length of the data array as part of your assignment. You will need to make a new array of larger size, copy the data from the old array into the new array, and change the reference to point to your new array. Let's assume that our storage array is declared AnyType data.
data.length==1), and you add n elements one-by-one to the ArrayList. After the first item is added, you'll have to call resize for each additional add. When you resize, you'll copy all the previous values over to the new array.
Consider the following questions.
The total number is the sum of the entries in the bottom row. (It may be useful to remember that 1+2+4+...+n = n(n+1)/2)
|Number of items (size)||1||2||3||4||5||6||7||8||9||10||11||12||13||14||15||16||17||...||n-1||n|
|calls resize? (Y/N)||N||Y||Y||Y||Y||Y||Y||Y||Y||Y||Y||Y||Y||Y||Y||Y||Y||...||Y||Y|
|# assignment statements in resize( )||0||1||2||3||4||5||6||7||8||9||10||11||12||13||14||15||16||n-2||n-1|
*** Total number of assignments performed (in terms of n): (n-1)*n/2
|Number of items (size)||1||2||3||4||5||6||7||8||9||10||11||12||13||14||15||16||17||...||n-1||n=2p||n+1|
|calls resize? (Y/N)||N||Y||Y||N||Y||...||N||Y|
|# assignment statements in resize( )||0||1||2||0||4||0||n|
You are to determine the total number of assignments; the chart will help you determine this value by summing the values in the bottom row. You may assume that n is in the form 2p+1 -- that's the worst case scenario. It may be useful to remember that 1+2+...+2p= 2p+1-1 = 2*2p-1.
*** Total number of assignments performed (in terms of n, so get rid of all p's, and simplify):
An important part of developing a reusable Abstract Data Type is being able to determine if you've correctly implemented all of its methods. A portion of the lab will be to write some test programs to test your MyArrayList implementation, to see if you can spot any problems with it.
A good programming technique is to "write a little, test a
little." By being able to come up with short tests that
you can use right after you create a method, you will have
greater confidence and insight as to the location of any bug
that appears later.
If you adhered to the honor code in this assignment, add the following statement at the top of your prelab.
I have adhered to the Honor Code in this assignment.
Write or type your solutions and hand in a paper copy
by the deadline listed at the top of this prelab. Late
prelabs will not be accepted.