preface

Tip: Here you can add the general contents to be recorded in this article:
For example, with the continuous development of artificial intelligence, machine learning technology is becoming more and more important. Many people have started learning machine learning. This paper introduces the basic content of machine learning.

Tip: the following is the main content of this article. The following cases can be used for reference

1, Construction of ArrayList

2, ArrayList common operations

Three, simulation implementation

1. Create class and its construction method

public class MyArrayList1<E> {
    private Object[] array;
    private int size;

    //Construction method: nonparametric construction
    public MyArrayList1(){

    }
    public int size(){
        return  size;
    }
}

Since it is possible to store various types of elements in the list, generic < E > is used here.

2. Specify the initial capacity of the sequence table

public MyArrayList1(int initCapacity){
    if(initCapacity>=0){
         array=new Object[initCapacity];
    }else{
         throw new IllegalArgumentException("The initial capacity is negative");
    }
}

The initial capacity must be a positive integer, or an exception will be thrown.

3. Judge whether the list is empty

public boolean isEmpty(){
        return size==0;
    }

4. Tail plug

    public boolean add(E e){
        ensureCapacity(size+1);
        array[size++]=e;
        return true;
    }
    //Capacity expansion
    private static final int MAX_ARRAY_SIZE=Integer.MAX_VALUE-8;
    private void ensureCapacity(int initCapacity){
        int oldCapacity= array.length;
        //It is preliminarily estimated that the capacity will be expanded by 1.5 times
        int newCapacity=oldCapacity+(oldCapacity>>1);
        //If it is less than the initial capacity after capacity expansion, it will still be based on the initial capacity
        if(newCapacity<initCapacity){
            newCapacity=initCapacity;
        }
        //If the maximum capacity is exceeded after capacity expansion, the maximum capacity will be used
        if(newCapacity>MAX_ARRAY_SIZE){
            newCapacity=MAX_ARRAY_SIZE;
        }
        array= Arrays.copyOf(array,newCapacity);
    }

Steps:
1. Capacity expansion
2. Put the element in the size position
3. Set size+1
Refinement and expansion:
1. First set the maximum value of the list:
The shape and structure of array objects, such as arrays of int values, are similar to standard Java objects. The main difference is that the array object has an additional metadata to represent the size of the array. So the maximum value here is the integer maximum value - 8
2. It is preliminarily estimated that the capacity will be expanded by 1.5 times. If the expanded capacity is less than the initial capacity, it will still be expanded by the initial capacity; If the maximum capacity is exceeded after capacity expansion, the maximum capacity will be used.
3. Use copyOf for capacity expansion

5. Insert e into the index position

    public void add(int index,E e){
        rangeCheckForAdd(index);
        ensureCapacity(size+1);

        //Move the index and its subsequent elements back one position
        for(int i=size-1;i>=index;i--){
            array[i+1]=array[i];
        }
        array[index]=e;
        size++;
    }
    //Detect whether the subscript is abnormal during insertion
    private void rangeCheckForAdd(int index){
        if(index>size){
            throw new IllegalArgumentException("add Subscript out of bounds");
        }
    }

Steps:
1. Check whether the subscript is abnormal during insertion. If yes, an exception will be thrown
2. Capacity expansion
3. Move the index and its subsequent elements back to a unified position (be sure to move from back to front here. If you move from front to back, all the moved elements will be the same element)

6. Delete the element at the index position

    public E remove(int index){
        rangeCheck(index);

        E e=(E)array[index];
        //Move the elements after index forward one position
        for(int i=index+1;i<size;i++){
            array[i-1]=array[i];
        }
        size--;
        return e;
    }
    //Check whether the subscript is abnormal
    private void rangeCheck(int index){
        if(index<0||index>=size){
            throw new IndexOutOfBoundsException("Subscript out of bounds");
        }
    }

Steps:
1. Check whether the subscript is abnormal. If yes, an exception will be thrown
2. Strongly convert the element with index index to E type for subsequent return
3. Move the elements after the index forward (from front to back)

7. Delete the first o encountered

    public boolean remove(Object o){
        int index=indexOf(o);
        if(index==-1){
            return false;
        }
        remove(index);
        return true;
    }
    //Gets o the location where the first occurrence occurs
    private int indexOf(Object o){
        if(o==null){
            for(int i=0;i<size;i++){
                if(array[i]==null){
                    return i;
                }
            }
        }else{
            for(int i=0;i<size;i++){
                if(array[i]==o){
                    return i;
                }
            }
        }
        return -1;
    }

Steps:
1. Get the location where o appears for the first time and dispose of null separately. If there is no o, return - 1 and return false
2. If any, call remove(). Return true

8. Get the element at the index position

    public E get(int index){
        rangeCheck(index);
        E e=(E)array[index];
        return e;
    }

Steps:
1. Check whether the subscript is abnormal
2. Forcibly convert the subscript index position element to type E and return

9. Set the element at the index position to e

    public E set(int index,E e){
        rangeCheck(index);
        array[index]=e;
        return e;
    }

Steps:
1. Check whether the subscript is abnormal
2. Set the index location element to e
3. Return to e

10. Empty

    public void clear(){
        for(int i=0;i<size;i++){
            array[i]=null;
        }
        size=0;
    }

Set each element to null, size=0

11. Judge whether o is in the linear table

    public boolean contains(Object o){
        return indexOf(o)>0;
    }

In fact, it is to judge whether the subscript of O is greater than o, because - 1 is returned when indexOf() is not present

12. Intercepting part list

    MyArrayList1<E> subList(int fromIndex,int toIndex){
        if(toIndex-fromIndex<0){
            throw new IllegalArgumentException("invalid parameter");
        }
        MyArrayList1<E> list=new MyArrayList1<>(toIndex-fromIndex);
        for(int i=fromIndex;i<toIndex;i++){
            list.add((E)array[i]);
        }
        return list;
    }

Steps:
1. Judge the validity of fromIndex and toIndex parameters
2. Create a new list to save the intercepted list

13. Rewrite toString

    @Override
    public String toString(){
        String s="[";
        if(size>0){
            for(int i=0;i<size-1;i++){
                s+=array[i];
                s+=",";
            }
            s+=array[size-1];
        }
        s+="]";
        return s;
    }

14. Main method

    public static void main(String[] args) {
        MyArrayList1<Integer> list=new MyArrayList1<>(3);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println(list);
        System.out.println("Length:"+list.size());

        list.add(0,0);
        System.out.println(list);
        if(list.contains(5)){
            list.add(5);
        }

        list.add(0);
        System.out.println(list);
        System.out.println(list.indexOf(0));
        System.out.println(list.lastIndexOf(0));

        list.remove(0);
        System.out.println(list);

        list.clear();
        System.out.println(list);
    }
}

4, Output results