Java容器ArrayList知识点总结

2023-09-12 08:25:06 59

ArrayList

底层实现是数组，访问元素效率高(查询快，插入、修改、删除元素慢)

与LinkedList相比，它效率高，但线程不安全。

ArrayList数组是一个可变数组，可以存取包括null在内的所有元素

每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小
随着向ArrayList中不断增加元素，其容量自动增长
在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这样可以减少递增式再分配的数量。
所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多进行扩容操作而浪费时间、效率
源码分析

底层使用数组实现

transientObject[]elementData;

构造方法

privatestaticfinalintDEFAULT_CAPACITY=10;
privatestaticfinalObject[]EMPTY_ELEMENTDATA={};
privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};
transientObject[]elementData;
privateintsize;

//构造一个空列表
publicArrayList(){
this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//构造一个指定初始容量的空列表
publicArrayList(intinitialCapacity){
if(initialCapacity>0){
this.elementData=newObject[initialCapacity];
}elseif(initialCapacity==0){
this.elementData=EMPTY_ELEMENTDATA;
}else{
thrownewIllegalArgumentException("IllegalCapacity:"+
initialCapacity);
}
}


//构造一个指定Collection元素的列表，这些元素按照Connection元素的迭代返回顺序进行排列
publicArrayList(Collectionc){
elementData=c.toArray();
if((size=elementData.length)!=0){
//c.toArraymight(incorrectly)notreturnObject[](see6260652)
if(elementData.getClass()!=Object[].class)
elementData=Arrays.copyOf(elementData,size,Object[].class);
}else{
//replacewithemptyarray.
this.elementData=EMPTY_ELEMENTDATA;
}
}

存储

//在列表的指定位置的元素用element替代，并且返回该位置原来的元素
publicEset(intindex,Eelement){
rangeCheck(index);//检查数组容量，抛出：IndexOutOfBoundsException

EoldValue=elementData(index);
elementData[index]=element;
returnoldValue;
}

//在列表的尾部添加指定元素
publicbooleanadd(Ee){
ensureCapacityInternal(size+1);//数组扩容
elementData[size++]=e;
returntrue;
}

//在列表的指定位置添加元素
publicvoidadd(intindex,Eelement){
rangeCheckForAdd(index);

ensureCapacityInternal(size+1);//IncrementsmodCount!!

//src:源数组,srcPro:源数组中的起始位置
//dest:目标数组，destPost:目标数组的起始位置，length:要复制的数组元素数量
//将当前位于该位置的元素以及所有后续元素后移一个位置
System.arraycopy(elementData,index,elementData,index+1,
size-index);
//用element替换index位置的元素
elementData[index]=element;
size++;
}

//在列表的尾部添加Connection中的元素，元素顺序按照Connection迭代器返回的顺序
publicbooleanaddAll(Collectionc){
Object[]a=c.toArray();//转化为一个数组

intnumNew=a.length;
ensureCapacityInternal(size+numNew);//IncrementsmodCount

//IncrementsmodCount!!
System.arraycopy(a,0,elementData,size,numNew);
size+=numNew;
returnnumNew!=0;
}

//在列表的指定位置添加Connection中的元素，元素顺序按照Connection迭代器返回的顺序
publicbooleanaddAll(intindex,Collectionc){
rangeCheckForAdd(index);

Object[]a=c.toArray();
intnumNew=a.length;
ensureCapacityInternal(size+numNew);//IncrementsmodCount

intnumMoved=size-index;
if(numMoved>0)
System.arraycopy(elementData,index,elementData,index+numNew,
numMoved);

System.arraycopy(a,0,elementData,index,numNew);
size+=numNew;
returnnumNew!=0;
}

读取

//移除此列表指定位置上的元素
publicEremove(intindex){
rangeCheck(index);

modCount++;
EoldValue=elementData(index);

intnumMoved=size-index-1;
if(numMoved>0)
System.arraycopy(elementData,index+1,elementData,index,
numMoved);
elementData[--size]=null;//cleartoletGCdoitswork

returnoldValue;
}

//移除此列表中的某个元素
publicbooleanremove(Objecto){
if(o==null){
for(intindex=0;index0)
System.arraycopy(elementData,index+1,elementData,index,
numMoved);
elementData[--size]=null;//cleartoletGCdoitswork
}

数组扩容

每当向数组中添加元素时，都需要去检查添加元素后元素的个数是否超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。

publicvoidensureCapacity(intminCapacity){
intminExpand=(elementData!=DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
?0:DEFAULT_CAPACITY;

if(minCapacity>minExpand){
ensureExplicitCapacity(minCapacity);
}
}

privatevoidensureCapacityInternal(intminCapacity){
if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

privatevoidensureExplicitCapacity(intminCapacity){
modCount++;

//overflow-consciouscode
if(minCapacity-elementData.length>0)
grow(minCapacity);
}

privatevoidgrow(intminCapacity){
//overflow-consciouscode
intoldCapacity=elementData.length;
intnewCapacity=oldCapacity+(oldCapacity>>1);
if(newCapacity-minCapacity<0)
newCapacity=minCapacity;
if(newCapacity-MAX_ARRAY_SIZE>0)
newCapacity=hugeCapacity(minCapacity);
//minCapacityisusuallyclosetosize,sothisisawin:
elementData=Arrays.copyOf(elementData,newCapacity);
}

privatestaticinthugeCapacity(intminCapacity){
if(minCapacity<0)//overflow
thrownewOutOfMemoryError();
return(minCapacity>MAX_ARRAY_SIZE)?
Integer.MAX_VALUE:
MAX_ARRAY_SIZE;
}

手写ArrayList

publicclassMyArrayList/*implementsList*/{
privatetransientObject[]elementData;
privateintsize;//元素个数

publicMyArrayList(){
this(10);
}

publicMyArrayList(intinitialCapacity){
if(initialCapacity<0){
try{
thrownewException();
}catch(Exceptione){
e.printStackTrace();
}
}
elementData=newObject[initialCapacity];
}

publicintsize(){
returnsize;
}

publicbooleanisEmpty(){
returnsize==0;
}
//根据index删掉对象
publicvoidremove(intindex)throwsException{
rangeCheck(index);
intnumMoved=size-index-1;
if(numMoved>0){
System.arraycopy(elementData,index+1,elementData,index,numMoved);
}
elementData[--size]=null;
}
//删掉对象
publicbooleanremove(Objectobj)throwsException{
for(inti=0;i=size){
thrownewException();
}
}
//扩容
publicvoidensureCapacity(){
//数组扩容和内容拷贝
if(size==elementData.length){
//elementData=newObject[size*2+1];这么写原来数组里的内容丢失
Object[]newArray=newObject[size*2+1];
//拷贝数组里的内容
/*for(inti=0;i

Java容器ArrayList知识点总结

热门推荐

随机推荐