一個簡單的動態數組實作
基於數組實作添加10w的容量在刪除所有容量平均是0.4秒這個效率是可觀的下面來一起看看代碼
package com.array;
import java.util.List;
import java.util.Random;
/**
*
* @author XiaoTian
* @date 2018-08-08
*/
//基于动态数组的实现 E 是泛型
//借用了一下 Java中的ArrayList的代码
//研究源码也是一种乐趣
//还能让我们技术有所提高
public class ArrayList<E> implements java.io.Serializable{
/**
* 初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 用于空实例的共享空数组实例。
*/
transient Object[] EMPTY_ELEMENTDATA = {};
/**
* 数组缓冲区，其中存储ArrayList的元素。
* ArrayList的容量是这个数组缓冲区的长度。
*/
transient Object[] elementData;
/**
* 用于默认大小的空实例的共享空数组实例。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 大小
*/
private int size;
/**
* 默认为空
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 自定义空间大小
* @param initialCapacity
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public int size() {
return size;
}
/**
* 添加一个元素 元素位置是最后
* @param e
*/
public void add(E e) {
ExtendElement(size + 1);
this.elementData[size++] = e;
}
/**
* 在头部添加元素
* @param e
*/
public void addHead(E e) {
this.elementData[0] = e;
}
/**
* 扩展元素
*/
private void ExtendElement(int size) {
//容量
if(this.elementData.length == 0) {
elementData = new Object[DEFAULT_CAPACITY];
}else if(this.elementData.length < size) {
EMPTY_ELEMENTDATA = elementData;
//获取当前容量
int oldCapacity = elementData.length;
//扩展容量 i + i >> 1 就是 i的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
elementData = new Object[newCapacity];
//1.源数组 2.源数组要复制的起始位置 3.目的数组 4.目的数组放置的起始位置 5.复制的长度
/**
* 调用 System的静态方法 arraycopy() 进行数组拷贝
* 标识为native意味JDK的本地库
* 如果频繁扩容会降低ArrayList的使用性能
* 赋值过程
*/
System.arraycopy(EMPTY_ELEMENTDATA,0,elementData,0,size-1);
}
}
/**
* 删除一个元素
*/
public E remove(int index) {
rangeCheck(index);
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//index + 1 是当前 index 下一个 之 赋给 index 就全部替换了
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // 清楚地让GC完成它的工作
//判断容量是否是当前的1/4 是就 缩容 不要浪费不必要的内存空间
ShrinkageCapacity();
return oldValue;
}
/**
* 删除最后一个
* @return
*/
public E removeLast() {
return remove(this.size - 1);
}
/**
* 判断是否大于size
* @param index
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//输出 Index 和 Size
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* 获取元素
* @param index
* @return
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* 查询当前元素的值
* @param index
* @return
*/
@SuppressWarnings("unchecked")
E elementData(int index) {
//获取索引位置的元素
return (E) elementData[index];
}
/**
* 缩容
* @param args
*/
public void ShrinkageCapacity() {
if(size == elementData.length / 4 && elementData.length / 2 != 0) {
EMPTY_ELEMENTDATA = elementData;
//缩二分之一
int oldCapacity = elementData.length / 2;
elementData = new Object[oldCapacity];
System.arraycopy(EMPTY_ELEMENTDATA,0,elementData,0,size-1);
}
}
//测试
public static void main(String[] args) {
long then = System.currentTimeMillis();
ArrayList<Integer> arrayList = new ArrayList<>();
Random random = new Random();
for (int i = 0; i < 100000; i++) {
arrayList.add(random.nextInt());
}
for (int i = 0; i < 99999; i++) {
arrayList.remove(0);
}
long now = System.currentTimeMillis();
System.out.println("Elapsed time:" + (now - then)+" 毫秒");
}
}登入後複製
這是執行上面程式碼的時間每個人的機器不一樣運作的效果也不一樣僅供參考
相關推薦：
# Java之動態代理類別實作日誌簡單實例
java 利用java反射機制動態載入類別的簡單實作
以上是Java實作：一個簡單的動態數組實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！
