数据结构与算法（一）数组的相关概念和底层java实现

一、前言

从今天开始，笔者也开始从0学习数据结构和算法，但是因为这次学习比较捉急，所以记录的内容并不会过于详细，会从基础和底层代码实现以及力扣相关题目去写相关的文章，对于详细的概念并不会过多讲解

二、数组基础

• 数组这个结构，其实就是将数据码成一排进行存放
  
  如上，就是一个数组，有6个空间，可以存放6个元素。且命名可以随意，例如我student数组可以叫students，也可以是studentList。
  具体这个元素是什么类型，在Java中要求是固定的，比如6个Int类型，6个String类型，或者6个Object自定义类型。
• 在数组中，有一个很重要的概念，叫作索引

在计算机的视角中，索引从0开始，之后依次递增，如果我们数组空间为n，那我们最后一个元素的索引是n-1,第一个元素的索引是0，有了索引，我们就可以直接访问数组第i个元素是什么。
例如我现在要对students数组中取索引为2的数据，那么students[2]即可取出，而students[2]对应的是数组的第三个元素。
索引可以有语意，也可以没有语意。例如我是一个学生列表，我的学生学号就对应的索引，此时索引有语意。再或者说我是一个分数列表，那对于这个列表的元素，分数想放在哪个索引对应的空间就放在哪里，此时索引没有语意。

• 代码实现

在java中如果我要声明一个数组，非常简单：
比如我声明一个Int类型的数组，就是int[] arr，String类型数组就是String[]
而给这个数组赋值的对象可以通过new int[n]/new String[n]这样的形式，n代表你想开辟的数组的空间大小，例如拿上面的6个空间的数组举例：

	public static void main(String[] args) {//想要使用数组，就需要事先开辟空间，就必须声明数组能装多少个元素int[] arr = new int[6];}

而我们要对这个数组进行赋值操作也很简单，写一个for循环，我们可以根据java中数组的方法arr.length()对其进行循环，为数组的每一个元素进行赋值吗，arr.length()就是代表这个数组的长度，即数组的空间大小,然后arr[i] = i即可为数组的每一个元素赋值。

	public static void main(String[] args) {//想要使用数组，就需要事先开辟空间，就必须声明数组能装多少个元素int[] arr = new int[6];for (int i = 0; i < arr.length; i++) {arr[i] = i;}}

而通过arr.length()去进行for循环比你要通过直接拿一个具体的数字硬编码的形式去进行赋值要好很多，代码更加的灵活，例如你的数组长度可能会发生变化，你通过arr.length()的话只需要专注于你的数组长度即可。
当然java中声明数组有另外的形式，当你想要在数组声明的时候就有它的初始值，那这种情况下，new int[]方括号内就可以不带空间大小，而是通过new int[]{}的形式，花括号内填写元素的初始值。
例如，我声明一个scores数组，初始化3个初始值，我就可以这样写：

int[] scores = new int[]{99,100,98};

这样我们的数组就开辟成有3个Int值的数组，我们可以写一个for循环打印验证下：

int[] scores = new int[]{99,100,98};for (int i = 0; i < scores.length; i++) {System.out.println(scores[i]);}

当然你也可以使用java的for增强循环，意义就是在scores数组中取出每一个score元素。在这个基础上我把每一个score元素的值打印出来，这种特性是因为数组有这可迭代的能力或者叫作可遍历的能力，这里不过多强调。

int[] scores = new int[]{99,100,98};for (int score : scores) {System.out.println(score);}

大家都可以试一下，两种形式的结果都是一样的。
而我们如果想要修改数组中元素的值，也非常简单，比如我想将上面的scores索引为0的元素的值修改为100，代码如下：

scores[0] = 100;

• 数组优点

数组最大的优点就是快速查询，例如students[2],快速查询索引为2的学生。
之前我们讲解索引的时候说过索引有语意和没有语意的区别，那么为了更好地放大数组的优点，数组最好应用于“索引有语意”的情况。而对于索引没有语意的情况，往往会使用其他的数据结构进行查询，这就是后话了。
很多场景中，虽然我们能给索引定义出来语意，但并非所有语意的索引都适用于数组，例如我想通过以人的身份证号作为索引，去找对应的人的一些属性。而由于身份证号作为索引一般都非常的大，对于计算机来说，开辟一个身份证号数字大小的空间是不值当甚至不可能的，且就算可以也会浪费相当多的空间，例如我数组就十个人，我要用身份证号作为索引去开辟，那势必会浪费特别大的空间。

• 在索引无语义的情况下使用数组
  如果索引有语意，那么使用数组就太简单了，直接根据索引查询具体的元素即可
  但是如果我们就是使用数组去处理索引没有语意的情况，也可以处理，但是会出现很多新的问题：
  ①数组只是一个提供待存放元素的空间的工具
  例如我们的数组有6个空间，但是我们现在需要考察的或者说只放了三个元素，那么访问没有元素的空间可能就是非法的，因为从用户的角度来看，是没有3,4,5对应的元素的。
  
  那么问题一就是索引没有语意，如何表示没有元素的空间
  问题二如何添加元素，如何删除元素？例如我们之前创建数组的时候已经规定好了大小，如果我们要再往其中添加元素超过了预定的空间大小该怎么办呢，这些都会一一解决。
  而java为我们提供的数组是没有这些方法的，我们必须自己编写：
  其实我们可以将Java提供的数组称为静态数组，我们自己编写的数组称为动态数组。
  由于数组本身是静态的,创建的时候必须指定它的大小，我们管这个叫容量capacity，也就是我们的数组空间最多可以装多少个元素。
  ps:我们数组空间最多可以装多少个元素和我们数组空间实际有多少个元素没有关系。我们把数组空间实际有多少个元素称为size,而数组初始化的时候，一个元素都没有，此时size=0,其实就指向了第一个没有元素的索引。而后面对数组操作的时候，我们就需要维护数组的size，例如增加或者删除元素的时候。
  
• 动态数组代码实现

那么我们现在就可以实现开始的动态数组了：

package com.mbw.Array;public class DynamicArray {//初始化数组private int[] array;//数组实际元素个数private int size;//之前讲解过capacity容量这个属性，其实它本质上等于array.length,所以没有必要设计//带有初始容量的构造函数public DynamicArray(int capacity){array = new int[capacity];size = 0;}//不带初始容量的构造函数，所以我们给它预先创建一个容量为10的数组，容量够不够后面可以解决public DynamicArray(){array = new int[10];size = 0;}//判断数组是否为空public boolean isEmpty(){return size == 0;}//获取数组当前元素个数public int gitSize(){return size;}//获取数组容量public int getLength(){return array.length;}
}

三、向动态数组中添加元素

①向数组末尾添加元素
之前说过，size指向数组中第一个没有元素的索引,我们向数组末尾添加元素，其实就相当于在size的位置添加元素，例如我们现在需要向数组末尾添加一个66的元素，其实就相当于是在size=0这个位置添加一个66的元素，与此同时由于元素个数为1，size=1，往后挪一格指向索引为1的没有元素的位置。
那么按照这样的逻辑，我们的代码可以这样写：

	public void addLast(int e){array[size] = e;size ++;}

②向任意位置添加元素
比如我现在想要在索引为1的位置添加一个元素，那么我从size-1的索引对应的元素开始，一直到Index对应的元素为止，这中间的所有原来的元素都要往后挪动一格，然后此时index对应的元素虽然还是原来的值，但是此时我们可以将它放心的把新的值赋值给它了。因为此时我其他的元素已经做了往后挪的处理。最后将size++即可。

那么由上述逻辑，我们可以写出以下程序：

public void add(int index, int e) {//如果size容量，则报错if (size == array.length) {throw new IllegalArgumentException("add failed,array is full");}//如果index比size还要大(中间会出现非法元素)或者index<0，也需报错if (index < 0 || index > size) {throw new IllegalArgumentException("add failed,index should >= 0 or index <= size");}//如果此时index 就等于 size，此时相当于前面的向数组末尾增加元素，不用走for循环if (index == size) {array[index] = e;size++;return;}//然后从最后一个元素开始，一直到需要添加的位置为结尾，将该元素赋值给后一个空间for (int i = size - 1; i >= index; i--) {array[i + 1] = array[i];}array[index] = e;size++;}

那么有了上述逻辑代码，其实我们之前写的向数组末尾添加元素，就可以改写为：

//往数组末尾添加元素public void addLast(int e) {add(size, e);}

那想必你还可以拓展向数组头增加元素的方法：

public void addFirst(int e) {add(0, e);}

然后我们就可以试一下，为了方便后续验证，我们可以重写toString()方便我们查看数组详情：

	@Overridepublic String toString() {return "DynamicArray{" +"array=" + Arrays.toString(array) +", size=" + size + ", capacity=" + getLength() +'}';}

然后试一下刚才我们写的add():

	public static void main(String[] args) {DynamicArray dynamicArray = new DynamicArray();dynamicArray.add(dynamicArray.size, 20);dynamicArray.add(dynamicArray.size, 23);dynamicArray.add(dynamicArray.size, 25);dynamicArray.addLast(100);dynamicArray.addFirst(10);dynamicArray.add(1, 30);System.out.println(dynamicArray.toString());}

四、获取数组索引对应的元素和修改对应索引的元素

这两个方法都比较简单
①获取数组索引对应的元素
我们需要注意index的范围，Index<0不用多说，当Index>=size，我们知道size是指向第一个没有元素的索引，所以我们自然不能让index等于size，哪怕size指向的这个元素确实因为删除方法有值，但其实这个元素仍然是非法的，我们不能让用户访问到。

	//获取index索引上的元素public int get(int index){if(index < 0 || index >= size){throw new IllegalArgumentException("get failed;index should >= 0 or index < size");}return array[index];}

②修改Index索引对应的元素
同理，我们可以写出以下代码：

	//修改Index索引上的元素public void set(int index, int e){if(index < 0 || index >= size){throw new IllegalArgumentException("get failed;index should >= 0 or index < size");}array[index] = e;}

五、包含、搜索和删除

首先说一下包含
①查看元素是否存在数组当中
逻辑很简单，我们只需从索引为0开始，size为结尾遍历一遍我们的数组，如果存在，那么就返回true，如果没有则返回false

	//查看数组是否包含epublic boolean contains(int e){for(int i = 0;i< size; i++){if(array[i] == e){return true;}}return false;}

②返回具体元素对应的索引
这个逻辑其实很像上述之前的包含，若存在，则返回找到的元素的索引，没找到返回无效索引-1

	public int find(int e){for(int i = 0;i< size; i++){if(array[i] == e){return 1;}}return -1;}

但是有些比较细心的朋友可能会觉得这个程序存在纰漏，如果我的数组存在同样的元素值，那这个就不太对了，我们这个程序顶多称为若存在，则返回找到的第一个元素的索引，没找到返回无效索引-1。如果需要详细一点，可以返回一个int数组或者列表，将找到的元素对应的索引全部放到其中返回。
③删除指定位置元素
删除其实逻辑很简单，了解了add其实就是从最后一个元素开始一直到index对应的索引位置结束，将其中的元素往后挪一个位置，删除就是反过来，我们从要删除的索引的后一个位置开始，一直到size前一个（数组最后一个有值元素对应的空间）索引对应的元素，往前挪一格，其实说是挪动，更像是一次赋值,最后size别忘了减一

可能有伙伴会觉得，我这样删除，size减一后，不就和它的意义不一致了吗，因为我的size指向的是第一个没有元素的空间，现在却指向了往前挪动的所有元素中最后一个索引对应的元素，可是大家可以想一下，size指向了有值的元素对客户是否有影响呢，其实是没有的，客户通过方法是访问不到size对应的元素的值的，也不会影响我的add等操作，所以其实size–后存在有值元素，也不会影响后续的操作，那么根据上述逻辑，我们可以完成删除代码：

	//从数组中删除Index位置的元素，返回删除的元素public int remove(int index{//如果size容量，则报错//如果index比size还要大(中间会出现非法元素)或者index<0，也需报错if (index < 0 || index >= size) {throw new IllegalArgumentException("add failed,index should >= 0 or index < size");}int result = array[index];for(int i = index + 1;i < size ; i++){array[i-1] = array[i];}size --;return result;}

那有了删除代码，我们可以同add完成删除第一个和删除最后一个元素：

	public int removeFirst(){return remove(0);}public int removeLast(){return remove(size - 1);}

且大家可以不用担心删除空数组删除的情况，如果说此时数组是空数组（size=0），调用删除第一个元素方法，index=0,那么会被上面remove的if语句中size = index命中从而抛出异常，如果调用删除最后一个元素的方法，idex-1=-1,从而被上面remove的if语句中index < 0命中从而抛出异常.
那我们有些朋友可能不想删除指定位置的元素，而是想从数组中删除特定元素的值。那么我们就可以结合之前的find()和remove()完成这个操作，需要注意的是，由于find存在只能找到第一个元素对应的索引的问题，我们的这个删除特定元素方法也只能删除一个，如果数组存在相同元素的话，那么其实是没有删除干净的，感兴趣的小伙伴可以自行拓展：

	public void deleteElement(int e){int index = find(e);if(index != -1){remove(index);}}

我们可以试验一下：

public static void main(String[] args) {DynamicArray dynamicArray = new DynamicArray();dynamicArray.add(dynamicArray.size, 20);dynamicArray.add(dynamicArray.size, 23);dynamicArray.add(dynamicArray.size, 25);dynamicArray.addLast(100);dynamicArray.addFirst(10);dynamicArray.add(1, 30);System.out.println(dynamicArray.toString());//删除四个元素dynamicArray.remove(1);dynamicArray.deleteElement(100);dynamicArray.removeFirst();dynamicArray.removeLast();System.out.println(dynamicArray.toString());}

最后应该剩下的就是20,23，结果也是正确的，size=2,前两个元素就是20,23.

感兴趣的小伙伴还可以对这个基础的数组进行扩展，比如添加泛型等等，这个届时和后面的动态数组的拓展代码我会一起给一个示范代码

package com.mbw.array;import java.util.Arrays;public class DynamicArray<T> {//初始化数组private T[] array;//数组实际元素个数private int size;//之前讲解过capacity容量这个属性，其实它本质上等于array.length,所以没有必要设计//带有初始容量的构造函数public DynamicArray(int capacity) {array = (T[])new Object[capacity];size = 0;}//不带初始容量的构造函数，所以我们给它预先创建一个容量为10的数组，容量够不够后面可以解决public DynamicArray() {array = (T[])new Object[10];size = 0;}//判断数组是否为空public boolean isEmpty() {return size == 0;}//获取数组当前元素个数public int gitSize() {return size;}//获取数组容量public int getLength() {return array.length;}//往数组末尾添加元素public void addLast(T e) {add(size, e);}public void addFirst(T e) {add(0, e);}public void add(int index, T e) {//如果size容量，则报错if (size == array.length) {throw new IllegalArgumentException("add failed,array is full");}//如果index比size还要大(中间会出现非法元素)或者index<0，也需报错if (index < 0 || index > size) {throw new IllegalArgumentException("add failed,index should >= 0 or index <= size");}if (index == size) {array[index] = e;size++;return;}//然后从最后一个元素开始，一直到需要添加的位置为结尾，将该元素赋值给后一个空间for (int i = size - 1; i >= index; i--) {array[i + 1] = array[i];}array[index] = e;size++;}//获取index索引上的元素public T get(int index){if(index < 0 || index >= size){throw new IllegalArgumentException("get failed;index should >= 0 or index < size");}return array[index];}//修改Index索引上的元素public void set(int index, T e){if(index < 0 || index >= size){throw new IllegalArgumentException("get failed;index should >= 0 or index < size");}array[index] = e;}//查看数组是否包含epublic boolean contains(T e){for(int i = 0;i< size; i++){if(array[i] == e){return true;}}return false;}//查看元素对应的数组索引位置,若存在，则返回找到的第一个元素的索引，没找到返回无效索引-1public int find(T e){for(int i = 0;i< size; i++){if(array[i] == e){return i;}}return -1;}//从数组中删除Index位置的元素，返回删除的元素public T remove(int index){//如果size容量，则报错//如果index比size还要大(中间会出现非法元素)或者index<0，也需报错if (index < 0 || index >= size) {throw new IllegalArgumentException("add failed,index should >= 0 or index < size");}T result = array[index];for(int i = index + 1;i < size ; i++){array[i-1] = array[i];}size --;return result;}public T removeFirst(){return remove(0);}public T removeLast(){return remove(size - 1);}public void deleteElement(T e){int index = find(e);if(index != -1){remove(index);}}@Overridepublic String toString() {return "DynamicArray{" +"array=" + Arrays.toString(array) +", size=" + size + ", capacity=" + getLength() +'}';}public static void main(String[] args) {DynamicArray<Integer> dynamicArray = new DynamicArray<>();dynamicArray.add(dynamicArray.size, 20);dynamicArray.add(dynamicArray.size, 23);dynamicArray.add(dynamicArray.size, 25);dynamicArray.addLast(100);dynamicArray.addFirst(10);dynamicArray.add(1, 30);System.out.println(dynamicArray.toString());dynamicArray.remove(1);dynamicArray.deleteElement(100);Integer removeFirst = dynamicArray.removeFirst();Integer removeLast = dynamicArray.removeLast();System.out.println(removeFirst);System.out.println(removeLast);System.out.println(dynamicArray.toString());}
}

六、动态数组

我们之前实现的数组仍然存在一个问题，它内部其实使用的还是一个java的静态数组，对于静态数组来说，它的容量是有限的，可是很多时候我们使用数组类很难预估我们究竟会放多少元素类，容量太大浪费空间，容量太小又有可能不够用，所以我们需要一种解决方案，使得我们数组容量是可伸缩的，这就是动态数组。

例如对于下面一个capacity=4的数组，目前已经放满了，如果我还想接着往下增加元素，根据现有逻辑是会抛出异常的，但是我们可以通过一些其他方法实现这个操作，我们可以开辟一个新的数组newData，新的数组要比原来的容量大上一些，比如之前是4个空间，我新数组的容量就是8，然后将原来数组的元素放到新数组newData中，从而达成通过NewData取代原来的数组，并且扩容的目的。
那么对于扩容的大小，我们更希望它能和原来的数组是成比例的正相关的，而不是在其基础上增加一个固定的常数，比如我如果固定增加的太小，那么当我的数组容量达到很大时候，这个时候就会频繁触发扩容，反之扩容一次增加的容量太大，那么在一开始数组容量很小的时候，一次性扩容很大的容量就会造成很多的空间浪费。所以我们就每次扩容为原来数组的2倍即可。当然关于倍数的选择和你具体的业务有关，拿我们java的动态数组arrayList来说，它每次扩容就是原来的1.5倍。
所以我们可以有如下代码：

private void resize(int newCapacity){T[] newArray = (T[])new Object[newCapacity];for (int i = 0; i < size; i++) {newArray[i] = array[i];}array = newArray;}

如上risize()扩容方法，大家可能会想for循环，每次新增一旦需要扩容，每次都要for循环，会不会太影响效率，这个我们后面的文章会专门解析这个问题。而对于引用问题，原来的数组由于我们将新数组替代它了，原来的数组就会被java的垃圾回收机制回收掉，不会影响内存空间。下面我们就可以应用resize()了
在add方法，如果满了，则扩容为原来2倍：

	public void add(int index, T e) {//如果index比size还要大(中间会出现非法元素)或者index<0，也需报错if (index < 0 || index > size) {throw new IllegalArgumentException("add failed,index should >= 0 or index <= size");}//如果size=容量，则自动扩容，每次扩容为原来数组容量的2倍if (size == array.length) {resize(2 * array.length);}if (index == size) {array[index] = e;size++;return;}//然后从最后一个元素开始，一直到需要添加的位置为结尾，将该元素赋值给后一个空间for (int i = size - 1; i >= index; i--) {array[i + 1] = array[i];}array[index] = e;size++;}

在remove方法，如果发现当前size是数组容量的1/2，那么我们可以将数组缩小为原来的1/2

	public T remove(int index) {//如果size容量，则报错//如果index比size还要大(中间会出现非法元素)或者index<0，也需报错if (index < 0 || index >= size) {throw new IllegalArgumentException("add failed,index should >= 0 or index < size");}T result = array[index];for (int i = index + 1; i < size; i++) {array[i - 1] = array[i];}size--;//如果发现size=当前数组容量一半，则将数组缩容至原来一半if (size == array.length / 2) {resize(array.length / 2);}return result;}

然后我们可以测试一下：

public static void main(String[] args) {DynamicArray<Integer> dynamicArray = new DynamicArray<>();for (int i = 0; i < dynamicArray.getLength(); i++) {dynamicArray.addLast(i);}System.out.println(dynamicArray.toString());dynamicArray.addLast(100);System.out.println(dynamicArray.toString());dynamicArray.addFirst(101);System.out.println(dynamicArray.toString());dynamicArray.removeLast();dynamicArray.removeLast();System.out.println(dynamicArray.toString());}

结果符合代码逻辑，至此，我们从底层实现的自定义动态数组就完成了。
而对于泛型数组，这里我给一个整体的代码实现，有java功底的朋友应该不会觉得困难：

package com.mbw.array;import java.util.Arrays;public class DynamicArray<T> {//初始化数组private T[] array;//数组实际元素个数private int size;//之前讲解过capacity容量这个属性，其实它本质上等于array.length,所以没有必要设计//带有初始容量的构造函数public DynamicArray(int capacity) {array = (T[]) new Object[capacity];size = 0;}//不带初始容量的构造函数，所以我们给它预先创建一个容量为10的数组，容量够不够后面可以解决public DynamicArray() {array = (T[]) new Object[10];size = 0;}//判断数组是否为空public boolean isEmpty() {return size == 0;}//获取数组当前元素个数public int gitSize() {return size;}//获取数组容量public int getLength() {return array.length;}//往数组末尾添加元素public void addLast(T e) {add(size, e);}public void addFirst(T e) {add(0, e);}public void add(int index, T e) {//如果index比size还要大(中间会出现非法元素)或者index<0，也需报错if (index < 0 || index > size) {throw new IllegalArgumentException("add failed,index should >= 0 or index <= size");}//如果size=容量，则自动扩容，每次扩容为原来数组容量的2倍if (size == array.length) {resize(2 * array.length);}if (index == size) {array[index] = e;size++;return;}//然后从最后一个元素开始，一直到需要添加的位置为结尾，将该元素赋值给后一个空间for (int i = size - 1; i >= index; i--) {array[i + 1] = array[i];}array[index] = e;size++;}//获取index索引上的元素public T get(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("get failed;index should >= 0 or index < size");}return array[index];}//修改Index索引上的元素public void set(int index, T e) {if (index < 0 || index >= size) {throw new IllegalArgumentException("get failed;index should >= 0 or index < size");}array[index] = e;}//查看数组是否包含epublic boolean contains(T e) {for (int i = 0; i < size; i++) {if (array[i] == e) {return true;}}return false;}//查看元素对应的数组索引位置,若存在，则返回找到的第一个元素的索引，没找到返回无效索引-1public int find(T e) {for (int i = 0; i < size; i++) {if (array[i] == e) {return i;}}return -1;}//从数组中删除Index位置的元素，返回删除的元素public T remove(int index) {//如果size容量，则报错//如果index比size还要大(中间会出现非法元素)或者index<0，也需报错if (index < 0 || index >= size) {throw new IllegalArgumentException("add failed,index should >= 0 or index < size");}T result = array[index];for (int i = index + 1; i < size; i++) {array[i - 1] = array[i];}size--;//如果发现size=当前数组容量一半，则将数组缩容至原来一半if (size == array.length / 2) {resize(array.length / 2);}return result;}public T removeFirst() {return remove(0);}public T removeLast() {return remove(size - 1);}public void deleteElement(T e) {int index = find(e);if (index != -1) {remove(index);}}@Overridepublic String toString() {return "DynamicArray{" +"array=" + Arrays.toString(array) +", size=" + size + ", capacity=" + getLength() +'}';}public static void main(String[] args) {DynamicArray<Integer> dynamicArray = new DynamicArray<>();for (int i = 0; i < dynamicArray.getLength(); i++) {dynamicArray.addLast(i);}System.out.println(dynamicArray.toString());dynamicArray.addLast(100);System.out.println(dynamicArray.toString());dynamicArray.addFirst(101);System.out.println(dynamicArray.toString());dynamicArray.removeLast();dynamicArray.removeLast();System.out.println(dynamicArray.toString());}private void resize(int newCapacity) {T[] newArray = (T[]) new Object[newCapacity];for (int i = 0; i < size; i++) {newArray[i] = array[i];}array = newArray;}
}