【数据结构Java版】自定义ArrayList实现的完整代码

分手后的思念是犯贱 2024-04-03 11:53 64阅读 0赞

自定义ArrayList实现的完整代码如下所示，其中包含用主函数测试，可以调试自行运行。

MyArrayList类：

/**
     * 顺序表：物理上元素相连的线性表
     * 约束：
     * 1) 0 <= size <= array.length
     * array[0, size) != null
     * array[size, array.length) == null
     */
    public class MyArrayList implements MyList {
        // 定义属性
        private Long[] array;   // array.length 也就是我们的容量（capacity）
        private int size;       // 保存元素的个数
    
        // 构造方法
        public MyArrayList() {
            // 容量没有规定，自行定义为 16 个
            this.array = new Long[16];
            // 这一步不是必须的，把数组中的每个位置都初始化成 null
            for (int i = 0; i < array.length; i++) {
                array[i] = null;
            }
            // 元素个数 = 0
            this.size = 0;
        }
    
        public MyArrayList(int initialCapacity) {
            this.array = new Long[initialCapacity];
            // 这一步不是必须的，把数组中的每个位置都初始化成 null
            for (int i = 0; i < array.length; i++) {
                array[i] = null;
            }
            // 元素个数 = 0
            this.size = 0;
        }
    
        @Override
        public int size() {
            return size;
        }
    
        // 扩容过程仅仅为了内部准备，不会对外
        // O(n)
        private void ensureCapacity() {
            if (this.size < this.array.length) {
                return;     // 此时不需要扩容
            }
    
            // 需要扩容
            // 1) 申请新数组，容量是原来的 2 倍
            int newLength = this.array.length * 2;
            Long[] newArray = new Long[newLength];
    
            // 2) 搬家
            for (int i = 0; i < this.size; i++) {
                newArray[i] = this.array[i];
            }
    
            // 3) 让顺序表的 array 引用指向新数组
            this.array = newArray;
        }
    
        // 时间复杂度：数据规模是 size，时间复杂度是 O(1)
        // 最坏情况，发生扩容的情况： O(n)
        // 我们认为扩容的发生是小概率事件
        // 平均事件复杂度：O(1)
        @Override
        public boolean add(Long e) {
            ensureCapacity();   // 这个方法结束之后，至少还有一个空间可以插入
    
            // 为 size 赋予一个新的逻辑含义 —— 尾插时的元素的位置
            array[size] = e;
            // 让元素个数的记录 + 1
            size = size + 1;
    
            // 返回 true 表示插入成功
            return true;
        }
    
        // 时间复杂度：O(n)
        @Override
        public void add(int index, Long e) {
            ensureCapacity();   // 这个方法结束之后，至少还有一个空间可以插入
    
            if (index < 0 || index > size) {
                // 下标不合法
                throw new ArrayIndexOutOfBoundsException("下标不合法");
            }
    
            // 此时下标一定是合法的
            // 将每个结点往后移位
            // i: 移位时的出发点
            for (int i = size - 1; i >= index; i--) {
                // array[i] 的元素搬到  array[i + 1]
                array[i + 1] = array[i];
            }
    
            // 将 e 放到 index 位置
            array[index] = e;
    
            // 元素个数增加了 1
            size = size + 1;
        }
    
        // 时间复杂度: O(n)
        @Override
        public Long remove(int index) {
            // 下标合法性检查
            if (index < 0 || index >= size) {
                // 下标不合法
                throw new ArrayIndexOutOfBoundsException("下标不合法");
            }
    
            // 先把要删除的元素保存起来
            Long e = array[index];
    
            // i 代表搬元素时的起始位置 [index + 1, size)
            for (int i = index + 1; i < size; i++) {
                array[i - 1] = array[i];
            }
    
            // 把不存在的元素置为 null
            // 真实中是否要置 null，需要根据性能考虑
            array[size - 1] = null;
    
            // 元素个数减一
            size = size - 1;
    
            // 返回被删除的元素
            return e;
        }
    
        // 时间复杂度是 O(n)
        @Override
        public boolean remove(Long e) {
            // 按照从前到后的顺序，找到第一个遇到的 e
            for (int i = 0; i < size; i++) {
                // 毕竟 array 的值 是否 和 e 相等（equals）
                if (array[i].equals(e)) {
                    // 删除 [i] 位置的元素
                    remove(i);  // O(n)
                    return true;
                }
            }
    
            // 说明没有找到 e
            return false;
        }
    
        // O(1)
        @Override
        public Long get(int index) {// 下标合法性检查
            if (index < 0 || index >= size) {
                // 下标不合法
                throw new ArrayIndexOutOfBoundsException("下标不合法");
            }
    
            return array[index];
        }
    
        // O(1)
        @Override
        public Long set(int index, Long e) {
            // 下标合法性检查
            if (index < 0 || index >= size) {
                // 下标不合法
                throw new ArrayIndexOutOfBoundsException("下标不合法");
            }
    
            Long oldE = array[index];
    
            array[index] = e;
    
            return oldE;
        }
    
    
        // O(n)
        @Override
        public int indexOf(Long e) {
            for (int i = 0; i < size; i++) {
                if (array[i].equals(e)) {
                    return i;
                }
            }
    
            return -1;
        }
    
        // O(n)
        @Override
        public int lastIndexOf(Long e) {
            for (int i = size - 1; i >= 0; i--) {
                if (array[i].equals(e)) {
                    return i;
                }
            }
    
            return -1;
        }
    
        // O(n)
        @Override
        public boolean contains(Long e) {
            return indexOf(e) != -1;
        }
    
        @Override
        public void clear() {
            // array 中全部置为 null
            for (int i = 0; i < size; i++) {
                array[i] = null;
            }
            this.size = 0;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        private static void 检查顺序表是否合法(MyArrayList list) {
            // 0 <= size <= array.length
            if (list.size < 0) {
                throw new RuntimeException();
            }
    
            if (list.size > list.array.length) {
                throw new RuntimeException();
            }
            // array[0, size) != null
            for (int i = 0; i < list.size; i++) {
                if (list.array[i] == null) {
                    throw new RuntimeException();
                }
            }
            // array[size, array.length) == null
            for (int i = list.size; i < list.array.length; i++) {
                if (list.array[i] != null) {
                    throw new RuntimeException();
                }
            }
        }
    
        private static void 断言顺序表的元素个数一定是(MyArrayList list, int size) {
            if (list.size != size) {
                throw new RuntimeException();
            }
        }
    
        private static void 断言顺序表的指定位置元素一定是(MyArrayList list, int index, long e) {
            // Long != long
            // long != long
            if (list.array[index] != e) {
                throw new RuntimeException();
            }
        }
        public static void main(String[] args) {
            // 之所以把测试代码写这里，是方便读取 private 的属性
            MyArrayList list = new MyArrayList();
            检查顺序表是否合法(list);
    
            // 无参构造方法定义的顺序表，size 应该是 0
            断言顺序表的元素个数一定是(list, 0);
    
            // 先测试尾插 add()
            boolean r;
    
            r = list.add(Long.valueOf(100));    // 手动把 int 包装成 Long
            // 检查 r 必须是 true
            if (r == false) {
                throw new RuntimeException();
            }
    
            检查顺序表是否合法(list);
            断言顺序表的元素个数一定是(list, 1);
            断言顺序表的指定位置元素一定是(list, 0, 100);
    
            r = list.add(200L);         // 编译器自动把 long 包装成 Long
            if (r == false) {
                throw new RuntimeException();
            }
            检查顺序表是否合法(list);
            断言顺序表的元素个数一定是(list, 2);
            断言顺序表的指定位置元素一定是(list, 0, 100);
            断言顺序表的指定位置元素一定是(list, 1, 200);
    
            r = list.add(300L);
            if (r == false) {
                throw new RuntimeException();
            }
            检查顺序表是否合法(list);
            断言顺序表的元素个数一定是(list, 3);
            断言顺序表的指定位置元素一定是(list, 0, 100);
            断言顺序表的指定位置元素一定是(list, 1, 200);
            断言顺序表的指定位置元素一定是(list, 2, 300);
    
            // 测试 根据 index 进行插入 add(int index, Long e)
    
            // [100, 200, 300]
            list.add(3, 1000L);
            // [100, 200, 300, 1000]
            检查顺序表是否合法(list);
            断言顺序表的元素个数一定是(list, 4);
            断言顺序表的指定位置元素一定是(list, 0, 100);
            断言顺序表的指定位置元素一定是(list, 1, 200);
            断言顺序表的指定位置元素一定是(list, 2, 300);
            断言顺序表的指定位置元素一定是(list, 3, 1000);
    
            // [100, 200, 300, 1000]
            list.add(0, 2000L);
            // [2000, 100, 200, 300, 1000]
            检查顺序表是否合法(list);
            断言顺序表的元素个数一定是(list, 5);
            断言顺序表的指定位置元素一定是(list, 0, 2000);
            断言顺序表的指定位置元素一定是(list, 1, 100);
            断言顺序表的指定位置元素一定是(list, 2, 200);
            断言顺序表的指定位置元素一定是(list, 3, 300);
            断言顺序表的指定位置元素一定是(list, 4, 1000);
    
            // [2000, 100, 200, 300, 1000]
            list.add(2, 3000L);
            // [2000, 100, 3000, 200, 300, 1000]
            检查顺序表是否合法(list);
            断言顺序表的元素个数一定是(list, 6);
            断言顺序表的指定位置元素一定是(list, 0, 2000);
            断言顺序表的指定位置元素一定是(list, 1, 100);
            断言顺序表的指定位置元素一定是(list, 2, 3000);
            断言顺序表的指定位置元素一定是(list, 3, 200);
            断言顺序表的指定位置元素一定是(list, 4, 300);
            断言顺序表的指定位置元素一定是(list, 5, 1000);
    
            // [2000, 100, 3000, 200, 300, 1000]
            //        list.add(13, 4000L);
            // 非法下标，应该看到 下标越界异常
    
            // [2000, 100, 3000, 200, 300, 1000]
            Long e = list.remove(2);
            // [2000, 100, 200, 300, 1000]
            if (e != 3000) {
                throw new RuntimeException();
            }
            检查顺序表是否合法(list);
            断言顺序表的元素个数一定是(list, 5);
            断言顺序表的指定位置元素一定是(list, 0, 2000);
            断言顺序表的指定位置元素一定是(list, 1, 100);
            断言顺序表的指定位置元素一定是(list, 2, 200);
            断言顺序表的指定位置元素一定是(list, 3, 300);
            断言顺序表的指定位置元素一定是(list, 4, 1000);
    
            // 测试下删除 remove(0)  remove(size - 1)
            //[100,200,300,1000]
    //        list.remove(0);
    //        检查顺序表是否合法(list);
    //        断言顺序表的元素个数一定是(list,4);
    //        断言顺序表的指定位置元素一定是(list,0,100);
    //        断言顺序表的指定位置元素一定是(list,1,200);
    //        断言顺序表的指定位置元素一定是(list,2,300);
    //        断言顺序表的指定位置元素一定是(list,3,1000);
    
            // 测试下删除 remove(0)  remove(size - 1)
            //[100,200,300]
    //        list.remove(3);
    //        检查顺序表是否合法(list);
    //        断言顺序表的元素个数一定是(list,3);
    //        断言顺序表的指定位置元素一定是(list,0,100);
    //        断言顺序表的指定位置元素一定是(list,1,200);
    //        断言顺序表的指定位置元素一定是(list,2,300);
    
            // [2000, 100, 200, 300, 1000]
            r = list.remove(100L);
            // [2000, 200, 300, 1000]
            if (r == false) {
                throw new RuntimeException();
            }
    
            检查顺序表是否合法(list);
            断言顺序表的元素个数一定是(list, 4);
            断言顺序表的指定位置元素一定是(list, 0, 2000);
            断言顺序表的指定位置元素一定是(list, 1, 200);
            断言顺序表的指定位置元素一定是(list, 2, 300);
            断言顺序表的指定位置元素一定是(list, 3, 1000);
    
    
            // [2000, 200, 300, 1000]
            list.add(200L);
            list.add(200L);
            // [2000, 200, 300, 1000, 200, 200]
            r = list.remove(200L);
            // [2000, 300, 1000, 200, 200]
            if (r == false) {
                throw new RuntimeException();
            }
    
            检查顺序表是否合法(list);
            断言顺序表的元素个数一定是(list, 5);
            断言顺序表的指定位置元素一定是(list, 0, 2000);
            断言顺序表的指定位置元素一定是(list, 1, 300);
            断言顺序表的指定位置元素一定是(list, 2, 1000);
            断言顺序表的指定位置元素一定是(list, 3, 200);
            断言顺序表的指定位置元素一定是(list, 4, 200);
    
            // 测试如果没有元素 r = remove(5000L);
            r=list.remove(5000L);
            if (r == true) {
                throw new RuntimeException();
            }
        }
    }

MyList接口：

/**
     * 自定义的线性表（以接口的形式体现）
     * 1.元素类型 Long
     * 1）int 下标 long 元素
     * 2）包装类：体现对象的形式而不是基本类型
     * 2.准备线性表的规定
     * 3.教学过程中体现：
     * 有元素的位置！=null
     * 没有元素的位置==null
     */
    public interface MyList {
        /**
         * 返回线性表中的元素个数
         * @return
         */
        int size();
    
        /**
         * 将 e 尾插到线性表中，一定返回 true
         * @param e
         * @return
         */
        boolean add(Long e);
    
        /**
         * 将 e 插入到线性表的 index 位置，从 [index, size()) 向后移
         * index 的合法下标 [0, size()]
         * 如果下标不合法：抛出一个 ArrayIndexOutOfBoundsException
         * @param index
         * @param e
         */
        void add(int index, Long e);
    
        /**
         * 删除 index 位置的元素
         * index 的合法下标：[0, size())
         * 如果下标不合法：抛出一个 ArrayIndexOutOfBoundsException
         * @param index
         * @return 从线性表中删除掉的元素
         */
        Long remove(int index);
    
        /**
         * 从前到后，删除第一个遇到的 e（ equals() == true）
         * @param e
         * @return 删除成功：true，没有该元素：false
         */
        boolean remove(Long e);
    
        /**
         * 直接返回 index 位置的元素
         * index: [0, size())
         * @param index
         * @return
         */
        Long get(int index);
    
        /**
         * 使用 e 替换 index 位置的元素
         * @param index [0, size())
         * @param e
         * @return 原来 index 位置的元素
         */
        Long set(int index, Long e);
    
        /**
         * 返回第一次遇到 e 的下标（equals() == true）
         * @param e
         * @return 如果没有找到，返回 -1
         */
        int indexOf(Long e);
    
        /**
         * 从后往前，返回第一次遇到 e 的下标（equals() == true）
         * @param e
         * @return 如果没有找到，返回 -1
         */
        int lastIndexOf(Long e);
    
        /**
         * 线性表中是否包含 e（equals）
         * @param e
         * @return
         */
        boolean contains(Long e);
    
        /**
         * 清空线性表
         */
        void clear();
    
        /**
         * 判断线性表是否是空的（empty） 等价于一个元素都没有
         * @return
         */
        boolean isEmpty();
    }

![95913d7606e74b85bdab6b0cb7902d0a.png][]

[95913d7606e74b85bdab6b0cb7902d0a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/493ccd92fb064832bd8aee64ae2d79ab.png