读代码跟写代码一样重要
List及实现类关系
集合类图.jpg
上述类图中，Collection、List为接口；AbstractCollection、AbstractList、AbstractSequentialList为抽象类；Vector、ArrayList、LinkedList为实现类
类的组织结构与比较
咱们从Collection的方法开始
Collection的方法
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
default boolean removeIf(Predicate<? super E> filter);//具有默认实现,可继承
boolean retainAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
default Spliterator<E> spliterator();
default Stream<E> stream();
default Stream<E> parallelStream()
上述列举的方法少了查和改，基本满足我们的集合操作了，那么AbstractCollection实现Collection是否只要将其全部实现就完事了呢
AbstractCollection的方法
public abstract int size();
public abstract Iterator<E> iterator();
boolean isEmpty();
boolean contains(Object o);
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
String toString();
//不可继承，只是toArray的辅助方法
private static <T> T[] finishToArray(T[] r, Iterator<?> it);
private static int hugeCapacity(int minCapacity);
从上我们发现AbstractCollection只新增toString一个可继承的方法，相比较Collection并没有给出更多的可继承的方法。没有hashCode、equals等方法。
这里我们具体看下AbstractCollection的toArray方法
/*
其中size()和iterator()都是abstract
*/
public Object[] toArray() {
// Estimate size of array; be prepared to see more or fewer elements
Object[] r = new Object[size()];
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) // fewer elements than expected
return Arrays.copyOf(r, i);
r[i] = it.next();
}
return it.hasNext() ? finishToArray(r, it) : r;
}
public <T> T[] toArray(T[] a) {
//提供了数组a，够大可以直接用作返回的数组
int size = size();
T[] r = a.length >= size ? a :
(T[])java.lang.reflect.Array//创建不晓得类型的数组所用的方法
.newInstance(a.getClass().getComponentType(), size);
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) { // 返回获取的r数组,容量跟a的容量相关
if (a == r) {//a和r一样大，直接返回r数组
r[i] = null; // null-terminate
} else if (a.length < i) {
//a比当前获取的元素小，返回当前获取的元素,数组的容量也为当前元素集的大小
return Arrays.copyOf(r, i);
} else {
//a比当前获取的元素大，返回当前获取的元素，但是数组的容量大，为a的容量
System.arraycopy(r, 0, a, 0, i);
if (a.length > i) {
a[i] = null;
}
}
return a;
}
r[i] = (T)it.next();
}
// more elements than expected
return it.hasNext() ? finishToArray(r, it) : r;
}
//对数组进行扩容
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
int i = r.length;
while (it.hasNext()) {
int cap = r.length;
if (i == cap) {
int newCap = cap + (cap >> 1) + 1;
// overflow-conscious code
if (newCap - MAX_ARRAY_SIZE > 0)
newCap = hugeCapacity(cap + 1);
r = Arrays.copyOf(r, newCap);
}
r[i++] = (T)it.next();
}
// trim if overallocated
return (i == r.length) ? r : Arrays.copyOf(r, i);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError
("Required array size too large");
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
明确toArray的思想，就是将集合转成数组，然后看源码，AbstractCollection的实现方式是通过abstract修饰的迭代器来进行遍历，然后将遍历得到的元素存入数组，迭代开始之前或者操作过程中，集合的元素可能发生了改变，如果元素变少了，那么就将当前迭代获取的元素返回，数组容量跟a相关。如果元素变多了，那么就开辟一个更大的空间，然后继续遍历集合元素，获取全部元素后返回。数组容量看上代码。
注意：
在使用迭代器遍历的时候，如果不是通过迭代器内部提供的增删改来修改集合，那么就会抛出异常，在AbatractList中可以看到具体的迭代器实现
List的方法
//Collection继承过来的接口方法
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
default Spliterator<E> spliterator()
//List定义的接口方法
boolean addAll(int index, Collection<? extends E> c);
default void replaceAll(UnaryOperator<E> operator)
default void sort(Comparator<? super E> c)
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
从上面的代码可以看出，Collection中的方法是不带顺序的。而List自己的接口方法就看到很多index，是有序的。
这里咱们看下replaceAll和sort
//UnaryOperator接口继承Function，提供了apply方法，给传入的参数做一层自定义的包装
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
上面的两个方法很简单，主要是调用了ListIterator和Arrays的方法来实现的。咱们下面先看下个ListIterator接口，Arrays内容比较多，下次再看
ListIterator的方法
//继承自Iterator接口
boolean hasNext();
E next();
void remove();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void set(E e);
void add(E e);
看到上面的代码，咱们发现ListIterator是继承Iterator的，可以进向前或者向后迭代。但是为什么还要实现set和add方法呢
AbstractList的方法
//继承自AbstractCollection的方法
public boolean add(E e)；
public void clear()
public Iterator<E> iterator()
public boolean equals(Object o)
public int hashCode()
//List接口中的方法
abstract public E get(int index);
public E set(int index, E element)
public void add(int index, E element)
public E remove(int index)
public int indexOf(Object o)
public int lastIndexOf(Object o)
public boolean addAll(int index, Collection<? extends E> c)
public ListIterator<E> listIterator()
public ListIterator<E> listIterator(final int index)
public List<E> subList(int fromIndex, int toIndex)
//AbstractList内部方法
protected void removeRange(int fromIndex, int toIndex)
private void rangeCheckForAdd(int index)
private String outOfBoundsMsg(int index)
从上面代码可以看出AbstractList实现了AbstractCollection的add、clear、iterator、equals、hashCode方法，结合AbstractCollection的实现的方法，AbstractCollection只剩size()方法未被实现。
我们来看下indexOf、lastIndexOf、listIterator、subList等方法
public int indexOf(Object o) {
ListIterator<E> it = listIterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return it.previousIndex();
} else {
while (it.hasNext())
if (o.equals(it.next()))//待会会看到next是先取值，然后移动index,previous也是一样
return it.previousIndex();
}
return -1;
}
public int lastIndexOf(Object o) {
ListIterator<E> it = listIterator(size());//将index指向末尾
if (o==null) {
while (it.hasPrevious())
if (it.previous()==null)
return it.nextIndex();
} else {
while (it.hasPrevious())
if (o.equals(it.previous()))
return it.nextIndex();
}
return -1;
}
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(final int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
public List<E> subList(int fromIndex, int toIndex) {
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}
indexof(o)和lastIndexOf(o)都很容易理解，indexof是顺序查找是否有相等的元素，然后返回。lastIndexOf是倒叙查找是否有相等的元素，然后返回。
listIterator和subList是对外提供的listItr和SubList对外提供实例化的方法
下面分别来看下Itr、ListItr、SubList、RandomAccessSubList
Itr
private class Itr implements Iterator<E> {
/**
* Index of element to be returned by subsequent call to next.
*/
int cursor = 0;
/**
* Index of element returned by most recent call to next or
* previous. Reset to -1 if this element is deleted by a call
* to remove.
*/
int lastRet = -1;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size();//查看下标是否到达末尾
}
public E next() {
checkForComodification();//检查迭代过程中，是否不同过本迭代器提供的方法改变了list元素，如果实例元素发生变化，则抛出异常。
//检查方式是通过每次改变元素位置的操作都记录list的操作次数到迭代器，操作之前先进行是否相等的判断
try {
int i = cursor;
E next = get(i); //通过list的get(i)获取元素
lastRet = i; //lastRet记录本次操作的位置
cursor = i + 1; //移动下标到下一个元素
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
//迭代器可以向前或者向后，如果向后，那么下标肯定比上一次位置要大，如果向前，从下面源码可以看出，下标和上一次操作的位置是一样的，所以不需要移动下标
if (lastRet < cursor)
cursor--;
lastRet = -1;//不允许继续remove或者set
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
从上面的源码咱们可以看出，iterator()方法获取的迭代器只能使用其内部提供的方法来修改元素，不然会抛出异常
ListItr
//继承自Itr，实现ListIterator接口
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;//检查下标是否在首部
}
public E previous() {
checkForComodification();
try {
int i = cursor - 1;
E previous = get(i);//获取上一个元素
lastRet = cursor = i;//再移动下标到上一个元素
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.set(lastRet, e);//remove和set都是相对上次操作过的迭代器元素
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
AbstractList.this.add(i, e);//在迭代器可见范围的末尾添加元素
lastRet = -1;
cursor = i + 1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
ListItr 继承了Itr实现了ListIterator接口。提供向前遍历，增加了获取下标的方法。
为什么next是先获取元素，再移动到下一个位置，而previous是先移动到上一个位置，再获取元素呢？
因为cursor初始值为0，而hasNext和hasPrevious判断的写法也限制了元素的顺序
SubList
class SubList<E> extends AbstractList<E> {
private final AbstractList<E> l;
private final int offset;
private int size;
SubList(AbstractList<E> list, int fromIndex, int toIndex) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > list.size())
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
l = list;
offset = fromIndex;
size = toIndex - fromIndex;
this.modCount = l.modCount;
}
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
return l.set(index+offset, element);
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
return l.get(index+offset);
}
public int size() {
checkForComodification();
return size;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
checkForComodification();
l.add(index+offset, element);
this.modCount = l.modCount;
size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = l.remove(index+offset);
this.modCount = l.modCount;
size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
l.removeRange(fromIndex+offset, toIndex+offset);
this.modCount = l.modCount;
size -= (toIndex-fromIndex);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
l.addAll(offset+index, c);
this.modCount = l.modCount;
size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
return new ListIterator<E>() {
private final ListIterator<E> i = l.listIterator(index+offset);
public boolean hasNext() {
return nextIndex() < size;
}
public E next() {
if (hasNext())
return i.next();
else
throw new NoSuchElementException();
}
public boolean hasPrevious() {
return previousIndex() >= 0;
}
public E previous() {
if (hasPrevious())
return i.previous();
else
throw new NoSuchElementException();
}
public int nextIndex() {
return i.nextIndex() - offset;
}
public int previousIndex() {
return i.previousIndex() - offset;
}
public void remove() {
i.remove();
SubList.this.modCount = l.modCount;
size--;
}
public void set(E e) {
i.set(e);
}
public void add(E e) {
i.add(e);
SubList.this.modCount = l.modCount;
size++;
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
return new SubList<>(this, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
private void checkForComodification() {
if (this.modCount != l.modCount)
throw new ConcurrentModificationException();
}
}
subList是List的一个子视图，我们看到SubList(AbstractList<E> list, int fromIndex, int toIndex)构造的时候传入AbstractList,后续sublist中的内容都是从AbstractList中获取的。
从checkForComodification函数看出，假如宿主AbstractList被修改后，操作sublist中的方法将会报ConcurrentModificationException异常
RandomAccessSubList
class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
super(list, fromIndex, toIndex);
}
public List<E> subList(int fromIndex, int toIndex) {
return new RandomAccessSubList<>(this, fromIndex, toIndex);
}
}
这个类和sublist的区别在于实现了RandomAccess接口，这个接口是用来标识是否本类可以进行快速访问的。
从AbstractList的subList方法能够看到RandomAccess的用法
ArrayList
讲到AbstractList时，大家想是否AbstractList就可以正常使用了呢。为什么还要往下讲。因为AbstractList没有可以存数据的容器。而且其大部分操作都是通过iterator来实现的，而AbstractList中的iterator则是通过为实现的list中的接口来实现的。下面咱们看下其具体的实现子类ArrayList
ArrayList的方法
//构造
public ArrayList(int initialCapacity)
public ArrayList()
public ArrayList(Collection<? extends E> c)
//abstractCollection方法
public int size()
public boolean isEmpty()
public boolean contains(Object o)
public Object[] toArray()
public <T> T[] toArray(T[] a)
public boolean add(E e)
public boolean remove(Object o)
public void clear()
public boolean addAll(Collection<? extends E> c)
public boolean removeAll(Collection<?> c)
public boolean retainAll(Collection<?> c)
public Iterator<E> iterator()
//abstractList
public int indexOf(Object o)
public int lastIndexOf(Object o)
public E get(int index)
public E set(int index, E element)
public void add(int index, E element)
public E remove(int index)
public boolean addAll(int index, Collection<? extends E> c)
protected void removeRange(int fromIndex, int toIndex)
private String outOfBoundsMsg(int index)
public ListIterator<E> listIterator(int index)
public ListIterator<E> listIterator()
public List<E> subList(int fromIndex, int toIndex)
//Cloneable的方法
public Object clone()
private void fastRemove(int index)
//Serializable的方法
private void writeObject(java.io.ObjectOutputStream s)
private void readObject(java.io.ObjectInputStream s)
//Iterable的方法，Collection继承自Iterable
public void forEach(Consumer<? super E> action)
E elementData(int index)
//内部方法
private void rangeCheck(int index)
private void rangeCheckForAdd(int index)
private boolean batchRemove(Collection<?> c, boolean complement)
从上面介绍的方法来看，之前在AbstractCollection中实现的Collection的方法，都被ArrayList给重新实现了一遍，而且还实现了List接口中的方法。此外还实现了Cloneable、Serializable等一系列的方法。
下面咱们首先看下AbstractCollection中被重写的方法，然后对比下为什么要重新
ArrayList重写的Collection的方法,列举部分
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public Object[] toArray() {
return Arrays.copyOf(elementData, size);//之前是从迭代器中取值，然后转成数组，现在拿到就是数组，直接按大小返回，一次操作不怕中间容器结构发生改变
}
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
public boolean add(E e) {//之前只是把add转到add(i,e)上，并没有真实现
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {//null代表的是空值，用==比较是否同一东西
fastRemove(index);//之前是通过iterator中的remove实现的
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {//比较对象的值是否相等
fastRemove(index);
return true;
}
}
return false;
}
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
//根据complement来决定新新容器elementData保留哪些元素
if (c.contains(elementData[r]) == complement)
//w的值是从0开始，所以要直接覆盖elementData当为新容器使用
//在用下标遍历的时候是不能修改集合结构的，所以不能直接用remove
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;//直接把w之后的剩余元素置空
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
//使用arraycopy将i+1开始的元素覆盖的i开始的元素
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
public void ensureCapacity(int minCapacity) {
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA在三个构造函数其中一个看到，是elementData属性的初始值
//刚刚构造过，就来扩容的话，就给DEFAULT_CAPACITY，10个
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(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;
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;
}
上面方法相比与AbstractCollection实现的方法来说，是可以正常使用了，使用实例属性elementData来成为真正的容器实现各种增删改查。
这里说下retainAll，跟AbstractCollection的retainAll实现思路是一样的。保留交集的元素，返回值跟是否交集无关
//ArrayList
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)//true,c里面包含list集合的元素，就把list集合的元素保留下来
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;//清空w之后的所有元素
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
//AbstractCollection
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();//不存在list中，就把list中的元素移除
modified = true;
}
}
return modified;//返回值跟交集无关
}
ArrayList实现List接口的方法，其实就是多了具体下标的操作，思路就是通过内存复制的方式来移动数组。具体的可以看代码，其实跟上面的abstractCollection方法实现类似。
ArrayList不仅实现了集合和list的功能，还添加了克隆和序列化的功能。
ArrayList的克隆
继承Cloneable接口实现的克隆方式，有些人说是浅克隆，其实他是真的把一个集合的数据拷贝到另一个地址的。不玩虚的。只是集合里面可能有对象元素，对象元素本身就是引用，所以拷过来的也就是那个对象的引用，在拷贝集合的层面上算是真实拷贝了，如果想把集合元素的对象的值也给克隆成一个新对象，咱们可以连带着把那个对象也克隆了，使那个对象实现Cloneable就可以了。
ArrayList的序列化
还有就是序列化，这个可以单独研究下，代码还是比较复杂的。最终就是通过反射的方式拿到ArrayList中实现的writeObject和readObject来调用实现ArrayList的序列化
LinkedList
LinkedList的东西也是比较多的。就等之后再写个新的来讲
类封装的思想
从集合框架图看，架构还是比较复杂的。咱们这里只是分析了List相关的类图。从上面的分析过程来看，为什么要把类封装成这样呢。
首先咱们知道Collection主要分为List、set和Queue(上面的集合框架图是不全的。)
其实是三种不同的数据结构。把他们的共性抽象到Collection接口中去，让AbstractCollection来实现其共性，当然也不是全实现，只是框定一个结构，具体的差异实现比如add和remove还是要到具体的数据结构类中去实现的。
再把三种不同数据结构的差异抽象到各自的接口中去，List,Set（我们看到set并没有实现具体的差异接口）,Queue。
使用AbstractList、AbstractSet、AbstractQueue类分别实现集合的共性（AbstractCollection）和各自的差异接口。
当然从上面分析也看到了，到了这一步还是没有完成的，因为List又可以分为用数组实现和用链表实现的。所以AbstractList、AbstractSet、AbstractQueue还是只能实现一些与具体数据结构无关的函数。
再到下面我们就看到带有具体数据结构的实现类了，比如ArrayList和LinkedList。
其实看完ArrayList和LinkedList的代码，大家也会很疑惑，为什么ArrayList等都是自己全部实现Collection和List接口的方法。压根就不理会AbstractList和AbstractCollection这一级别的实现呢。
也许实现这些抽象类只是一种代码风格，也许是为了给大家一个更好的扩展点吧
等把其他几个分支撸完，再回来看这是怎么回事，现在理解还是不够
网友评论