List
List是一个维持内部元素有序的采集器，其中的每个元素都会拥有一个索引，每个元素都可以
通过他的索引获取到元素，并且索引的开始下标是从0开始的，List中的元素还可重复。
而Set中不不含重复元素的。
以上便List的定义。实际中List仅是一个接口，并没有具体的方法实现，只是定义好了统一的方法。
以下便是List的继承结构：
- Iterable
- Collection
- List
- Collection
我们先来看看顶级的Iterable：
Instances of classes that implement this interface can be used with
the enhanced for loop.
也就是说继承了这个接口能增强子类的循环能力。
Iterable中有唯一定义的接口方法：
Iterator<T> iterator();
他的作用就是返回一个Iterator<T>的实例。
接下来看看Iterator到底是什么东西
他是一个对象序列的迭代器，例如说集合。
它拥有三个接口方法：
//是否还有更多的没有被迭代的元素，有则返回true，否则返回false
public boolean hasNext();
//返回下一个对象元素，并且是迭代器前进，如果没有元素了的话会抛出NoSuchElementException
public E next();
//移除最后通过next()返回对象元素。此方法只能在调用next()后才能调用，否则会抛出IllegalStateException
public void remove();
我们再来看看Collection接口：
Collection是所受Collection类型的根节点，也就是说所有的集合类型的都会实现这个接口。
| 方法 | 说明 |
|---|---|
| add(E object) | 尝试将一个对象添加到Collection中，保证添加成功了该对象元素就包含在Collection中。在实现该接口方法的类中，需要根据具体的添加规则抛出相应的Exception。注意一点是抛出异常了就不会返回false,而添加成功会返回true。 |
| addAll(Collection<? extends E> collection) | 试图将参数中的collection的所有元素添加到当前实例中的Collection中。添加成功返回ture，否则返回false。 |
| clear() | 将原本collection中的元素全部删除。如果移除操作不允许会抛出UnsupportedOperationException。 |
| contains(Object object) | 遍历Collection中的所有元素，找到一个相等的元素则返回true，否则返回false。可能抛出的异常：ClassCastException，NullPointerException。 |
| containsAll(Collection<?> collection) | Collection是是否包含参数中collection中的每个元素，即使是每个参数仅仅包含一次都会返回true，否则返回false。参数collection＝＝null 或者 collection中至少包含一个null元素的时候回抛出NullPointerException |
| equals(Object object） | 当前Collection中与给定的object是否相等。 |
| hashCode() | 返回Collection中所有元素的哈希值和，主要用于比较。 |
| isEmpty() | 是否Collection中没有元素。 |
| Iterator<E> iterator() | 返回一个迭代器实例，用来访问Collection中的内容。 |
| remove(Object object) | 将Collection中与参数object相等的元素。可能抛出的异常：UnsupportedOperationException,ClassCastException,NullPointerException |
| removeAll(Collection<?> collection) | 将在Collection中包含参数collection中的元素移除。返回的结果是Collection中不包含有参数collection中的元素。 |
| retainAll(Collection<?> collection) | 将Collection中不包含在参数collection中的元素移除。返回的结果是Collection中包含有参数collection中的元素。 |
| size() | 返回Collection中元素的个数，如果个数大于Integer.MAX_VALUE，返回的结果是Integer.MAX_VALUE |
| Object[] toArray() | 将Collection中的所有元素根据迭代顺序以一个新数组返回，即使Collection的底层已经是一个数组结构。 |
| <T> T[] toArray(T[] array) | 将Collection中的元素根据迭代顺序添加到给定的array中，如果array不能装下Collection中的所有元素则会新建一个对应类型，对应大小的数组，如果array的大小大于Collection的元素个数，则array多余的索引位置元素置为null。 |
而List在Collection的基础上增加了以下接口方法：
| 方法 | 说明 |
|---|---|
| add(int location, E object) | 在索引location处插入一个元素，location＝＝size()的话，直接在末尾添加。<size的话，在location处插入，location之后的元素依次后移。location < 0 或者 location > size()则抛出IndexOutOfBoundsException |
| boolean addAll(int location, Collection<? extends E> collection) | 在指定索引处插入一个contains的所有元素 |
| E get(int location) | 返回指定索引处的元素。location < 0 或者 location > size()则抛出IndexOutOfBoundsException |
| int indexOf(Object object) | 返回一个指定object元素在list中的索引，没有此元素则返回-1 |
| int lastIndexOf(Object object) | 最后一个等于指定object元素的索引，没有则返回-1 |
| remove(int location) | 根据索引移除元素，location < 0 或者 location > size()则抛出IndexOutOfBoundsException |
| remove(Object object) | 找到并移除了该元素则返回true，否则返回false |
| E set(int location, E object) | 将指定索引位置设置为元素object。会有IndexOutOfBoundsException，ClassCastException。 |
| List<E> subList(int start, int end) | 返回索引start到end处的子列表，会有IndexOutOfBoundsException。 |
此外还有：
ListIterator<E> listIterator();
ListIterator<E> listIterator(int location);
其中ListIterator继承子Iterator，新添加了几个方法：
public boolean hasPrevious();
public int nextIndex();
public E previous();
public int previousIndex();
void set(E object);
ArrayList
ArrayList继承自AbstractList，实现了Cloneable，Serializable，RandomAccess接口
而AbstractList继承自AbstractCollection<E>实现了List<E>接口，是一个抽象类，他的子类必须实现iterator(),size()这个两个抽象方法，以使得可以创建处一个不可变的集合。而创建一个可修改的集合类型则需要重写add()方法。
ArrayList是List的一个基于数组的实现类，支持增加，移除，替换等元素操作。并且支持所有元素类型包括null。它的所有操作同步进行的。而CopyOnWriteArrayList则可以用于高度并发，频繁遍历的情形。
数组容量增长步长。
private static final int MIN_CAPACITY_INCREMENT = 12;
构造函数
初始化时指定数组容量，直到自己数据容量的时候，最好都指定。默认是一个空数组。
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
public ArrayList() {
array = EmptyArray.OBJECT;
}
//指定一个collection初始化的时候
public ArrayList(Collection<? extends E> collection) {
if (collection == null) {
throw new NullPointerException("collection == null");
}
//先转化成数组
Object[] a = collection.toArray();
if (a.getClass() != Object[].class) {
//创建一个长度为collection长度的新数组，并将collection数组复制到新数组中
Object[] newArray = new Object[a.length];
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
}
添加
添加的时候基本策略是，有指定添加的索引位置的时候就检查是否索引越界，如果是则直接抛出越界异常。然后是检查当前数组是否已经装满，如果是则计算新的数组容量，并创建一个新的数组，原数组的元素复制到新数组并将新添加的元素加入到list的末尾，更新size值。
@Override public boolean add(E object) {
Object[] a = array;
int s = size;
//原数组已满
if (s == a.length) {
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;//容量加一
modCount++;
return true;
}
该方法是根据传入的当前数组容量值计算并返回新的容量值，时空权衡。
扩容策略：
- 当前容量小于最下增长量的一半：
当前容量＋最小增长量 - 当前容量大于等于最下增长量的一半:
当前容量＋当前容量/2
private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}
查找
| 方法 | 默认返回值 |
|---|---|
| public boolean contains(Object object) | false |
| public int indexOf(Object object) | -1 |
| public int lastIndexOf(Object object) | -1 |
| public boolean remove(Object object) | false |
当需要查找的元素对象不为空的时候，从头开始遍历数组的元素，equals则直接返回对应类型。
查找的元素对象为空时，从头开始遍历数组的元素，遇到一个 ==null的元素的时候则直接返回对应类型。
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
...
return ...;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
...
return ...;
}
}
}
remove一个元素的时候会有这么一个操作：a[s] = null; 是为了防止内存溢出。
指定位置元素移除： public E remove(int index)，只需检测时候下标越界。不越界则移除该位置的元素。
移除元素位置之后的元素都前移一位
System.arraycopy(a, index + 1, a, index, --s - index);
//此时a[s] == a[s－1]，所以可以删除末尾的那个a[s]
a[s] = null; // Prevent memory leak
size = s;
在每次list的增删改操作的时候都会modCount++。modCount是用来记录list的修改次数，
主要是在ArrayList总的内部迭代器ArrayListIterator中使用
ArrayListIterator
//剩余没有被迭代到的元素数量
private int remaining = size;
//可被使用remove()移除的元素的索引, -1表示没有可以被移除的元素
private int removalIndex = -1;
//期待的list操作次数，可判断是否存在并发操作
private int expectedModCount = modCount;
//是否迭代完
public boolean hasNext() {
return remaining != 0;
}
public E next() {
ArrayList<E> ourList = ArrayList.this;
int rem = remaining;
//存在并发操作
if (ourList.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
//已经迭代完，继续迭代抛出异常， 用hasNext()做检查，避免此异常
if (rem == 0) {
throw new NoSuchElementException();
}
remaining = rem - 1;
//ourList.size - rem处的元素
return (E) ourList.array[removalIndex = ourList.size - rem];
}
public void remove() {
Object[] a = array;
int removalIdx = removalIndex;
...
System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
a[--size] = null; // Prevent memory leak
removalIndex = -1;//重新置为-1，表示该索引的元素已移除。除非被next()更新。
expectedModCount = ++modCount;//会更新list的操作次数
}
再来看看的ArrayList的迭代器中定义的equals策略
public boolean equals(Object o) {
//引用相等
if (o == this) {
return true;
}
//参数o不是List的子类
if (!(o instanceof List)) {
return false;
}
List<?> that = (List<?>) o;
int s = size;
//两个list的size不想等
if (that.size() != s) {
return false;
}
Object[] a = array;
if (that instanceof RandomAccess) {
for (int i = 0; i < s; i++) {
Object eThis = a[i];
Object ethat = that.get(i);
if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
return false;
}
}
} else { // 参数的list不支持随机访问，则使用迭代器进行迭代
Iterator<?> it = that.iterator();
for (int i = 0; i < s; i++) {
Object eThis = a[i];
Object eThat = it.next();
if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
return false;
}
}
}
return true;
}
网友评论