数据结构系列之数组

什么是数组？

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

数组的特性

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

线性表结构：数组、链表、队列、栈

非线性表:与线性表对立，在非线性表之中，数据之间并不是简单的前后关系。

非线性表结构：二叉树、堆、图等。

2、连续的内存空间与相同的数据结构

数组的寻址公式

a[i]_address = base_address + i * data_type_size

低效的“插入”和“删除”

由于数组的内存连续性，数组在“插入”和“删除”会执行大量的搬迁工作，势必会影响性能损耗。数组的“插入”和删除的最好情况的时间复杂度为O(1)，最坏的时间复杂度为O(n)，平均的时间复杂度为O(n)

3、注意数组的越界性问题

数组越界在C语言中是未决行为，编译器并没有做数组越界的检查

Java语言对数组越界进行了异常检查，如果数组越界，会抛出java.lang.ArrayIndexOutOfBoundsException

Java中的数组容器

Java中的数组进行了封装，表现为ArrayList

ArrayList初始容量为10，支持动态扩容，如果存储空间不够，会将数组扩容至1.5倍

在事先知道ArrayList大小情况下，尽量初始化时将大小指定好，提高容器处理效率

何时使用数组？

使用基本类型时可使用数组，Java容器中的ArrayList不支持基本数据类型，只支持封装后的数据类型，如Integer

场景比较简单时，不用去使用ArrayList封装的方法时，使用数组

如果遇到多维场景时，尽量使用数组

为什么很多编程语言中都使用0作为数组的起始下标？

1、如果使用下标为1的话，计算数组的内存地址公式为

a[k]_address = base_address + (k -1) * type_size

每次去寻址时都会计算(k - 1) ，会增加CPU的执行次数

2、历史原因，沿用C语言的设计思路