数据结构与算法笔记day02：数组

2019-03-28 本文已影响0人楠楠喜欢泡枸杞

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

线性表就是数据排成一条线一样的结构，每个线性表上的数据最多只有前和后两个方向：

与之对立的是非线性表，它的数据并不是简单的前后关系：

学习完之后看到一条评论，觉得说的很好，搬运过来：

“我觉得随机访问Ramdom Acess更应该翻译成任意访问，更能表达数组的特性。”

其实随机访问表示的意思就是可以访问任意一个位置上的元素，那么它是怎样实现随机访问的呢？

我们建立一个int型数组：

打个比方，假设计算机给数组a[10]分配了一块连续内存空间1000~1039，其中内存块的首地址为base_address=1000。我们访问某一个元素只需要通过寻址公式，就可以计算出每个下标元素的内存地址。

一个小注意事项，数组支持随机访问，根据下标随机访问的时间复杂度为O(1)，但是没有提供下标的查找时间复杂度就不是它了，比如用二分法，时间复杂度是O(logn)。

但是它的"插入”和“删除”操作则比较低效，因为某一个位置做了改动，它后面的元素位置都需要随之做改动。

但是有个小办法，如果这个数组中的元素并没有顺序要求，那我们要给k位置插入元素，可以直接将k位置的元素搬到最后，然后将新数据放在k位置上，这时的时间复杂度就会为O(1)：

删除的话，比如我们要删除下面的三个元素：

我们可以先记录下已经删除的数据，每次的操作并不是真正地搬移数据，只是记录数据已经被删除，当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

其实这也是JVM标记清除垃圾回收算法的核心思想。

有个评论讲的很形象：

关于数组越界的例子：

C语言中这段代码会出现死循环，原因依然搬运一个评论中的很形象的说法（评论出大神呀）：

所以arr[3]=0就相当于i=0，又回到了循环的起点，继续循环，如此往复，陷入死循环。

但并非所有的语言都像C一样，把数组越界检查的工作丢给程序员来做，像Java本身就会做越界检查，会抛出异常。

1)Java ArrayList无法存储基本类型，比如int、long，需要封装为Integer、Long类，这个过程存在性能性能消耗，如果很在意性能，或者希望使用基本数据类型，可以用数组。

2)数据大小事先已知，并且对数据的操作非常简单用不到容器提供到的大部分方法，可以用数组。

3)对于业务开发，直接使用容器就够了，省时省力，毕竟损耗一丢丢性能完全不会影响到系统整体的性能，但是如果做非常底层的开发，比如网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

1)比如a[k]，a表示数组首地址，k表示偏移量，计算a[k]的内存地址方式为：

若从1开始计数的话，计算方式变成：

效率会有一丢丢损失。

2)历史原因。（这个可能才是主要原因，哈哈~）因为C语言设计者用0开始计数组下表，之后的高级语言都效仿了C语言，这样就在一定程度上减少了C语言程序员学习Java的学习成本，所以沿用这个习惯。（当然也有一些语言不是从0开始计数，甚至还有一些支持负数下标）