Generic ArrayList

Question

Can anyone recommend improvements to the compress() method?

public class ArrayList<E> {
private Object[] array;
public static final int DEFAULT_SIZE = 20;
private int size = 0;
public ArrayList(){
 this(DEFAULT_SIZE);
}
public ArrayList(int size){
 array = new Object[size];
}
public void add(E element){
 ensureCapacity();
 array[size++] = element;
}
public E remove(int index){
 if(index>=size || index < 0 ){throw new RuntimeException("Invalid index");}
 E element = (E) array[index];
 array[index] = null;
 --size;
 compress();
 return element;
}
public E get(int index){
 if(index > size){throw new RuntimeException("Invalid index");}
 E element = (E) array[index];
 return element;
}
public int size(){
 return this.size;
}
private void ensureCapacity(){
 if(size < array.length){ return;}
 resize();
}
private void resize(){
 Object[] temp = new Object[array.length*2];
 copy(array,temp);
 array = temp;
}
private void copy(Object[] src, Object[] dest){
 if(dest.length< src.length){throw new RuntimeException(src+ " cannot be copied into "+dest);}
 for(int i=0;i<src.length; i++){
 dest[i] = src[i];
 } 
}
private void compress(){
 int skipCount =0;
 for(int i=0;i < size && i<array.length; i++){
 if(array[i]==null){
 ++skipCount; 
 }
 array[i]=array[i+skipCount];
 }
}
}

• skiwi: Can you explain more about what you are actually doing? Are you, knowingly that ArrayList exists, making your own implementation for fun? Why does it not implement the List<E> interface?

Answer 1

General

There are a few things in here....

• You allow users to add a null value in the add() method, but you will then 'compress' it later if you remove something.

• you have an off-by-one error on the get() (but not remove() ) methods... it should be >= size, and not > size.

• compress() is only called from remove(). I would recommend removing the compress() method and making remove just compress 1 value:

  public E remove(int index){
   if(index>=size || index < 0 ){throw new RuntimeException("Invalid index");}
   E element = (E) array[index];
   --size;
   System.arraycopy(array, index + 1, array, index, size - index);
   array[size] = null;
   return element;
  }
  

  Alternatively, pass in an int value to the compress method.

  If you do the above you will correctly support null values.

• Although it is tempting, don't call your class ArrayList.... it competes with the standard class name, and will produce problems. Use something like 'MyArrayList'.

Generics

What you have right now is fine with respect to the Generics.

If you want to be a bit more correct, you can use a Class-type initializer, and use that to create correctly typed arrays, and avoud the generic (T)array[index] casting later.... but that is a pain, and requires passing Class<T> clazz in as the constructor.

Answer 2

1. I agree with @rolfl, that System.arraycopy is better but about the following code:

   private void copy(Object[] src, Object[] dest){
    if(dest.length< src.length){throw new RuntimeException(src+ " cannot be copied into "+dest);}
    for(int i=0;i<src.length; i++){
    dest[i] = src[i];
    } 
   }
   

   If dest.length bigger than src.length you get an exception with the following message:

   java.lang.RuntimeException: [Ljava.lang.Object;@1318e59 cannot be copied into [Ljava.lang.Object;@787ee7
   

   It's not very useful, I'd rather put the size of the arrays to the message.

2. for (int i = 0; i < size && i < array.length; i++) {
   

   I think the following would be a little bit easier to read:

   for (int i = 0; i < Math.min(size, array.length); i++) {
   

3. private Object[] array;
   

   I'd rename array to data to reflect its purpose.

4. remove check negative indexes:

   if (index >= size || index < 0) {
    throw new RuntimeException("Invalid index");
   }
   

   get doesn't:

   if (index > size) {
    throw new RuntimeException("Invalid index");
   }
   

   It would be more user-friendly to check that in both method. You could create a common checkIndex() method to remove the duplication. Furthermore, putting the invalid index into the exception message would be useful.