5
\$\begingroup\$

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();

    }

}
\$\endgroup\$
  • 5
    \$\begingroup\$ You didn't post your original, working code. I know this since the "constructor" name is customArrayList with a lowercase c. The constructor always has the same name as the class. The C must be uppercase, otherwise the code does not compile. \$\endgroup\$ – Roland Illig Feb 7 at 6:50
6
\$\begingroup\$

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;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Calling get from remove creates a possibility where the get method is overridden by a subclass and the overriding implementation breaks the remove method. Thus the get method should be final or the shared functionality should be refactored into a private method. \$\endgroup\$ – TorbenPutkonen Feb 8 at 7:33
5
\$\begingroup\$

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;
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Do you really want to re-invent the whole wheel? Starting with an abstract class and wrapping up using extends java.util.AbstractList lets you neglect whatever parts you choose. \$\endgroup\$ – greybeard Feb 8 at 22:10
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Welcome to CodeReview@SE. A block quote (markdown: > quoted contents commonly is used for longer quoted parts (attributions welcome). You can often see observations and advice about a single issue with the code from the question as one item in a list - markdown: ` - Integer Overflow…`. \$\endgroup\$ – greybeard Feb 7 at 6:28
  • \$\begingroup\$ thanks I have updated the format as suggested \$\endgroup\$ – Jatish Feb 7 at 6:36
  • \$\begingroup\$ @greybeard nice catch, I have fixed it. \$\endgroup\$ – Jatish Feb 10 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.