如何手写一个ArrayList

比眉伴天荒 2022-05-12 12:20 249阅读 0赞

写完HashMap，觉得手痒痒，所以隔了一天再来实现一下简单的ArrayList，ArrayList相比而言就非常的简单，主要的核心点有以下几个方面：

1.ArrayList的底层是由数组构成的

2.添加时需要考虑扩容问题

3.对于index索引的操作，需要考虑到下标不合法的异常

4.remove操作的时候，需要一点数学知识进行一下逻辑操作

下面贴出我的代码:

MyList接口:

public interface MyList {
    
        // 求容量
        int size();
    
        // 是否为空
        boolean isEmpty();
    
        // 判断是否存在
        boolean contains(Object o);
    
        // 清空集合
        void clear();
    
        // 返回添加是否成功
        boolean add(Object object);
    
        // 返回删除是否成功
        boolean remove(int index);
    
        // 获取索引位置的值
        Object get(int index);
    
    }

MyArrayList 实现类的代码：

/***
     * author kxm
     * email 806857264@qq.com
     * date 2018/9/17
     */
    public class MyArrayList implements MyList {
    
        private int size;
        private Object[] elementData;
        // JDK源码规定长度
        private static final int DEFAULT_CAPACITY = 10;
    
        // 构造方法 --- 空参
        public MyArrayList(){
            this(DEFAULT_CAPACITY);
        }
        // 有参构造方法
        public MyArrayList(int initialCapacity){
            /*
             * 1.含参构造器
             * 2.要对传入的初始量的合法性进行检测
             * 3.通过新建数组实现
             */
            if(initialCapacity < 0){
                try {
                    throw new Exception();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            elementData=new Object[initialCapacity];
        }
    
        // 返回长度
        @Override
        public int size() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            // 返回长度是否为0即可
            return size == 0;
        }
    
        // 暂时只考虑直接equals的情况
        @Override
        public boolean contains(Object o) {
            for(Object old : elementData){
                if(o.equals(old)){
                    return true;
                }
            }
            return false;
        }
    
        // 清除数组
        @Override
        public void clear() {
            elementData = new Object[DEFAULT_CAPACITY];
            size = 0;
        }
    
        @Override
        public boolean add(Object object) {
            ensureCapacity();
            elementData[size] = object;
            size++;
            return true;
        }
    
        @Override
        public boolean remove(int index) {
            /*
             * 1.下标合法性检测
             * 2.删除指定下标对象，并返回其值
             * 3.通过数组复制实现
             * 4.因为前移，数组最后一位要置为空
             */
            rangeCheck(index);
            int arrnums=size - index - 1;
            if(arrnums > 0){
                // 思路：从被删除的索引的下一位开始复制给新的当前数组索引的起始位置，长度为size - index - 1 --- 数学问题
                System.arraycopy(elementData, index+1, elementData,index, arrnums);
            }
            elementData[--size]=null;
            return true;
        }
    
        @Override
        public Object get(int index) {
            rangeCheck(index);
            return elementData[index];
        }
    
        // 数组容量检测方法 --- 如果超了就得扩容
        private void ensureCapacity(){
            if(size==elementData.length){
                Object[] newArray=new Object[size * 2 + 1];
                System.arraycopy(elementData, 0, newArray, 0, elementData.length);
                elementData=newArray;
            }
        }
    
        // 对索引下标进行合法性检查
        private void rangeCheck(int index){
            if(index<0||index>=size){
                try {
                    throw new Exception();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }
    
        @Override
        public String toString() {
            return "MyArrayList{" +
                    "elementData=" + Arrays.toString(elementData) +
                    '}';
        }
    }