数据结构-1-数组

学习闲话

一旦设计到框架的选择，技术选型，或者研究工具底层的时候，往往就需要一些通用的知识，比如数据结构和常用的算法，网络协议，操作系统等等知识，算是无论往哪个方向发展的必经之路了。所以这段时间根据极客时间课程《数据结构与算法之美》 的学习写了这一系列的笔记。后期计划再系统学习网络协议，操作系统等系列课程。

进入主题

基本概念

数据就是在内存中使用连续的内存空间，用于存储一系列相似数据的线性表数据结构。

因为符合两个条件：

1，内存连续；

2，一组相似数据；

所以，可以保证存储和查询的顺序：

比如连续的存储顺序在内存的地址是从 001001(base_address) – 00101100 ；并且数组中每一个元素的大小是 5 个字节data_type_size ，就可以使用下面的公式计算出数组中每一个数据的内存位置：

a[i]_address = base_address + i * data_type_size

操作的复杂度分析

首先，根据上面的分析，按照下表访问数组的时间复杂度是O(1)，这个很好理解。如果是查找数组中的特定对象（不知道下表），时间复杂度肯定不是O(n)。

对于增删的操作，时间复杂度是比较大的，比如在i位置插入一个数据，需要把后面的数据一次往后挪一个位子，复杂度是O(i)，如果是对于长度为n 的数组，对于怎加一个元素的最好，最坏和平均时间复杂度分别是：O(1);O(n);O(n);

正常的删除操作也是如此，但是有一个取巧的思路是标记删除，就是每一个删除不是真正删除，而是对需要删除的数据做一个删除标记（只适用于一些不追求数据连续性的场景），在存储空间不足的时候在做真正的删除（JVM标记清除垃圾回收算法的核心思想??）。

封装容器和数组的选择（基于JAVA）

如果知道数据规模并且是比较基础的操作，能选择数组性能会有一些提升。

数组一旦确定大小便固定了，如果事先不知道数据规模自己进行数组的扩容肯定比较麻烦；但是比如ArrayList自己实现了动态扩容，使用起来比较方便。

然后封装的容器，比如ArrayList不支持基本数据类型，自动拆箱和自动装箱会有很小的性能损耗。