java 数组

1.线性表

数据的逻辑结构分为:线性结构和非线性结构。

不搞晦涩的专业术语。线性就是有头有尾，数据层面解释的特征就是

1. 集合中必须有唯一一个是第一个元素
2. 集合中必须有唯一一个事最后一个元素
3. 除了第一个元素前面没有元素，其他都有一个前置元素
4. 除了最后一个元素没有后置元素，其他都有一个后置元素

当然上面说的都是废话，没什么作用，其实小伙伴们知道什么是线性结构就行了。

常见的线性的数据结构:一维数组、链表、栈、队列

非线性结构: 数、图、堆

2.数组基础

2.1 概念和结构

数组两个特点 

1. 连续的内存空间
2. 必须存储相同的数据类型

2.2 寻址公式 （查询）

既然内存空间是连续的，所以我们找到每个下标的时候就很方便

a[i] = baseAddress + i * baseTypeDate (每个数据类型占用的内存空间都不一样！)

那么这样的访问方式，实际上就很快，O(1)的时间复杂度，因为不会因为数组的大小从而获取数据变慢！我只需要知道下标和初始值以及类型就行了。那么你看我们数组的定义方法，这三个信息都有了。

int array[]=new int[]{1,2,3};
int []array=new int[]{1,2,3};
double array[]=new double[]{1.1,2.2,3.3};

2.3 插入删除 

数组插入的效率就很低了，怎么个低法？

我在数组中央插入一个新的值，那么原来位置上的数据和后置的位置是不是都要往后移？那么这个就和数据量有关了，数据越多我移动的时间越慢！

删除也是一样的道理，数组中间我删除了一个元素，那么后置的元素都要往前移动一个单位。

那我删一个移动一次效率肯定很慢，那么我们可以将要删除的数据先打个标记，统一删除之后，一次性移动，那么效率就快多了！这个也是jvm 垃圾回收算法的核心思想。

3.leetcode 11题

算法   --  双指针夹逼思想，

283 -- 快慢指针

4.动态数组

我们的ArrayList 底层实现的原理就是动态数组实现的。