Array

In this section, we will implement naive simple ArrayList here which utilised java default array.

We first define the array, initialisation and size function.

class SSEArrayList {
    private int[] arr = null;

    public SSEArrayList(){
        arr = new int[0]; //create array with 0 size
    }

    public int size(){
        return arr.length;
    }
}

Next we will define the add function.

    //this is an O(n) operation
    public void add(int toBeAdded){
      int[] tempArr = arr.clone();
      arr = new int[this.size()+1];

      //copy actually is 0(n) operation
      System.arraycopy(tempArr, 0, arr, 0, tempArr.length);

      arr[this.size()-1] = toBeAdded;
    }

Whenever we add something, we will expand the array size by 1 and copy the previous array across, and assign the last element of the array to be variable toBeAdded.
This operation takes O(n) time because the copying.

The next simple functions to implement is print and get.

    //this is an O(n) operation
    public void print(){
        for (int i=0; i<arr.length; i++){
            System.out.print(arr[i] + ",");
        }
        System.out.println("");
    }

    //this is an O(1) operation
    public int get(int index){
        return arr[index];
    }

print is O(n) operation because it loops through of the array and get is O(1) operation because it just use index to access the variable.

The next function will be "add" function at specified index.

     //this is an O(n) operation
    public void add(int idx, int toBeAdded) throws Exception {
        if (idx >= this.size()){
            throw new Exception("index bigger or equal to size");
        }else {
            int[] tempArr = arr.clone();
            arr = new int[this.size() + 1];

            //shift array actually is 0(n) operation
            for (int i=0; i< tempArr.length; i++){
                if (i < idx){
                    arr[i] = tempArr[i];
                }else if (i>= idx){
                    arr[i+1] = tempArr[i];
                }
            }

            arr[idx] = toBeAdded;
        }
    }

It is actually an O(n) operation because we need to shift the elements, after that we add at specified index. We actually expand the size of the array by 1.

The next function will be "remove" function at specified index.

    public void remove(int idx) throws Exception {
        if (idx >= this.size()){
            throw new Exception("index bigger or equal to size");
        }else {
            int[] tempArr = arr.clone();
            arr = new int[this.size() - 1];

            //shift array actually is 0(n) operation
            for (int i=0; i< tempArr.length; i++){
                if (i < idx){
                    arr[i] = tempArr[i];
                }else if (i> idx){
                    arr[i-1] = tempArr[i];
                }
            }
        }
    }

It is actually an O(n) operation because after we actually shift the elements and forget the one at the specified index. We actually shrink the size of the array by 1.

Note: This implementation is naive and simple, haven't been thoroughly tested, please do not use in production, it is meant for simple explanation only. And also there can be better implementation that takes less time complexity.

You can try to run the code here:
Run on jdoodle