数据结构篇|数组
1. 简介
在计算机科学中，数组数据结构（英语：array data structure），简称数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。——出自维基百科
2. 数组的使用
int[] arr = new int[10];
for (int i = 0; i < 10; i++){
arr[i] = i;
}
通过上面所示的代码可以看出，首先定义了一个容量为10的数组，然后再通过循环将数组中的元素进行赋值。
int[] scores = new int[]{100,99,66};
for (int i = 0; i<scores.length; i++){
System.out.println(scores[i]);
}
上面所示的是数组的另一种赋值方式，通过手动传入3个数，对数组元素进行赋值。
3. 实现自己的ArrayList
- 实现ArrayList前的准备工作
在实现我们自己的ArrayList之前，首先要创建一个Array类
image.png
public class Array {
private int[] data;
private int size;
}
创建完Array类之后，需要在类中定义一个整形的数组data用来存放数据，然后还要定义一个整形变量size，用来记录数组中元素的个数。
//构造函数，传入capacity设置数组初始容量
public Array(int capacity){
data = new int[capacity];
size = 0;
}
//无参构造函数，默认数组容量为10
public Array(){
this(10);
}
然后再设置两个构造方法，用来实现对数组的初始化，第一个构造方法我们可以传入一个整形的变量capacity，它是用来设置数组容量的，在构造方法中我们就可以对数组进行初始化了，初始化的步骤也就是将capacity传入数组中，并将数组中元素的个数初始化为0。
接下来还可以再设置一个无参的构造方法，可以用在用户不知道需要多少容量时使用，这里我们就使用this关键字对数组的默认大小设置为10。
- 实现getSize()、getCapacity()、isEmpty()
//获取数组中的元素个数
public int getSize(){
return size;
}
//获取数组容量
public int getCapacity(){
return data.length;
}
//判断数组是否为空
public boolean isEmpty(){
return size==0;
}
写完了构造方法之后再为数组添加3个方法，这三个方法的作用如代码的注释所示。
- 实现add()及相关方法
//向第index个位置添加元素e
public void add(int index,int e){
if (size==data.length){
throw new IllegalArgumentException("AddLast failed. Array is full.");
}
if (index<0||index>size){
throw new IllegalArgumentException("Add failed. Index is illegal.");
}
for (int i=size-1;i>=index;i--){
data[i+1] = data[i];
}
data[index] = e;
size++;
}
image.png
接下来我们实现一下向数组中添加元素的方法，因为是添加元素所以需要指定想要添加的位置index和想要添加的元素e，然后我们需要判断一下数组中是否还有剩余空间，如果没有则抛出异常。然后还要对用户传来的index进行判断，如果用来传来了负数或者超出了数组个数的下标，那一定也是不合法的，所以要抛出异常。
对参数合法性的判断已经完成了，那么接下来就实现一下具体的添加方法吧。首先需要将第index位置以及之后的元素全部向后移动1位，这里需要注意不可以从前开始移动，应该从后面开始移动，移动完成之后就会将第index个位置空出，接着我们就对第index个位置进行了元素的添加，添加完成之后不要忘记还需要对size变量进行维护，到了这里我们的添加操作就全部完成了。
//向所有元素后添加一个新元素
public void addLast(int e){
add(size,e);
}
//向所有元素前添加一个新元素
public void addFirst(int e){
add(0,e);
}
接下来基于上面实现的add方法可以再实现两个方法，一个是向数组末尾添加元素，一个是向数组头添加元素。这里需要做的就是直接调用add方法并指定对应的索引和元素。
- 实现get()与set()方法
//获取索引为index的元素
int get(int index){
if (index<0||index>size){
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
return data[index];
}
void set(int index,int e){
if (index<0||index>size){
throw new IllegalArgumentException("Set failed. Index is illegal.");
}
data[index] = e;
}
通常我们在使用数组时，都会希望使用数组的下标来获取对应的元素值，那么我们接下来就实现一下自己的get方法。首先我们会在get方法的参数列表中传入index所以需要判断index的合法性。如果不合法则抛出异常，如果合法就直接返回对应的元素值。
既然有了get方法那么肯定也是要有set方法的。同样set方法中也需要判断下标的合法性，如果合法就将元素e添加到对应的下标处。
- 实现contains()和find()方法
//查找数组中是否包含元素e
public boolean contains(int e){
for (int i = 0; i < size; i++) {
if (e==data[i]){
return true;
}
}
return false;
}
public int find(int e){
for (int i = 0; i < size; i++) {
if (e==data[i]){
return i;
}
}
return -1;
}
关于contains()方法的实现我们首先需要传入想要查找的元素e，然后进行循环，如果有元素和e相同时便返回true，如果直到循环结束也没有找到相同的元素就返回false。与之类似的find()方法是同样的思路，不同的是因为返回值不同所以返回的是元素对应的下标，如果没有找到就返回-1。
- 实现remove()及相关方法
public int remove(int index){
if (index<0||index>=size){
throw new IllegalArgumentException("Remove failed. Index is illegal.");
}
int ret = data[index];
for (int i=index+1;i<size;i++){
data[i-1] = data[i];
}
size--;
return ret;
}
接下来我们来实现删除方法，首先需要传入一个index，那么检查下标合法性也就是必不可少的了。判断完之后将需要删除的元素保存下来留作返回值。通过循环将index位置之后的元素全部向前移动1位，最后不要忘记对size的维护，并将删除了的结果值进行返回。
public int removeFirst(){
return remove(0);
}
public int removeLast(){
return remove(size-1);
}
public boolean removeElement(int e){
int index = find(e);
if (index!=-1){
remove(index);
return true;
}
return false;
}
实现了remove()方法之后，我们可以基于它来实现一些相关的方法，其中removeFirst()和removeLast()方法只需要我们传入对应的下标即可。然后removeElement()方法需要传入想要删除的元素e，并将待删除的元素的下标进行保存，根据上面实现的find()方法可以轻松的完成这个操作。然后进行判断如果index!=-1便调用remove()方法将下标传入然后返回true，如果没有找到的话就返回false。
4.使用泛型
前面我们使用数组实现了增删改查的功能，但是细心的同学也许会发现，这个集合只支持整数类型。如果一个集合只可以支持一种数据类型的话，那显然不是完美的，所以我们在这一点中需要引入泛型。
- 泛型的实现
public class Array<E>
我们只需要在Array类后面指定泛型的类型，在这里我将泛型类型指定为E(Element)，然后对各个方法的参数进行更改即可。
5.实现动态数组
在使用了泛型之后，我们的
ArrayList就已经得到了进步，但是还有一点美中不足的就是数组的容量是固定的，如果我们在创建的时候无法预估有多少数据量的话，传入的容量大了就会造成内存空间的浪费，而传的过小的话就会出现容量不足的尴尬，所以在这节我将以动态数组的方式解决这个问题。
- 具体实现
private void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
首先我们要创建一个方法resize()，需要传入的容量是newCapacity，接着再创建一个新的数组叫做newData，然后对data进行循环遍历将data中的元素全部移动到newData中，然后再将data指向newData，这样便实现了动态数组的方法。
- 动态数组的使用
//向第index个位置添加元素e
public void add(int index,E e){
if (index<0||index>size){
throw new IllegalArgumentException("Add failed. Index is illegal.");
}
if (size==data.length){
resize(getCapacity()*2);
}
for (int i=size-1;i>=index;i--){
data[i+1] = data[i];
}
data[index] = e;
size++;
}
首先，在add()中使用动态数组，当数组中的元素个数和数组的容量相同时调用resize()方法，在这里将新数组的容量设置为原数组容量的2倍。
public E remove(int index){
if (index<0||index>=size){
throw new IllegalArgumentException("Remove failed. Index is illegal.");
}
E ret = data[index];
for (int i=index+1;i<size;i++){
data[i-1] = data[i];
}
size--;
//实现数组的缩容
if (size==data.length/2){
resize(getCapacity()/2);
}
return ret;
}
resize()不仅在添加操作中适用，在删除操作中也同样适用。每当删除完一个元素，对size进行维护之后便对size进行判断，如果元素个数是当前数组容量的一半时，便对数组的容量进行缩小，这里传入的参数是原数组的二分之一。
6.简单的时间复杂度分析
说到数据结构，不得不谈的就是时间复杂度的问题，每次在书中或者网上肯定多多少少的会看到一些像
O(1)、O(n)、O(lgn)、O(nlogn)、O(n^2)这些对复杂度的表示，那么它们到底是什么呢？让我们接着往下看吧！
-
大O是什么意思?
大O描述的是算法的运行时间和输入数据之间的关系。
public static int sum(int[] nums){
int sum = 0;
for (int num : nums) {
sum+=num;
}
return sum;
}
首先看上面的这段程序，我们都可以看出它是计算nums数组中的和的操作，那么这段程序的时间复杂度是多少呢？
它的时间复杂度是O(n)，其中n是nums中的元素个数。这就表示了程序的运行时间和n的大小呈线性关系。
-
为什么要用大O，叫做O(n)?
这个函数在忽略常数的情况下的实际时间为：T=c1*n+c2，其中c1为for循环（循环nums.length次，同时每次执行sum+=num）所用的时间，c2为创建sum并将其进行初始化和return sum所用的时间。
T = 2*n+2; //O(n)
T = 2000*n+10000; //O(n)
上面这两个T在大O的意义下都是O(n)的算法，因为它们都是线性时间的算法。
T = 1*n*n+0; //O(n^2)
这个T的时间复杂度就是O(n^2)的算法，因为它的时间消耗与n呈平方关系。
总结：对以上的两种复杂度的算法进行比较可以看出O(n)时间复杂度的算法是优于O(n^2)的算法的 ，但是这也并不能说明O(n^2)算法就一定比O(n)的算法时间性能差，就比如是在n的数字比较小的时候。所以具体哪个算法性能比较好是需要查看代入的数字的大小才能做出判断的。
-
动态数组的时间复杂度分析
-
添加操作
addLast(e) O(1)
因为向数组末尾添加元素可以直接进行添加，可以在常数时间内完成，所以时间复杂度为O(1)。
addFirst(e) O(n)
因为向数组头添加元素需要将数组中的所有元素全部向后移动1位，所以时间复杂度位O(n)。
add(index,e) O(n)
这个方法的时间复杂度需要看index的取值，如果取的小，那么向后移动的元素就多一些，时间复杂度就是O(n)的，如果取的大，向后移动的元素就会少一些，时间复杂度就是O(1)的。平均而言需要向后移动二分之一的元素，那么时间复杂度就为O(n/2)，因为之前所说时间复杂度的计算会把常常数忽略掉所以时间复杂度为O(n)。 -
删除操作
删除操作与添加操作类似，removeLast(e)是O(1)的时间复杂度，removeFirst(e)是O(n)的时间复杂度，remove(index,e)是O(n/2)=O(n)的时间复杂度。 -
修改操作
修改操作如果可以通过索引进行，那么时间复杂度为O(1)。如果不知道索引那么时间复杂度为O(n)。 -
查询操作
查找操作如果知道索引的话，那么时间复杂度为O(1)，如果不知道索引的话，我们就需要将数组中的元素进行遍历，所以时间复杂度为O(n)。
-
总结：整体来看添加操作的时间复杂度是O(n)的算法，删除操作的时间复杂度也是O(n)的，因为计算时间复杂度通常需要取最坏时间复杂度。修改操作已知索引时复杂度为O(1)，未知索引时时间复杂度为O(n)，查询操作已知索引时复杂度为O(1)，未知索引时时间复杂度为O(n)。
