java容器体系（二）----List（ArrayList）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java容器体系（二）----List（ArrayList），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含11972字，纯文字阅读大概需要18分钟。
内容图文
一、List的解析
List是 java 中的有序列表，按照元素加入的顺序有序存储，元素可以重复，它的实现类主要包括 ArrayList、Vector 、LinkedList 等。
List 相关类图如下所示：
List提供的方法声明如下图所示：
List 继承自Collection 类，拥有Collection 所有的方法，如 add(E e)、size()、isEmpty()、remove(Object o)、clear()、itrator() 等，同时也有 Collection 没有的方法声明，如 List 提供了可以按照元素的索引位置增删改的方法 add(int index)、remove(int index)、set(int index,E e), List 接口除了正常的itrator()迭代器的功能，还提供了一种特殊的迭代器 ListIterator，该迭代器继承自 Iterator，故提供了Iterator 的一切功能，允许元素的插入和更换，同时允许获取从指定位置开始的迭代器。
ListIterator<E> listIterator(); ListIterator<E> listIterator(int index); // 指定位置开始
二、ArrayList的解析
ArrayList 是 List 的实现子类之一，是最常用的List，它的底层是使用数组实现的，因此需要一段连续的内存空间，数组的大小可以调整。
public
class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}
ArrayList 继承自抽象类 AbstractList ,实现了 List、RandomAccess、Cloneable、Serializable，表明它支持随机访问、克隆及序列化操作，之所以继承AbstractList是因为它当中有部分已有方法体的函数可以供子类直接使用，如果需要的话，子类还可以重写。
1、成员变量常量
private
static
final
int DEFAULT_CAPACITY = 10; // 默认的数组容量，即构造方法无参数时的数组容量privatestaticfinal Object[] EMPTY_ELEMENTDATA = {};
privatestaticfinal Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // 没有使用private修饰方便嵌套类的访问privateint size; // elementData 数组中已存储的元素数量，<=elementData.lengthprotectedtransientint modCount = 0; // 用于记录发生结构性修改的次数，如add、remove方法，codCount会加1
2、构造函数
ArrayList有三个构造函数：
public ArrayList(int initialCapacity) { // 初始化数组容量if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} elseif (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
thrownew IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // {} 空数组 }
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) // 存在不为Object[].class的情况，复制的Object数组赋值给elementData
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;
}
}
Collection 中 toArray 的声明方式为 “Object[] toArray()”，但在参数如果传入 Arrays.asList("a","b","c") 的话，elementData.getClass() 将是String[].class，因为Arrays.asList内部toArray是将内部存储的数组指向传入的数组，存储类型是取决于传入类型，而不一定是Object[]；而如ArrayList存储的Object类型的数组，toArray是以 Arrays.copyOf(elementData, size) 的方式实现的，返回类型当然是Object[]。
2、add方法
ArrayList 中提供了两个 add 方法，一个是在列表的尾部添加元素；一个是在列表指定的位置添加元素，并将原当前位置的元素及其后面的元素向后移动一位。
//
最列表的末尾添加元素
public
boolean
add(E e) {
ensureCapacityInternal(size + 1); // 确保容量足够，modCount+1
elementData[size++] = e;
returntrue;
}
// 将当前位置的元素及之后的向后移动，在指定的位置添加元素publicvoid add(int index, E element) {
rangeCheckForAdd(index); // 检测新添加位置是否<0或者当前已存储元素数量，是的抛出越界异常
ensureCapacityInternal(size + 1); // 确保elementData中的容量大于等于为size + 1!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 先向后移动元素，（将数组中从index位置开始的元素，复制到从index+1开始额位置上，复制数据的长度）
elementData[index] = element;
size++;
}
介绍一下用到的方法：
private
void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // elementData == {} 时，取需要的最小容量和10的较大值，即最小容量的最小值是10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
privatevoid ensureExplicitCapacity(int minCapacity) {
modCount++; // 此时将modCount+1
// 如果需要的最小容量大于当前容量则扩容if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 根据最小容量扩容privatevoid grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量扩充为原来的1.5倍if (newCapacity - minCapacity < 0) // 新容量小于最小容量时（添加一般不会发生，除非原有容量太小）
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // 新容量>Integer.MAX_VALUE - 8时，根据最小容量扩容
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); // 最终扩容}
privatestaticint hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflowthrownew OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; // 最小容量大于MAX_ARRAY_SIZE时，取Integer.MAX_VALUE，否则为MAX_ARRAY_SIZE}
privatevoid rangeCheckForAdd(int index) {
if (index > size || index < 0)
thrownew IndexOutOfBoundsException(outOfBoundsMsg(index));
}
3、addAll方法
ArrayList提供了两个添加 Collection 所有元素的方法：一个是在尾部添加，另一个是从指定位置开始添加。
public
boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // 确保容量足够，modCount+1
System.arraycopy(a, 0, elementData, size, numNew); // 将a数组中从0开始的元素复制到elementData尾部开始的地方
size += numNew; // 实际使用量增加return numNew != 0;
}
publicboolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index); // 检查是否越界
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCountint numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved); // 将原数组index位置开始的元素复制到index+numNew开始的地方
System.arraycopy(a, 0, elementData, index, numNew); //将a中元素复制到从index开始的地方
size += numNew;
return numNew != 0;
}
4、get方法
get方法用于获取列表具体位置的元素
public E get(int index) {
rangeCheck(index); // 检查是否越界，index<size;index>=size时，抛出IndexOutOfBoundsException，index<0时，ArrayIndexOutOfBoundsExceptionreturn elementData(index);
}
privatevoid rangeCheck(int index) {
if (index >= size)
thrownew IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
4、set方法
public E set(int index, E element) {
rangeCheck(index); // 检查是否越界,index<size
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
5、remove方法
ArrayList 本身提供了两个 remove 方法，一个是根据具体的位置删除；另一个是根据元素删除。
public E remove(int index) {
rangeCheck(index); // 检查是否越界index，只判断index<size
modCount++; // modCount+1
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved); // index之后的元素前一位
elementData[--size] = null; // size-1，之前已使用容量的最后一位清空以使GC生效return oldValue;
}
// ArrayList 允许重复的元素，本 remove 方法只会删除第一个相等的元素publicboolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) { // 为null时，直接判断是否等于null fastRemove(index);
returntrue;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) { // 调用 equals 判断是否相等 fastRemove(index);
returntrue;
}
}
returnfalse;
}
// 基本上和 remove(int index) 实现一样，因为 index 是在数组中遍历的结果，因此不需要判断是否越界privatevoid 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
}
5、clear方法
clear() 方法用于清空元素。
public
void
clear() {
modCount++;
// clear to let GC do its workfor (int i = 0; i < size; i++)
elementData[i] = null; // 清空每一个位置的元素，是GC生效
size = 0; // size置为0
}
6、iterator方法
Collection 提供了 Iterator() 方法用于返回迭代器 Iterator 对象，在 ArrayList 中它的实现方式是返回了一个它的内部类 Itr 的实例，Itr 实现了 Iterator 接口。让我们先看一下 Itr 的内部实现。
private
class Itr implements Iterator<E> {
int cursor; // 下一个的元素位置,初始为0int lastRet = -1; // 当前访问元素的位置int expectedModCount = modCount; // 初始化expectedModCount等于外部类的modCountpublicboolean hasNext() { // 表明当前位置的后一个位置是否存在元素，一般需要cursor<size，已访问最后一个元素时，cursor=sizereturn cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification(); // 判断expectedModCount和modCount是否还是相等的int i = cursor;
if (i >= size) // 当前位置是最后一个元素时，一般存在i=size的可能性，
//抛出NoSuchElementException，不是IndexOutOfBoundsExceptionthrownew NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) // i>elementData实际容量时，抛出ConcurrentModificationException异常，不过单线程情况下应该不会发生，多线程可能会thrownew ConcurrentModificationException();
cursor = i + 1; // 记录下一元素的位置，cursor<=sizereturn (E) elementData[lastRet = i]; // 返回元素，上一个访问元素的位置更新 }
publicvoid remove() {
if (lastRet < 0) // 没有使用next()就调用remove()时会抛出异常thrownew IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet); // 调用的是外部类的remove(int index)方法，外部类的modCount，size会更新！！！！
cursor = lastRet; // 下一元素的位置改为当前位置
lastRet = -1; // 这里也是需要注意的点，下面会讲解！！！！！！
expectedModCount = modCount; // 此时modCount已更新，在这里更新expectedModCount
} catch (IndexOutOfBoundsException ex) {
thrownew ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
publicvoid forEachRemaining(Consumer<? super E> consumer) { // todo 有机会认识认识Consumer Objects.requireNonNull(consumer);
finalint size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
thrownew 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();
}
finalvoid checkForComodification() {
if (modCount != expectedModCount) //不相等时，抛出ConcurrentModificationException异常thrownew ConcurrentModificationException();
}
}
Itr 内部没有构造方法，使用的是默认提供的构造方法。
注意： 在遍历的过程中，如果调用了 Itr 的 remove() 方法后，中间如果没有使用 next() 方法 ，紧跟着又使用了 remove() 方法之后，会抛出 IllegalStateException 异常。在 next() 和 remove() 中，lastRet 都经过了修改，next() 在返回当前位置元素的时候，将lastRet 赋值为当前元素位置；而在 remove() 方法中，是将 cursor 赋值为当前元素的位置，lastRet 赋值为-1，再次调用 remove() 方法，在其第一行代码中会检验出 lastRet < 0,抛出 IllegalStateException 异常。
在 next() 和 remove() 实际操作之前都会调用 checkForComodification() 用于检验 Itr() 实例中的 expectedModCount 和外部类 ArrayList 的 modCount 是否相等。
7、listIterator方法
java提供了两个listiterator方法，一个无参数，从 elementData开始位置返回一个 ListIterator 对象；另一个有参数，从数组指定位置返回 listIterator 对象。
public ListIterator<E> listIterator() {
returnnew ListItr(0);
}
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size) // 允许 index = sizethrownew IndexOutOfBoundsException("Index: "+index);
returnnew ListItr(index);
}
下面介绍一下ListItr：可以看到，返回的是ListItr 对象，该类也是ArrayList 的内部类，继承自 ArrayList 内部类同时实现了 ListIterator 接口：
private
class ListItr extends Itr implements ListIterator<E> { }
既然 ListItr 继承自 Itr 类，那么 ListItr 也会存在它的三个成员变量 cursor、lastRet 和 expectedModCount，调用无参数构造初始化与 Itr 的无参数构造方法没什么区别，有参数的构造方法会将 cursor 赋值。
ListItr(int index) { super(); cursor = index; }
ListIterator 不仅能够向后遍历，还能够向前遍历，介绍一下内部的方法
public
boolean hasPrevious() { // 判断是否有前一节点return cursor != 0;
}
publicint nextIndex() { // 下一个访问节点的位置return cursor;
}
publicint previousIndex() { // 前一个节点的位置return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification(); // 判断exceptedModCount 是否等于 ModCountint i = cursor - 1;
if (i < 0)
thrownew NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) // 多线程并发可能会遇到thrownew ConcurrentModificationException();
cursor = i; // 向前遍历后，下一访问节点改为前一节点return (E) elementData[lastRet = i]; // 上一个访问节点的位置改变 }
publicvoid set(E e) {
if (lastRet < 0)
thrownew IllegalStateException();
checkForComodification(); // 判断exceptedModCount 是否等于 ModCounttry {
ArrayList.this.set(lastRet, e); // 将上一访问节点的元素设为新值
} catch (IndexOutOfBoundsException ex) {
thrownew ConcurrentModificationException();
}
}
publicvoid add(E e) {
checkForComodification(); // 判断exceptedModCount 是否等于 ModCounttry {
int i = cursor;
ArrayList.this.add(i, e); // 调用外部类方法
cursor = i + 1;
lastRet = -1; // 同样上一访问节点会置为-1，所以不能同时调用add和set或者add和remove
expectedModCount = modCount; // expectModCount 会修改
} catch (IndexOutOfBoundsException ex) {
thrownew ConcurrentModificationException();
}
}
ArrayList 是 fail-fast（快速失败）的，当一个线程对其进行迭代时，另一个线程对其发生结构性的改变，就会抛出ConcurrentModificationExceptiion异常。
原文：https://www.cnblogs.com/guaniu2750/p/13610117.html
内容总结
以上是互联网集市为您收集整理的java容器体系（二）----List（ArrayList）全部内容，希望文章能够帮你解决java容器体系（二）----List（ArrayList）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。