美文网首页
动态数组

动态数组

作者: 木山手札 | 来源:发表于2019-12-15 17:46 被阅读0次
    • 全局变量
    private int size;
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;
    

    size用来保存数组内部已经使用的容量,elements是用于存储数据的容器,size<=elemnets.lengthDEFAULT_CAPACITY是常量,表示容器初始化时的大小

    • 初始化
    public ArrayList(int capacity) {
        capacity = (capacity <= DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = (E[]) new Object[capacity];
    }
    

    如果capacity<=DEFAULT_CAPACITY,就初始化容器为默认大小

    • 获取指定位置的值
        public E get(int index) {
            rangeCheck(index);
            return elements[index];
        }
    

    直接通过index获取,所有的通过索引操作elements时都需要对index进行合法性校验

    • index合法性校验
        private void rangeCheckForAdd(int index) {
            if (index < 0 || index > size) {
                indexOutOfBoundException(index);
            }
    
        }
    
        private void rangeCheck(int index) {
            if (index < 0 || index >= size) {
                indexOutOfBoundException(index);
            }
        }
    

    正常的校验范围时不能<0,index不能>=size,site是从1开始递增的,比如set()时不能修改size值,site此时为null,修改会越界,但是add操作时index可以=size

    • 在指定位置添加元素
        public void add(int index, E element) {
            rangeCheckForAdd(index);
            ensureCapacity(size + 1);
    
            for (int i = size; i > index; i--) {
                elements[i] = elements[i - 1];
            }
            elements[index] = element;
            size++;
        }
    

    在index位置添加元素时,index位置和index后的位置元素的索引位置都需要+1,也就是index位置后的元素都需要向后移动一个位置
    移动元素位置需要从后移动,如果从index位置开始移动会覆盖掉index+1位置的值
    添加新元素后site+1

    • 修改指定位置的值
        public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elements[index];
            elements[index] = element;
            return oldValue;
        }
    
    • 找出元素在数组中的索引位置
        public int indexOf(E element) {
            if (element == null) {
                for (int i = 0; i < size; i++) {
                    if (elements[i] == null) {
                        return i;
                    }
                }
            } else {
                for (int i = 0; i < size; i++) {
                    if (element.equals(elements[i])) {
                        return i;
                    }
                }
            }
            return -1;
        }
    

    element可以为null,为null时查找数组中第一个为null的位置,for()循环不需要循环elements.length,只需要size位置就可以
    element不为null时,循环查找数组,elements使用了范型数组,判断element是否在elments时,比较需要使用equals

    • 删除index位置元素
        public E remove(int index) {
            rangeCheck(index);
    
            E old = elements[index];
            for (int i = index + 1; i < size; i++) {
                elements[i - 1] = elements[i];
            }
            elements[--size] = null;
            return old;
        }
    

    删除时需要从index+1位置开始向前移动一个位置
    最后size位置的元素一定设置为null,不然对象引用可能会造成泄漏,即不能访问,但又无法被垃圾回收

    • 数组扩容
        private void ensureCapacity(int capacity) {
            int oldCapacity = elements.length;
            if (oldCapacity > capacity) return;
    
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            E[] newElements = (E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) {
                newElements[i] = elements[i];
            }
            elements = newElements;
        }
    

    capacity是size+1,elements.length>capacity时不需要扩容
    扩容为原来容量的1.5倍,使用>>1运算

    相关文章

      网友评论

          本文标题:动态数组

          本文链接:https://www.haomeiwen.com/subject/mdxlnctx.html