Reviewing custom array List class of java

Question

I am using JDK 12 and I have developed the custom array list in java with a basic understanding Please let me know if there are any flaws in it that I can correct the same

First the POJO class

public class Employee {
    private String id;
    private String name;

    public Employee(String id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Employee[id=" + id + ", name=" + name + "] ";
    }

}

Then come the main logic class of ArrayList, which is the heart

class CustomArrayList<E> {

    private static final int INITIAL_CAPACITY = 10;
    private Object[] elementData;
    private int size = 0;


    public customArrayList() {
        elementData = new Object[INITIAL_CAPACITY];
    }


    private void ensureCapacity() {
        int newIncreasedCapacity = elementData.length * 2;
        elementData = Arrays.copyOf(elementData, newIncreasedCapacity);
    }


    public void add(E e) {
        if (size == elementData.length) {
            ensureCapacity();
        }
        elementData[size++] = e;
    }


    @SuppressWarnings("unchecked")
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size " + index);
        }
        return (E) elementData[index];
    }


    public Object remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size " + index);
        }

        Object removedElement = elementData[index];
        for (int i = index; i < size - 1; i++) {
            elementData[i] = elementData[i + 1];
        }
        size--;   //reduce size of ArrayListCustom after removal of element.
        return removedElement;
    }


    /**
     * method displays all the elements in list.
     */
    public void display() {
        System.out.print("Displaying list : ");
        for (int i = 0; i < size; i++) {
            System.out.print(elementData[i] + " ");
        }
    }

}

and finally, the test class to test the custom implementation of the ArrayList

public class ArrayListTest {

    public static void main(String... a) {
        CustomArrayList<Employee> list = new CustomArrayList<>();
        list.add(new Employee("1", "saral"));
        list.add(new Employee("2", "amit"));
        list.add(new Employee("3", "dinesh"));
        list.add(null);
        list.display();
        System.out.printf("\n element at index %d = %s%n", 1, list.get(1));
        System.out.printf("element removed from index %d = %s%n", 1, list.remove(1));

        System.out.println("\n" +
                "let's display list again after removal at index 1");
        list.display();

    }

}

Answer 1

The CustomArrayList API is inconsistent because I can declare a list of type E to add elements of type E, but when I remove an element from it, I get an Object element:

public Object remove(int index) { /* ... */ }

---

Inside CustomArrayList you work with Object[] elementData. From the book Effective Java; Item 26 you could change your code to:

class CustomArrayList<E> {

  private E[] elementData;
  /* ... */

  public CustomArrayList() {
    elementData = (E[]) new Object[INITIAL_CAPACITY];
  }

  /* ... */

}

---

Inside remove you modify elementData in an imperative way. You could use System.arraycopy which would be more deklarative.

public Object remove(int index) {
 /* ... */
 Object removedElement = elementData[index];
 for (int i = index; i < size - 1; i++) {
   elementData[i] = elementData[i + 1];
 }
 /* ... */
}

public E remove(int index) {
  /* ... */

  if (size - 1 - index >= 0)
    System.arraycopy(elementData, index + 1, elementData, index, size - 1 - index);

  /* ... */
}

---

The methods get and remove contain a code duplication:

public E get(int index) {
 if (index < 0 || index >= size) {
   throw new IndexOutOfBoundsException("Index: " + index + ", Size " + index);
  }
 return (E) elementData[index];
}

public Object remove(int index) {
 if (index < 0 || index >= size) {
   throw new IndexOutOfBoundsException("Index: " + index + ", Size " + index);
 }

 Object removedElement = elementData[index];

 /* ... */

 return removedElement;
}

It is possible to invoke get inside remove like:

public E remove(int index) {
  E elementToRemove = get(index);

  if (size - 1 - index >= 0)
    System.arraycopy(elementData, index + 1, elementData, index, size - 1 - index);

  size--;

  return elementToRemove;
}

Answer 2

Dangling Reference

If you add 10 elements into the array, and then you remove the last item, the array capacity will be 10, the array size will be 9, and the last element, self.elementData[9] will still point to the item that was removed. This means the item can never be garbage collected.

Fix: When you remove an element from the array, you should null the last element.

size--;
elementData[size] = null;  // Ensure no dangling references
return removedElement;

Answer 3

Employee

If you're not going to change the fields for Employee, then they should be final. As it stands, there doesn't seem to be anyway to access the values...

List interface

Your list implementation doesn't really make sense to me. I think part of that is because you've implemented your display method as part of the list. This really doesn't belong there, writing to the console has nothing to do with storing/retrieving elements from a collection. More than that, by putting the method within the class itself, you've deprived yourself of an opportunity to test out using your class in the real world.

Iterating through the items in a list is one of it's core functionalities. You should be able to trivially write this function outside of your class. At the moment this would be harder than necessary, because you don't expose the size property. So you essentially iterate until the get throws an exception. You have a very similar experience if you want to remove an item from the list (unless you happen to know the index because you've hard coded the elements). It can be done, but it feels quite messy.

ensureCapacity

I was expecting this to perform the 'is the collection big enough, if not resize it' check. It only performs the resizing, instead the check is performed in the add method. This seems wrong to me. I'd consider either renaming the method to indicate that it's actually growing the collection, or putting the checking into the method so that it's name more accurately reflects what it does.

Testing

Rather than writing a test harness that outputs to the console, consider writing actual unit tests. Most IDE's have built in JUnit integration and the process of writing tests to validate your collection really help you to understand how usable your API is from the outside.

The whole wheel

Do you really want to re-invent the whole wheel? A lot of the legwork for figuring out usable interfaces for collections has already been done. If you implement the Collection<E> interface, then it would mean your class both conforms to developer expectations and also allow you to make use of other built in features when using your collection, such as streaming.

Answer 4

The Custom implementation is good.

Improvement/Suggestions-

1. Integer Overflow is not handled for the size

   private static final int HUGE_CAPACITY = Integer.MAX_VALUE - 3;
   
   private void ensureCapacity() {
     // Here newIncreasedCapacity can be negative value
     int newIncreasedCapacity = elementData.length > 0 ? elementData.length * 2 : INITIAL_CAPACITY;
     // Handles the capacity never goes out of bounds
     if(newIncreasedCapacity < 0) {
         newIncreasedCapacity = HUGE_CAPACITY;
   
         // To handle overflows with the index
         if(size == HUGE_CAPACITY) {
            // throw the exception - or replace the last element
         }
     }
     // Copy the elements
     elementData = Arrays.copyOf(elementData, newIncreasedCapacity);
   }
   

2. Duplicate code for check range in get/remove function

   private boolean checkCapacity() {
       if (index < 0 || index >= size) {
             throw new IndexOutOfBoundsException("Index: " + index + ", Size " + 
            index);
   
       }
   }
   

3. Even if no element is inserted, a first initialization will hold memory

   private static final Object[] DEFAULT_EMPTY_ELEMENT_STORE = {};
   // New data store initialized with EMPTY store i.e. DEFAULT_EMPTY_ELEMENT_STORE
   public SimpleArrayList() {
       super();
       elementData = DEFAULT_EMPTY_ELEMENT_STORE;
   }
   

4. Optimized remove method

   for (int i = index; i < size - 1; i++) {
           elementData[i] = elementData[i + 1];
   }
   size--;   //reduce size of ArrayListCustom after removal of element.
   

   to be replaced with

   int copyLength = size - index - 1;
   if (copyLength > 0) {
       System.arraycopy(elementData, index + 1, elementData, index, copyLength);
   }
   elementData[--size] = null;
   

For more details and ideas, you may also refer to SimpleArrayList.