系列文章请查看 「数据结构&算法」必知必会系列：1. 开篇#计划路线

线性表

在介绍「数组」之前，我们先引入一个概念「线性表」。

顾名思义，线性表就是数据排成像线一样的结构。每个线性表上的数据最多只有「前」和「后」两个方向。

常见的线性表数据结构如下：

本篇，就来介绍一下「数组」这种最基础、最简单的数组结构，

数组

每种编程语言中，基本都有数组这种数据类型。不过，我们这讨论的「数组」是一种最基础的数据结构。

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据，并且不支持动态扩容。

package main

import "fmt"

func main() {
	arr := [3]int{1, 2, 3}
	a := &arr[0]
	b := &arr[1]
	c := &arr[2]
	fmt.Printf("%v\n%v\n%v\n", a, b, c)
}

上述 🌰 为 go 实现（https://play.golang.org/p/uffnTzWV_3p），无需了解语法，直接看打印如下：

打印内容为指针的内存地址，🌰 中 arr 满足了数组的特性：连续的内存空间和相同类型的数据

如果是 JS 或者 Python 等语言的开发者，可能会定义如 a = [1, "abc"] 的 ”数组“。

这里，我的理解是此”数组“非彼「数组」， a = [1, "abc"] 只是 JS 或者 Python 支持不同元素放入”数组“ （Python 中为列表）。

高效的「随机访问」

注意，数据结构中的「数组」限制了 连续的内存空间和相同类型的数据。

因此，才让数组有了一个堪称“杀手锏”的特性：「随机访问」。那从内存访问角度来看，是如何实现的呢？

上图表现了上述示例中数组的内存分配情况。

比较好理解的是，我们可根据寻址公式，计算出要「随机访问」元素的内存地址：

a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小。上例， go int 类型数据为8个字节(64 位)。

我们来分析一下上述公式的时间复杂度 => O(1)

所以，数组支持「随机访问」，根据下标随机访问的时间复杂度为 O(1)。

数组是适合查找操作，但是查找的时间复杂度并不为 O(1)。即便是排好序的数组，你用二分查找，时间复杂度也是 O(logn)。

低效的「插入|删除」

连续内存和相同元素的限制有利有弊，有利于「随机访问」，有弊于「插入|删除」。

其实还是比较好理解的，数组可理解为排着一队人，如果要在队伍当中随意”加插/拉出“一人，势必影响到整个队伍。

最坏时间复杂度是 O(n)， 因为每个位置插入/删除元素的概率一致，所以平均情况时间复杂度为 (1+2+…n)/n=O(n)

那，如何能处理得更高效一点呢？我们来看下最好复杂度：

  • 插入：O(1) ，即插入为最后一个（类似做操晚到了排最后，不影响队伍 😁）
  • 删除：O(1) ，即删除了最后一个

但是，如果我们明确要求来的 X 排到指定位置（关系户 →_→），但是对原来的队伍不关心顺序（可能原本就是无序）。可以采用如下方式，比如 X 确定排第三，那么我们可以先让 C 排到最后，再把第三个位置给 X 即可。

利用这种处理技巧，在特定场景下，在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)。这个处理思想在快排中也会用到，排序那一节具体来看吧，这里就说到这儿。

删除操作，我们也会有一些特别的处理，比如标记删除而不是真正删除，只有没有更多空间时，才触发真正删除。

类似 JVM 标记清除垃圾回收算法的核心思想。

Golang 中 slice 切片arr[:i] 方式的引用并没有删除底层数组，感觉也和这个思想有异曲同工的效用。

动态扩容 & 数组越界

现在来看数组的另一个特性：不支持动态扩容。

某些开发可能又疑惑了，哪里不支持扩容了，直接 append 或者 push 不要太爽哦

✍️ 很多语言支持容器类，比如 Golang 中的 Slice、 Java 中的 ArrayList、C++ STL 中的 vector

以 Golang 中的 Slice 为例，我们完全不需要关心底层的扩容逻辑，Slice 已经帮我们实现好了。

（如果对 Go slice 扩容机制感兴趣的，可参见 Go slice扩容深度分析 ）

的确，业务开发完全可以快乐地使用 slice（其他语言同理，参考大佬专栏引用 ↓）

对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

数组大小已知，或者多维数组，建议用定长的数组。

这里，简单谈下数组越界。虽然大部分语言会判错，比如 Golang，会直接抛出 out of bounds ... 错误。

但是，数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。而且，很多计算机病毒也正是利用到了代码中的数组越界可以访问非法地址的漏洞来攻击系统，所以写代码的时候一定要警惕数组越界。

总结

数组（Array）是一种线性表数据结构，用一组连续的内存空间来存储具有相同类型的数据，并且不支持动态扩容。

特点是支持随机访问，但插入&删除较低效，平均复杂度 O(n)。

在之后的算法学习中，我们会针对数组的插入用一些处理技巧。

在平时的业务开发中，我们可以快乐地使用可扩容的容器类（如 Golang slice 等）。

一定要警惕数组越界，尤其是 C 语言开发者。