Comp 271 lab 1 - MyList

Goals

Overview

This lab deals with a class MyList, which should be looking more and more like ArrayList by now; MyList.zip is here. The resizing add() operation is completed, through the operation ensureCapacity(int neededCapacity). This does nothing if there is room, but otherwise adds space so the total is ~50% more than neededCapacity. It is taken, more or less, from ArrayList.java.

You are to implement the following features. Further information on them can be found in the ArrayList java documentation.

1. add(int n, EltType e)   This adds element e to the middle of the list. Everything from position n to the end of the list must be moved over by one. You will have something like things[n+1] = things[n], but be careful about the order of the loop! See Bailey page 52 for the right way and the wrong way. After you have created room, you set things[n]=e.

Note that to add near the front of the MyList is relatively inefficient; especially if you add several items, you have lots of moving to do! The LinkedList approach makes insertion much more efficient.

2. indexOf (EltType e)   This searches the array for e, and returns its position, or -1 if e is not found. That is, it returns the first integer n such that things[n] equals e, or else -1. When looking for a match, use the .equals() method to compare e and get(i), not ==.

As a search operation, indexOf is again relatively inefficient; on average, if N is the size of the MyList, the search will take N/2 steps (why?)

3. addAll(MyList<EltType e> L)   This adds all the elements of L at once. The official ArrayList.addAll() allows you to addAll the elements of any Collection, that is, the elements of anything with an Iterator. However, we'll settle for just this simpler case. However, you definitely should allocate new space only once, with neededCapacity.

4. equals(Object other)   This returns true if the current MyList is the same as ob, false otherwise. Step 1 should be to verify that other is in fact a MyList<EltType>; if not, the answer is false (if so, you still have to go on). However, you can't do that with generics. All you can do is to verify that other is a MyList. (When we do this, we cast other to otherlist, and can now work with otherlist as a MyList object, not an Object.)

So what if otherlist is a MyList of some other element type? We'll get there when we start comparing elements: equality will fail, provided we use .equals() for that test, and we'll return false.

The next two steps in the code provided (left for you to do) are to verify that the size() values of the two lists (this and otherlist) are the same, and that corresponding elements from 0 to size()-1 are the same. If a mismatch is found at any point you return false; otherwise you get to the end of the method and return true. Comparing sizes is easy; to compare elements you will need to set up a loop (eg for (i=0;i<size(); i++)) and compare get(i) and otherlist.get(i). If they are not .equals(), return false.

To submit your project, create a zipfile and email it to me at pld@cs.luc.edu.