Array

Array

Array is a linear table data structure. It uses a group of contiguous memory space to store a group of data of the same type. Find elements fast: through the index, you can quickly access the element at the specified location

Linear table & non-linear representation

In a non-linear table, the data is not a simple context.

time complexity

The array supports random access, and the time complexity of random access according to the subscript is O(1)

Insert operation

The time complexity is O(n), assuming the length of the array is n, now, if we need to insert a piece of data into the kth position in the array. In order to vacate the k-th position for the new data, we need to move all the elements of the k-nth part backward one place sequentially.

 public void add(int index, E e) {
        if (size == data.length)
            throw new IllegalArgumentException("array list is full");
        if (index <0 || index> size) {
            throw new IllegalArgumentException("add error");
        }
        for (int i = size-1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }

Delete operation

The time complexity is O(n),

Dynamic array

public void resize(int newCapcity){
        E[] newData =(E[])new Object[newCapcity];
        for(int i = 0;i<size;i++){
            newData[i] = data[i];
        }
        data = newData;
    }
Reference: https://cloud.tencent.com/developer/article/1437148 Array-Cloud + Community-Tencent Cloud