数据结构与算法-数组

说起数组，我们都很熟悉，几乎所有的编程语言中都有数组这种数据类型，不仅如此，数组也是一种最基础的数据结构。

尽管数组看起来非常基础、简单，但是我们估计很少去深入的研究过它的原理。

回想一下主流的几种编程语言C、C++、Java中我们是如何使用数组的。在这些语言中，数组下标都是从0开始的，我们可能不禁要问：为什么数组下标是从0开始的？

让我们带着这个问题一探究竟

如何实现随机访问？

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

先来解释下线性表。线性表指的是数据像线性排列的一种数据结构，每个线性表上数据最多只有前后两个方向。数组、链表、栈、队列都是线性表结构。 与线性表对立的概念叫非线性表，是指数据之间的关系非简单的线性，而较为复杂的一对多，或多对多。非线性的数据结构有树、图、堆等。 再解释连续的内存空间和相同类型的数据。这个特性限定了数组的操作，使得数组的插入和删除操作变的很低效，因为要保持数据在内存中的连续性，在插入和删除的时候就不得不花费大量的时间去移动数据。但正是因为这个特性，才让数组的随机访问变的可能。

那么数组具体是怎么通过下标进行随机访问的呢？

下面用一个大小为10的数组a[10]举例说明下。 如上图假设数组a被分配的内存地址为1000-1039。内存首地址为1000，那么访问第一个元素a[0]就是要计算a[0]所在的地址，a[0]相对于首地址的地址偏移量为0*data_type_size(数据类型大小)。所以a[0]的地址为 a[0]_address = 首地址+偏移量 = 1000+0=1000。其他依次类推，由此我们可以得到一个寻址公式：

a[i]_address = base_address+i*data_type_size

base_address为首地址，data_type_size为数据类型大小，如果数据为int类型则data_type_size = 4 byte

特别注意下,数组根据下标随机访问的时间复杂度为O(1),但并不是数组的整体所有查找效率都为O(1)。

现在我们似乎能够回答数组下标从0开始的问题了，因为计算地址的比较方便，如果从1开始的话那么地址计算公式就变成了： a[i]_address = base_address+（i-1）*data_type_size 其实这个也没什么大问题，主要还是因为历史问题，最初的C语言就是这么规定的,后来的语言借鉴了C,于是这个习惯被保留到了其他语言中。实际上，数组下标完全可以从1开始，甚至在python中可以从-1开始。

低效的 “插入”、“删除”

刚开始我们说了数组因为要保持数据存储的连续性，导致插入和删除操作变的低效，那具体是怎么变得低效呢？又该如何改进？ 插入操作 假设数组长度为n,现在要在k位置插入一个新的数据，估算下大概的时间复杂度。 如果是在数组末尾插入，则不需要挪动数据，时间复杂度为O(1); 如果是在中间插入，则需要将k~n的位置上数据全部向后挪动一个位置。最坏时间复杂度为O(n)。平均时间复杂度为（1+2+3+…n）/n=O(n)。

以上考虑到数组元素高度有序，不能打乱顺序的情况，但是如果说数组元素之间没有严格的先后顺序呢？这个时候我们就不需要将k~n的数据都向后移动一位了，我们只需要将k位置的数据搬到数组的最后，然后将要插入的数据放到k位置即可，这样时间复杂度仅为O(1)。例如下图：

删除操作 删除操作和插入类似，如过删除数组末尾，最好时间复杂度为O(1)。如果删除数组第一个元素，最坏时间复杂度为O（n），平均时间复杂度也为O（n）。

类似的，如果不需要考虑数组元素的顺序性，则可以考虑改进删除策略：数组未满时，我们将要删除的元素标记一下，等数组满的时候，给打上标记的数组元素一起删除。这点类似于JVM中的标记清除垃圾回收算法。

如下图例子，假设有个长度为10的数组，现在依次删除了前三个数据1、3、5，我们先不做真正的删除操作，二是给删除了的数据标记一下，待到新插入数据时，发现数组满了，这个时候再将1、3、5真正的删除。

数组越界问题

分析一段C语言的代码：

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

这段代码将会无限循环输出 “hello world”,因为数组下标最大为2，而不是3，当i=3时实际上访问的地址已经不属于数组arr的范围了，a[3]所在的地址正好是i的地址,所以a[3]=i=0;

在C语言中，数组越界不会被编译器发现，因此越界后的数组就会随机访问到内存中的某个地址，会对程序结果造成不可预估的错误，而且极其难以排查。所以在C语言中使用数组下标时要格外注意数组下标越界的情况。需要慎之又慎。

而在java中，就不会存在这种问题了，因为java本身就会检查数组是否越界，一旦越界了，jvm就会抛出java.lang.ArrayIndexOutOfBoundsException。从这点来讲，Java比C更容易编写健壮的代码。

容器能否完全替代数组？

在Java中，ArrayList这个容器类可谓是最常用的集合类之一了，那么ArrayList与数组相比有哪些优势呢？

一反面ArrayList封装了数组实现的诸多细节，对外提供简单的接口，方便使用；另一方面ArrayList支持动态扩容。

实际上ArrayList的动态扩容原理是创建了一个更大的数组（1.5倍），将原数组的数据全部copy过来。此过程涉及内存申请和数据迁移，所以会消耗一定时间。如果我们事先能够确定数组大小，则可以指定ArrayList的大小以提升效率。

ArrayList<User> users = new ArrayList(10000);
for (int i = 0; i < 10000; ++i) {
  users.add(xxx);
}

不过，即使已经有了如此方便的容器，我们有时候仍然需要使用数组： 1、ArrayList无法存储基本数据类型，因此当需要基本数据类型的数组时选用数组。另外使用基本类型的包装类型会有一定的性能损耗，要是对性能有极致追求可以选用数组。 2、如果数据规模大小已知，且用不到容器的诸多操作方法，则直接使用数组。 3、当需要表示多维数组时，使用数组更为直观。比如 Object[][] array；而用容器的话则需要这样定义：ArrayList array。

总之，在进行业务开发时，就选用容器优先，省时省力，不会对性能造成太大的影响。如果是进行一些底层的开发，比如网络框架，操作系统等，需要把性能优化做到极致的工作，则选用数组优先。

以上内容来自极客时间。仅供个人学习用，如有侵权，后果自负。