Java中ArrayList的工作原理详解
1.ArrayList
以数组实现。节约空间,但数组有容量限制。超出限制时会增加50%容量,用System.arraycopy()复制到新的数组。因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。按数组下标访问元素-get(i)、set(i,e)的性能很高,这是数组的基本优势。如果按下标插入元素、删除元素-add(i,e)、remove(i)、remove(e),则要用System.arraycopy()来复制移动部分受影响的元素,性能就变差了。越是前面的元素,修改时要移动的元素越多。直接在数组末尾加入元素-常用的add(e),删除最后一个元素则无影响。
ArrayList是一个相对来说比较简单的数据结构,最重要的一点就是它的自动扩容。
2.构造方法
ArrayList提供了三个构造方法:
ArrayList(intinitialCapacity):指定容量 ArrayList():构造一个默认容量为10的ArrayList ArrayList(Collectionc):构造一个指定Collection的ArrayList
3.add
//添加指定元素到list末尾 publicbooleanadd(Ee){ //检查是否需要扩容 ensureCapacityInternal(size+1);//IncrementsmodCount!! //赋值 elementData[size++]=e; returntrue; } privatevoidensureCapacityInternal(intminCapacity){ if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){ //比较默认的容量10和传入的容量,返回大点的数 minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity); } //扩容 ensureExplicitCapacity(minCapacity); } privatevoidensureExplicitCapacity(intminCapacity){ //记录修改次数 modCount++; //overflow-consciouscode if(minCapacity-elementData.length>0) grow(minCapacity); } privatevoidgrow(intminCapacity){ //overflow-consciouscode //记录当前list的容量 intoldCapacity=elementData.length; //扩展为原来的1.5倍 intnewCapacity=oldCapacity+(oldCapacity>>1); //如果扩展1.5倍还不能满足,直接扩展为需求值 if(newCapacity-minCapacity<0) newCapacity=minCapacity; if(newCapacity-MAX_ARRAY_SIZE>0) newCapacity=hugeCapacity(minCapacity); //minCapacityisusuallyclosetosize,sothisisawin: elementData=Arrays.copyOf(elementData,newCapacity); }
也就是说,当增加数据的时候,如果ArrayList的大小已经不满足需求时,那么数组大小就会变为原来的1.5倍,之后就是把老的数据拷贝新的数组里面。例如我创建的list的容量时10,当我们已经添加了10个元素的之后,再添加就会进行自动扩容到15。
get,set
publicEget(intindex){ rangeCheck(index); returnelementData(index); } publicEset(intindex,Eelement){ rangeCheck(index); EoldValue=elementData(index); elementData[index]=element; returnoldValue; }
get()和set()就比较简单了,进行范围检查后就可以进行对应的操作了。由于ArrayList是动态数组,所以我们完全可以根据下标来获取ArrayList中的元素,而且速度还比较快,故ArrayList长于随机访问。
remove
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; }
remove()首先进行范围检查,然后计算移动的开始位置,如果大于0的话就进行移动并返回旧值
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持毛票票!