数组的特性、基本操作和应用场景

淩亂°似流年 2021-12-03 12:01 335阅读 0赞

### 数组的特性、基本操作 ###

*  数组
 *   *  数组是什么
     *  数组中的操作
     *  容器和数组

# 数组 #

> 数组是一种最基础的数据结构，本文整理自极客时间相关课程，主要目的是把一些给我印象深刻的点记录下来。

## 数组是什么 ##

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

*  线性表
 *  连续内存空间
 *  相同类型

**线性表**  
形象地来看，线性表就是数据排成像一条线一样的结构，并且最多只有前和后两个方向。数组、链表队列、栈等都是线性表结构。  
与其对立的概念是非线性表，如二叉树、堆、图等。在非线性表中，数据之间并不是简单的前后关系。

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

*  因为这两个限制，数组具有了 “随机访问” 特性。
 *  在数组中删除、插入数据，需要做大量数据搬移工作。

**如何根据下标随机访问数组元素？**  
一维数组：a\[i\] = base\_address + i \* data\_type\_size  
其中data\_type\_size指数据中每个元素的大小。例如：

a[0] = base_address + 0 * data_type_size
    a[1] = base_address + 1 * data_type_size
    a[2] = base_address + 2 * data_type_size
    a[n] = base_address + n * data_type_size

上面对应的计算方式是数组下标从0开始的情况。  
在大多数编程语言中，数组都是从0开始编号的。设想一下如果数组下标是从1开始呢？

a[1] = base_address + （1-1） * data_type_size
    a[2] = base_address + （2-1） * data_type_size
    a[3] = base_address + （3-1） * data_type_size
    a[n] = base_address + （n-1） * data_type_size

对比可以发现，如果数组从1开始编号：则每次随机访问元素都**多了一次减法操作**，表达式相比之下比较复杂。

> 通过下标访问数组是非常基础的操作，从效率优化的角度考虑，为了减少一次减法操作，数据选择了从0开始编号，而不是从1开始；从历史角度考虑，C设计者用0开始计数数组下标，其他语言就沿袭下来了这个设计。

## 数组中的操作 ##

**数组的查找时间复杂度**  
在和链表最对比时往往会说 “链表插入删除O(1)查找O(n)，数组插入删除O(n)查找O(1)”。  
这种说法是有问题的，确切的说，数组是**随机访问**（即通过下标访问指定位置元素）的**时间复杂度是O(1)**，而在数组中查找指定元素（比如说找数组中2这个元素在哪里）的时间复杂度一般来说并不是O(1)。

*  对于**排序好**的数组来说，可以使用二分查找，其查找复杂度是 **O(log n)**
 *  对于**无序**数组来说，还是得遍历数组，其查找复杂度是 **O(n)**

**数组的插入操作**  
在数组中末尾插入元素，时间复杂度是O(n)。  
在数组中**指定位置**插入元素，如果需要**保持原数组元素的顺序**，则时间复杂度是**O(n)**；如果**不需要保持原数组元素的顺序**，可以把该指定位置元素放到数组末尾，将待插入元素放进指定位置，这样时间复杂度是**O(1)**。（快排中有用到这个思想）

**数组的删除操作**  
在数组的删除操作中，为了内存的连续性，需要做很多数据搬移工作。一般来说，删除数组末尾元素，最好时间复杂度O(1)；删除数组开头元素，最坏时间复杂度O(n)。

为了改善删除操作的效率，我们可以将多次删除操作集中在一起执行：

*  每次删除操作并不真正搬移数据，只记录数据已经被删除。
 *  当数组中已经没有更多空间存储数据时，再触发一次真正的删除操作。
 *  这样就大大减少了删除操作导致的数据搬移。
 *  JVM的垃圾回收算法中的标记-清除算法就是这么做的。

## 容器和数组 ##

Java中我们惯用ArrayList，其底层是一个可以动态增长的数组。ArrayList和数组相比，优势在于：

*  将很多数组操作的细节封装起来
 *  支持动态扩容

在使用数组时，我们必须预先指定数组大小。并且如果要加入的元素数量大于指定的数组大小，还要申请一个更大的空间，将原来的数据复制进去。而使用ArrayList则不用这样，因为其内部有自动扩容机制。

但是**扩容操作涉及内存申请和数据搬移**，其实是很**耗时**的。容器将这些操作包装起来，为程序员提供了一个简单的接口，虽然使得编程更加容易，但容易使人忽略其内部实现，而不同的使用方法会有不同的效率。所以在使用容器的时候，我们要稍微关注一下其内部实现，尤其关注一些比较耗时的操作。看看有没有比较好的使用方式，可以减少这些耗时操作。比如说在ArrayList中虽然不用指定大小，但预先知道需要向其中放大量数据时，建议在创建ArrayList时指定大小。这样可以减少扩容次数，而扩容是非常耗时的。

数组和容器相比，使用数组更适合的场景：

*  ArrayList等容器类都是无法存储基本类型的，对于int、long等基本类型只能存储器对应包装类，而在自动装箱和自动拆箱中会带来性能消耗。所以在关注性能的场景下，需要存储基本类型时，使用数组。
 *  如果数据大小事先知道，并且对数据操作简单，可以直接使用数组。
 *  多维数组用数组表示更直观，用容器不够直观。
 *  业务开发用容器，框架开发追求性能用数组。