Our array list implementation will support below operations:

size – returns size of the arraylist

isEmpty – Returns whether the list is empty.

get – Returns (but does not remove) the element at index i.

set – Replaces the element at index i with e, and returns the replaced element.

add – Inserts element e to be at index i, shifting all subsequent elements later.

remove – Removes and returns the element at index i, shifting subsequent elements earlier.

Implementation

As the name suggest we will implement arraylist using array. For this, first we will create an interface which will give us the functionalities to be implemented for creating list.

public interface List< E> {
 
    int size( );
 
    /** Returns whether the list is empty. */
    boolean isEmpty( );
 
    /** Returns (but does not remove) the element at index i. */
    E get(int i) throws IndexOutOfBoundsException;
 
    /** Replaces the element at index i with e, and returns the replaced element. */
    E set(int i, E e) throws IndexOutOfBoundsException;
 
    /** Inserts element e to be at index i, shifting all subsequent elements later. */
    void add(int i, E e) throws IndexOutOfBoundsException;
 
    /** Removes/returns the element at index i, shifting subsequent elements earlier. */
    E remove(int i) throws IndexOutOfBoundsException;
}

Array Based Implementation

In an array-based implementation we maintain the following fields:

• an array of a default capacity (In our case we have kept it 20),
• A variable size which will refers to the current size of the array list.

The array based implementation is shown in below code snippet with purpose and functioning of the each method. Each operation is also having the time complexity associated with them for this implementation.

public class ArrayList < E> implements List< E> {
 
    public static final int CAPACITY = 20;
    E[] data;
    private int size=0;
     
    public ArrayList(){
        this(CAPACITY);
    }
     
    public ArrayList(int capacity) {
        data = (E[]) new Object[capacity];
    }
 
  /**
    * This runs on O(1)
    *
    */
     
    @Override
    public int size() {
        return size;
    }
 
  /**
    * This runs on O(1)
    *
    */
     
    @Override
    public boolean isEmpty() {
        return size==0;
    }
 
   /**
     * While getting an element at index i, we will check for boundary condition first.
     * If it passes then we will return element at given array index.
     * This runs on O(1)
     *
     */
      
    @Override
    public E get(int i) throws IndexOutOfBoundsException {
        if(i < 0 && i >= size+1)
            throw new IndexOutOfBoundsException("Illigal index"+i);
        return data[i];
    }
 
   /**
     * This runs on O(1)
     * Setting an element at index i will also first check for boundary condition.
     * After that we will set element value at index i and return the old value
     * of the element at index i
     */
      
    @Override
    public E set(int i, E e) throws IndexOutOfBoundsException {
        if(i < 0 && i >= size+1)
            throw new IndexOutOfBoundsException("Illigal index"+i);
        E temp = data[i];
        data[i] = e;
        return temp;
    }
 
   /**
     * This runs on O(n)
     * For adding an element, we will check for boundary conditions once it is
     * passed we will check for current capacity.
     *
     * If array is full, we call the resize method and then add the new element
     * at given index
     *
     * To add element in natural order, we will pass the i as current size of
     * the arraylist.
     *
     * To add element in between, we will first shift all the elements to make
     * room for new element then we set it at given index
     *
     */
     
    @Override
    public void add(int i, E e) throws IndexOutOfBoundsException {
         
        if(i < 0 && i >= size+1)
            throw new IndexOutOfBoundsException("Illigal index"+i);
         
        if(size==data.length)
            resize(data.length *2);
         
        for(int k=size-1;k>=i;k--){
            data[k+1] = data[k];
        }
        data[i] = e;
        size++;
    }
     
   /**
     * This runs on O(n)
     * First check for bounday condition. shift all the elements to left
     * which are after the element to be removed. Return the removed element
     *
     */
 
    @Override
    public E remove(int i) throws IndexOutOfBoundsException {
         
        if(i < 0 && i >= size+1)
            throw new IndexOutOfBoundsException("Illigal index"+i);
         
        E temp = data[i];
         
        for(int k=i;k<=size-1;k++){
            data[k]=data[k+1];
        }
        data[size-1] = null;
        size--;
        return temp;
    }
     
   /**
     * This method will resize the underlying array when the array gets full.
     * We have used the native array copy method to copy all the elements
     * to new array.
     *
     */
      
    protected void resize(int capacity)
    {
        E[] temp = (E[]) new Object[capacity];
        System.arraycopy(data, 0, temp, 0,data.length);
        data = temp;
    }  
}

Download Complete Java Program »

Apart from this, we can also have other methods which our implementation support.Some of these operations are, addAll(Adds all elements of other list) We can also think about shrinking the arraylist space when more than half of the array list is empty though it will have little trade off between space and time complexity.

You can always go to Oracle Docs and check for other operation supported by arraylist and try to implement it yourself.

Though arrrayList have its advantages over arrays, it has some disadvantages as well. When there is a requirements of frequent insert/delete of the intermediate elements, at that time arraylist will not be that efficient as every time elements needs to shifted to right/left after each insertion and deletion.