Java动态数组

左手的ㄟ右手 2022-05-16 20:29 214阅读 0赞

一个简单的动态数组实现

基于数组实现 添加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;
    	}
    
        /**
         * 添加一个元素 元素位置 index
         * @param e
         */
        private void add(E e,int index) {
        	ExtendElement(size + 1);
        	if(index!=size)
        		System.arraycopy(elementData, index, elementData, index + 1, size);
        	this.elementData[index] = e;
        	size++;
        }
        /**
         * size这个位置添加一个元素
         * @param e
         */
        public void add(E e) {
        	add(e,size);
        }
        
        /**
         * 在头部添加元素
         * @param e
         */
        public void addHead(E e) {
        	add(e,0);
        }
        
        /**
         * 扩展元素
         */
        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);
        	}
        }
        
        /**
         * 删除一个元素
         */
        private 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);
        }
        
        /**
         * 删除第一个元素
         */
        public E removeHead() {
        	return remove(0);
        }
        
        /**
         * 判断是否大于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)+" 毫秒");
     	}
    }

![70][] 这是运行上面代码的时间 每个人的机器不一样运行的效果也不一样 仅供参考

[70]: /images/20220517/7745ddf0bdcd44c69fdc9add743db8b9.png