数组--java--动态数组--有序数组--底层

写在开头：


这篇文章包括数组的基础、一点底层的内容和一些稍微深入的东西。
作为第一个深入学习的数据结构，现在还不太知道怎么样了。有缺点请指出。
还有内容之后在补充。
本来是想和ArrayList源码一起来写进来的，但是发现实在不好插入进来了。还是到时候换一篇文章写了。

基础–java中的数组

数组是应用最广泛的数据存储结构。

因为里面元素是连续存储的，所以数组中的元素的地址可以用索引计算出来。
第$i$个元素的地址：$address=baseAddress(起始索引)+i\ast size$
size是每一个元素所占的字节大小，如int占4，double占8

在许多语言中都把数组当作基本数据类型，但是在java中是把他们当作对象来对待的，所以在创建数组的时候使用new关键字。

创建数组

我们一般会把[]放在类型后面，清晰的代表着数据类型的一部分

int[] arr = new int[n];

像大部分的对象一样，arr只是作为存储这个对象的地址值。且大小固定，一旦创建就不可修改。

空间占用

用int来介绍

• 8字节的markword：记录对象的hash码等状态信息。这个具体会在java类介绍中。
• 4字节的类指针：指定这个对象的类型，数据指向类的字节码文件。
• 4字节的数组大小：所以最高$2^{32}$的容量
• 数据元素+对其字节：内存对齐

初始化数组

创建数组后

• 如果是基本数据类型会自动初始化数组

• 如果是引用类型，则他们会是特殊的null对象

   如果尝试访问null的数据项，会出现Null Point Assignment（空指针赋值错误）
  

对于基本数据类型我们还可以通过{}来初始并创建数组

int[] arr= {1,2,3};

访问元素

第一个元素下标为0，所以容量为10的数组，下标为0-9.
越界访问会出现Array Index Out Of Bounds（数组越界错误）错误

插入查找

在n位置设置为num

arr[n]=num;

查询n位置的数

System.out.println(arr[n]);

删除元素

删除第n个元素
想要删除的话，将n后面的元素全部往前一个就可以了。

for(int i = n-1;i<arr.length-1;i++{arr[i]=arr[i+1]
}
arr[arr.length-1]=0;

动态数组

因为普通数组，大小是写死的。很不方便，所以我们需要动态数组。
在java中有ArrayList类是已经实现了动态数组了。

这里介绍的是手写动态数组，但是不考虑泛型，只用整形数字。

想要实现动态数组，那么我们需要一些属性来标记

• 数组：我们需要一个基本数组来存储。
• 大小：我们需要记录数组已经存储了的大小。
• 容量：记录数组的大小，在不够用的时候进行扩容处理。

public class Array{private int size = 0;private int capacity = 8;private int[] array = new int[capacity];
}

添加
这个应该是用的最多的，所以我们先设计这个。
在不考虑扩容的情况下，在最后设置成element，大小加一就可以了。

public void add(int element){array[size] = element;size++;
}

插入
实现在index位置插入element：
我们需要将index之后的元素往后移动一位就可以实现了

public void insert(int index,int element){System.arraycopy(array,index,array,index+1,size-index);array[index]=element;
}	

我们需要对其进行容量判断，并实现扩容。

扩容

为了节省空间，在需要使用的时候在给数组空间。

private int[] array={};

对于扩容我们首先判断容量是否是0。

public void grow(){if(array.length > 0){capacity += capacity>>1；array = Arrays.copyOf(array,capacity);}else{capacity = 8;array = new int[capacity];}
}

插入和添加

然后我们可以改进我们的代码了。
是否满

private boolean isFull(){return size == capacity;
}

在index位置插入元素

public void insert(int index, int element){if (isFull()){//判断是否需要扩容grow();}if (index < 0 || index > size){//判断index是否合法throw new IndexOutOfBoundsException("Index: " + index + ", Size " + size);}System.arraycopy(array, index, array, index + 1, size - index);//将index后面的元素往后移动array[index] = element;size++;
}

在最后位置添加就可以复用代码了。

public void add(int element){insert(size,element);
}

测试：
测试代码中重写了toString方法，在下一节有。

重写toString

我们需要toString方法输出的只是我们的数组就可以了，所以这里需要重写toString方法。
这里建议使用append字符，而不是字符串，效率高。

@Override
public String toString() {StringBuilder sb = new StringBuilder();sb.append('[');for (int i = 0; i < size-1; i++) {sb.append(array[i]).append(',').append(' ');}sb.append(array[size-1]);sb.append(']');return sb.toString();
}

删除

将index索引位置元素删除：

• 去除index索引元素
• 后面元素前移

public int remove(int index){//判断index是否合法if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size " + size);}int oldValue = array[index];//去除元素int numMoved = size - index - 1;//查看后面元素的数量if (numMoved > 0)System.arraycopy(array, index+1, array, index,numMoved);//将后面的元素往前移动array[--size] = 0; // clear to let GC do its workreturn oldValue;//返回删除的元素
}

二维数组

创建数组

int[][] array = new int[2][2];

初始化

int[][] arry = {{1,2,3},{2,3,4}
};

二位数组的实现：
起始就是一个数组存储着各种数组的地址值。

二维数组注意点

因为有缓存机制的影响，所以我们尽量在遍历的时候同一层的使用如：
int[x][y]

for(int i = 0;i<x;i++)for(int j = 0;j<y;j++)。。。

这样子速度会更快。

有序数组

在有序数组中，因为查询位置则会成为重点。所以我们会选择二分查询来加快速度。但不会书写二分查询的代码，而是直接调用API，不过需要学习的可以点击链接去看看。而动态数组中的内容也不在重复。
有序数组需要在动态数组的基础上实现。
很多也是复用了代码。
下面是不同点：

• 对于给定位置插入和删除，我们不再对外公开所以权限给位private
• 查询使用的Arrays的二分查询的api
• 不用在判断位置是否合法了

实现

private int size = 0;
private int capacity = 0;
private int[] array = {};//扩容
public void grow() {if (array.length > 0) {capacity += capacity >> 1;array = Arrays.copyOf(array, capacity);} else {capacity = 8;array = new int[capacity];}
}//插入数据
private void insert(int index, int element) {if (isFull()) {//判断是否需要扩容grow();}if (index < 0 || index > size) {//判断index是否合法throw new IndexOutOfBoundsException("Index: " + index + ", Size " + size);}System.arraycopy(array, index, array, index + 1, size - index);//将index后面的元素往后移动array[index] = element;//插入元素size++;
}public void add(int element) {if (isFull()) {//判断是否需要扩容grow();}//二分查找元素应该插入的位置int i = Arrays.binarySearch(array, 0, size, element);if (i < 0) {i = -i - 1;}insert(i, element);
}private boolean isFull() {return size == capacity;
}public boolean delete(int index) {int i = Arrays.binarySearch(array, 0, size, index);if (i<0){return false;}remove(i);return true;
}
private void remove(int index) {int numMoved = size - index - 1;//查看后面元素的数量if (numMoved > 0)System.arraycopy(array, index + 1, array, index,numMoved);//将后面的元素往前移动array[--size] = 0; // clear to let GC do its work
}@Override
public String toString() {StringBuilder sb = new StringBuilder();sb.append('[');for (int i = 0; i < size - 1; i++) {sb.append(array[i]).append(',').append(' ');}sb.append(array[size - 1]);sb.append(']');return sb.toString();
}

测试