学习笔记——数据结构：数组

我就是我 2022-05-11 14:10 212阅读 0赞

来简单总结一下这几天学的数组，数组虽然从一接触java开始就在用，但是没有学习过数组本身。

**目录**

1. 什么是数组？

2. 数组怎么用？

3. 从内存深入数组

4. 数组如何实现随机访问？

5. 为什么数组的插入、删除低效？

6. “打破”数组固定长度的局限

7. 与容器相比，数组更好的使用场景

8. 为什么很多编程语言的数组都从0开始编号?

--------------------

### 1. 什么是数组？ ###

数组是编程语言最常见的一种线性表的数据结构。

他用一种连续的内存空间，来存储相同的数据类型。

> 关键点：
> 
> 线性表：数据排成像线一样得结构。数据间有前后关系。
> 
> 连续的内存空间和相同的数据类型：随机访问。这也是数组查询效率高的原因。

### 2. 数组怎么用？ ###

使用数组前要初始化数组。

> 两种初始化方式：
> 
> 例：静态初始化：int\[ \] arr = new int\[ \]\{1, 2, 3, 4\}; 直接给定元素
> 
> 例：动态初始化：int\[ \] arr = new int\[ 4\]; 给定数组容量为四个
> 
> 【从可读性角度来说，不推荐 int arr\[ \] 这种格式】

数组的使用：

> 数组通过下标（从0开始）随机访问：
> 
> int\[ \] arr = new int\[ \]\{1, 2, 3, 4\};
> 
> System.out.println(int\[1\]); //输出：2
> 
> 通过下标赋值：
> 
> int\[ \] arr1 = new int\[ 4\];
> 
> arr1\[0\] = 45;
> 
> 遍历数组：
> 
> 使用for循环或者增强for循环即可。

数据访问越界问题

当访问下标大于等于数组容量，就会出现：java.lang.arrayIndexOutOfBoundException.

### 3. 从内存深入数组 ###

在java语言中，数组也是一种类型，java语言要求数组元素类型是惟一的。

数组是一种引用数据类型，数组引用变量只是一个引用，数组元素和数组变量在内存中是分开的。

![70][] 数组在内存的存储示意

要访问图示中的数组元素，则程序中只能通过P\[index\]的形式实现。

> 看待一个数组，看把他分成两部分看，一部分是数组引用（数组变量）；还有一部分就是运行在堆中的实际数组对象，通常无法直接访问，只有通过数组引用变量来访问。

### 4. 数组如何实现随机访问？ ###

现在有一个数组:

int[] a = new int[10];

那么计算机会分配一个连续的内存空间1000~1039，其中该内存空间起始位置记为baseaddr=1000;

计算机会给数组中的每个元素分配一个地址，通过这个地址来访问元素，这个地址是通过一个寻址公式计算得出;

寻址公式：baseaddr + i * data_type_size = a[i]_addr;
    第i个元素内存地址为：起始地址 + 元素下标 * 元素类型长度

数组支持随机访问，所以时间复杂度为：O(1)。

### 5. 为什么数组的插入、删除低效？ ###

插入：

假设要往一个长度为n 的数组的k位置插入数据。以为数组内存空间是连续的，所谓插入前，要将k~n这部分元素依次向后挪一位。

最好时间复杂度：在最后一位插入，时间复杂度为：O(1).

最坏时间复杂度：在第一位插入，时间复杂度为:O(n).

因为插入的概率一样，所以平均时间复杂度为：O(n)。

在元素无序的条件下,如果在k位置插入m元素，可以把k位置原来的元素直接放到最后一位，然后把m放入k位置。所以在特定场景，这种插入方法时间复杂度将为O(1)

删除:

和插入类似，最好时间复杂度：O(1). 最坏时间复杂度为:O(n). 平均时间复杂度为：O(n)。

在某些特殊情况下，要删除一些元素，不需要将多次删除操作一起执行，而是把每次删除操作不是真正删除元素，而是把要删除的元素记录下来，当数据没有多余空间存储元素时，在触发一次真正的删除操作。（JVM标记垃圾清除算法的思想）

### 6. “打破”数组固定长度的局限 ###

[二次封装数组，实现动态数组。][Link 1]

### 7. 与容器相比，数组更好的使用场景 ###

容器如法存储基本类型，在自动装箱过程会有一定性能损耗，在很注重性能或希望使用基本类型时，可以选择数据；

在容量确定，并且对数据操作简单，也可以选择数组。

### 8. 为什么很多编程语言的数组都从0开始编号? ###

原因1：从数组内存模型来看，“下标”最确切的定义是“偏移”。

a\[0\]就是偏移为0的位置，a\[k\]就是偏移为k的位置，所以寻址公式为：

> baseaddr + k \* data\_type\_size = a\[k\]\_addr;

但如果从1开始，那么寻址公式为;

> baseaddr + (k - 1) \* data\_type\_size = a\[k\]\_addr;

对于CPU来说，需要多做一次减法指令。

原因2：历史原因。

C语言从0开始，所以后来的部分高级语言，模仿C从0开始，也是为了减少C程序员学习java的成本。

[70]: /images/20220505/8b7d2eae1e7c45c690909cee4b95c3a8.png
[Link 1]: https://github.com/liujinmai/data_structure/commit/de0d0d7bf99fcc51b09c32cd9d19e83e270f8d2a