利用数组实现列表基本功能

ゞ浴缸里的玫瑰 2021-11-19 16:26 283阅读 0赞

package mydata;
    
    /**
     * 自定义链表，具有链表的基本功能
     * @param <E>
     *     泛型
     */
    public class MyArrayList<E> implements Iterable<E> {
        /* 列表默认容量，可扩展 */
        private static final int DEFAULT_CAPACITY = 10;
    
        /* 列表大小 */
        private int theSize;
    
        /* 修改次数 */
        private int modCount = 0;
    
        /* 存储数据的数组 */
        private E[] theItems;
    
        /*
         * 无参构造器，初始化数组
         */
        public MyArrayList() {
            doClear();
        }
    
        /*
         * 清除列表
         * @return: void
         */
        public void clear(){
            doClear();
        }
    
        /*
         * 清除列表，恢复为原始状态
         * @return: void
         */
        private void doClear(){
            theSize = 0;
            ensureCapacity(DEFAULT_CAPACITY);
            modCount++;
        }
    
        /*
         * 扩展列表大小
         * @param newCapacity : 新的大小
         * @return: void
         */
        public void ensureCapacity(int newCapacity){
            if(newCapacity < theSize){
                return;
            }
            E[] old = theItems;
            theItems = (E[]) new Object[newCapacity];
            for(int i = 0; i < size() ; i++ ){
                theItems[i] = old[i];
            }
        }
    
        /*
         * 返回列表大小
         * @return: int
         */
        public int size(){
            return theSize;
        }
    
        /*
         * 列表是否为空
         * @return: boolean
         */
        public boolean isEmpty(){
            return size() == 0;
        }
    
        /*
         * 避免浪费空间，使得容量与列表大小一致
         * @return: void
         */
        public void trimToSize(){
            ensureCapacity(size());
        }
    
        /*
         * 获取指定索引下的值
         * @param index : 索引
         * @return: E
         */
        public E get(int index){
            if(index <0 || index >= size()){
                throw new ArrayIndexOutOfBoundsException();
            }
            return theItems[index];
        }
    
        /*
         * 设置指定索引的值
         * @param index : 索引
         * @param newVal : 新值
         * @return: E 旧值
         */
        public E set(int index, E newVal){
            if(index <0 || index >= size()){
                throw new IndexOutOfBoundsException();
            }
            E old = theItems[index];
            theItems[index] = newVal;
            return old;
        }
    
        /*
         * 添加数据，默认添加到表最后
         * @param val : 要添加的值
         * @return: boolean 添加结果
         */
        public boolean add(E val){
            add(size(), val);
            return true;
        }
    
        /*
         * 添加数据到指定索引
         * @param index : 指定索引
         * @param val : 值
         * @return: void
         */
        public void add(int index, E val){
            if(theItems.length == size()){
                ensureCapacity(size() * 2 +1);
            }
            for(int i = theSize; i > index; i--){
                theItems[i]=theItems[i-1];
            }
            theItems[index] = val;
            theSize++;
            modCount++;
        }
    
        /*
         * 删除指定索引值
         * @param index : 索引
         * @return: E 删除的值
         */
        public E remove(int index){
            E old = theItems[index];
            for(int i = index; i <  size()-1; i++){
                theItems[i] = theItems[i+1];
            }
            theSize--;
            modCount++;
            return old;
        }
    
        /*
         * 获取迭代器
         * @return: java.util.Iterator<E>
         */
        public java.util.Iterator<E> iterator(){
            return new ArrayListIterator();
        }
    
        /**
         *  自定义迭代器
         */
        private class ArrayListIterator implements java.util.Iterator<E>{
            /* 目前索引 */
            private int current = 0;
    
            /* 修改次数，与MyArrayList中的modCount对应，用于测试迭代中列表是否修改 */
            private int expectModCount = modCount;
    
            /* 是否可以移除标志 */
            private boolean okToMove = false;
    
            /*
             * 是否有下一个数
             * @return: boolean
             */
            public boolean hasNext(){
                return current < size();
            }
    
            /*
             * 返回本次索引的值，并指向下一位
             * @return: E
             */
            public E next(){
                if(expectModCount != modCount){
                    throw new java.util.ConcurrentModificationException();
                }
                if(!hasNext()){
                    throw new java.util.NoSuchElementException();
                }
                okToMove = true;
                return theItems[current++];
            }
    
            /*
             * 移除当前索引的上一位，并使索引自减
             * @return: void
             */
            public void remove(){
                if(modCount != expectModCount){
                    throw new java.util.ConcurrentModificationException();
                }
                if(!okToMove){
                    throw new IllegalStateException();
                }
                MyArrayList.this.remove(--current);
                expectModCount++;
                okToMove = false;
            }
        }
    }

转载于:https://www.cnblogs.com/lotz/p/10928239.html