乐趣区

重学数据结构之数组篇

jiezi

数组在我们日常的编程工作中会经常用到，它不仅仅是一种编程语言的数据类型，还是一种最基础的数据结构。今天我们来重新认识一下它。
@[toc]

数组是什么？

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

关键词

  • 线性表
  • 连续的内存空间和相同类型的数据

线性表，表示数据像糖葫芦一样被串起来，每个数据最多只有前后两个方向。除了数组，其他线性表结构的还有，栈、链表、队列等。


与之对应的就是非线性表，即内部数据元素非简单的前后关系，比如，二叉树，图，堆等结构。

连续内存空间和相同类型数据，提供了“随机访问”的特性，但是在插入和删除数据的时候，会导致大量的内存空间需要进行迁移。以保证内存空间的连续性。

数组是如何通过下标随机访问元素的

首先我们创建一个数组 int[] a = new int[10]。假如计算机给我们创建的数组内存地址如下，内存地址范围 1000~1039，内存的首地址为 k =1000；

那么每个元素的内存地址等于首地址加上数据类型占用的字节数, 那计算公式就是

a[i]_address = k + i * data_byte_size

比如，第三个元素的地址为：1000 + 2* 4 = 1008

插入和删除操作低效原因

假如我们有一个长度为 n 的数据，现在我们需要将一个元素 x, 插入到 k 的位置，那么为了保证数组内存空间的连续性，那么 k~n 之间的数据都需要顺序的往后挪一位。
从时间复杂度上来说看，如果插入的数据正好是数组的末尾，就不需要移动任何数据，那么时间复杂度为 O(1)；如果恰好插入在数组的头部，那么后面的元素都要顺序后移一位，那么最坏时间复杂度就是 O(n)；其实在数组每个位置插入元素的概率是一样的，所以平均时间复杂度为 O(n)。
如果数组中的元素是有序的，那么我们需要遵循上面的方法；如果数组中的元素不需要有序呢，比如我们有个元素需要插入到 k 位置，最简单的方式就是将原来 k 位置的元素放到数组的末尾，将新元素放在 k 的位置上，这种情景下，插入元素的时间复杂度就是 O(1)了。
同样的删除操作也是一样，最好的时间复杂度为 O(1), 最坏的为 O(n)，平均为 O(n)
再将元素多次删除时，为了提高效率，可以考虑将删除操作集中在一起。我们在进行删除操作是，并不是真正的删除，只是将需要删除的元素进行标记，当数组没有更大存储空间时，再进行一次真正的删除，删除标记的元素。这就大大减少了每次删除元素进行的搬移操作，这也是 JVM 标记清除垃圾回收算法的核心思想。

数组越界问题

首先对于 Java 语言来说，java 本身会做数组越界检查，比如下面的代码，就会抛出异常
java.lang.ArrayIndexOutOfBoundsException。

int[] a = new int[6];
a[6] = 10;

而在 C 语言中，数组越界是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。因此需要 C 语言的开发者，在开发过程中需要处理数组越界问题。

数组和容器的适用场景

Java 中 ArrayList 的使用是非常常见的。ArrayList 相对于数组来说有两大优点：

  • 分装了数组的需要操作细节，比如插入，删除操作
  • 动态扩容。数组是固定的，而 ArrayList 在存储空间不够的时候，会自动扩容为 1.5 倍大小。

实际业务开发场景中，如果一直数据的数量大小，在使用 ArrayList 时建议指定大小，减少内存扩容申请和数据搬移的耗时，比如我们已知数据大小为 10000

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

那么什么时候使用数组更合适呢？

  • 数据大小已确定，数据操作比较简单，
  • 多维数组，使用数组比较直观
  • Java ArrayList 无法存储基本类型数据，比如 int,long 等，需要进行装箱拆箱，有一定的性能损耗，使用数组会比较合适

为什么数据的下标索引是从零开始

首先我们回到上面计算元素内存地址的公式
如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[i]就表示偏移 i 个 type_size 的位置

a[i]_address = base_address + i * data_byte_size

如果下标索引从 1 开始，那么公式就变成了

a[i]_address = base_address + (i-1) * data_byte_size

对比上面的公式，从 1 开始编号，每次随机访问数组元素都多了一次 (i-1) 减法运算，对于 CPU 来说，就是多了一次减法指令, 增加了性能开销。

面试问题

面试官：说一说链表和数组的区别？
答：1、数组中的元素存在一个连续的内存空间中，而链表中的元素可以不存在于连续的内存空间。
2、数组支持随机访问，根据下标随机访问的时间复杂度是 O(1)；链表适合插入、删除操作，时间复杂度为 O(1）

觉得文章不错的，给我点个赞哇，关注一下呗！
技术交流可关注微信公众号【君伟说】，加我好友一起探讨
微信交流群：加好友（备注技术交流）邀你入群，抱团学习共进步

退出移动版