【java数据结构与算法学习】ArrayList的实现

「爱情、让人受尽委屈。」 2022-05-31 12:30 156阅读 0赞

今天开始，下定决心学习数据结构和算法！每天进步一点点！

ArrayList的实现原理，其内部是维护是一个可变数组。

优点：查询快，根本原因是数组元素在内存中是连续存放的，所以当访问元素的时候我们只需知道首地址，根据

**Ai = A1 + (i-1)\*每个元素占有的空间大小**，就能很快的得到元素，这是一个复杂度为O(1)

缺点：增删慢，从代码中就可以看出，需要不断的移动元素的位置，时间复杂度是O(n)的。

import java.util.Iterator;
    import java.util.NoSuchElementException;
    
    public class MyArrayList<AnyType> implements Iterable<AnyType> {
    
        private static final int DEFAULT_CAPACITY = 10;
        private AnyType[] theItems;
        private int theSize;
    
        public MyArrayList(){
            doClear();
        }
        private void doClear(){
            theSize = 0;
            ensureCapacity(DEFAULT_CAPACITY);
        }
        //确保容量
        private void ensureCapacity(int newCapacity){
            //这里防止用户传入小于集合长度的参数
            if (newCapacity < theSize){
                return;
            }
            //保存原来的数组
            AnyType[] old = theItems;
            //分配新的数组
            theItems = (AnyType[]) new Object[newCapacity];
            /*
                注意：如果是调用构造或者清空方法后进入的该方法，此时size()已经是0，
                所以for循环条件不成立，虽然old引用了空对象，但不会产生空指针异常
             */
            for (int i = 0; i < size(); i++) {
                theItems[i] = old[i];
            }
    
        }
        //清空集合
        public void clear(){
            doClear();
        }
        //返回集合大小
        public int size(){
            return theSize;
        }
        //判断集合是否为空
        public boolean isEmpty(){
            return theSize == 0;
        }
        //去掉集合中多申请的空间
        private void trimToSize(){
            ensureCapacity(size());
        }
        //获取集合中的值
        public AnyType get(int index){
            if (index < 0 || index >= size()){
                throw new ArrayIndexOutOfBoundsException();
            }
            return theItems[index];
        }
        //往集合中设置值，返回原来的值
        public AnyType set(int index, AnyType newVal){
            if (index < 0 || index >= size()){
                throw new ArrayIndexOutOfBoundsException();
            }
            AnyType oldVal = theItems[index];
            theItems[index] = newVal;
            return oldVal;
        }
        //添加元素
        public boolean add(AnyType x){
            add(size(), x);
            return true;
        }
        //在指定位置添加元素
        public void add(int index, AnyType x){
            if (index < 0 || index > size()){
                throw new ArrayIndexOutOfBoundsException();
            }
            //注意，添加元素的时候有两种情况，一是内部数组满了，二是内部数组没有满
            if (theItems.length == size()){
                ensureCapacity(size()*2 + 1);
            }
            //仅仅是移动元素
            for (int i = size();i > index;i--){
                theItems[i] = theItems[i-1];
            }
            //插入元素
            theItems[index] = x;
            theSize++;
        }
        //删除指定位置的元素
        public AnyType remove(int index){
            if (index < 0 || index > size()){
                throw new ArrayIndexOutOfBoundsException();
            }
            AnyType removeItem = theItems[index];
            //注意：这里的条件是size()-1，如果是size()，theItem[i+1]会出现越界异常
            for (int i = index; i < size()-1; i++) {
                theItems[i] = theItems[i+1];
            }
            theSize--;
            return removeItem;
        }
        @Override
        public Iterator<AnyType> iterator() {
            return new ArrayListIterator();
        }
        //内部类
        private class ArrayListIterator implements Iterator<AnyType>{
            //当前迭代器位置
            private int current = 0;
            @Override
            public boolean hasNext() {
                return current < size();
            }
    
            @Override
            public AnyType next() {
                if (!hasNext()){
                    throw new NoSuchElementException();
                }
                return theItems[current++];
            }
    
            public void remove(){
                MyArrayList.this.remove(--current);
            }
        }
    }