前言：我们之前实现了一个双端队列，这是一个比较完善的数据结构，两端的插入和删除都非常快。但是，当我们需要访问队列中第一个队列的第i项时，总是需要从sentinel节点开始，遍历第i-1项，才能找到第i项。在最坏的情况下，我在中间。这时候我们需要遍历链表长度n的一半n/2。假设n很大，耗时会比较大（O(n)）。考虑到数组可以直接访问下标，完成对第i项的查找几乎是O(1)，所以本类决定使用数组来实现List1.AList这个抽象数据类型，首先创建一个类AList，其成员是一个int数组，size大小，初始化构造函数，首先分配一个长度为100的数组项，每一项为0，因为一开始我们没有添加任何元素，所以size=0公共类AList{私有int[]项目；私有整数大小；publicAList(){items=newint[100];大小=0；}}同前面的Deque，对于AList，有操作：addLast()：在末尾添加数据removeLast()：删除并返回末尾数据get()：返回第i项数据getLast()：获取数组的最后一个元素数据size()：返回List的长度通过观察，我们可以发现数组有如下不变量：数组末尾添加下一个元素的位置（下标）为alwayssizesize永远是数组的长度，数组最后一项的下标永远是size-1（因为数组的索引是从0开始的）所以我们可以这样写上面的数据操作：//在数组末尾添加元素publicvoidaddLast(intx){items[size]=x;尺寸+=1；}//获取数组的最后一个元素publicintgetLast(){returnitems[size-1];}//查询itemipublicintget(inti){returnitems[i];}//查询数组长度publicintsize(){returnsize;}//删除public最后一项intremoveLast(){intx=items[size-1];大小=大小-1;返回x;}2.ResizingArray一开始我们定义的item数组的大小默认是100。假设我们现在需要添加第101项Data11，数组当前的容量显然是不够的。这时候我们需要重新调整数组的大小，即resizingArray。我们先考虑最简单的方法，就是用System.arraycopy():int[]a=newint[size+1];System.arraycopy(items,0,a,0,size);[尺寸]=11;项目=一个；大小=大小+1；我们重新声明一个新的数组a，相比原数组item的长度为1位，将原数组item的值复制到a中，a的最后一位用来存放新的数据，这样求解阵列容量不足的问题。后面也可以写成一个特殊的函数resize()来操作和复制数组：privatevoidresize(intcapacity){int[]a=newint[capacity];System.arraycopy(items,0,a,0,size);items=a;}publicvoidaddLast(intx){if(size==items.length){resize(size+1);}项目[大小]=x;size+=1;}3.分析ResizingArray的时间复杂度回忆一下我们之前的SLList，向队尾添加一个元素的时间复杂度是O(1)，那么对于AList来说，时间复杂度与列表？想一想，如果此时原数组的大小为100，并向其中添加一条新数据，那么addLast()需要做的是：声明一个大小为101的新数组，并复制100个元素101次操作总共需要201个内存空间。如果添加两个新元素怎么办？按照以上步骤，一共需要101+102=203个空格，新加1000个，需要101+102+103+...+1000=495450个空格，也就是50万左右的空格。可以看出在linux中内存空间消耗非常大接下来可以在运行命令javafilename之前加上一个时间，从而获取程序的运行时间。常数阶，总运算时间的累加是常数的积分：函数是一条直线。对于后者，每次复制操作都是从0开始，将原数组的所有元素复制到新数组中。复制操作的时间复杂度为O(n)，总复制次数累加为n的整数，为抛物线4.优化ResizingArray时间复杂度优化将每个size+1改为size?refactor，即就是，每次扩充数组size从一个数变成乘以某个数，这样就变成了GeometricResizing，可以大大降低时间复杂度publicvoidaddLast(intx){if(size==items.length){调整大小（大小*RFACTOR）；}项目[大小]=x;size+=1;}空间和内存优化如果我们有一个大小为100,000的数组，当我删除99,999项时，原始数组中只剩下1项实际上，删除操作只是不断向左移动大小，原来数组占用的内存空间依然存在，这样剩余的内存就浪费了很多。考虑引入一个使用率，定义为“使用率”R=size/items.length如果R<0.25，将数组长度减半5。保存任何数据类型，而不仅仅是整数。例如，使用ElemType作为泛型参数。在此之前需要注意的一件事是，Java不允许我们创建泛型对象数组，这意味着我们不能这样写：Elemtype[]items=newElemtype[8];相反，可以先创建一个Object类型的数组，然后强制将类型转换为泛型数组：Elemtype[]items=(Elemtype[])newObject[8];虽然编译器会产生一个warning，后面会解释...最后是一点优化。我们在写removeLast()的时候，只用了size=size-1;末尾的元素值仍然存在于数组中，但被我们忽略了。当数组很大时，这会造成内存浪费，所以在执行size=size-1之前，将原来的结束元素值赋给null，让垃圾回收器回收，避免“游荡”items[size-1]=null;大小-=1；
