数组

线性表示最常用而且最为简单的一种数据结构，一个线性表示 n 个数据元素的有限序列，有以下特点：

 

存在唯一的第一个的数据元素

存在唯一被称为最后一个的数据元素

除了第一个以外，集合中每一个元素均有一个前驱

除了最后一个元素之外，集合中的每一个数据元素都有一个后继元素

线性表包括下面几种：

 

数组：查询 / 更新快，查找/删除慢

链表

队列

栈

int[] nums = new int[100];
int[] nums = {1,2,3,4,5};

Object[] Objects = new Object[100];

int nums[100];

数组是一种线性的结构，一般在底层是连续的空间，存储相同类型的数据，由于连续紧凑结构以及天然索引支持，查询数据效率高:

 

假设我们知道数组a的第 1 个值是 地址是  296,里面的数据类型占 2 个 单位，那么我们如果期望得到第 5 个： 296+（5-1）*2 = 304,O(1)的时间复杂度就可以获取到。

 

更新的本质也是查找，先查找到该元素，就可以动手更新了：

但是如果期望插入数据的话，需要移动后面的数据，比如下面的数组，插入元素6，最差的是移动所有的元素，时间复杂度为O(n)

而删除元素则需要把后面的数据移动到前面，最差的时间复杂度同样为O(n):

Java代码实现数组的增删改查：

package datastruction;

import java.util.Arrays;

public class MyArray {
    private int[] data;

    private int elementCount;

    private int length;

    public MyArray(int max) {
        length = max;
        data = new int[max];
        elementCount = 0;
    }

    public void add(int value) {
        if (elementCount == length) {
            length = 2 * length;
            data = Arrays.copyOf(data, length);
        }
        data[elementCount] = value;
        elementCount++;
    }

    public int find(int searchKey) {
        int i;
        for (i = 0; i < elementCount; i++) {
            if (data[i] == searchKey)
                break;
        }
        if (i == elementCount) {
            return -1;
        }
        return i;
    }

    public boolean delete(int value) {
        int i = find(value);
        if (i == -1) {
            return false;
        }
        for (int j = i; j < elementCount - 1; j++) {
            data[j] = data[j + 1];
        }
        elementCount--;
        return true;
    }

    public boolean update(int oldValue, int newValue) {
        int i = find(oldValue);
        if (i == -1) {
            return false;
        }
        data[i] = newValue;
        return true;
    }
}

// 测试类
public class Test {
    public static void main(String[] args) {
        MyArray myArray = new MyArray(2);
        myArray.add(1);
        myArray.add(2);
        myArray.add(3);
        myArray.delete(2);
        System.out.println(myArray);
    }
}