Java实现基本数据结构（一）——数组
文章目录
- 数组概念
- Java中的数组
- Java语言实现数组类
- 设计一个静态整型数组类
- 实现泛型
- 设计一个动态泛型数组类
数组概念
所谓数组，是有序的元素序列。 若将有限个类型相同的变量的集合命名，那么这个名称为数组名。 在数据结构中，数组是一种线性表，就是数据排列成一条直线一样的结构。在内容空间中，数组的表现是一块连续的内存和储存有相同的数据类型。正因为这个特性，数组可以实现通过索引下标，在O(1)的时间复杂度内快速检索某个数据，这就是“随机访问”。但是由于内存空间是连续的，所以数组在进行插入和删除操作时，就需要对数据进行维护，进行大量的数据搬移工作。
Java中的数组
Java中的基础数组是一种静态数组，在创建的时候空间就是固定的，后期无法进行扩容或者缩容。 其创建方法如下
int[] arr = new int[10]; //创建一个容量为10的int型数组String[] strArr = new String[10] //创建一个容量为10的字符串数组;基础数组其实并不符合数据结构中对于数组的定义，因为基础数组无法自动扩容和缩容。 在JDK中，其实也实现了可以动态扩容的数组，比如常用的java.util.ArrayList这个类，就是一个动态的泛型数组类。 泛型：泛型是程序设计语言的一种特性。允许程序员在强类型程序设计语言中编写代码时定义一些可变部分，那些部分在使用前必须作出指明。比如在ArrayList类中，我们实例化的时候，需要指定存储的数据类型，这个类本身是可以接收实例化时指定的任意数据类型（基础数据类型除外，只能使用基础数据类型的包装类）。
Java语言实现数组类
在本文中，我们将从数据的设计开始，抛弃JDK已经实现的ArrayList类，重新通过Java语言实现一个数组的数据结构类，从底层理解这个数据结构的原理与思想。
设计一个静态整型数组类
首先，我们先设计一个静态的数组，以int数组为例。不考虑扩容，先从最简单的类来理解数组的基本功能。 数组可以表示为下图：
上图代表一个容量为7，里面每个空间存储了一个int类型的 1 ，这样一个数组。 数组最大的优点就是通过索引值快速查询数据，比如array[2]可以快速查询到第三个空间中的数据 1 。根据这个优点，我们可以想到，数组比较适合存储索引有语义的数据，比如成绩单这种，我们把名次当做索引，分数当做数据用一个数组存储起来，就可以快速获取某个名次的分数。 按照这个数组，我们可以设计一个数组类，首先设计好数组的功能：
- 要能获取数组中的数据个数。
- 要能获取数组的容量。
- 要能判断数组是否为空。
- 要能向数组中插入元素
- 要能从数组中查询元素
- 要能从数组中删除元素
根据上述功能，我们先进行代码的编写实现这个类的前三个功能：获取元素个数，获取数组容量，判断数组是否为空(在后续的代码中，我们将省略Java的包名，直接对类的主体进行展示)：
public class Array {
private int[] data; // 定义一个基础数组，用来存放数据。
private int size; // 用记录数组中的数据个数。
// 构造函数，实例化的时候需要指定一个容量capacity对数组进行初始化
public Array(int capacity) {
data = new int[capacity];
size = 0;
}
// 无参构造，实例化时不指定容量将默认为10
public Array() {
this(10); // 调用有参构造函数
}
// 获取数组中元素的个数
public int getSize() {
return size;
}
// 获取数组的容量
public int getCapacity() {
return data.length; // 这里不可以直接return capacity，因为capacity不是成员变量。
}
// 判断当前数组是否为空
public boolean isEmpty() {
return size == 0;
}
}到这里，我们已经封装了一个Array数组类，实现了一部分基础功能，下面我们将实现向数组中添加元素的功能。向数组中添加元素的原理如下图所示：
我们想把77这样一个元素插入到索引为1的位置上，作为数组这样一种数据类型来讲，要想在数组中间插入元素，需要将插入位置开始的元素，全部向后面移动一个位置，这是数组的性质。
如上图所示，我们需要将88，99，100三个元素从索引1，2，3的位置，挪动到索引2，3，4位置上，再将77插入到索引1的位置上。 在这一过程中，我们需要注意的点有以下几点：
- 数组的容量是否已满，如果数组已经满了，就没有办法向后挪动，再插入元素了。
- 插入的位置一定是数组的有效位置。理解size和data.length的区别，一个是用户能看到的长度，一个是数组的容量，data.length 减 size这一部分的元素，用户是看不到的，我们对用户屏蔽。
- 每次插入后，数组的size指针需要进行维护，向后移动一个距离，代表元素数+1.
我们将这一过程变成代码（针对某一个函数，我们只展示该函数的代码块，在章节末尾再将所有代码整合进类中，以此减少文章的行数，更有利于阅读）：
public class Array {
// 向数组中索引为index的位置插入一个元素
public void add(int index, int e) {
// 如果数组已经满了，就抛出异常，添加失败
if(size == data.length)
throw new IllegalArgumentException("Array is full.");
// 如果索引值小于0或者索引值大于了数组元素的个数，抛异常
if (index < 0 || index > size)
throw new IllegalArgumentException("Wrong index.");
// 将index位置开始的元素向后移动一格
for (int i = size - 1 ; i >= index ; i--)
data[i + 1] =data[i];
// 将e插入到index索引位上
data[index] = e;
// 维护元素个数+1
size ++;
}
// 一个将元素e快速插入数组头部方法
public void addFirst(int e) {
add(0, e);
}
// 一个将元素e快速插入数组尾部的方法
public void addLast(int e) {
add(size, e);
}
}至此，我们完成了数组添加元素的操作，下面我们来完成从数组中查询和修改元素的操作：
- 查询索引为index位置的元素：根据数组的性质，直接返回data[index]的值就可以。
- 查询元素e是否存在在数组中：数组中查询是否存在元素e，就需要对数组进行遍历。
- 修改索引为index位置的元素：直接将data[index]进行更新即可，这是java基础数组的操作方法。
- 从索引为index位置删除元素：该操作和插入元素可以看做是相反的操作，我们将一个元素删除，其实就是将index之后的元素前移一位，index位置的元素就被覆盖掉了。操作后对size进行维护，size–。
代码实现：
public class Array {
// 查询索引为index位置的元素e
public int get(int index) {
// 如果索引值小于0或者索引值大于了数组元素的个数，参数不合法，抛异常
if (index < 0 || index > size)
throw new IllegalArgumentException("Wrong index.");
return data[index];
}
// 查询数组中是否存在元素e
public boolean isExist(int e) {
for (int i = 0; i < size; i++)
{
if (data[i] == e)
return true;
}
return false;
}
// 查询元素e在数组中的位置
public int findIndex(int e) {
for (int i = 0; i < size; i++)
{
if (data[i] == e)
return i;
}
// 没有找到元素e就返回-1
return -1;
}
// 从数组中移除索引为index位置的元素，并将该元素返回
public int remove(int index) {
if (index < 0 || index > size)
throw new IllegalArgumentException("Wrong index");
// 记录data[index]元素，最后返回变量ret
int ret = data[index];
// 从index+1开始往前覆盖数组
for (int i = index + 1; i < size; i++)
data[i-1] = data[i];
size --;
return ret;
}
// 一个快速删除头部元素的方法
public int removeFirst() {
remove(0);
}
// 一个快速删除尾部元素的方法
public int removeLast() {
remove(size);
}
// 从数组中删除元素e
public void removeElement(int e) {
int index = findIndex(e);
if (index != -1)
remove(index);
}
}OK！写到这里，我们就完成了这个数组类的所有基础功能，当然这些功能有一些可能在实际中并不常用，我们在学习的时候还是以了解底层实现思想为主，就写的比较详细。 最后，我们将重写一下toString函数，来完成数组的输出功能：
public class Array {
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
res.append('[');
for (int i = 0; i < size - 1; i++) {
res.append(data[i]);
if (i != size)
res.append(", ");
}
res.append(']');
return res.toString();
}
}好了，我们将所有代码整合起来，就完成了我们通过Java代码实现的一个静态int型数组，代码如下：
public class Array {
private int[] data; // 定义一个基础数组，用来存放数据。
private int size; // 用记录数组中的数据个数。
// 构造函数，实例化的时候需要指定一个容量capacity对数组进行初始化
public Array(int capacity) {
data = new int[capacity];
size = 0;
}
// 无参构造，实例化时不指定容量将默认为10
public Array() {
this(10); // 调用有参构造函数
}
// 获取数组中元素的个数
public int getSize() {
return size;
}
// 获取数组的容量
public int getCapacity() {
return data.length; // 这里不可以直接return capacity，因为capacity不是成员变量。
}
// 判断当前数组是否为空
public boolean isEmpty() {
return size == 0;
}
// 向数组中索引为index的位置插入一个元素
public void add(int index, int e) {
// 如果数组已经满了，就抛出异常，添加失败
if(size == data.length)
throw new IllegalArgumentException("Array is full.");
// 如果索引值小于0或者索引值大于了数组元素的个数，抛异常
if (index < 0 || index > size)
throw new IllegalArgumentException("Wrong index.");
// 将index位置开始的元素向后移动一格
for (int i = size - 1 ; i >= index ; i--)
data[i + 1] =data[i];
// 将e插入到index索引位上
data[index] = e;
// 维护元素个数+1
size ++;
}
// 一个将元素e快速插入数组头部方法
public void addFirst(int e) {
add(0, e);
}
// 一个将元素e快速插入数组尾部的方法
public void addLast(int e) {
add(size, e);
}
// 查询索引为index位置的元素e
public int get(int index) {
// 如果索引值小于0或者索引值大于了数组元素的个数，参数不合法，抛异常
if (index < 0 || index > size)
throw new IllegalArgumentException("Wrong index.");
return data[index];
}
// 查询数组中是否存在元素e
public boolean isExist(int e) {
for (int i = 0; i < size; i++)
{
// 泛型类中的值比较需要用equals方法
if (data[i].equals(e))
return true;
}
return false;
}
// 查询元素e在数组中的位置
public int findIndex(int e) {
for (int i = 0; i < size; i++)
{
// 泛型类中的值比较需要用equals方法
if (data[i].equals(e))
return i;
}
// 没有找到元素e就返回-1
return -1;
}
// 从数组中移除索引为index位置的元素，并将该元素返回
public int remove(int index) {
if (index < 0 || index > size)
throw new IllegalArgumentException("Wrong index");
// 记录data[index]元素，最后返回变量ret
int ret = data[index];
// 从index+1开始往前覆盖数组
for (int i = index + 1; i < size; i++)
data[i-1] = data[i];
size --;
return ret;
}
// 一个快速删除头部元素的方法
public int removeFirst() {
return remove(0);
}
// 一个快速删除尾部元素的方法
public int removeLast() {
return remove(size);
}
// 从数组中删除元素e
public void removeElement(int e) {
int index = findIndex(e);
if (index != -1)
remove(index);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
res.append('[');
for (int i = 0; i < size - 1; i++) {
res.append(data[i]);
if (i != size)
res.append(", ");
}
res.append(']');
return res.toString();
}
}最后我们创建一个测试用例来测试一下我们自己实现的Array类：
public class Main {
public static void main(String[] args) {
Array arr = new Array(8);
// 从数组尾部依次插入0-7
for (int i = 0; i < 8; i++) {
arr.addLast(i);
}
System.out.println(arr.toString());
arr.remove(5);
System.out.println(arr.toString());
arr.removeElement(2);
System.out.println(arr.toString());
}
}输出结果为：
可以看到，我们这个数组成功实现了插入，指定位置移除与指定元素移除的操作。 静态数组的讲解到此就结束了。
实现泛型
我们前文所创建的Array类是一个只能存储int元素的数组，如果我们想要存储String类型呢？ 此时，Java中的泛型机制就可以很好的帮助到我们。泛型的写法很简单，只需要在类名后面加上<>，尖括号中填写任意一个大写字符，比如一般写成，就是声明一个泛型类。此时，E表示的就是派生自Object的任意类。我们在实例化该类时，就需要指定存储的数据类型。（所以此时无法输入基本数据类型如int，只能使用包装类Integer。） 需要注意的是，在泛型类中，由于有些类无法使用 == 的方式对值进行相等比较（比如对象的引用），在isExist()和findIndex()函数中，我们需要用equals方法进行值的比较：
data[i].equals(e)我们将上文的Array类的一部分代码拿出来作为示例，将它泛型化，相信大家可以很快的理解泛型类的实现。
public class Array<E> { //泛型
private E[] data; // 定义一个存储E类型元素的数组，用来存放数据。
private int size; // 用记录数组中的数据个数。
// 构造函数
public Array(int capacity) {
// 由于JAVA中不支持泛型数组，我们需要用对Object数组造型的方法来达到泛型的目的
data = (E[])new Object[capacity];
size = 0;
}
// 向数组中索引为index的位置插入一个元素e
public void add(int index, E e) {
if(size == data.length)
throw new IllegalArgumentException("Array is full.");
if (index < 0 || index > size)
throw new IllegalArgumentException("Wrong index.");
for (int i = size - 1 ; i >= index ; i--)
data[i + 1] =data[i];
data[index] = e;
size ++;
}
}我们可以看到，此时我们将int e，这样一种传入参数，全部用E e来替换，这就是泛型类的使用方法。 学会了使用泛型类，下面我们就将数组这样的一种数据结构完整的实现——加入扩容机制。
设计一个动态泛型数组类
之前我们提到过，JDK中已经实现了一个ArrayList这样一个泛型类，平时工作与学习我们可以直接拿来使用。但在本章节中，作为学习，我们将亲自动手设计并实现一个动态数组，来学习数据结构的底层实现。
Java中的数组，其实没有真正意义上的动态性，我们只能通过自己的方法来实现这样一种效果。 最直观和最实用的方法，就是当我们当前的数组容量装满之后，我们新创建一个新的数组，新数组的容量是之前旧数组的x倍，再将旧的数组元素全部拷贝到新数组中，后面我们丢弃旧的数组，维护新的数组就可以。其实JDK中很多的类都使用了这一思想，比如说常用的ArrayList和HashMap。 按照这种思想，我想大家其实已经有了一定的思路，我们只需要给前文完成的静态数组添加进一个扩容函数，每当数组满了，就新建数组拷贝数据，就完成了动态数组的功能。
首先，我们给数组设计一个扩容函数resize();
public class ArrayList<E> {
private E[] data; // 定义一个基础数组，用来存放数据。
private int size; // 用记录数组中的数据个数。
// 数组扩容系数，当数组的元素个数大于等于数组的容量*系数时，进行扩容
private double resizeRatio = 0.75;
// 扩容方法，对数组进行扩容，该方法对用户屏蔽，所以私有
private void resize(int newCapacity) {
E[] newData = (E[])new Object[newCapacity];
for (int i = 0; i < size; i++)
newData[i] = data[i]; // 拷贝数据
// 将对象的引用更新，此时指针指向了新数组的内存地址
data = newData;
}
}扩容方法写好之后，我们就可以改写我们的插入方法，在之前的静态数组中，如果数组满了，我们就报错。有了扩容方法之后，数组满了我们就扩容，再进行插入操作。改写后的插入方法如下：
public class ArrayList<E> {
private E[] data; // 定义一个基础数组，用来存放数据。
private int size; // 用记录数组中的数据个数。
// 数组扩容系数，当数组的元素个数大于等于数组的容量*系数时，进行扩容
private double resizeRatio = 0.75;
// 向索引index位置插入一个元素e
public void add(int index, E e) {
// 索引不合法就报错
if (index > size || index < 0)
throw new IllegalArgumentException("Wrong index");
// 如果数组满足：已存元素个数等于元素容量*系数，就扩容，新数组容量为之前的2倍
if (size == (int)(data.length*resizeRatio))
resize(2 * data.length);
// 继续进行插入操作
for (int i = size - 1; i >= index; i--)
{
data[i+1] = data[i];
}
data[index] = e;
size ++;
}
// 扩容方法，对数组进行扩容，该方法对用户屏蔽，所以私有
private void resize(int newCapacity) {
E[] newData = (E[])new Object[newCapacity];
for (int i = 0; i < size; i++)
newData[i] = data[i]; // 拷贝数据
// 将对象的引用更新，此时指针指向了新数组的内存地址
data = newData;
}
}完成插入操作之后，相信大家对动态数组的实现思想有了一定的了解，而查询、修改与删除操作，在动态数组中，其实与静态数组没有什么不同。为了更高效利用空间，我们可以在删除元素后，对数组进行缩容，来节约内容空间。动态数组类的全部代码如下：
public class ArrayList<E> {
private E[] data; // 定义一个基础数组，用来存放数据。
private int size; // 用记录数组中的数据个数。
// 数组扩容系数，当数组的元素个数大于等于数组的容量*系数时，进行扩容
private double resizeRatio = 0.75;
public ArrayList() {
this(10);
// TODO Auto-generated constructor stub
}
public ArrayList(int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
public int getSize() {
return size;
}
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return (size == 0);
}
// 向索引index位置插入一个元素e
public void add(int index, E e) {
// 索引不合法就报错
if (index > size || index < 0)
throw new IllegalArgumentException("Wrong index");
// 如果数组满足：已存元素个数等于元素容量*系数，就扩容，新数组容量为之前的2倍
if (size == (int)(data.length*resizeRatio))
resize(2 * data.length);
// 继续进行插入操作
for (int i = size - 1; i >= index; i--)
{
data[i+1] = data[i];
}
data[index] = e;
size ++;
}
// 扩容方法，对数组进行扩容，该方法对用户屏蔽，所以私有
private void resize(int newCapacity) {
E[] newData = (E[])new Object[newCapacity];
for (int i = 0; i < size; i++)
newData[i] = data[i]; // 拷贝数据
// 将对象的引用更新，此时指针指向了新数组的内存地址
data = newData;
}
public void addFirst(E e) {
add(0, e);
}
public void addLast(E e) {
add(size, e);
}
public E get(int index) {
if (index < 0 || index > size)
throw new IllegalArgumentException("Wrong index");
return data[index];
}
public void set(int index, E e) {
if (index < 0 || index > size)
throw new IllegalArgumentException("Wrong index");
data[index] = e;
}
// 查询数组中是否存在元素e
public boolean isExist(E e) {
for (int i = 0; i < size; i++)
{
if (data[i].equals(e))
{
return true;
}
}
return false;
}
// 查询元素e在数组中的位置
public int findIndex(E e) {
for (int i = 0; i < size; i++)
{
if (data[i].equals(e) )
{
return i;
}
}
return -1;
}
// 从数组中移除索引为index位置的元素，并将该元素返回
// 缩容后，如果数组元素个数满足条件，就进行缩容
public E remove(int index) {
if (index < 0 || index > size)
throw new IllegalArgumentException("Remove failed");
E ret = data[index];
for (int i = index + 1; i < size; i++)
{
data[i-1] = data[i];
}
size --;
data[size] = null;
// 如果数组的空间有一半没用就缩容为原来的1/2
if (size == data.length / 2)
resize(data.length/2);
return ret;
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size - 1);
}
public void removeElement(E e) {
int index = findIndex(e);
if (index != -1)
remove(index);
}
@Override
public String toString() {
// TODO Auto-generated method stub
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
res.append('[');
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size -1)
{
res.append(", ");
}
}
res.append(']');
return res.toString();
}
}最后，我们写一个测试用例来对我们实现的动态数组类进行测试：
public class Main {
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<Integer>(8);
// 从数组尾部依次插入0-6
for (int i = 0; i < 6; i++) {
arr.addLast(i);
}
System.out.println(arr.toString());
arr.addLast(6);
System.out.println(arr.toString());
}
}执行结果：
可以看到，数组自动进行了容量的扩充。
至此，我们数组这样一种数据结构在Java中的实现，就已经讲解完成，祝大家学习愉快。