动态数组在java中的实现

kerrycode 阅读:47 2022-10-05 12:31:26 评论:0

声明:

data为数组名。

size为数组中最后一个元素的下一个位置。

实现动态数组的原因:

因为java中的数组是静态的,在new数组时就需要指定数组的大小,如果需要存储的元素为未知的个数,设置空间过大会造成浪费,设置空间过小会无法存入全部数据,我们利用自己写的resize()方法,便可以实现自动扩容,不再担心数组容量的问题。

需要自动扩容或自动缩容的时候一般是数组满了或数组空余空间过多的时候,多发生在添加和删除操作中。

size == data.length的时候表示数组已满,调用resize(int newCapacity)方法,参数传入2*data.length,意为新创建的数组长度为原数组的二倍。

size == data.length /4 并且data.length/2 != 0的时候,调用resize方法进行缩容。

在ArrayList的自动扩容方法中参数默认为1.5*capacity

在resize()方法实现中new了一个新的名为newData的数组用来接收原数组中的元素。利用for循环将数组中的元素进行转移。

add方法实现

//向指定位置添加元素e 
	public void add(int index,E e){ 
		if(index<0||index>size){ 
			throw new IllegalArgumentException("AddLast failed.Require index error"); 
 
		} 
		if(size == data.length){ 
			resize(2*data.length); 
		} 
		 
		for (int i = size-1; i >= index; i--) { 
			data[i+1] = data[i]; 
		} 
		data[index] = e; 
		size++; 
	}

remove方法实现

//删除元素,并返回被删除的元素 
	public E remove(int index){ 
		if(index<0 || index >=size){ 
			throw new IllegalArgumentException("Remove failed. Index is illegal"); 
		} 
		E ret = data[index]; 
		for (int i = index+1; i < size; i++) { 
			data[i-1] = data[i]; 
		} 
		size--; 
		data[size] = null;//loitering objects  != memory leak 
		 
		if(size == data.length /4 && data.length/2 != 0){ 
			resize(data.length/2); 
		} 
		return ret; 
	}

resize方法实现

private void resize(int newCapacity){ 
		E[] newData = (E[])new Object[newCapacity]; 
		for (int i = 0; i < size; i++) { 
			newData[i] = data[i]; 
		} 
		data = newData; 
	}

Array类

package array; 
public class Array<E> { 
	private E[] data; 
	private int size; 
	@SuppressWarnings("unchecked") 
	public Array(int capacity){ 
		data = (E[]) new Object[capacity]; 
		size = 0; 
	} 
	public Array(){ 
		this(10); 
	} 
	public int getSize(){ 
		return size; 
	} 
	public int getCapacity(){ 
		return data.length; 
	} 
	public boolean isEmpty(){ 
		return size == 0; 
	} 
	//向第一个位置添加一个元素 
	public void addFirst(E e){ 
		add(0,e); 
	} 
	//向最后一个位置添加一个元素 
	public void addLast(E e){ 
		add(size,e); 
	} 
	//向指定位置添加元素e 
	public void add(int index,E e){ 
		if(index<0||index>size){ 
			throw new IllegalArgumentException("AddLast failed.Require index error"); 
		} 
		if(size == data.length){ 
			resize(2*data.length); 
		} 
		for (int i = size-1; i >= index; i--) { 
			data[i+1] = data[i]; 
		} 
		data[index] = e; 
		size++; 
	} 
	//获取index位置的元素e 
	public E get(int index){ 
		if(index<0 || index >=size){ 
			throw new IllegalArgumentException("Get failed. Index is illegal"); 
		} 
		return data[index]; 
	} 
	//修改index索引位置的元素e 
	public void set(int index, E e){ 
		if(index<0 || index >=size){ 
			throw new IllegalArgumentException("Get failed. Index is illegal"); 
		} 
		data[index] = e; 
	} 
	//判断元素是否存在于数组中 
	public boolean contains(E e){ 
		for (int i = 0; i < size; i++) { 
			if(data[i].equals(e)){ 
				return true; 
			} 
		} 
		return false; 
	} 
	//找到元素并返回索引 
	public int find(E e){ 
		for (int i = 0; i < size; i++) { 
			if(data[i].equals(e)){ 
				return i; 
			} 
		} 
		return -1; 
	} 
	//删除元素,并返回被删除的元素 
	public E remove(int index){ 
		if(index<0 || index >=size){ 
			throw new IllegalArgumentException("Remove failed. Index is illegal"); 
		} 
		E ret = data[index]; 
		for (int i = index+1; i < size; i++) { 
			data[i-1] = data[i]; 
		} 
		size--; 
		data[size] = null;//loitering objects  != memory leak 
		 
		if(size == data.length /4 && data.length/2 != 0){ 
			resize(data.length/2); 
		} 
		return ret; 
	} 
	public E removeFirst(){ 
		return remove(0); 
	} 
	public E removeLast(){ 
		return remove(size-1); 
	} 
	//从数组中删除元素e 
	public void removeElement(E e){ 
		int index = find(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; i++) { 
			res.append(data[i]); 
			if(i != size-1){ 
				res.append(","); 
			} 
		} 
		res.append(']'); 
		return res.toString(); 
	} 
	private void resize(int newCapacity){ 
		E[] newData = (E[])new Object[newCapacity]; 
		for (int i = 0; i < size; i++) { 
			newData[i] = data[i]; 
		} 
		data = newData; 
	} 
}

Main测试:

package array; 
 
public class Main { 
	public static void main(String[] args){ 
		Array<Integer> arr = new Array<>(); 
		for (int i = 0; i < 10; i++) { 
			arr.addLast(i); 
		} 
		System.out.println(arr); 
		arr.add(1, 100); 
		System.out.println(arr); 
		arr.addFirst(-1); 
		System.out.println(arr); 
		arr.set(0, 1); 
		System.out.println(arr); 
	} 
}

以上就是java中动态数组的具体实现的详细内容,更多请关注亿速云其它相关文章!


本文参考链接:https://www.yisu.com/zixun/133021.html
标签:java
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

我的关注

全民解析

搜索
关注我们