Java实践:一个简单的动态数组实现
程序员文章站
2022-03-27 09:21:28
...
一个简单的动态数组实现
基于数组实现 添加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实践:一个简单的动态数组实现的详细内容,更多请关注其它相关文章!
上一篇: dw如何新建css规则
下一篇: php运行原理与变量类型
推荐阅读
-
Java实现一个简单的定时器代码解析
-
Java实现把两个数组合并为一个的方法总结
-
基于自定义的动态数组实现一个栈(Java语言)
-
java简单实现数组的增删改查方法
-
Java实现给定一个无序的整数数组,找到其中最长上升子序列的长度。
-
Java实现一个简单的加密解密方法
-
c语言和Java语言实现,两数之和:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
用java和scala实现一个简单Flink的分布式缓存(Distributed Cache)
-
回顾数据结构(Java版)——写一个简单的循环队列(数组实现)
-
合并两个有序链表为一个链表,最简单的java实现