欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java——模拟实现ArrayList和LinkedList类(一)

程序员文章站 2022-04-18 18:37:39
...

由于数组一旦定义,其长度就无法改变,某些情况下给我们的编程带来了不便。Java提供了两个集合——ArrayList类和LinkedList类,用来代替数组,有效解决了数组长度不能动态改变的问题。

为了加深对数组和这两个集合类的理解,于是模拟这两个类实现了两个Box类,用来代替Array。为了方便,这里只实现了存储int类。

模拟实现ArrayList

ArrayList 的好处是:可以动态增加数组长度,便于遍历数组,但是增加和删除数组内元素开销比较大。

 

代码实现:

package mybox;

public interface Box {
    public  abstract boolean add(int element);//增加
    public abstract int get(int index);//获取指定位置元素
    public abstract int remove(int index);//删除指定位置元素
    public abstract int size();//获取存储的有效数据长度
    public abstract void show();//展示Box中存储的数据
}

首先定义一个Box接口,规范ArrayBox类和LinkedList类.

 

public class ArrayBox implements Box{
    //设计一个静态常量 用来存储数组的默认长度
    private static  final int DEFAULT_CAPACITY = 10;
    //设计一个自己的属性 用来存放真实的数据
    private int[] elementData;
    //设计一个自己的属性,用来记录数组内存储的有效元素个数
    private int size=0;

在ArrayBox类中实现Box接口,并且定义三个属性,DEFAULT_CAPACITY用来指定初始化时默认数组的长度,int[] elementDate用来存储数据,size用来标记存储的数据个数。

从这里可以看出,ArrayBox底层实际上还是依靠数组来完成数据存储的。那么他是怎么解决数组长度不可变的呢?慢慢往下看。

 

  public ArrayBox(){
        elementData=new int[DEFAULT_CAPACITY];
    }
    public ArrayBox(int capacity){
        elementData = new int[capacity];
    }

这里定义了两个构造函数,一个数默认无参的构造函数,构建出的底层数组长度就是一开始设置的DEFAULT_CAPACITY长度;

另一个是我们自己定义的有参构造函数,用于建立指定长度的底层数组。

 

由于实现了Box接口,所以接下来我们就来重写Box中的五个方法:

1、add()方法

 public boolean add(int element){
        //确保数组容量够用
        this.ensureCapacityInternal(size+1);
        //直接将新来的元素存入数组中,并且让size多记录一个
        elementData[size++]=element;//先将element值赋给elementData[size],之后size再++
        //返回true确认插入成功
        return true;
    }

在向ArrayBox对象中增加元素时,首先我们要确定这个对象底层的数组容量还够不够。如果够,我们就直接放就好了,如果不够就需要对数组进行扩容。

ensureCapacityInternal()方法的参数是当传入一个element后,数组装下这个元素所需要的最小长度。这里size是实际以及存储的元素个数,size+1就是如果 加入这个新来的元素,需要的最小数组长度。

 

为了判断数组容量是否足够,我们又新定义了一个方法:ensureCapacityInternal()

 //确保数组内部的容量
    private void ensureCapacityInternal(int minCapacity){
        //判断所需要的最小容量与原数组容量关系
        if(minCapacity-elementData.length>0){//如果所需长度比定义的数组长度大
            this.grow(minCapacity);//对数组进行扩容
        }
    }

在这里我们可以看到,当数组长度不够时,我们调用了grow()方法来对数组进行扩容。ArrayBox能改变长度的原因就在这里了。

  //给数组扩容
    private void grow(int minCapacity){
        //先获取原数组长度
        int oldCapacity=elementData.length;
        //新数组长度扩围原来的1.5倍
        int newCapacity = oldCapacity+(oldCapacity>>1);

        if(newCapacity-minCapacity<0){
            newCapacity=minCapacity;
        }
        elementData = this.copyOf(elementData,newCapacity);
    }

传入的参数是存储当前元素所需要的最小长度。为了保证充足的容量存放数据,也避免每来一个元素都要调用一次grow()方法以及一次性扩容太多导致内存浪费,所以选择每次扩容为当前容量的1.5倍。出于效率考虑,这里的0.5倍采用移位计算(底层二进制向右移位表示缩小为原来的1/2,这样的计算速度快一点)如果扩容1.5倍还不够的话,就直接扩容到所需要的最小长度。

(我们这里所设计的是一个元素一个元素的增加,所以 

if(newCapacity-minCapacity<0){
            newCapacity=minCapacity;
        }

这行代码会显得无意义。但是当我们传入的不是单个元素,而是想要将另一个数组中的元素增加进来时,就可能出现扩容1.5倍依然不够存放的情况,这时候我们就直接扩容到装下所有元素所需要的最小长度就可以了)

 

elementData = this.copyOf(elementData,newCapacity);

这行代码中,我们在函数:copyOf()中创建了一个长度为newCapacity的新的数组,将原数组内容存入这个新数组,并将新数组的引用返回,并赋值给elementData。这样表面上看就是这个数组扩容了,实际上elementData中存储的引用已经改变了。

 private int[] copyOf(int[] oldArray,int newCapacity){
        int[] newArray=new int[newCapacity];
        for(int i=0;i<oldArray.length;i++){
            newArray[i]=oldArray[i];
        }
        return newArray;
    }

 

至此,数组的扩容环节已经全部完成。此时我们再返回add()方法中,和给普通数组赋值一样往内增加就可以了。

 

2、remove()方法

 //用来删除给定位置的元素,参数是索引
    public int remove(int index){
        this.rangeCheck(index);
        //找到index位置的元素 保留起来留给用户
        int oldValue = elementData[index-1];
        for(int i=index-1;i<size-1;i++){
            elementData[i]=elementData[i+1];
        }
        //将最后一个元素删除,并让size减少一个记录
        elementData[--size]=0;
        return oldValue;
    }

在删除元素之前,需要判断我们传进来的索引是否合法,有没有越界。

定义rangeCheck()方法:

 //判断给定的index是否合法
    private void rangeCheck(int index){
        if(index<0||index>=size){
            //自定义一个异常 来说明问题
           throw new BoxIndexOutOfBoundsException("Index"+index+",Size"+size);
        }
    }

如果索引越界,就抛出异常(自定义异常),否则就继续执行。当要删除第index个元素(即elementDa[index-1])时,将第index+1个元素开始后面的每一个元素往前挪一个位置,即覆盖前一个位置的值,这样就达到了删除的效果。但是这样也会造成一个问题,我们只是将原本这个位置的值覆盖了,但是数组长度并没有改变。 操作完成后,数组最后一个位置其实还是有值,只是值为0;这里其实应该调用一个自定义方法,在该方法中重新建立一个数组,长度为删除元素后当前数组的长度。

 

3、get()

 public int get(int index){
        //先检测给定的index是否合法
        this.rangeCheck(index);
        //若合法,则找到对应位置的元素
        return elementData[index-1];
    }

4、size()

//设计方法获取size有效个数
    public int size(){
        return size;
    }

5、show()

 public void show(){
        for(int i=0;i<size;i++){
            System.out.print(elementData[i]+"  ");
        }
    }

 

至此,一个简化版的ArrayList类就完成了。

如果想要更接近真实的ArrayLi类,可以将elementData数组做成 泛型,然后add、remove、get方法重载。。。