Java使用数组实现ArrayList的动态扩容的方法
提到数组大家肯定不会陌生，但我们也知道数组有个缺点就是在创建时就确定了长度，之后就不能更改长度。所以Java官方向我们提供了ArrayList这个可变长的容器。其实ArrayList底层也是用数组进行实现的，今天我们就自己使用数组实现ArrayList的功能。
一、整体框架
废话不多说，我们以存放int类型元素为例，看一下ArrayList需要的成员变量和需要实现的方法。
publicclassArrayList
privateintsize;//用来记录实际存储元素个数
privateint[]elements;//用来存储元素的数组
//构造方法：在创建ArrayList对象时，初始化elements数组
publicArrayList(intcapacity){
elements=newint[capacity];
}
/**
*元素的数量
*@return
*/
publicintsize(){}
/**
*是否为空
*@return
*/
publicbooleanisEmpty(){}
/**
*查看元素的索引
*@paramelement
*@return
*/
publicintindexOf(intelement){}
/**
*是否包含元素
*@paramelement
*@return
*/
publicbooleancontains(intelement){}
/**
*获取index位置的元素
*@paramindex
*@return
*/
publicintget(intindex){}
/**
*设置index位置的元素
*@paramindex
*@paramelement
*@return原来的元素
*/
publicintset(intindex,intelement){}
/**
*在index索引位置插入元素
*@paramindex
*@paramelement
*/
publicvoidadd(intindex,intelement){}
/**
*添加元素到尾部
*@paramelement
*/
publicvoidadd(intelement){}
/**
*删除index位置的元素
*@paramindex
*@return
*/
publicintremove(intindex){}
/**
*清除所有元素
*/
publicvoidclear(){}
/**
*用来打印列表
*/
publicStringtoString(){}
}
二、方法实现
框架我们已经有了，接下来我们一步步实现方法就行。
size()方法：
这个方法很简单，因为我们有size属性，直接将其返回就行了。
publicintsize(){
returnsize;
}
isEmpty()方法：
这个方法也很简单，判断是否为空只需要判断size是否为0即可。
publicbooleanisEmpty(){
returnsize==0;
}
indexOf(intelement)方法：
这个方法是用来查询元素的所在索引位置，并返回。我们通过遍历列表查找即可，找到就将元素返回，没有找到返回-1。
publicintindexOf(intelement){
for(inti=0;i
contains(intelement)方法：
这个方法是用来查看所传元素是否在数组中，我们可以直接通过indexOf()方法查看返回值是否不等于-1，不等于-1返回true，等于-1返回false。
publicbooleancontains(intelement){
returnindexOf(element)!=-1;
}
get(intindex)方法：
这个方法用来获取指定索引位置的元素，我们直接返回数组的指定索引位置元素即可。
publicintget(intindex){;
returnelements[index];
}
set(intindex,intelement)方法:
这个方法用来将指定索引位置元素改为指定元素，并将原来元素返回，我们通过数组索引获取到该位置元素，并将指定元素赋值给该位置索引并将原来元素返回。
publicintset(intindex,intelement){
intold=elements[index];
elements[index]=element;
returnold;
}
add(intindex,intelement)方法：
个方法是在指定索引位置插入指定元素，我们首先将指定索引位置的元素以及之后所有的元素向后移动一位，然后再将指定元素赋值给数组的指定索引位置，最后并将size加1。
publicvoidadd(intindex,intelement){
for(inti=size;i>index;i--){
elements[i]=elements[i-1];
}
elements[index]=element;
size++;
}
add(intelement)方法：
这个方法是在数组尾部添加元素，我们直接调用add(intindex,intelement)方法，将size作为index的参数传入即可。
publicvoidadd(intelement){
add(size,element);
}
remove(intindex)方法：
这个方法用来删除指定索引位置的元素，并将要删除元素返回，我们首先通过指定索引获取原来元素，当删除该元素后需要将index索引后面的所有元素向前移动一位，最后将size减1。
publicintremove(intindex){
intold=elements[index];
for(inti=index+1;i
clear()方法：
这个方法，用于清空数组中所有元素，我们只需要将size赋值为0即可。
publicvoidclear(){
size=0;
}
toString()方法：
这个方法用于将所有元素打印出来，通过StringBuilder对象进行拼接，最后转成字符串返回即可。
publicStringtoString(){
StringBuilderstring=newStringBuilder();
string.append("size=").append(size).append(",[");
for(inti=0;i
以上代码基本实现了对数组的进行数据的增删改查，但最后想达到我们的目的还要进一步优化。
三、优化
1.实现动态扩容
当我们向数组中添加元素时，如果数组已经满了我们就需要就数组进行动态扩容。扩容的原理并不是真的对原数组进行增加内存操作，而是重新创建一个更大的数组，并将原数组的元素赋给新的数组。我们声明一个私有方法确保添加元素前数组的容量足够。
privatevoidensureCapacity(intcapacity){
intoldCapacity=elements.length;
if(oldCapacity>=capacity)return;
//新容量为旧容量的1.5倍
intnewCapacity=oldCapacity+(oldCapacity>>1);
int[]newElements=newint[newCapacity];
for(inti=0;i
我们在add()方法中首先调用ensureCapacity(intcapacity)方法进行判断数组容量是否足够，不够进行扩容。
publicvoidadd(intindex,Eelement){
ensureCapacity(size+1);
for(inti=size;i>index;i--){
elements[i]=elements[i-1];
}
elements[index]=element;
size++;
}
2.确保索引不越界
当我们在调用传入索引的方法时，首先要保证传入索引在可用范围内，不然会出现角标越界的异常。
定义outOfBound()方法，用于抛出角标越界异常信息。
privatevoidoutOfBounds(intindex){
thrownewIndexOutOfBoundsException("Index:"+index+",Size:"+size);
}
定义rangeCheck()方法用于检查索引是否越界，如果越界，调用outOfBound()抛出异常。
privatevoidrangeCheck(intindex){
if(index<0||index>=size){
outOfBounds(index);
}
}
而对于调用add()方法时所传入的索引范围可以取到size位置，我们在定义一个rangeCheckForAdd()方法，用于检查调用add()方法时索引是否越界。
privatevoidrangeCheckForAdd(intindex){
if(index<0||index>size){
outOfBounds(index);
}
}
在get()方法，set()方法和remove()方法中，先调用rangeCheck()方法，检查传入索引是否越界。
publicintget(intindex){
rangeCheck(index);
returnelements[index];
}
publicintset(intindex,Eelement){
rangeCheck(index);
intold=elements[index];
elements[index]=element;
returnold;
}
publicintremove(intindex){
rangeCheck(index);
intold=elements[index];
for(inti=index+1;i
3.设置常量以及重写构造方法
对于类中的常数我们更希望封装成常量，并且声明一个默认容量，希望在创建对象时未传入容量参数或传入容量参数过小直接创建一个相对大小合适的数组。
privatestaticfinalintDEFAULT_CAPACITY=10;//我们将默认容量设为10
privatestaticfinalintELEMENT_NOT_FOUND=-1;//我们将获取指定元素的索引时，未找到的返回值-1封装为常量
//声明无参构造方法，在调用无参构造方法是直接创建默认容量的数组
publicArrayList(){
elements=newint[DEFAULT_CAPACITY];
}
//声明有参构造方法，在传入参数小于默认容量时，我们仍然创建默认容量数组
publicArrayList(intcapaticy){
capaticy=(capaticy
四、使用泛型
以上步骤已经使用数组完全实现了ArrayList的全部功能，但只能存放int类型的数据，如果我们希望储存其他类型的数据我们只需要使用Java中的泛型就能够完成。
思路与上述完全一样，整体代码如下：
publicclassArrayList{
/**
*元素的数量
*/
privateintsize;
/**
*所有的元素
*/
privateE[]elements;
privatestaticfinalintDEFAULT_CAPACITY=10;
privatestaticfinalintELEMENT_NOT_FOUND=-1;
publicArrayList(){
elements=(E[])newObject[DEFAULT_CAPACITY];
}
publicArrayList(intcapaticy){
capaticy=(capaticyindex;i--){
elements[i]=elements[i-1];
}
elements[index]=element;
size++;
}
/**
*删除index位置的元素
*@paramindex
*@return
*/
publicEremove(intindex){
rangeCheck(index);
Eold=elements[index];
for(inti=index+1;i=capacity)return;
//新容量为旧容量的1.5倍
intnewCapacity=oldCapacity+(oldCapacity>>1);
E[]newElements=(E[])newObject[newCapacity];
for(inti=0;i=size){
outOfBounds(index);
}
}
privatevoidrangeCheckForAdd(intindex){
if(index<0||index>size){
outOfBounds(index);
}
}
@Override
publicStringtoString(){
StringBuilderstring=newStringBuilder();
string.append("size=").append(size).append(",[");
for(inti=0;i
到此这篇关于Java使用数组实现ArrayList的动态扩容的方法的文章就介绍到这了,更多相关JavaArrayList动态扩容内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！