数据结构-数组

一、定义

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

1、线性表

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

is-line.jpg
非线性表
非线性表中数据之间并不是简单的前后关系。
二叉树、堆、图等。
not-line.jpg

2、连续的内存空间和相同类型的数据

这两个限制有利有弊。
利：查询高效。支持随机访问，根据下标随机访问的时间复杂度为O(1)
弊：删除、插入低效。为了保证数组的连续性，就要做大量的数据搬移工作
随机访问的实现
拿一个长度为10的int类型的数组int[] a = new int[10]来举例。在图示中计算机给数组a[10]，分配了一块连续内存空间1000~1039，其中，内存块的首地址为base_address = 1000。

我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

其中data_type_size表示数组中每个元素的大小。这个例子中数组存储的是ini类型数据，所以data_type_size就为4个字节。

arr-address.jpg

二、操作

1、查找

时间复杂度是O(logn)

for (int i = 0; i < n; i++){
    a[i]_address = base_address + i * data_type_size
    if (a[i]_address == m){
        return i;
    }
}

2、插入

假设数组的长度为n，现在，如果我们需要将一个数据插入到数组中的第k个位置。为了把第k个位置腾出来，给新来的数据，需要将第k~n这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢？

如果在数组末尾插入元素，那就不需要移动数据了，这时的时间复杂度为O(1)。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度为O(n)。因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为(1+2+3+4+...n)/n=O(n)。

如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移k之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当做一个存储数据的集合。在这种情况下，如果要将某个数组插入到第k个位置，为了避免大规模的数据搬移，还有一个简单的办法就是，直接将第k位的数据搬移到数组元素的最后，把新的元素直接放入第k个位置。这时，时间复杂度会降为O(1)

arr-insert.jpg

3、删除

跟插入类似，如果我们要删除第k个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。

如果删除数组末尾的数据，则最好情况时间复杂度为O(1);如果删除开头的数据，则最坏情况时间复杂度为O(n);平均情况时间复杂度为O(n)。

实际上，在某些特殊场景下，我们并不一定非要追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？

为了避免d,e,f,g,h这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。这就是JVM标记清除垃圾回收算法的核心思想。

arr-delete.jpg

突然想到了垃圾桶。
生活中，我们扔进屋里垃圾桶的垃圾，
并没有消失，只是被 ''标记'' 成了垃圾，
只有垃圾桶塞满时，才会清理垃圾桶。
再次存放垃圾。-- 夜下凝月

三、数组下标为什么从0开始

从数组存储的内存模型上来看，“下标”最确切的定义是“偏移（offset）”。前面也讲到如果用a来表示数组的首地址，a[0]就是偏移为0的位置，也就是首地址，a[k]就表示偏移k个type_size的位置，所以计算a[k]的内存地址只需要用这个公式：

a[k]_address = base_address + k * type_size

但是，如果数组从1开始计数，那我们计算数组元素a[k]的内存地址就会变为：

a[k]_address = base_address + (k-1)*type_size

对比俩公式，可以发现从1开始编号，每次随机访问数组元素都多了一次减法运算，对于cpu来说就是多了一次减法指令。

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

网站导航

网站导航