Array with generic class

import java.util.Arrays;

public class Array<E> {
    
    private E[] data;
    private int size;

    //  Pass in capacity Initialize the capacity of the array 
    public Array(int capacity) {
    
        //  Generic classes cannot be instantiated directly , adopt Object Cast 
        data =  (E[])new Object[capacity];
        size = 0;
    }

    //  No arguments structure , The initial capacity of the default array is 10
    public Array() {
    
        this(10);
    }

    //  Returns the number of elements in the array 
    public int getSize() {
    
        return size;
    }

    //  Get the capacity of the array 
    public int getCapacity() {
    
        return data.length;
    }

    //  Determine whether the array is empty 
    public boolean isEmpty() {
    
        return size == 0;
    }

    //  Add an element after all elements 
    public void addLast(E e) {
    
        /** * if (size == data.length) { * throw new IllegalArgumentException("Array is full."); * } * data[size] = e; * size ++ ; */
        add(size, e);
    }
    //  Add an element before all elements 
    public void addFirst(E e) {
    
        add(0, e);
    }

    //  In the index Insert a new element at a location 
    public void add(int index, E e) {
    
        if (size == data.length) {
    
            throw new IllegalArgumentException("Array is full.");
        }

        if (index < 0 || index > size)
            throw new IllegalArgumentException("Require index >= 0 and index <= size");

        for (int i = size - 1; i >= index; i -- ) {
    
            data[i + 1] = data[i];
        }
        data[index] = e;
        size ++ ;
    }

    //  Query whether the array contains elements e
    public boolean contains(E e) {
    
        for (int i = 0; i < size; i ++ ) {
    
            if (data[i].equals(e))
                return true;
        }
        return false;
    }

    //  Find the elements in the array e The index , If it doesn't exist , Then return to -1
    public int find(E e) {
    
        for (int i = 0; i < size; i ++ ) {
    
            if (data[i].equals(e))
                return i;
        }
        return -1;
    }

    //  Delete the elements of the specified index , Return deleted elements 
    public E remove(int index) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");
        E res = data[index];
        for (int i = index + 1; i < size; i ++ ) {
    
            data[i - 1] = data[i];
        }
        size -- ;
        data[size] = null;
        return res;
    }

    //  Delete first element , Return deleted elements 
    public E removeFirst() {
    
        return remove(0);
    }

    //  Delete tail element , Return deleted elements 
    public E removeLast() {
    
        return remove(size - 1);
    }

    //  Remove elements e, If it does not exist , Then the meal returns -1
    public void removeElement(E e) {
    
        int index = find(e);
        if (index != -1)
            remove(index);
    }

    //  Get index location as index The elements of 
    public E get(int index) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");
        return data[index];
    }

    //  Change the index position to index The elements of 
    public void set(int index, E e) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");
        data[index] = e;
    }

    @Override
    public String toString() {
    
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append("[");
        for (int i = 0; i < size; i ++ ) {
    
            res.append(data[i]);
            if (i != size - 1)
                res.append(", ");
        }
        res.append("]");
        return res.toString();
    }
}

Test the effect

public class Student {
    
    private String name;
    private double score;

    public Student(String name, double score) {
    
        this.name = name;
        this.score = score;
    }

    public Student() {
    
    }

    @Override
    public String toString() {
    
        return "Student{" +
                "name='" + name + '\'' +
                ", score=" + score +
                '}';
    }

    public static void main(String[] args) {
    
        Array<Student> arr = new Array<>();
        arr.addLast(new Student(" Zhang San ", 33));
        arr.addLast(new Student(" Li Si ", 66));
        arr.addLast(new Student(" Wang Wu ", 88));
        System.out.println(arr);
    }
}

Dynamic array with automatic capacity expansion

The principle of capacity expansion ： When the number of array elements is greater than the capacity of the array , Create a larger array , Copy the original array to the newly created array , Point the reference of the array to the new array , Old arrays will be recycled by the garbage collector .

import java.util.Arrays;

public class Array<E> {
    
    private E[] data;
    private int size;

    //  Pass in capacity Initialize the capacity of the array 
    public Array(int capacity) {
    
        //  Generic classes cannot be instantiated directly , adopt Object Cast 
        data =  (E[])new Object[capacity];
        size = 0;
    }

    //  No arguments structure , The initial capacity of the default array is 10
    public Array() {
    
        this(10);
    }

    //  Returns the number of elements in the array 
    public int getSize() {
    
        return size;
    }

    //  Get the capacity of the array 
    public int getCapacity() {
    
        return data.length;
    }

    //  Determine whether the array is empty 
    public boolean isEmpty() {
    
        return size == 0;
    }

    //  Add an element after all elements 
    public void addLast(E e) {
    
        /** * if (size == data.length) { * throw new IllegalArgumentException("Array is full."); * } * data[size] = e; * size ++ ; */
        add(size, e);
    }

    //  Add an element before all elements 
    public void addFirst(E e) {
    
        add(0, e);
    }

    //  In the index Insert a new element at a location 
    public void add(int index, E e) {
    
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Require index >= 0 and index <= size");

        if (size == data.length) {
    
            //  Call the expansion function 
            resize(2 * data.length);
        }

        for (int i = size - 1; i >= index; i -- ) {
    
            data[i + 1] = data[i];
        }
        data[index] = e;
        size ++ ;
    }

    //  Expansion function 
    private void resize(int newCapacity) {
    
        E[] newData = (E[])new Object[newCapacity];
        for (int i = 0; i < size; i ++ )
            newData[i] = data[i];
        data = newData;
    }

    //  Query whether the array contains elements e
    public boolean contains(E e) {
    
        for (int i = 0; i < size; i ++ ) {
    
            if (data[i].equals(e))
                return true;
        }
        return false;
    }

    //  Find the elements in the array e The index , If it doesn't exist , Then return to -1
    public int find(E e) {
    
        for (int i = 0; i < size; i ++ ) {
    
            if (data[i].equals(e))
                return i;
        }
        return -1;
    }

    //  Delete the elements of the specified index , Return deleted elements 
    public E remove(int index) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");

        E res = data[index];
        for (int i = index + 1; i < size; i ++ ) {
    
            data[i - 1] = data[i];
        }
        size -- ;
        data[size] = null;
        //  When too much space is wasted in the array , Reduce capacity 
        if (size == data.length / 2)
            resize(data.length / 2);

        return res;
    }

    //  Delete first element , Return deleted elements 
    public E removeFirst() {
    
        return remove(0);
    }

    //  Delete tail element , Return deleted elements 
    public E removeLast() {
    
        return remove(size - 1);
    }

    //  Remove elements e, If it does not exist , Then the meal returns -1
    public void removeElement(E e) {
    
        int index = find(e);
        if (index != -1)
            remove(index);
    }

    //  Get index location as index The elements of 
    public E get(int index) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");
        return data[index];
    }

    //  Change the index position to index The elements of 
    public void set(int index, E e) {
    
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Index is illegal");
        data[index] = e;
    }

    @Override
    public String toString() {
    
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append("[");
        for (int i = 0; i < size; i ++ ) {
    
            res.append(data[i]);
            if (i != size - 1)
                res.append(", ");
        }
        res.append("]");
        return res.toString();
    }
}

Check automatic capacity expansion

Verify automatic volume reduction

Simple time complexity analysis **( Analyze according to the worst case )**

Sharing time complexity and preventing complexity fluctuation

Average complexity

The complexity oscillates

occasionally " lazy ", But it's more efficient ！

Improved code

if (size == data.length / 4 && data.length / 2 != 0)
   	resize(data.length / 2);