数据结构之数组

2023-11-19

前言

线性表与连续内存

数组是如何支持随机访问

前言

数组是我们平时开发中经常遇到的一种数据结构，提起数组，我们能想到最大的特点就是，要提前定义好，需要提前申请好内存空间。

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

线性表与连续内存

对于线性表的指的是我们数据的储存方式，就好像一条线一样，前一条数据和后一条数据是有关联性的，就好像被串联起来一样。比如我们常见的数组、链表、队列、栈都是线性表结构。

对于连续的内存空间和相同类型的数据：由于内存空间是连续的，在随机访问有很好的性能，但是也是要求连续的内存空间，当删除数据的时候，需要做大量的数据搬移，影响性能。

数组是如何支持随机访问

数组是如何支持随机访问的：前面提到了数组申请到的内存空间是连续的，并且是相同类型的数据。

假设我们申请的初始位置的地址为100，每个类型数据占用的内存大小为4 ，那么通过我们便可以很快计算出：a[i]的地址为100+4*i。获取到i的地址后，我们就可以通过地址快速的查找到数据的值，

所以数组在通过下标访问的时候，时间复杂度是O(1)，查询效率是非常高的。

数组的插入与删除

随之而来的，便是数组在插入数据和删除数据比较差的性能。

假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。

跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。

在删除数据操作的时候，我们有一个小技巧：我们并不是每次的删除操作都去真正的搬移数据，只是记录数据已经被删除，当数组没有更多存储数据的时候，我们再触发一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

很多时候我们并不是要去死记硬背某个数据结构或者算法，而是要学习它背后的思想和处理技巧，这些东西才是最有价值的。如果你细心留意，不管是在软件开发还是架构设计中，总能找到某些算法和数据结构的影子。

数组越界

数组的使用中，还有一个不太方便的点，很多时候，可能程序的运行，数组下标的增长并不是朝着我们想象的方向去，但是我们的内存空间是提前申请。我们需要时刻警惕数组下标越界的问题。

我们在平时开发中，并不会直接的使用数组这种底层的数据结构，我们更多的使用高级语言封装的容器，比如:Java 语言就帮我们封装了ArrayList，并提供了更多的封装。比如不不需要过多的担心数组越界的问题。ArrayList会帮我们自动扩容:原理就是新建一个1.5倍容量的数组，并进行数据迁移，迁移完成后，删除原来的数组。不过我们最好在创建的时候事先指定数据的大小，虽然可以支持自动扩容，但是扩容操作比较耗时。

作为高级语言编程者，有如下使用经验

Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
还有一个是我个人的喜好，当要表示多维数组时，用数组往往会更加直观。比如 Object[][] array；而用容器的话则需要这样定义：ArrayList<ArrayList<object>

总结：

数组是最基础、最简单的数据结构了。数组用一块连续的内存空间，来存储相同类型的一组数据，

最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)。在平时的业务开发中，

我们可以直接使用编程语言提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。

参考文章：

本章内容来源于对王争大佬的数据结构与算法之类的专栏。

05 | 数组：为什么很多编程语言中数组都从0开始编号？-极客时间

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)