深入浅出数据结构之数组-阿里云开发者社区

深入浅出数据结构之数组

数据结构是计算机存储、组织数据的方式

常用的数据结构有数组、链表、栈、队列、散列表（哈希表）、堆、树、图等

熟悉数据结构能够帮助我们在平常工作中更好的使用

本篇文章将围绕数组深入浅出的解析数组的特点、适用场景以及设计如何实现数组

数组的特点

存储元素内存连续

数组是在内存中连续存储多个元素的结构，元素能够通过数组的下标（索引）进行访问

数组的下标从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源码或者手写一个简单的数组，这样能够大大加深自己对数组的理解

总结

本篇文章围绕数组，深入浅出的解析数组的特点、适用的场景以及设计数组思路与实现数组过程代码

数组是内存空间连续的结构，能够随机访问数组中的元素

在数组中间进行插入、删除需要挪动其他元素，这是额外的性能消耗，只有在数组末尾进行插入、删除才是最高效的

扩容与缩容会对数据进行复制，也是额外的性能消耗，如果知道操作数据规模就应该在初始化时设置，避免发生扩容缩容

在设计实现数组时，不仅要考虑到需要记录数组的信息，还要考虑到不合理的情况，对不合理的参数进行校验拦截

深入浅出数据结构之数组