从零手工实现java中的ArrayList容器（三个版本的迭代）

注：为方便理解，分为三个版本，每个版本在上一个的基础上扩展，如果你有足够的基础，可以直接翻到最下面看最终版本代码，我会详细注释

内部方法与变量

add(),set(),get(),remove(),empty(),size(),checkRank(),toString()
size,elementData [],DEFAULT_CAPACITY

核心问题

以上都是实现ArrayList的指导思想，接下来我们直接上代码

第一版

package collection;

/**
 * 自定义实现一个ArrayList
 */
public class MyArrayList {
    //存储元素的数组
    private Object [] elementData;
    //当前元素的个数
    private int size;  
    //数组默认大小
    private final static int DEFAULT_CAPACITY=10;
    
    public MyArrayList(int capacity){
        elementData=new Object[capacity];
    }
    //当没有设置列表大小时，默认为10
    public MyArrayList(){
        elementData=new Object[DEFAULT_CAPACITY];
    }
    //每加一个元素，先把元素放在size位置处（因为此时数组中最后一个元素位于size-1处）,然后size++
    public void add(Object object){
        elementData[size++]=object;
    }
    
    //将数组转换为列表的样式输出，
    @Override
    public String toString() { 
        StringBuilder stringBuilder=new StringBuilder("[");
        for(int i=0;i<size;i++) {
            stringBuilder.append(elementData[i]);
            stringBuilder.append(",");
        }
        //现在stringBuilder中最后一个字符时逗号，我们将它转换为]号
        stringBuilder.setCharAt(stringBuilder.length()-1,']');
        return stringBuilder.toString();
    }

    public static void main(String[] args){
        MyArrayList myArrayList =new MyArrayList();
        myArrayList.add("a");
        
        System.out.println(myArrayList);
        for(int i=0;i<5;i++){
            myArrayList.add("a"+i);
        }
        System.out.println(myArrayList);

    }
}

效果如图

但是明显有很多问题，除了方法少之外，还有数组越界没有检查，而且不能设置泛型

第二版

package collection;

/**
 * arraylist数组扩容add()，泛型,size,empty
 */
//设置泛型比较简单，直接在类名后加，并且修改传入元素的类型名(add())
public class MyArrayList02<E> {
    private Object [] elementData;
    private int size;
    private final static int DEFAULT_CAPACITY=10;

    public MyArrayList02(int capacity){
        elementData=new Object[capacity];
    }
    public MyArrayList02(){
        elementData=new Object[DEFAULT_CAPACITY];
    }
    
    //边界检查，当实际容量(size)达到了数组最大容量之后
    //我们将新建一个比原来大1/2的数组，然后再赋给原来的数组
    public void add(E object){
        if(size==elementData.length){
            Object [] newArray=new Object[elementData.length+elementData.length<<1];
            System.arraycopy(elementData,0,newArray,0,elementData.length);
            elementData=newArray;
        }
        elementData[size++]=object;
    }
    //获得列表长度
    public int size(){
        return size;
    }
    //判定是否为空
    public boolean empty(){
        if(size==0){
            return true;
        }
        return false;
    }
    @Override
    public String toString() {
        StringBuilder stringBuilder=new StringBuilder("[");
        for(int i=0;i<size;i++) {
            stringBuilder.append(elementData[i]);
            stringBuilder.append(",");
        }
        stringBuilder.setCharAt(stringBuilder.length()-1,']');
        return stringBuilder.toString();
    }

    public static void main(String[] args){
        MyArrayList03<String> myArrayList02 =new MyArrayList03<>();
        for(int i=0;i<20;i++) {
            myArrayList02.add("a"+i);
        }
        System.out.println(myArrayList02);
        System.out.println("数组长度："+myArrayList02.size());
        System.out.println("数组是空吗？"+myArrayList02.empty());
    }
}

原数组默认只有10，自动将数组扩容，新增大小为原来的1/2，用移位的方法获得，这也是ArrayList源码中使用的方法，并且新增了size(),empty()方法

但是，依旧有问题，比如新建一个空列表~

第三版

package collection;

/**
 * set,get,checkRank边界检查,remove
 */
public class MyArrayList03<E> {
    private Object [] elementData;
    private int size;
    private final static int DEFAULT_CAPACITY=10;
    //这里表示传入有容量的列表
    public MyArrayList03(int capacity){
        if(capacity<0){
            throw new RuntimeException("容量不能为负");
        }
        elementData=new Object[capacity];
    }
    //这里是没有传参的列表，默认容量是10
    public MyArrayList03(){
        elementData=new Object[DEFAULT_CAPACITY];
    }
    //添加元素，先判定是否到了数组边界，如果到了就扩容，然后添加一个位置
    public void add(E object){
        if(size==elementData.length){
            Object [] newArray=new Object[elementData.length+elementData.length<<1];
            System.arraycopy(elementData,0,newArray,0,elementData.length);
            elementData=newArray;
        }
        elementData[size++]=object;
    }
    //移除元素，将目标元素后面的元素挨个赋给前一位，这样会导致最后一位和倒数第二位相同，size--不输出最后一位
    //为了避免意外错误，我们把最后一位手动设为空
    public void remove(int index){
        //a,b,c,d,e,f
        //a,b,c,e,f
        checkRank(index);
        int moveElement=size-index-1;
        if(moveElement>0) {
            elementData[size] = null;
            System.arraycopy(elementData, index + 1, elementData, index, moveElement);
        }
        size--;
        
    }
    @Override
    public String toString() {
        StringBuilder stringBuilder=new StringBuilder("[");
        if(size==0)stringBuilder.append("]");
        //这里以size为输出大小，所以以后的add或者remove等只需要修改size就可以获得位置或者删除位置
        for(int i=0;i<size;i++) {
            stringBuilder.append(elementData[i]);
            stringBuilder.append(",");
        }
        //将最后一个逗号改为"]"
        stringBuilder.setCharAt(stringBuilder.length()-1,']');
        return stringBuilder.toString();
    }
    
    public E get(int index){
        checkRank(index);
        return (E)elementData[index];
    }
    public void set(E e,int index){
        checkRank(index);
        elementData[index]=e;
    }
    //检查数组是否越界
    public void checkRank(int index){
        if(index<0||index>size-1){
            throw new ArrayIndexOutOfBoundsException("索引不合法");
        }
    }
    //获得列表长度
    public int size(){
        return size;
    }
    //判定是否为空
    public boolean empty(){
        if(size==0){
            return true;
        }
        return false;
    }
    public static void main(String[] args){
        MyArrayList03<String> myArrayList03 =new MyArrayList03<>();
        System.out.println(myArrayList03);
        for(int i=0;i<1;i++)
            myArrayList03.add("a"+i);
        System.out.println("添加1个元素后列表长度为"+myArrayList03.size());
        System.out.println("列表元素 "+myArrayList03);
        myArrayList03.remove(0);
        System.out.println("删除第一个元素后 "+myArrayList03);
    }
}

进行了更多的边界检查，同时新增了remove(),get,set等使用方法，也改进了toString方法