Java——模拟实现ArrayList和LinkedList类(一)
由于数组一旦定义,其长度就无法改变,某些情况下给我们的编程带来了不便。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方法重载。。。