专栏首页星月小站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 。根据这个优点,我们可以想到,数组比较适合存储索引有语义的数据,比如成绩单这种,我们把名次当做索引,分数当做数据用一个数组存储起来,就可以快速获取某个名次的分数。 按照这个数组,我们可以设计一个数组类,首先设计好数组的功能:

  1. 要能获取数组中的数据个数。
  2. 要能获取数组的容量。
  3. 要能判断数组是否为空。
  4. 要能向数组中插入元素
  5. 要能从数组中查询元素
  6. 要能从数组中删除元素

根据上述功能,我们先进行代码的编写实现这个类的前三个功能:获取元素个数,获取数组容量,判断数组是否为空(在后续的代码中,我们将省略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的位置上。 在这一过程中,我们需要注意的点有以下几点:

  1. 数组的容量是否已满,如果数组已经满了,就没有办法向后挪动,再插入元素了。
  2. 插入的位置一定是数组的有效位置。理解size和data.length的区别,一个是用户能看到的长度,一个是数组的容量,data.length 减 size这一部分的元素,用户是看不到的,我们对用户屏蔽。
  3. 每次插入后,数组的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);
	}
	
}

至此,我们完成了数组添加元素的操作,下面我们来完成从数组中查询和修改元素的操作:

  1. 查询索引为index位置的元素:根据数组的性质,直接返回data[index]的值就可以。
  2. 查询元素e是否存在在数组中:数组中查询是否存在元素e,就需要对数组进行遍历。
  3. 修改索引为index位置的元素:直接将data[index]进行更新即可,这是java基础数组的操作方法。
  4. 从索引为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中的实现,就已经讲解完成,祝大家学习愉快。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer题解

    在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少存在一个数字是重复的。 请找出数组中任意一个重复的数字,但不能修改输入的数组。 例如输...

    星如月勿忘初心
  • Java后端面试学习知识总结——GC

    JVM之所以能够自动回收内存,是因为JVM的开发人员使用了一些垃圾回收算法,来让JVM自己判断哪些对象可以回收,哪些对象不可以回收。

    星如月勿忘初心
  • Java后端面试学习知识总结——JVM

    JVM就是Java虚拟机,Java的跨平台机制就是建立在强大的Java虚拟机的基础上。Java是一种先编译后解释型的语言,当我们写了一段Java代码,在运行之前...

    星如月勿忘初心
  • 封装数组之改进为泛型数组

    前言:通过上一节我们对我们需要封装的数组,进行了基本的增删改查的封装,但只局限于int类型的操作,为了能提供多种类型数组的操作,我们可以将其进一步封装为泛型数组...

    wfaceboss
  • ArrayList源码解析(基于Java8)扩容删除

    JavaEdge
  • ArrayList 源码分析

    ArrayList 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,所...

    lwen
  • Java集合框架源码解析之ArrayList

    叶志陈
  • 算法学习之动态数组类

    让我们的数据结构可以放置“任何”数据类型 不可以是基本数据类型,只能是类对象 boolean,byte , char,short,int,long,floa...

    慕白
  • 搞定数据结构-数组结构

    从数组存储的内存模型来看,“下标”最确切的定义应该是”偏移”,如果用a来表示数组的首地址,a0 就是偏移为0的位置,也就是首地址,a k就表示偏移k个type_...

    用户3045442
  • Java数据结构告诉你如何选用数据集合(2)顺序表

    今天接着上次的内容详细讲,用Java实现一个顺序表。名字就取MyArrayList,有点随便。上次讲了,顺序表的实现是使用数组实现的,那么在编写顺序表的时候就需...

    ZackSock

扫码关注云+社区

领取腾讯云代金券