JAVA随时笔记(三)：自己实现一个简单的ArrayList

港控/mmm° 2022-05-25 01:06 130阅读 0赞

本着更加深刻的理解ArrayList的目的，所以自己实现一个简单的ArrayList,只是实现了List接口，实现了大部分的方法，其实还有一些地方不完善，比如对于参数的异常判断，返回值的判断，还有常数的直接使用。其实只要明白其中的原理即可。

MyArrayList类：

package testpackge.util;
    
    import java.util.*;
    
    /** * 自己实现ArrayList有，实现List接口，实现大部分方法 * * @Authoc: Alic(1071631279 @ qq.com) * @creattime: 2018/5/420:11 */ public class MyArrayList<E> implements List<E>{
    
        /** * MArrayList内部实际是一个object数组，初始化默认是一个空的数组 */ private Object[] elementData = {};
        /** * 集合中数据的个数 */ private int size;
    
        /** * 默认空参构造 */ public MyArrayList(){
    
        }
    
        /** *有参构造 * @param capacity 初始化容量 */ public MyArrayList(int capacity){
            this.elementData = new Object[capacity];
        }
    
        /** * 集合作为构造参数 * @param c 初始化加入的集合 */ public MyArrayList(Collection<? extends E> c){
            this.elementData = c.toArray();
            this.size = c.size();
        }
    
    
        /** * 添加元素，默认添加到末尾 * @param e 添加的元素 * @return 返回false */ public boolean add(E e) {
            //扩容方法
            grow(size+1);
            //把元素添加到元素的末尾
            elementData[size++] = e;
            return true;
        }
    
    
        /** * 在指定位置添加元素 * @param index 指定索引位置 * @param element 添加的元素 */ public void add(int index, E element) {
            //越界检查
            if(index>size||index<0){
                throw new RuntimeException("ArrayIndexOutOfBoundsException");
            }
            //扩容
            grow(size+1);
            //把elementData的index及后面的size-index个元素复制到elementData的index+1开始的位置上
            System.arraycopy(elementData,index,elementData,index+1,size-index);
            //index赋值element
            elementData[index] = element;
            //size增加
            size++;
        }
    
        /** * 添加一个集合 * @param c 添加的集合 * @return 返回false */ public boolean addAll(Collection<? extends E> c) {
            //转换为数组
            Object[] objects = c.toArray();
            //数组长度
            int num = objects.length;
            //扩容操作
            grow(size+num);
            //把objects的0开始的num个元素复制到elementData的size开始的位置上
            System.arraycopy(objects, 0, elementData, size, num);
            //更改size的值
            size += num;
            return true;
        }
    
    
        /** * 指定位置添加一个集合 * @param index 指定位置索引 * @param c 添加的集合 * @return 返回true */ public boolean addAll(int index, Collection<? extends E> c) {
            //越界检查
            if(index>size||index<0){
                throw new RuntimeException("ArrayIndexOutOfBoundsException");
            }
            //转换为数组
            Object[] objects = c.toArray();
            //数组的长度
            int num = objects.length;
            //扩容
            grow(size+num);
    
            //把elementData的index开始的size-index个元素复制到elementData的index+num开始的位置上
            System.arraycopy(elementData,index, elementData, index+num, size-index);
            //把objects的0开始的num个元素复制到elementData的index开始的位置上
            System.arraycopy(objects,0, elementData, index, num);
            //更新size的值
            size += num;
            return true;
        }
    
    
        /** * 扩容方法 * @param capacity 需要的最小容量值 */ private void  grow(int capacity){
            //集合目前的容量
            int oldcapacity = elementData.length;
            //如果集合初始化为添加任何元素，空的数组
            if(oldcapacity==0){
                //默认容量10
                elementData = new Object[10];
            }else {
                //把容量扩大至原来的1.5倍
                while (capacity < oldcapacity) {
                    //把elementData的数据复制到capacity大小的新数组中并且返回，
                    elementData = Arrays.copyOf(elementData, capacity = oldcapacity + oldcapacity >> 1);
                }
            }
        }
    
    
        /** * 移除o元素 * @param o 删除元素 * @return 找到删除返回true,否则返回false */ public boolean remove(Object o) {
    
            //获取索引位置
            int indexOf = indexOf(o);
            if(indexOf>=0){
                //删除索引indexOf的元素
                remove(indexOf);
                return true;
            }
            return false;
        }
    
        /** * 删除index的元素 * @param index 索引位置 * @return 返回对应元素 */ public E remove(int index) {
            //越界检查
            if(index>size||index<0){
                throw new RuntimeException("ArrayIndexOutOfBoundsException");
            }
            E e = (E)elementData[index];
            //把elementData的index+1开始的size-index-1个元素复制到elementData的index开始的位置上
            System.arraycopy(elementData,index+1,elementData,index,size-index-1);
            //把最后一个元素置为null,便于GC,size更新
            elementData[size--] = null;
            return e;
        }
    
        /** * 移除c的全部集合 * @param c 集合对象 * @return 返回true */ public boolean removeAll(Collection<?> c) {
            //迭代器迭代删除
            Iterator<?> iterator = c.iterator();
            while(iterator.hasNext()){
                Object next = iterator.next();
                remove(next);
            }
            return true;
        }
    
        /** * 获取o对应的索引 * @param o 查找的对象 * @return 返回对应索引位置，找到就返回 */ public int indexOf(Object o) {
            //如果是null值，循环遍历判断有无null值
            if(o==null){
                for(int i = 0;i<size;i++){
                    if(elementData[i]==null){
                        return i;
                    }
                }
            }else{
                //循环遍历判断，使用equals判断是否相等
                for(int i = 0;i<size;i++){
                    if(o.equals(elementData[i])){
                        return i;
                    }
                }
            }
            return -1;
        }
    
        /** * 获取集合中最后一个o值 * @param o 获取o相等的值 * @return 返回对应的索引位置 */ public int lastIndexOf(Object o) {
            //循环从后向前白遍历
            if(o==null){
                for(int i = size-1;i>=0;i--){
                    if(elementData[i]==null){
                        return i;
                    }
                }
            }else{
                for(int i = size-1;i>=0;i--){
                    if(o.equals(elementData[i])){
                        return i;
                    }
                }
            }
            return -1;
        }
    
        /** * 获取size的值 * @return 返回size值 */ public int size() {
            return size;
        }
    
        /** * 判断是否为空，即判断size是否为0 * @return 为空返回true,否则返回false */ public boolean isEmpty() {
            return size==0;
        }
    
        /** * 判断是否包含o值，如果indexOf返回-1就没有对应的值 * @param o 判断包含的值 * @return 包含就返回true,否则返回false */ public boolean contains(Object o) {
            return indexOf(o)>=0;
        }
    
    
        /** * 是否包含c中所有的值 * @param c 判断的集合对象 * @return 全部包含返回true,否则返回false */ public boolean containsAll(Collection<?> c) {
    
            //迭代判断，有一个不是就返回false
            Iterator<?> iterator = c.iterator();
            while(iterator.hasNext()){
                Object next = iterator.next();
                if(indexOf(next)<0){
                    return false;
                }
            }
            return true;
        }
    
    
        /** * 清除集合元素 */ public void clear() {
            //循环遍历置为null.便于GC
            for(int i = size-1;i>=0;i--){
                elementData[i]=null;
            }
            //更改size为0
            size = 0;
        }
    
        /** * 获取index所有上的值 * @param index * @return 返回对应的元素 */ public E get(int index) {
            //越界检查
            if(index>size||index<0){
                throw new RuntimeException("ArrayIndexOutOfBoundsException");
            }
            return (E)elementData[index];
        }
    
    
        /** * 更新index上的值为element * @param index * @param element * @return 返回index旧的值 */ public E set(int index, E element) {
            //越界检查
            if(index>size||index<0){
                throw new RuntimeException("ArrayIndexOutOfBoundsException");
            }
            //index的原始值
            E e = (E)elementData[index];
            //更改index的引用为element
            elementData[index] = element;
            return e;
        }
    
        /** * 转换为数组 * @return 返回数组 */ public Object[] toArray() {
            //创建一个长度为size的数组，循环遍历赋值
            Object[] objects = new Object[size];
            for(int i = 0;i<size;i++){
                objects[i]=elementData[i];
            }
            return objects;
        }
    
        /** * 截取formIndex到toIndex的值的集合，包含左右边界 * @param fromIndex 起始值 * @param toIndex 结束值 * @return 返回截取的集合 */ public List<E> subList(int fromIndex, int toIndex) {
            //越界检查，已经确保fromIndex小于等于toIndex
            if(fromIndex>size||fromIndex<0||toIndex>size||toIndex<0||fromIndex>toIndex){
                throw new RuntimeException("ArrayIndexOutOfBoundsException");
            }
            //创建新的对象
            MyArrayList<E> myArrayList = new MyArrayList();
            //创建toIndex-fromIndex+1长度的数组
            Object[] objects = new Object[toIndex-fromIndex+1];
            //遍历赋值
            for(int i = fromIndex;i<=toIndex;i++){
                objects[i]=elementData[i];
            }
            //设置size值
            myArrayList.size = toIndex-fromIndex+1;
            //设置集合的元素数组
            myArrayList.elementData = objects;
            return myArrayList;
        }
    
    
        /** * 重写toString方法 * @return 返回集合数据的字符串 */ @Override
        public String toString() {
            //创建stringBuder对象
            StringBuilder stringBuilder = new StringBuilder();
            //遍历拼接字符串，每一个对象加一个"，"
            stringBuilder.append("[");
            for(int i = 0;i<size;i++){
                stringBuilder.append(((E)elementData[i]).toString());
                stringBuilder.append(",");
            }
    
            //清除最后一个"，"字符
            int lastIndexOf = stringBuilder.lastIndexOf(",");
            if(lastIndexOf>0){
                stringBuilder.deleteCharAt(lastIndexOf);
            }
            stringBuilder.append("]");
            return stringBuilder.toString();
        }
    
        /** * 迭代器对象 */ public class Itr implements Iterator<E>{
            /** * 迭代到的索引位置 */ private int cursor;
    
            /** * 是否还有下一个元素，即判断迭代位置是否已到size * @return 还有返回true，没有返回false */ @Override
            public boolean hasNext() {
                return cursor!=size;
            }
    
            /** * 返回下一个元素，直接返回elementData的对应数据 * @return 返回对应元素 */ @Override
            public E next() {
                return (E)elementData[cursor++];
            }
        }
    
        /** * 返回迭代器对象，创建一个内部类 * @return 内部类迭代器对象 */ public Iterator<E> iterator() {
            return new Itr();
        }
    
       //下面的方法其实都是一样的，只要明白了其中的原理即可，以下四个方法不实现了
    
        public ListIterator<E> listIterator() {
            return null;
        }
    
        public ListIterator<E> listIterator(int index) {
            return null;
        }
    
        public boolean retainAll(Collection<?> c) {
            return false;
        }
    
        public <T> T[] toArray(T[] a) {
            return null;
        }
    }

Main测试代码：

MyArrayList<ClassA> myArrayList = new MyArrayList();
    ClassA a1 = new ClassA(12,"a1");
    ClassA a2 = new ClassA(13,"a2");
    ClassA a3 = new ClassA(14,"a3");
    ClassA a4 = new ClassA(15,"a4");
    
    System.out.println("------初始化后------");
    System.out.println("size："+myArrayList.size());
    
    System.out.println("------开始添加元素------");
    myArrayList.add(a1);
    System.out.println(myArrayList);
    
    System.out.println("contrins方法,是否包含a1："+myArrayList.contains(a1));
    System.out.println("size：" + myArrayList.size());
    
    System.out.println("在1位置添加一个元素a2");
    myArrayList.add(1,a2);
    System.out.println(myArrayList);
    System.out.println("size：" + myArrayList.size());
    System.out.println("在2位置添加一个元素a3");
    myArrayList.add(2,a3);
    System.out.println(myArrayList);
    System.out.println("size：" + myArrayList.size());
    
    System.out.println("获取2位置上的元素："+myArrayList.get(2));
    
    
    System.out.println("获取a1元素的索引位置：" + myArrayList.indexOf(a1));
    
    System.out.println("判断集合是否为空：" + myArrayList.isEmpty());
    
    System.out.println("移除索引为1的元素：");
    myArrayList.remove(1);
    System.out.println(myArrayList);
    System.out.println("size：" + myArrayList.size());
    System.out.println("移除a3：");
    myArrayList.remove(a3);
    System.out.println(myArrayList);
    System.out.println("size：" + myArrayList.size());
    
    System.out.println("添加a2元素");
    myArrayList.add(a2);
    System.out.println(myArrayList);
    System.out.println("size：" + myArrayList.size());
    System.out.println("更新索引1位置的元素为a4");
    myArrayList.set(1,a4);
    System.out.println(myArrayList);
    System.out.println("添加a3元素");
    myArrayList.add(a3);
    System.out.println(myArrayList);
    System.out.println("size：" + myArrayList.size());
    
    System.out.println("截取索引为0-2的元素，得到subList：");
    List<ClassA> subList = myArrayList.subList(0, 2);
    System.out.println(subList);
    
    System.out.println("clear方法清空subList：");
    subList.clear();
    System.out.println(subList);
    
    System.out.println("toArray方法得到数组：");
    Object[] objects = myArrayList.toArray();
    for (int i = 0,len = myArrayList.size();i<len;i++){
        System.out.println(myArrayList.get(i));
    }
    
    System.out.println("迭代器测试：");
    Iterator<ClassA> iterator = myArrayList.iterator();
    while (iterator.hasNext()){
        System.out.println(iterator.next());
    }
    
    System.out.println("有参构造得到arrayList");
    MyArrayList arrayList = new MyArrayList(myArrayList);

System.*out*.println(arrayList);

输出结果：

------初始化后------
    size：0
    ------开始添加元素------
    [ClassA{age=12, name='a1'}]
    contrins方法,是否包含a1：true
    size：1
    在1位置添加一个元素a2
    [ClassA{age=12, name='a1'},ClassA{age=13, name='a2'}]
    size：2
    在2位置添加一个元素a3
    [ClassA{age=12, name='a1'},ClassA{age=13, name='a2'},ClassA{age=14, name='a3'}]
    size：3
    获取2位置上的元素：ClassA{age=14, name='a3'}
    获取a1元素的索引位置：0
    判断集合是否为空：false
    移除索引为1的元素：
    [ClassA{age=12, name='a1'},ClassA{age=14, name='a3'}]
    size：2
    移除a3：
    [ClassA{age=12, name='a1'}]
    size：1
    添加a2元素
    [ClassA{age=12, name='a1'},ClassA{age=13, name='a2'}]
    size：2
    更新索引1位置的元素为a4
    [ClassA{age=12, name='a1'},ClassA{age=15, name='a4'}]
    添加a3元素
    [ClassA{age=12, name='a1'},ClassA{age=15, name='a4'},ClassA{age=14, name='a3'}]
    size：3
    截取索引为0-2的元素，得到subList：
    [ClassA{age=12, name='a1'},ClassA{age=15, name='a4'},ClassA{age=14, name='a3'}]
    clear方法清空subList：
    []
    toArray方法得到数组：
    ClassA{age=12, name='a1'}
    ClassA{age=15, name='a4'}
    ClassA{age=14, name='a3'}
    迭代器测试：
    ClassA{age=12, name='a1'}
    ClassA{age=15, name='a4'}
    ClassA{age=14, name='a3'}
    有参构造得到arrayList
    [ClassA{age=12, name='a1'},ClassA{age=15, name='a4'},ClassA{age=14, name='a3'}]