深入浅出数据结构之数组
数据结构是计算机存储、组织数据的方式
常用的数据结构有数组、链表、栈、队列、散列表（哈希表）、堆、树、图等
熟悉数据结构能够帮助我们在平常工作中更好的使用
本篇文章将围绕数组深入浅出的解析数组的特点、适用场景以及设计如何实现数组
数组的特点
存储元素内存连续
数组是在内存中连续存储多个元素的结构，元素能够通过数组的下标（索引）进行访问
数组的下标从0开始，比如图中创建了一个长度为5（连续空间）的数组，其中从下标0开始存储元素1、2、3、4
数组中存储什么元素，由什么类型的数组决定，比如我规定创建int类型的数组，那么数组中元素类型就都应该是int，并且数组中每个元素占4Byte空间
随机访问
由于数组内存空间是连续的且元素类型大小相同，这能让数组做到对每个元素的"随机访问"
比如我知道这个int数组存储真实数据的物理空间偏移量位置offset为500，则下标为0的元素就是从offset=500开始存储的，则下标为3的元素就是从offset=500+(3 * 4)=512 开始的
插入/删除时可能需要挪动其他元素
在数组中寻找某个关键元素时，我们可以选择将数组遍历（从头到尾）查找一边，这样平均时间复杂度就变成O（n）其中n为数据规模，随着数组中元素的增多耗时将会上升
在数组中插入某个元素时，如果插入的是数组末尾则时间复杂度不高为常量级别O（1），如果插入的是数组中间，由于空间连续，还需要将后续所有元素向后挪动一位，平均时间复杂度为O（n）
比如图中将元素0插入到下标2的位置
删除同理，比如将元素1删除时其他元素向前挪动
扩容与缩容
当发生添加操作时且数组已经被占满了就会发生扩容，需要创建一个更大的数组来装载元素，由于数组的特点，创建新数组后还需要将老数组所有元素迁移到新数组中
扩容大小是需要权衡的，当数组太小且后续还有添加操作时，扩容太小将会导致后续又进行扩容；当数组太大且后续无添加操作时，扩容太大可能导致浪费空间（图中是从长度为5 扩容为长度为10）
频繁删除元素后，数组可能存在大量空余空间，这时候如果想避免浪费空间就能进行缩容，以此来节约空间，缩容流程与扩容相似，也是新创建数组再对元素做迁移，也会额外耗时
适用场景
刚刚分析过数组的特点，熟悉特点的同学已经能够从特点分析出数组适用于哪些场景了
数组是空间连续的，支持随机访问的，访问数组中某个元素的时间成本都相同，这很适用于想查找某个下标位置上元素是什么的场景
对数组中最后一个元素进行添加/删除时，时间复杂度是常量级别的，这适用于频繁在数组尾部添加/删除的场景
数组的扩容/缩容会额外耗费时间，如果操作时就知道数据大小，可以在创建数组时就进行初始化大小，避免扩容
设计实现数组
设计数组时，需要考虑用变量来记录数组的一些信息
考虑到通用性，可以使用泛型来实现各种类型的对象数组，可能需要一个size变量来记录数组中元素的数量
public class ListArray<T> { private int size = 0; private Object[] element; }
考虑到要给用户提供初始化大小，还需要INITSIZE变量来记录初始化数组长度
private final int INITSIZE = 5; ListArray() { element = new Object[INITSIZE]; } ListArray(int elements) { if (elements <= 0) element = new Object[INITSIZE]; else element = new Object[INITSIZE]; }
当遇到不理想的情况时返回一个特殊的常量ERROR
private final int ERROR = -1;
提供一些基础能够使用数组的方法等等
查看元素数量
public int size() { return size; }
判断数组是否为空
public boolean isEmpty() { return size == 0; }
查找元素
public int indexOf(T elements) { if (elements==null){ for (int i = 0; i < size; i++) { if (element[i]==null) return i; } }else { for (int i = 0; i < size; i++) { if (elements.equals(element[i])) return i; } } return ERROR; }
判断数组中是否包含某个元素
public boolean contains(T element) { return indexOf(element) != ERROR; }
获取下标位置的元素，查询前还要判断所给下标是否越界
//时间复杂度：O(1) public T get(int index) { checkIndex1(index); return (T) element[index]; } private void checkIndex1(int index) { if (index < 0 || index >= size) throw new ArrayIndexOutOfBoundsException("您输入的下标数有误"); }
将某位置的下标元素替换为新元素，并返回旧元素
//设置对象，返回的是旧对象 //时间复杂度：O(1) public T set(int index,T elements) { checkIndex1(index); T oldElement = (T) element[index]; element[index] = elements; return oldElement; }
添加元素，添加前需要检查扩容， 扩容中的迁移其实不需要遍历老数组迁移，可以使用APISystem.arraycopy();直接将老数组数据复制到新数组中
/* 添加对象到最后 时间复杂度： 最好：O(1) 在末尾添加元素 最差：O(n) 扩容，移动元素 平均：O(1) 均摊：O(1) 连续多次复杂度低，出现个别复杂度高的情况（把复杂度高的均摊给复杂度低的） n是数据规模，这里数据规模是size(数组大小) */ public void add(T element) { add(size, element); } /* 往index位置添加对象 时间复杂度： 最好：O(1) 在末尾添加元素 最差：O(n) 在头部添加元素，所有元素往后挪一位 平均：O(n) n是数据规模，这里数据规模是size(数组大小) */ public void add(int index, T elements) { checkIndex2(index); capacityExpansion(size + 1); for (int i = size; i > index; i--) { element[i] = element[i - 1]; } element[index] = elements; size++; } //检查Index是否正确 private void checkIndex2(int index) { if (index < 0 || index > size) throw new ArrayIndexOutOfBoundsException("您输入的下标数有误"); } //扩容 private void capacityExpansion(int capacity) { int oldExpansion = element.length; if (capacity <= oldExpansion) return; //(oldExpansion >> 1) = 0.5 oldExpansion int newExoansion = oldExpansion + (oldExpansion >> 1); Object[] newElement = new Object[newExoansion]; for (int i = 0; i < size; i++) { newElement[i] = element[i]; } element = newElement; }
其他方法不一一展示，数组的实现相对简单，不熟悉的同学可以去查看ArrayList源码或者手写一个简单的数组，这样能够大大加深自己对数组的理解
总结
本篇文章围绕数组，深入浅出的解析数组的特点、适用的场景以及设计数组思路与实现数组过程代码
数组是内存空间连续的结构，能够随机访问数组中的元素
在数组中间进行插入、删除需要挪动其他元素，这是额外的性能消耗，只有在数组末尾进行插入、删除才是最高效的
扩容与缩容会对数据进行复制，也是额外的性能消耗，如果知道操作数据规模就应该在初始化时设置，避免发生扩容缩容
在设计实现数组时，不仅要考虑到需要记录数组的信息，还要考虑到不合理的情况，对不合理的参数进行校验拦截
