什么是数组
数组是一种非常基础的数据结构，它的专业定义如下：数组（Array）是一种线性表数据结构。它使用一组连续的内存空间，来存储一组具有相同类型的数据。
在这段定义中，有两个重点：
- 线性表：线性表就是数据排成一条线一样的结构。每个线性表上的数据最多只有前后两个方向。除了数组，链表、队列、栈等都是线性表结构
- 数组具有连续的内存空间和相同的数据类型，正是这一特性，使得数组拥有了它最显著的特征：“随机访问”。
数组的特点
数组的优点
首先我们使用一张图看一看数组的存储方式：
数组的存储形式.jpg
你会发现，数组的存储是一块连续的存储空间，这让我们可以通过简单的计算就可以直接获得数组中某个元素的地址，而这个特点，使得数组拥有了它最大的优势：随机访问
具体的计算公式如下：
a[i]_address = base_address + i * data_type_size
数组的缺点
数组连续的内存空间让它可以方便地随机访问，但是也带来了一些弊端：为了保持内存的连续性，在数组中进行插入、删除等操作就需要做大量的数据搬移工作。
下面以数据插入作为例子：
数组的插入.jpg
上面的图片展示了一个数据插入的操作：
我希望将x插入数组中的第3个位置，这就使得我么需要将原本第 3~5的三个数据顺序的向后挪动，这使得数组的插入操作的平均时间复杂度为O(n)。
同理，你会发现数组的删除操作也要涉及大量的数据搬移工作，这让数组在有大量插入删除操作的环境中的性能大打折扣。
当然，你可以使用一些方法将这种特性带来的影响降低，比如设置一个删除标记，等标记的数据达到一定数量后再一起删除。
警惕数组的访问越界问题
在专栏文章中给出了一段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;
}
在C语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的，所以如果你使用上面的代码，根据之前说过的地址计算公式，arr[3] 会访问超出数组arr范围的地址，根据代码逻辑，这段代码会循环输入“hello world”。
实际上，arr[3]会得到 i 的地址，而根据你所使用的C语言的编译器的不同，许多编译器会阻止你访问这个地址。其实使用什么编译器不重要，你需要记住的是：数组越界是一个经常出现bug的点
并非所有的语言都像C一样，很多语言都会进行越界检查，这让你debug的过程轻松了不少。
语言中的容器类
由于数组要求相同的数据类型，这降低了数组的灵活性，许多语言的语法库中提供了“容器类”，比如 Java 中的 ArrayList、C++ STL 中的 vector。他们可以提供与数组类似的功能。
在这些类中，封装了许多对数组的操作细节，比如为你执行插入、删除数据时的搬移操作，并且支持动态扩容。
这类容器有好有坏，专栏的作者给出了一些建议，我讲它们复制如下：
- Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
- 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
- 还有一个是我个人的喜好，当要表示多维数组时，用数组往往会更加直观。比如 Object[][] array；而用容器的话则需要这样定义：ArrayList<ArrayList<object> > array。
- 我总结一下，对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。
上面就是关于数组的全部内容
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论