ArrayList是java集合框架中比较常用的数据结构,其实底层就是一个数组的操作实现,但是这个数组呢可以实现容量大小的动态变化,这就是比较特别的地方吧。另外ArrayList不是线程安全的。
框架结构
从图中可以看出ArrayList类继承了AbstractList类,实现了List、RandomAccess、Serialzable、Cloneable接口
实现RandomAccess接口:可以通过下标序号快速访问
实现了Cloneable,能被克隆
实现了Serializable,支持序列化
成员变量
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;
...
}
- DEFAULT_CAPACITY默认容量是10
- EMPTY_ELEMENTDATA 空集合
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA 默认空集合 (与EMPTY_ELEMENTDATA有点区别,在不同的构造函数中用到),第一个元素添加时会扩容成默认容量10
- elementData真正存放数据的地方
- size 数组元素个数
构造函数
/** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative */
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);
}
}
指定初始化长度,当然这个初始化容量长度不能小于0,如果等于0,则赋一个空集合EMPTY_ELEMENTDATA。
/** * Constructs an empty list with an initial capacity of ten. */
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
这是最常用的默认构造方法,其中使用默认的初始容量大小10,并赋予一个空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
/** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
使用已有集合来创建ArraList,将集合里的值复制到ArrayList中。首先把集合转换成数组,然后判断转换的数组类型是否为Obejct[]类型,如果是则将数组的值拷贝到list中,否则或者容量为0,则赋予一个空数组
常用的操作
添加操作
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
//扩容之后再添加元素
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新容量为原来容量的二分之三倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//新容量小于需要扩容的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//新容量大于数组能申请的最大值 MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
size表示ArrayList的元素个数。在添加元素之前先要确保数组有足够容量。当当前数组需要的空间不够时,就需要扩容了,并且保证新容量不能比当前需要的容量小,然后调Arrays.copyOf()创建一个新的数组并将数据拷贝到新数组中,且把引用赋值给elementData
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++;
}
指定数组index位置添加元素。首先会检查index是否超出数组的范围;然后既然要添加元素,就要保证有足够的数组空间;当然要在index位置插入元素,得让index后所有的元素往后移动一位,腾出index位置设置要添加的元素。
添加元素时,都涉及到了对数组的复制移动,用到了两种方法
Arrays.copyOf(elementData, newCapacity);
System.arraycopy(elementData, index, elementData, index + 1,size - index);
第一个方法是生成一个同样大小的新对象,当然底层也是使用了System.arraycopy方法
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
第二个方法是将数组复制到指定数组中,还可以选择复制数组的长度。使用arraycopy方法 自己复制自己,将数组要放置的地方的对象移到后面去
实质上都是底层clone来的结果
删除操作
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;
}
删除指定位置的元素。首先也是检查index的合法性,然后取得该位置的旧元素,计算需要移动的长度,如果需要移动的,则调用System.arraycopy方法将index位置后的元素所有往前移动一位,将数组最后一位置为null,方便GC工作,最后返回被删除的元素。
public boolean remove(Object o) {
if (o == 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 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
}
删除指定元素,这里删除的是数组中第一个找到的元素。fastRemove方法移除,这里没有进行index范围检查
获取操作
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
获取指定index位置的元素。这个实现很简单,首先index范围检查,然后直接取数组中index位置元素返回。
修改操作
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
修改指定位置的元素,并返回旧值
迭代器
使用集合的都知道,在for循环遍历集合时不可以对集合进行删除操作,因为删除会导致集合大小改变,从而导致数组遍历时数组下标越界,严重时会抛ConcurrentModificationException异常
使用迭代器遍历删除,运行正常
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
从代码中可以看出iterator方法返回的是一个Itr()对象。
Itr对象有三个成员变量:
cursor:代表下一个要访问的数组下标
lastRet:代表上一个要访问的数组下标
expectedModCount:代表ArrayList修改次数的期望值,初始为modeCount
Itr有三个主要函数:
hasNext:实现简单,判断下一个要访问的数组下标等于数组大小,表示遍历到最后了
next:首先判断 expectedModCount 和 modCount 是否相等。每调用一次 next 方法, cursor 和 lastRet 都会自增 1。
remove :首先会判断 lastRet 的值是否小于 0,然后在检查 expectedModCount 和 modCount 是否相等。然后直接调用 ArrayList 的 remove 方法删除下标为 lastRet 的元素。然后将 lastRet 赋值给 cursor ,将 lastRet 重新赋值为 -1,并将 modCount 重新赋值给 expectedModCount。
remove方法弊端:
调用 remove 之前必须先调用 next。因为 remove 开始就对 lastRet 做了校验。而 lastRet 初始化时为 -1。
next 之后只可以调用一次 remove。因为 remove 会将 lastRet 重新初始化为 -1
总结
ArrayList是一个可以自动扩容的动态数组。
ArrayList的默认容量大小是10
扩容为原来的1.5倍,如果1.5倍还不够的话,直接扩容成我们所需要的容量,1.5倍或所需容量太大的话,直接扩容成Integer.MAX_VALUE或MAX_ARRAY_SIZE
扩容之后通过数组拷贝确保元素的准确性,尽量减少扩容机制
复制和扩容使用了Arrays.copyOf和System.arraycopy方法
ArrayList查找效率高,插入删除操作效率相对低
size 为集合实际存储元素个数
elementData.length 为数组长度,表示数组可以存储多少个元素
如果需要边遍历边 remove ,必须使用 iterator。且 remove 之前必须先 next,next 之后只能用一次 remove。
今天的文章JAVA集合-ArrayList分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/15645.html