Java数据结构—动态数组和时间复杂度分析

一、数组基础

1.1 定义

数组(Array)是一种线性表数据结构，它用一组连续的内存空间来存储一组具有相同类型的数据。

1.2 创建流程

当我们在 java 中当创建一个数组时，会在内存中划分出一块连续的内存，当有数据进入的时候会将数据按顺序的存储在这块连续的内存中。当需要读取数组中的数据时，需要提供数组中的索引，然后数组根据索引将内存中的数据取出来，返回给读取程序。

把数据码成一排进行存放：

所有的数据结构都支持几个基本操作：读取、插入、删除数组索引可以有语意，也可以没有语意，比如说 student[2]，就代表是这个数组中的第三个学生。

因为数组在存储数据时是按顺序存储的，存储数据的内存也是连续的，所以数组最大的优点就是能够快速查询，寻址读取数据比较容易，但是插入和删除就比较困难。

为什么数组最大的优点就是能够快速查询。因为当我们在读取数据时，只需要告诉数组获取数据的索引位置就可以了，数组就会把对应位置的数据，读取出来

插入和删除比较困难是因为这些存储数据的内存是连续的，数组大小固定，插入和删除都需要移动元素

例如：一个数组中编号 0>1>2>3>4这五个内存地址中都存了数组的数据，但现在你需要往4中插入一个数据，那就代表着从4开始，后面的所有内存中的数据都要往后移一个位置。

二、编写我们自己的数组类

我们知道想要维护某一个数据，我们需要对这个数据有这最基本的增、删、改、查，这几个基本功能，所以我们自己手动编写的数组类，也是需要有用这几个最基本的功能，虽然不会像 List、Map这些类，那么强大，但是对于我们普通的开发来说，基本是可以满足，下图所示就是我们一个基本的数组类，那么我们是如何对数组进行改造，来编写一个属于我们自己的数组类的呢，这里我们以增加和删除做重点讲解，本文中的所有源码会在最后贴出来，请往下看。

从上图中我们可以得知，我们创建数组类的时候，需要三个元素 data、size、capacity，而我们所需要使用的数组，肯定是要能够支持多种数据类型，而不是单一的数据结构，因此，我们可以在设计类的时候，是需要加上泛型支持，让我们的数据结构可以支持放置任何数据类型。

data：需要传递的数据size：元素中的个数capacity：数组的初始容量

注意：我们上面所说的放置任何数据类型，只能是类对象，不可以是基本数据类型，但是我们每个基本数据类型都有对应的包装类，所以我们的基本类型也是可以使用的，不过只是使用的是它的包装类

因此，我们在设计我们的数组类的时候，我们可以这么设计

/**
*@program:
*@ClassNameArrayPlus
*@description:
*@author:lyy
*@create:2019-11-1822:27
*@Version1.0
**/
publicclassArrayPlus<E>{
privateE[]data;
privateintsize;
//构造函数，传入数组的容量capacity构造array
publicArrayPlus(intcapacity){
data=(E[])newObject[capacity];
size=0;
}
//无参数的构造函数，传入数组的容量capacity=10
publicArrayPlus(){
this(10);
}
//获取元素中的个数
publicintgetSize(){
returnsize;
}
//获取数组的容量
publicintgetCapacity(){
returndata.length;
}
//返回数组是否为空
publicbooleanisEmpty(){
returnsize==0;
}
@Override
publicStringtoString(){
StringBufferres=newStringBuffer();
res.append(String.format("Array：Size=%d，capacity=%d\\n",size,data.length));
res.append("[");
for(inti=0;i<size;i++){
res.append(data[i]);
if(i!=size-1)
res.append("，");
}
res.append("]");
returnres.toString();
}
}

2.1 数组添加元素

在数组中是如何添加数据的呢，首先我们需要创建一个拥有初始容量的数组，当我们创建完成之后，size是指向第一个元素的，也就是 index=0的地方，当我们添加第一个数据后也就是 data[0]=12后，我们的元素中的个数 size，需要往后挪一位的，也就是 size++的操作，每当我们操作一位，就需要将上面的操作重复执行，直到最后一个元素添加到我们的数组中。

如下图所示：

知道了怎么操作，但是我们要如果通过代码来完成呢?

首先我们要清楚在添加的时候，在哪里?添加什么数据?，在哪里：我们要在数据的什么地方进行添加，也就是要添加到数组中的哪个下标—— index的地方，知道了在下标，我们只需要将添加的数据，添加到数组中为 index 的地方即可，除此之外，我们只需要对添加时，做一些基本的判断就可以了，代码如下：

//在所有元素后添加一个新元素
publicvoidaddLast(Ee){
add(size,e);
}
//想所有元素前添加一个新元素
publicvoidaddFirst(Ee){
add(0,e);
}
//在第Index个位置插入一个新元素e
publicvoidadd(intindex,Ee){
if(size==data.length)
thrownewIllegalArgumentException("Addfailed.Arrayisfull.");
if(index<0||index>size)
thrownewIllegalArgumentException("Addfailed.Requireindex<0||index>size.");
for(inti=size-1;i>=index;i–)
data[i+1]=data[i];
data[index]=e;
size++;
}

测试代码：

publicclassMain2{
publicstaticvoidmain(String[]args){
ArrayPlus<Integer>arr=newArrayPlus<>();
for(inti=12;i<16;i++)
arr.addLast(i);
System.out.println(arr);
}
}

返回结果：

Array：Size=4，capacity=10
[12，13，14，15]

在数组中是如何执行插入呢?如下图所示：

测试代码：

publicstaticvoidmain(String[]args){
ArrayPlus<Integer>arr=newArrayPlus<>();
for(inti=12;i<16;i++)
arr.addLast(i);
System.out.println(arr);
arr.add(1,100);
System.out.println(arr);
}

返回结果：

Array：Size=4，capacity=10
[12，13，14，15]
Array：Size=5，capacity=10
[12，100，13，14，15]

2.2 数组删除元素

如果我们想要删除索引为1的元素，是怎样操作的呢，首先我们需要先将索引为2的数据，覆盖到索引为1的元素上，再将索引为3的数据放到索引为2上，依次循环操作，直到最后一位元素，我们在将最后一位元素的数据设置为 null，这样垃圾回收机制就会自动帮我们清除这个元素。整个过程就完成了删除元素的功能，具体流程如下图所示：

实现代码：

//查找数组中元素e所在的索引，如果不存在元素e，则返回-1
publicintfind(Ee){
for(inti=0;i<size;i++){
if(data[i].equals(e))
returni;
}
return-1;
}
//从数组中删除index位置的元素，返回删除的元素
publicEremove(intindex){
if(index<0||index>=size)
thrownewIllegalArgumentException("removefailed.Indexisillegal.");
Eret=data[index];
for(inti=index+1;i<size;i++)
data[i-1]=data[i];
size–;
//loiteringobjects!=memoryleak
data[size]=null;//如果一旦使用新的元素，添加新的对象就会覆盖掉
returnret;
}
//从数组中删除第一个位置的元素，返回删除的元素
publicEremoveFirst(){
returnremove(0);
}
//从数组中删除最后一个位置的元素，返回删除的元素
publicEremoveLast(){
returnremove(size-1);
}
//从数组中删除元素e
publicvoidremoveElement(Ee){
intindex=find(e);
if(index!=-1)
remove(index);
}

测试：

importcom.bj.array.ArrayPlus;
publicclassMain2{
publicstaticvoidmain(String[]args){
ArrayPlus<Integer>arr=newArrayPlus<>();
for(inti=12;i<16;i++)
arr.addLast(i);
System.out.println(arr);
arr.add(1,100);
System.out.println(arr);
arr.remove(1);
System.out.println(arr);
}
}

返回示例：

Array：Size=4，capacity=10
[12，13，14，15]
Array：Size=5，capacity=10
[12，100，13，14，15]
Array：Size=4，capacity=10
[12，13，14，15]

我们看到结果已经把索引为1的删除了，到这里我们已经完成了一大半了，还有一小点也是最重要的，就是当我们添加数据超过了我们的初始容量大小的时候，就会报错，初始容量，无法添加超过的数据，那么我们应该怎么操作呢?其实很简单，我们只需要给我们数组类，添加一个扩容的方法即可，当我们元素的个数等于数组长度的时候，我们就进行扩容，我们称之为动态数组。

2.3 动态数组

前边我们讲过的用new给基本类型和对象在运行时分配内存，但它们的已经在编译时就已经确定下来，因为我们为之申请内存的数据类型在程序里有明确的定义，有明确的单位长度。但是，总有些时候，必须要等到程序运行时才能确定需要申请多少内存，甚至还需要根据程序的运行情况追加申请更多的内存。从某种意义上讲，这样的内存管理才是真正的动态。下面，我将带大家编写一个程序为一个整数型数组分配内存，实现动态数组。当你们看到下面这个图的时候，有没有想到什么，没错，有点像C++里面的指针

实现代码：

//在第Index个位置插入一个新元素e
publicvoidadd(intindex,Ee){
if(index<0||index>size)
thrownewIllegalArgumentException("Addfailed.Requireindex<0||index>size.");
if(size==data.length)
resize(2*data.length);
for(inti=size-1;i>=index;i–)
data[i+1]=data[i];
data[index]=e;
size++;
}
privatevoidresize(intnewCapacity){
E[]newData=(E[])newObject[newCapacity];
for(inti=0;i<size;i++)
newData[i]=data[i];
data=newData;
}

动态数组测试：

importcom.bj.array.ArrayPlus;
publicclassMain2{
publicstaticvoidmain(String[]args){
ArrayPlus<Integer>arr=newArrayPlus<>();
for(inti=0;i<10;i++)
arr.addLast(i);
System.out.println(arr);
arr.add(1,100);
System.out.println(arr);
for(inti=0;i<6;i++)
arr.remove(i);
arr.removeLast();
System.out.println(arr);
}
}

测试结果：

Array：Size=10，capacity=10
[0，1，2，3，4，5，6，7，8，9]
Array：Size=11，capacity=20
[0，100，1，2，3，4，5，6，7，8，9]
Array：Size=4，capacity=10
[100，2，4，6]

从结果中我们可以看到，当我们数组元素超过初始容量大小时，自动扩容到初始容量的两倍也就是20，当我们数组长度小于1/4的时候，为什么是1/4的时候而不是1/2的时候呢，下面我们会做详细介绍。当我们数组长度小于1/4的时候，会自动缩回到初始10的容量，不会去占据大量的内存空间。

三、时间复杂度分析

3.1 基础

五种常见的时间复杂度 1) O(1)：常数复杂度, 最快的算法，数组的存取是O(1) 1) O(n)：线性复杂度, 例如：数组, 以遍历的方式在其中查找元素 1) O(logN)：对数复杂度 1) O(nlogn)：求两个数组的交集, 其中一个是有序数组，A数组每一个元素都要在B数组中进行查找操作，每次查找如果使用二分法则复杂度是 logN 1) O(n2)：平方复杂度，求两个无序数组的交集

在这里，大O描述的是算法的运行时间和输入数据之间的关系

3.2 举例说明

大家可以看下面一个例子

publicstaticintsum(int[]nums){
intsum=0;
for(intnum:nums)sum+=num;
returnsum;
}

这个算法是 O(n) 复杂度的，其中 n是nums中的元素个数，算法和n呈线性关系
为什么说他是 O(n)的时间复杂度呢，因为这个算法运行的时间的多少是和 nums中元素的个数成线性关系的，那么这个线性关系，表现在我们的 n 是一次方，它不是 O(n) 方的，也不是 O(n) 的立方，n 对应的是一次方。
我们忽略常数，实际时间是：T=c1*n+c2c1：我们要把这个数据从 nums数组中取出来，其次我们还要把 sum这个数取出来，然后 num这个数和 sum相加，最终呢我们要这个结果扔回给 sum中c2：开始开辟了一个Int型的空间，我们把它叫 sum ，要把 0 初始化赋值给sum，在最终呢我们还要把这个 sum 给 return 回去

一方面把 c1 和 c2 具体分析出来是不大必要的，另一方面也是不太可能的，为什么说不可能呢?如果说把 num 从 nums 中取出来，基于不同的语言，基于不同的实现，它实际运行的时间是不等的，就算转换成机器码，它对应的机器码的指令数也有可能是不同的，就算是指令数是相同的，同样的一个指令，在我们 cpu 的底层，你使用的 cpu 不同，很有可能，执行的操作也是不同的，所以在实际上我们可能说出 c1 是几条指令，但是却很难说出 c1 到底是多少，c2也是同理，正因为如此，我们在进行时间复杂度时，是忽略这些常数的。

忽略这些常数就意味着什么，就意味着这些 t=2*n+2和t=2000*n+10000算法这些都是 O(n) 的算法，见下面列表：换句话说他们都是线性数据的算法，也就是说我们这个算法消耗的时间是和我们输入数据的规模成一个线性相关的， t=1*n*n+0也线性算法是和我们成平方关系的，他的性能比上面的差，因为他是 O(n^2)的

O(n)和O(n^2)并不代表说 O(n)的算法快于 O(n^2)的算法，我们要看 n 的常数，比如 n=3000的时候，或者 n>3000的时候， O(n^2)消耗的时间是远远大于 O(n)的，n越大 O(n)远远快于 O(n^2)O：描述的是一个算法，也就是说渐进时间复杂度当高阶项和低阶项同时出现的时候，低阶项会被忽略，比如说：T=2*n*n+300n+10当中 2*n*n，是 O(n^2)级别的算法，属于高阶项， 300n是 O(n)的算法低阶项，当n无穷大的时候，低阶项起的作用很小。

3.3 分析动态数组的时间复杂度

3.3.1 添加操作

添加操作总体来说属于 O(n) 级别的复杂度，如下列表

在程序设计中，我们要采用最严谨的设计，需要考虑到最坏的情况，所以我们说添加操作时属于 O(n)级别的复杂度，是因为我们在 addLast的时候，有可能会进行 resize的操作，我们从最坏的情况分析是对的，但是 addLast不可能每次都是进行 resize操作，比如 size 有十个，我们要添加十个元素后才会触发一个 resize,我们要在添加十个元素才会触发一个 resize，因此我们使用最坏情况进行分析的是不合理的，那么分析 addLast时间复杂度呢，请看下面小节。

3.3.2 resize的复杂度分析