`数组`

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

线性表 线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

image.png

非线性表 区分于线性表，数据不是排成一条线，有结构不固定。不是简单的前后关系。比如二叉树、堆、图等。

image.png

连续内存空间和相同类型
这样一来，就可以做到对数组的随机访问，在查找数据的效率上就特别高,时间复杂度为O(1)。当然有利有弊，比如在删除和新增数据的时候会有数据的搬移操作。

比如数据删除：

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

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

2. 数组和容器类数组

数组： int [] x = new int [] {1,2,3,4};
容器数组：List<Integer> list = Arrays.asList(1,2,3,4);

数组操作基本数据类型，容器数组操作的是包装数据类型。而且容器类数组支持动态扩容，
扩容的源码,每次加上原来容积的1.5倍：

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

假如我们有这样的一个问题，创建一个数组大小为300的数组，下面的哪个更高效：

List<Integer> listOne = new ArrayList<>();
List<Integer> lisTwo =new ArrayList<>(300);
for (int i = 0; i < 300; ++i) { 
listOne.add(i);
lisTwo.add(i);
}

当然平时开发中，直接用容器数组就足够了。Autoboxing、Unboxing的性能开销在数据小完全可以忽略的。

3. 回到刚才的问题，为什么很多数组都从0开始编号

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。
如果从0开始编号
a[k]_address = base_address + k * type_size
如果从1开始编号
a[k]_address = base_address + (k-1)*type_size

数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。c语言的处理方式也是这样，java沿用过来。

记录成长，砥砺前行。

最后编辑于：2019.12.22 11:35:05