ArrayList简单学习
类声明:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
AbstractList是个抽象类,RandomAccess是个给List用的标记接口,为了指明这个容器支持快速(一般是常量时间复杂度)的随机访问。
List接口
public interface List<E> extends Collection<E> {
boolean add(E e);
void add(int index, E element);
boolean remove(Object o);
E remove(int index);
E set(int index, E element);
E get(int index);
...
}
ArrayList的类变量
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
第一个是默认容量;
第二个是当用户指定ArrayList的容量为0的时候,返回的一个数组。
第三个是一个空数组实例
- 当用户没有指定 ArrayList 的容量时(即调用无参构造函数),返回的是该数组==>刚创建一个 ArrayList 时,其内数据量为 0。
- 当用户第一次添加元素时,该数组将会扩容,变成默认容量为 10(DEFAULT_CAPACITY) 的一个数组===>通过 ensureCapacityInternal() 实现
-它与 EMPTY_ELEMENTDATA 的区别就是:该数组是默认返回的,而后者是在用户指定容量为 0 时返回
第四个是真正保存数据data的数组,ArrayList 的容量就是该数组的长度
第五个显然就是ArrayList里面存了的元素的个数了。
构造函数
无参:
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
就将elementData这个数组指向默认的空数组。
指定容量的:
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
就根据这个传进来的容量,new一个相应的Object数组。
如果传进来的是0,就让elementData指向说好的那个代表这个状态的空数组。
add方法之add(E e)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
介个ensureCapacityInternal方法很明显,就是要确保底层数组的capacity能够装得下原来的size + 1后的数据。
在确保操作完成后,就在末尾添加这个元素。
然后看这个ensureCapacityInternal方法:
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
} ensureExplicitCapacity(minCapacity);
}
第一个if中,意思是这是不是用户调用默认构造器构造了ArrayList实例后第一次添加元素,是的话,此时底层数组的length是为0的。那么就更新这个minCapacity,如果传进来的minCapacity比10小,就变成10.
所以这个方法的意思是,确定正确的底层数组的capacity值。
再调用ensureExplicitCapacity方法:
ensureExplicitCapacity:
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
这个方法意思是,真正去确保底层数组有这个minCapacity的length。
如果现在这个底层数组的length还没到这个需要有的最小capacity的值,就要扩容。
这个modCount++是因为ArrayList的结构要变了,如果扩容的话,底层数组的length变而且添加了一个新值;如果不用扩容,则因为添加了新值,所以结构变化。
然后看这个grow方法:
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
由这个
int newCapacity=oldCapacity+ (oldCapacity >> 1);
可见,默认的扩容方式应该是原来的数组length + 原来的length/2。
如果这个默认的加大方法不足以达到minCapacity的要求,就直接newCapacity为minCapacity,如果newCapacity比最大值还大,就用hugeCapacity方法返回一个符合固定的值(如果很大就返回Integer.MAX_VALUE)。
然后就调用Arrays数组的一个复制数组的方法,elementData指向一个新的容量是newCapacity的新Object数组。(注意还没插入新值的),然后回到add方法里面在已经够容量的数组里面插入新值就搞定。
add(int index, E element)方法
public void add(int index, E element) {
rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
第一行是越界检查的方法。
第二行上面介绍了,是保证底层数组的length足够装下原来的size + 1个数据,调用后可能什么都没做,也可能扩容了。
第三行是调用System的一个static方法,这是个复制数组的方法,把index开始的size - index个元素,移到(同一个数组)的index + 1到index + 1 + (size - index)的位置去,也就是index开始的所有元素往后挪咯。(性能开销就是在这些操作)
然后再在index的位置赋值咯,size即ArrayList容纳的元素个数加一。
remove(int index)方法
public E remove(int index) {
rangeCheck(index); modCount++;
E oldValue = elementData(index); int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work return oldValue;
}
前面两行就不解释了,第三行获得要删除的那个元素。
numMoved——删除这个元素后,index后面的需要往前挪的元素的个数。
numMoved表示在执行删除操作时数组需要移动的元素个数,将elementData数组中从index后一位开始的所有元素(即numMoved个元素)往前"移动"1位(这样一移动,index位置的元素会被后面的元素覆盖,间接起到了删除元素的作用),然后把最后的那个元素置空,(然后gc就可以处理了)同时将size变量减1。
还有个remove(Object o)差不多:
public boolean remove(Object o) {
if (o == null) {//删null值喔
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
} /*
* Private remove method that skips bounds checking and does not
* return the value removed.一个没有范围检查和没有返回值的快速删除函数
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
有个删null对象的操作,然后还有个fastRemove而已,不多讲了。
get和set方法
直接用数组的方式get和set,很方便。
总结
- ArrayList底层实现是数组。
- 当使用无参数构造函数创建ArrayList对象时,ArrayList对象中的数组初始长度为0(是一个空数组)。
- ArrayList的扩容策略是每次都增加当前数组长度的一半(非固定分配)。
- ArrayList的扩容方式是直接创建一个新的数组,并将数据拷贝到新数组中。
最新文章
- 滑动验证的设计与实现J2EE
- mysql互换表中两列数据方法
- IOS开发中有用的第三方库
- php工具 phpstorm 的快捷键 的使用(待添加
- 工作中遇到的问题--eclipse没有方法提示
- Demo_张仕传_结构体考试-modify
- Gora官方文档之二:Gora对Map-Reduce的支持
- BZOJ 1018
- Spring Resource之ResourceLoaderAware接口
- JavaSE 教程的选择
- href与src 区别
- Tomcat 调优方案
- Linux 的文件权限和目录配置
- Android 性能优化之减少UI过度绘制
- python名片管理
- Linux安装Apache常见报错(二)
- PHP请求ws出现的问题
- Nginx主程序使用介绍
- Verilog使用相对路径时应注意的问题
- 主动学习(Active Learning)
热门文章
- centos 7 / 6 smokeping安装
- mongodb给我们提供了fsync+lock机制把数据暴力的刷到硬盘上
- Material Design 之 定义状态栏(Status Bar)的颜色
- CodeForces813E:Army Creation (主席树---上一题的加强版)
- the generation has been cancelled because errors have been found by the check model
- PHP多种序列化/反序列化的方法 json_encode json_decode
- Azure SQL Database (27) 创建Table Partition
- RTC驱动程序分析
- nginx proxy https
- 20个Flutter实例视频教程-第07节: 毛玻璃效果制作