前言

本章详细阐述了数组这一种线性数据结构的使用方法以及相关操作。

数组的基本使用方法

下面程序示范了数组的基本使用方法。

package 数组;public class 数组的基本使用 {public static void main(String[] args) {//创建一个数组int[] arr1 = new int[3];//获取数组长度int length1 = arr1.length;//打印数组长度System.out.println("arr1's length" + length1);//访问数组中的元素：数组名[下标] 注意：下标从0开始，最大可以取到：数组长度-1int element0 = arr1[0];//打印数组第一个元素的值System.out.println("element0:"+element0);//为数组中的元素赋值arr1[0] = 99;System.out.println("element0:"+element0);arr1[1] = 98;arr1[1] = 97;//遍历数组for (int i = 0; i < length1; i++) {System.out.println("arr1 element"+i+":"+arr1[i]);}//创建数组的另一种方式，创建同时为数组中的元素赋值int[] arr2 = new int[]{90,98,97};}
}

但从上面的程序中我们可以很容易的看出来，就是数组的长度拥有不可变性，因为数组一旦被定义之后，即长度和地址空间就是确定的了，想要更改就很不容易，对其元素的增加和删除都会很麻烦，但麻烦归麻烦，我们有解决办法。

数组元素的添加

比如原数组arr长度为3并且有三个值，现在我们想要让该数组添加一个新的值在后面，怎么办呢？
我们的想法是：
因为数组长度不可变，且原数组arr长度为3并且有三个值，那么我们会新建一个数组叫newArr，这个数组我们定义长度为4，我们将arr原数组的三个值都赋给newArr这个新数组，然后将newArr的最后一个元素位置赋上要添加的那个元素的值，最后将arr引用指向我们的新数组newArr即可。
代码如下：

package 数组;import java.util.Arrays;public class 数组的基本使用 {public static void main(String[] args) {//解决数组长度不可变的问题int[] arr = new int[]{9,8,7};//快速打印数组中的元素方法System.out.println(Arrays.toString(arr));//要添加到数组的新元素int dst = 6;//创建一个新数组，长度为原数组的长度+1int[] newArr = new int[arr.length+1];//把原数组的值都赋给新数组//注意这里的终止循环条件应该是i小于原数组的长度//如果是小于新数组的长度的话，因为新数组比原数组长的缘故，会导致数组下标越界异常for (int i = 0; i < arr.length; i++) {newArr[i] = arr[i];}//打印一下新数组的元素System.out.println(Arrays.toString(newArr));//将新数组的最后一个值赋上我们的目标添加元素newArr[3] = dst;//将arr原数组的引用指向我们的新数组arr = newArr;//打印arr数组System.out.println(Arrays.toString(arr));}
}

数组元素的删除

比如现在我们有一个数组，它包含的元素有9，8，7，6，5，现在我们要删除7这个元素，怎么做？
我们的想法是：
同上面添加元素的方法相同，因为数组的不可变性，所以我们要创建一个新数组newArr，它的长度定义为原数组长度-1（因为是删除一个元素），然后我们只要将除了要删除的元素以外的其他元素都放进新数组里面，最后将原数组的引用指向新数组即可。
代码如下：

package 数组;import java.util.Arrays;public class 数组的基本使用 {public static void main(String[] args) {//目标数组int[] arr = new int[]{9,8,7,6,5};//已知要删除的元素是7，,其下标为2int dst = 2;//创建一个新数组，原数组长度为5，那么新数组长度为5-1=4int[] newArr = new int[4];//使用循环将原数组的值赋进新数组中for (int i = 0; i < newArr.length; i++) {//要删除的元素的前面的所有元素，那么直接赋值if(i < dst){newArr[i] = arr[i];}else{//到要删除的元素的后面的所有元素了//因为原数组arr比新数组newArr多一个要被删除的元素，所以应该将其加1newArr[i] = arr[i+1];}}//将原数组的引用指向我们所创建的新数组arr = newArr;//输出答案System.out.println(Arrays.toString(arr));}
}

数组元素的插入

这算一个上面删除问题的一个延伸叭，思想都差不多，直接上代码：

package 数组;import java.util.Arrays;public class 数组的基本使用 {public static void main(String[] args) {//目标数组int[] arr = new int[]{9,8,6,5};//已知要插入的元素是7,其目标插入的位置下标为2int dstNum = 7; //插入的元素值int dstLoc = 2; //插入的数组中的位置//创建一个新数组，原数组长度为4，那么新数组长度为4+1=5int[] newArr = new int[5];//使用循环将原数组的值赋进新数组中for (int i = 0; i < newArr.length; i++) {//当i 小于 dstLoc时，直接赋值即可if(i < dstLoc){newArr[i] = arr[i];}else if(i == dstLoc){//当i 等于 dstLoc时，将目标插入值赋给新数组newArr[i] = dstNum;}else{//当i 大于 dstLoc时，因为原数组比新数组少一个，//且因为在i == dstLoc判断时i自加了一次，// 所以原数组此时下标应该-1来给新数组进行赋值//否则将会数组越界异常newArr[i] = arr[i-1];}}//将原数组的引用指向新数组arr = newArr;//打印答案System.out.println(Arrays.toString(arr));//将原数组的引用指向我们所创建的新数组}
}

类ArrayList集合的底层实现过程

但是在实际使用当中，我们在进行数组的增删改查时不会像上面一样写的这么繁琐，这是因为Java的基础类库中已经替我们封装好了一些数据结构集合API，我们可以直接使用，比如ArrayList，现在我们可以自己来实现一个ArrayList集合，通过上面的知识，可以巩固一下基础，以加深对数组这种数据结构的理解：

package 数组;import java.util.Arrays;public class MyArray {//类变量//创建一个用于存储数据的数组private int[] elements;//方法//new对象时就初始化这个数组public MyArray(){elements = new int[0];}//获取数组长度public int size(){return elements.length;}//往数组末尾添加一个元素public void add(int element){//创建一个新数组int[] newArr = new int[elements.length+1];//把原数组中的元素赋值到新数组中for (int i = 0; i < elements.length; i++) {newArr[i] = elements[i];}//把添加的元素放入到新数组中newArr[elements.length] = element;//使用新数组替换旧数组elements = newArr;}//删除数组中的元素,index是要删除第几个位置元素的索引public void delete(int index){//判断下标是否越界if(index < 0 || index > elements.length-1){throw new RuntimeException("数组下标越界异常");}//创建一个新数组,长度为原数组-1int[] newArr = new int[elements.length-1];//循环将原数组的值放入新数组中for (int i = 0; i < newArr.length; i++) {//i 小于 要删除目标位置元素的索引，则直接赋值即可if(i < index){newArr[i] = elements[i];}else{ //i 大于等于 要删除目标位置元素的索引时，则原数组的索引应该+1再赋值newArr[i] = elements[i+1];}}//将原数组引用指向新数组elements = newArr;}//取出指定位置的元素,index是获取哪一个元素的下标索引public int get(int index){return elements[index];}//插入一个元素到指定位置,index插入的位置索引，element是插入的元素值public void insert(int index, int element){//判断下标是否越界if(index < 0 || index > elements.length-1){throw new RuntimeException("数组下标越界异常");}//创建一个新数组int[] newArr = new int[elements.length+1];//将原数组中的元素赋值到新的数组中for (int i = 0; i < elements.length; i++) {//目标位置之前的元素，直接赋值if(i < index){newArr[i] = elements[i];}else{ //目标之后的元素newArr[i+1] = elements[i];}}//执行完上面的循环之后我们会发现，我们需要插入的元素还没插//所以我们在循环结束后，将其插入新数组中newArr[index] = element;//将原数组引用指向新数组elements = newArr;}//替换指定位置的元素public void set(int index,int element){//判断下标是否越界if(index < 0 || index > elements.length-1){throw new RuntimeException("数组下标越界异常");}elements[index] = element;}//打印所有元素到控制台public void show(){System.out.println(Arrays.toString(elements));}}

数组的线性查找算法

功能：输入我们要查找的元素的值，然后进行查找，查找成功则返回该元素位置的下标，找不到则返回-1
代码如下：

public class Main {public static void main(String[] args) {//查找的目标数组int[] arr = new int[]{2,3,5,6,8,4,9,0};//查找的目标元素值int target = 8;//查找的目标元素所在下标int index = -1;//遍历数组查找所求的目标值for (int i = 0; i < arr.length; i++) {if(arr[i] == target) {index = i;break; //找到之后停下循环，以节省运行时间}}//输出index，为-1则没有找到，不为-1则已经找到System.out.println("index: "+index);}
}

数组的二分查找算法

线性查找算法效率比较低，而二分查找则会高些。
但是二分查找算法也有缺点，它有前置需求就是：我们所要查找的这个数组必须是有序的，否则不能使用二分查找。
思路：

用一个begin开始指针指向数组的第一个元素，用一个end指针指向数组的最后一个元素，再用一个mid指针指向数组的中间元素（即(end+begin)/2的值），怎么样，这二分是不是很形象？
然后每一次循环，先判断查找的目标值是否与我们的中间mid值相等，相等则说明找到了不相等则说明没有，这个时候再判断我们的中间值是比目标值大还是小，因为数组是有序的，所以如果中间值比目标值大，那么我们第二次循环缩小查找范围，查找中间值往左的区域（因为目标值小于我们的中间值，说明在左侧），即end值发生变化，它将指向mid - 1的位置（因为mid值已经与目标值比较过了，所以指向mid-1而不是mid），而这时mid也要刷新，它将在左侧区域去指向一个新的中间值，即mid = (begin+end)/2;
但如果我们的中间值是比目标值小的话，分析思路同上，那么目标值应该是位置我们中间值的右侧，这时我们改变的则是begin的值，它将指向mid+1的位置，此时也要刷新mid的值。然后如此反复循环，直到查找到我们要的目标元素或者查找完了所有元素。
但我们应该有一个循环结束的标记，即在所有元素都被查找完之后也没查找到目标值时起作用，那么什么时候才是查找完呢？
其实很好想，就是当左边的指针（begin）变化到了右边指针（end）的后面（或相等于右边指针）时，表示所有元素已经被遍历完。

代码如下：

public class Main {public static void main(String[] args) {//目标数组，必须有序int[] arr = new int[]{1,2,3,4,5,6,7,8,9};//目标元素int target = 8;//begin指针指向数组的第一个元素int begin = 0;//end指针指向数组的最后一个元素int end = arr.length-1;//mid指针记录每一次查找的中间位置int mid = (begin+end) / 2;//记录查找元素目标的下标索引int index = -1;//循环查找while (true){//判断此时是否已经遍历完所有元素if(begin >= end) break;//判断中间的这个元素是不是我们的目标查找元素if( arr[mid] == target){index = mid;break;}else{//中间这个元素不是我们要查找的元素//那么我们判断它是比我们的目标元素的索引位置要大还是小if(arr[mid] > target){//把结束位置调整到中间位置的前一个位置end = mid - 1;}else{begin = mid + 1;}}//调整完end和begin位置之后，要更新我们的中间位置指针midmid = (begin + end) / 2;}//循环结束，输出index看找没找到System.out.println("index: "+index);}
}

数组实现栈数据结构

栈就不用多说了吧，就是类似于压子弹的过程，添加元素和删除元素都只能从一端进行的数据结构就是栈。
如图：
在这里插入图片描述
注意：出栈也只能从最上面的栈顶出栈。
代码实现：

package 数组;public class MyStack {//栈的底层我们使用数组来存储数据int[] elements;public MyStack(){elements = new int[0];}//压入栈元素public void push(int element){//创建一个新数组int[] newArr = new int[elements.length+1];//把原数组中的元素赋值到新数组中for (int i = 0; i < elements.length; i++) {newArr[i] = elements[i];}//把添加的元素放入到新数组中newArr[elements.length] = element;//使用新数组替换旧数组elements = newArr;}//返回栈顶元素并弹出该元素public int pop(){//当栈内没有元素时，pop应该抛异常if(elements.length == 0) throw new RuntimeException("栈空异常，无法POP");//先取出数组的最后一个元素int element = elements[elements.length - 1];//然后我们创建一个新的数组来代替原来少了栈顶元素的那个数组int[] newArr = new  int[elements.length - 1];//循环赋值for (int i = 0; i < newArr.length; i++) {newArr[i] = elements[i];}//原数组引用指向新数组elements = newArr;return element;}//查看栈顶元素public int peek(){//这不就是查看数组的最后一个元素吗return elements[elements.length - 1];}//判断栈是否为空public boolean isEmpty(){return elements.length == 0;}}

数组实现队列数据结构

这个感觉也很基础叭…和栈不一样，队列遵循先进先出原则，也就是一段进行数据的添加，另一端则进行数据的删除。
如图：
在这里插入图片描述