Assignment Description
If you've not done so, I suggest you do Lab 0 first.
In this lab you'll be creating your first implementation of a data structure from the Java Collections Framework. Specifically, we'll be constructing an ArrayList. You should be very familar with using this data structure and its methods by now -- two different add methods, get, set, remove, isEmpty, size, and so forth.
ArrayList is just an implementation of the List interface that uses an array to store items that are put into it. (We'll see a different storage structure later when we look at LinkedList.) The List interface has over 20 methods that you need to implement!!! Fortunately, many of these methods can be handled without worrying about how the data is actually being stored. For example, isEmpty() might just check to see if (0==size()). Much of this work has already been done in the AbstractList class.
To keep our version of the data structure separate from the existing ones in Java, we'll be prefixing each with "My". In this case, you'll be creating MyArrayList which is a child of the AbstractList class.
- 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. (See Weiss 4.7 for reminders.)
- Skimming through the documentation for AbstractList,
what methods must you implement to create a concrete child
class and what methods do you need to override to be able to do
adds/removes successfully?
Backing storage
As I'm sure you recall, an array is fixed in size while ArrayList dynamically expands itself as necessary. Now that we know that our MyArrayList will be using a regular array for storage, this means that the number of spaces in the array (capacity) might be different than the number of items in the MyArrayList (size). The capacity must always be greater than or equal to the size -- otherwise we must be losing data. (Consider one of the flippy CD holders -- you've got a certain number of slots where you could put CDs and then there is the number of CDs you've actually put in it.)
- 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?
- Write a private resize() method that increases the length
of the data array by 1. You'll need to make a new array, 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[].
- Suppose that data.length is currently s. How many assignment
statements does your resize method need to perform, in terms of s,
in order to copy everything into the new array?
(You may ignore loop counter assignment statements, such as i++.)
If you're having a hard time coming up with the formula, try counting the
number of assignments when s=2, s=3, etc., and then try
to find a pattern.
(For example, the loop
for( i=0; i < 5; i++ ) { temp[i] = 4; }has 5 assignment statements. The loop
for( i=0; i < s; i++ ) { temp[i] = 4; }has s assignment statements. How many assignment statements does your loop from question 4 have?)
Resizing options
Hopefully by now you'll have realized that when you add something to MyArrayList, you might need to resize things. Otherwise, you risk not being able to fit all of your lovely data into your structure.
-
Write the implementation for the add(int
index, AnyType element) method. Don't forget to throw the
specified exception of needed and to call resize if necessary.
(See ArrayList's
add method for details.)
-
Now do the same for the set(int
index, AnyType element) method. Pay close attention to what it is
supposed to return and throw.
- Suppose you start with an arraylist of size 1 (and with data.length=1), and
you add n elements one-by-one to the arraylist. How many calls
to resize will you make, in terms of n? What is data.length
for these successive calls? Therefore, in total, how many assignment
statements are performed for all these resizes? I will accept any
answer in an acceptable range, but be as accurate as you can. The
following may (or, may not) help organize your thoughts. Your final
answer would be the sum of the entries in the bottom row.
data.length 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ... n-1 n calls resize? (Y/N) Y ... Y # assignment
statements
total number of assignments performed (in terms of n):
- Now suppose you change your resize method to double the
length of the data array, instead of only incrementing by one. Answer
the previous question again and comment on the result. If it helps, you
may assume that n is a power of 2. It may be useful to
remember that 1+2+...+2p= 2p+1 = 2*2p.
data.length 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ... n-1 n=2p calls resize? (Y/N) Y ... Y # assignment
statements
total number of assignments performed (in terms of n):
Part 2 - Testing things
An important part of developing a reusable ADT is being able to determine if you've correctly implemented everything. A portion of this lab will be writing some programs that will test out your MyArrayList implementation and allow you to spot if there are any problems in it.
A good programming technique is to "write a little, test a little". By being able to come up short test 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.
- Come up with three short test that will test an aspect of
one of the methods you are planning on implementing. Describe (you
don't need to do this in Java) what actions you will do in the test and
what the expected outcome should be. For example, perhaps I might want
to test the constructor. I would call the constructor and then print
out the value given by size() as well as looking at the array's
length to see if it was what I expected.
Frequent sources of errors come from adding/removing things, repeated operations, and dealing with edge cases (is that supposed to be less-than or less-than-or-equal?)
handin
If you adhered to the honor code in this assignment, add the following statement to the top of your prelab.
I have adhered to the Honor Code in this assignment.
Write or type up your solutions and hand in a paper copy by the deadline listed at top. Late prelabs will not be accepted.
Last Modified: February 10, 2012 - Benjamin A. Kuperman
