共计 26283 个字符，预计需要花费 66 分钟才能阅读完成。
1.List 接口的个性
java.util.List 接口继承于 Collection 接口，与 Map 最大的不同之处，在于它属于单列汇合, 相当于一个 列表，有以下这些特点：
- 有程序，依照增加的顺序存储，是一种线性构造。
- 能够依据索引查问元素。
- 元素能够反复。
An ordered collection(also known as a sequence).The user of this interface has precise control over where in the list each element is inserted.The user can access elements by their integer index(position in the list), and search for elements in the list.<p >
Unlike sets, lists typically allow duplicate elements. More formally,lists typically allow pairs of elements <tt>e1</tt> and <tt>e2</tt> such that <tt>e1.equals(e2)</tt>, and they typically allow multiple null elements if they allow null elements at all. It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare.<p>
上面是 List 接口的继承关系：
2.List 接口的源码解析
继承于 Collection 接口，有程序，取出的程序与存入的程序统一，有索引，能够依据索引获取数据，容许存储反复的元素，能够放入为 null 的元素。
最常见的三个实现类就是 ArrayList，Vector,LinkedList，ArrayList 和Vector都是外部封装了对数组的操作，惟一不同的是，Vector是线程平安的，而 ArrayList 不是，实践上 ArrayList 操作的效率会比 Vector 好一些。
外面是接口定义的办法：
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 addAll(int index, Collection<? extends E> c); // 批量增加，指定开始的索引
boolean removeAll(Collection<?> c); // 批量移除
boolean retainAll(Collection<?> c); // 将 c 中不蕴含的元素移除
default void replaceAll(UnaryOperator<E> operator) {}// 替换
default void sort(Comparator<? super E> c) {}// 排序
void clear();// 革除所有的元素
boolean equals(Object o);// 是否相等
int hashCode(); // 计算获取 hash 值
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(); // 获取 List 迭代器
ListIterator<E> listIterator(int index); // 依据索引获取以后的地位的迭代器
List<E> subList(int fromIndex, int toIndex); // 截取某一段数据
default Spliterator<E> spliterator(){} // 获取可切分迭代器比拟罕用的几个办法无非增删改查：
E get(int index); // 通过索引获取元素
E set(int index, E element);// 批改元素
void add(int index, E element);// 在指定地位插入元素
E remove(int index);// 依据索引移除某个元素下面的办法都比较简单，值得一提的是外面呈现了 ListIterator，这是一个性能更加弱小的迭代器，继承于Iterator, 只能用于List 类型的拜访，拓展性能例如：通过调用 listIterator() 办法取得一个指向 List 结尾的 ListIterator，也能够调用listIterator(n) 获取一个指定索引为 n 的元素的 ListIterator, 这是一个能够双向挪动的迭代器。
操作数组索引的时候须要留神，因为 List 的实现类底层很多都是数组，所以索引越界会报错IndexOutOfBoundsException。
3. 相干子类介绍
说起 List 的实现子类，最重要的几个实现类如下：
ArrayList：底层存储构造是数组构造，减少删除比较慢，查找比拟快，是最罕用的 List 汇合。线程不平安。LinkedList：底层是链表构造，减少删除比拟快，然而查找比较慢。线程不平安。Vector：和 ArrayList 差不多，然而是线程平安的，即同步。
3.1 ArrayList
class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.SerializableArrayList 继承了 AbstractList 接口，实现了 List，以及随机拜访，可克隆，序列化接口。不是线程平安的，如果须要线程平安，则须要抉择其余的类或者应用Collections.synchronizedList(arrayList)
容许存储 null 元素，也容许雷同的元素存在。
其底层实际上是数组实现的，那为什么咱们应用的时候只管往里面存货色，不必关怀其大小呢？因为 ArrayList 封装了这样的性能，容量能够动态变化，不须要使用者关怀。
3.1.1 成员变量
transient示意这个属性不须要主动序列化，因为 element 存储的不是真的元素的对象，而是指向对象的地址，所以这样的属性序列化是没有太大意义的。对地址序列化之后，反序列化的时候找不到之前的对象，所以须要手动实现对对象的序列化。
// 真正存取数据的数组
transient Object[] elementData;
// 理论元素个数(不是 elementData 的大小，是具体寄存的元素的数量)
private int size;那在哪里去实现对西那个的序列化和反序列化的呢？这个须要咱们看源码外面的 readOject() 和writeOject()两个办法。其实就除了默认的序列化其余字段，这个 elementData 字段，还须要手动序列化和反序列化。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// 序列之前须要保留本来的批改的次数，序列化的过程中不容许新批改
int expectedModCount = modCount;
// 将以后类的非动态和非 transient 的字段写到流中，其实就是默认的序列化
s.defaultWriteObject();
// 将大小写到输入流中
s.writeInt(size);
// 依照程序序列化外面的每一个元素，留神应用的是 `writeOject()`
for (int i=0; i<size; i++) {s.writeObject(elementData[i]);
}
// 如果序列化期间有产生批改，就会抛出异样
if (modCount != expectedModCount) {throw new ConcurrentModificationException();
}
}
// 反序列化
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// 读取默认的反序列化数据
s.defaultReadObject();
// 读取大小
s.readInt(); // ignored
if (size > 0) {// 和 clone()相似，依据 size 调配空间，而不是容量
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// 循环读取每一个元素
for (int i=0; i<size; i++) {a[i] = s.readObject();}
}
}很多人可能会有疑难，为什么这个函数没有看到有调用呢？在哪里调用的呢？
其实就是在对象流中，通过反射的形式进行调用的，这里就不开展了，下次肯定！！！有趣味能够看看。
如果咱们创立的时候不指定大小，那么就会初始化一个默认大小为 10。
private static final int DEFAULT_CAPACITY = 10;外面定义了两个空数组，EMPTY_ELEMENTDATA名为空数组,DEFAULTCAPACITY_EMPTY_ELEMENTDATA名为默认大小空数组, 用来辨别是空构造函数还是带参数构造函数结构的 arrayList, 第一次增加元素的时候应用不同的扩容。之所以是一个空数组，不是 null，是因为应用的时候咱们须要制订参数的类型。
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};还有一个非凡的成员变量 modCount，这是疾速失败机制所须要的，也就是记录批改操作的次数，次要是迭代的时候，避免元素被批改。如果操作前后的批改次数对不上，那么有些操作就是非法的。transient 示意这个属性不须要主动序列化。
protected transient int modCount = 0;序列化 id 如下：为什么须要这个字段呢？这是因为如果没有显示申明这个字段，那么序列化的时候回主动生成一个序列化的 id，这样子的话，假如序列化实现之后，往原来的类外面增加了一个字段，那么这个时候反序列化会失败，因为默认的序列化 id 曾经扭转了。假如咱们给它指定了序列化 id 的话，就能够防止这种问题，只是减少的字段反序列化的时候是空的。
private static final long serialVersionUID = 8683452581122892189L;3.1.2 构造方法
构造方法有三个，能够指定容量，指定初始的元素集，能够什么都不指定。
// 指定初始化的大小
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);
}
}
// 什么都不指定，默认是空的元素集
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
// 传入一个汇合，转成数组之后，复制一份作为显得数据集
public ArrayList(Collection<? extends E> c) {Object[] a = c.toArray();
if ((size = a.length) != 0) {if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}3.1.3 罕用增删改查办法
增加元素
add()办法有两个：
add(E e)：增加一个元素，默认是在开端增加add(int index, E element)：在指定地位 index 增加 (插入) 一个元素
public boolean add(E e) {
// 确定容量是不是足够，足够就不会减少
ensureCapacityInternal(size + 1);
// size+ 1 的中央，赋值为当初的 e
elementData[size++] = e;
return true;
}
// 在指定的地位插入一个元素
public void add(int index, E element) {
// 查看插入的地位，是否非法
rangeCheckForAdd(index);
// 查看是不是须要扩容，容量是否足够
ensureCapacityInternal(size + 1); // Increments modCount!!
// 复制 index 前面的元素，都往后面挪动一位（这是 c ++ 实现的底层原生办法）System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 在 index 处插入元素
elementData[index] = element;
// 理论的存储元素个数减少
size++;
} 查问元素
get()办法绝对比较简单，获取之前查看参数是否非法，就能够返回元素了。
public E get(int index) {
// 查看下标
rangeCheck(index);
return elementData(index);
}
// 查看下标
private void rangeCheck(int index) {if (index >= size)
// 数组越界
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} 更新元素
set()和之前的 get() 有点像，然而必须制订批改的元素下标，查看下标之后，批改，而后返回旧的值。
public E set(int index, E element) {
// 查看下标
rangeCheck(index);
// 获取旧的值
E oldValue = elementData(index);
// 批改元素
elementData[index] = element;
// 返回旧的值
return oldValue;
}删除元素
依照元素移除，或者依照下标移除元素
public E remove(int index) {
// 查看下标
rangeCheck(index);
// 批改次数扭转
modCount++;
// 获取旧的元素
E oldValue = elementData(index);
// 计算须要挪动的下标（往前面挪动一位）int numMoved = size - index - 1;
if (numMoved > 0)
// 调用 native 办法将前面的元素复制，挪动往前一步
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将之前的元素置为空，让垃圾回收不便进行
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o) {
// 为空的元素
if (o == null) {for (int index = 0; index < size; index++)
if (elementData[index] == null) {fastRemove(index);
return true;
}
} else {
// 遍历，如果 equals, 则调用删除
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {fastRemove(index);
return true;
}
}
return false;
}
// 疾速删除办法
private void fastRemove(int index) {
// 批改次数减少 1
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
}ArrayList是基于数组动静扩容的，那它什么时候扩容的呢？如同下面的源代码中咱们没有看到，其实是有的，所谓扩容嘛，就是容量不够了，那么容量不够的时候只会产生在初始化一个汇合的时候或者是减少元素的时候，所以是在 add() 办法外面去调用的。
在最小调用的时候容量不满足的时候，会调用 grow()，grow() 是真正扩容的函数，这里不开展了。
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));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}3.1.4 小结一下
- ArrayList 是基于动静数组实现的，减少元素的时候，可能会触发扩容操作。扩容之后会触发数组的拷贝复制。remove 操作也会触发复制，前面的元素对立往前面挪一位，原先最初面的元素会置空，这样能够不便垃圾回收。
- 默认的初始化容量是 10，容量不够的时候，扩容时候减少为原先容量的个别，也就是原来的 1.5 倍。
- 线程不平安，然而元素能够反复，而且能够放 null 值，这个须要留神一下，每次取出来的时候是须要判断是不是为空。
3.2 LinkedList
LinkedList底层是以双向链表实现的，这是和 ArrayList 最大的不同，除此之外它还实现了 Deque 接口, 继承 AbstractSequentialList,AbstractSequentialList 继承了 AbstractList。
同时它也是 线程不平安 的。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable双向链表底层的数据结构如下:
private static class Node<E> {
// 以后节点的数据
E item;
// 下一个节点
Node<E> next;
// 上一个节点
Node<E> prev;
// 构造方法
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}3.2.1 成员变量
外面的成员变量次要有三个，之所以记录同时记录头结点和尾节点，次要是为了可能更快的插入以及查找数据。
// 元素个数
transient int size = 0;
// 链表的首节点
transient Node<E> first;
// 俩表的尾节点
transient Node<E> last;3.2.2 构造函数
构造函数次要有两个，一个是无参数的够着，一个是须要初始化元素集的函数，初始化的时候其实是调用了批量增加元素的函数addAll()。
public LinkedList() {}
public LinkedList(Collection<? extends E> c) {this();
// 调用了批量增加元素的函数
addAll(c);
}3.2.3 罕用函数
增加元素
linkFirst()在队列头部增加元素linkLast（）在队列尾部增加元素
// 往头部增加元素
public void addFirst(E e) {linkFirst(e);
}
// 往尾部增加元素
public void addLast(E e) {linkLast(e);
}
private void linkFirst(E e) {
// 首节点
final Node<E> f = first;
// 创立新节点，新节点的 next 是之前的首节点
final Node<E> newNode = new Node<>(null, e, f);
// 让新节点，作为首节点
first = newNode;
/**
* 判断新退出的节点是不是第一个增加的元素
*/
if (f == null)
// 如果这是首次往 list 外面增加节点，那么 last 也须要置为新的节点
last = newNode;
else
// 如果这不是第一次往 list 外面增加节点，那么就把原来的首节点的后面一个元素（指针）指向新的节点
f.prev = newNode;
// 元素个数 +1
size++;
// 批改次数 +1
modCount++;
}
void linkLast(E e) {
// 尾节点
final Node<E> l = last;
// 创立新的节点，新节点的后面一个元素是之前的尾节点（新节点的 pre 指针指向后面一个元素（之前的尾节点））final Node<E> newNode = new Node<>(l, e, null);
// 让当初的新插入节点，成为尾节点
last = newNode;
// 判断之前的最初一个节点是不是空的
if (l == null)
// 如果是空的，那么阐明之前没有插入过节点，当初的节点也是第一个节点。first = newNode;
else
// 如果不是空的，那么阐明之前后面的有节点的，须要把之前的尾节点的下一个元素（指针）指向当初新加的节点。l.next = newNode;
// 个数减少
size++;
// 批改次数减少
modCount++;
}调用 add() 办法，默认是在尾部增加元素。
public boolean add(E e) {linkLast(e);
return true;
}当然，除了能够在收尾增加元素之外，还能够在两头指定地位增加元素，通过上面这个办法实现。
public void add(int index, E element) {
// 查看 index 是否在非法的范畴
checkPositionIndex(index);
// 如果 index 等于大小 size，那么应该间接在尾部增加元素即可
if (index == size)
linkLast(element);
else
// 否则须要调用 linkBefore 在后面插入
linkBefore(element, node(index));
}下面有一个函数是node(index)，这个函数是依据 index 索引获取节点, 比拟有意思的一点，是当这个索引在后面一半的时候，从后面开始遍历，当这个索引在前面半局部的时候，从前面往前面遍历。判断在哪一部分，应用的是二进制。
Node<E> node(int index) {if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}在某个下标之前插入元素的函数，首先须要判断索引 index 的地位是否非法，如果 index 正好等于大小 size 的话，那就间接在最初面插入该元素即可，否则，须要调用函数，在某个元素之前插入。
public void add(int index, E element) {checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}在尾部插入节点linkLast():
void linkLast(E e) {
// 保留最初一个元素
final Node<E> l = last;
// 新建一个节点，上一个元素是之前的最初一个元素
final Node<E> newNode = new Node<>(l, e, null);
// 将新节点作为最初一个节点
last = newNode;
// 如果最初一个节点为空
if (l == null)
// 阐明原来的 list 是空的，那么第一个元素也就是当初插入的元素
first = newNode;
else
// 否则原来的元素的下一个元素指定为新的元素
l.next = newNode;
// 大小扭转
size++;
// 批改次数扭转
modCount++;
}在某个节点的后面插入，调用linkBefore
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 获取以后节点的后面一个节点
final Node<E> pred = succ.prev;
// 创立一个新节点，e 它的后面一个节点指针指向后面一个节点 pred，前面一个节点指向 succ
final Node<E> newNode = new Node<>(pred, e, succ);
// succ 的后面一个节点指针指向 newnode
succ.prev = newNode;
如果 pred 为空
if (pred == null)
// 阐明之前的链表就是空的，刚刚插入的节点就是第一个节点
first = newNode;
else
// 否则须要将后面节点的下一个节点指针指向新节点
pred.next = newNode;
// 大小减少 1
size++;
// 批改次数减少
modCount++;
}查问元素
次要是 get(int index) 这个函数：
public E get(int index) {
// 查看下标是否非法
checkElementIndex(index);
// 间接调用下面说过的 node(index)办法，获取到节点之后，再返回其 item
return node(index).item;
}批改元素
批改元素，次要调用的是 set(index,element) 办法, 次要是先查找到该节点，而后将其 item 属性批改。
public E set(int index, E element) {
// 校验 index 的合法性
checkElementIndex(index);
// 查找节点
Node<E> x = node(index);
// 保留原来的节点
E oldVal = x.item;
// 批改 item 为新的元素
x.item = element;
// 返回旧的元素
return oldVal;
}删除元素
removeFirst()：移除第一个元素removeLast()：移除最初一个元素remove(Object object): 移除 objectpop(): 移除首个元素remove()：移除首个元素remove(int index): 移除索引为 index 的元素clear()：移除所有的元素
删除第一个元素
public E removeFirst() {
// 取出第一个元素
final Node<E> f = first;
// 如果为空，则不非法
if (f == null)
throw new NoSuchElementException();
// 真正的从链表中剔除第一个元素
return unlinkFirst(f);
} private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 保留以后元素的 item
final E element = f.item;
// 取出下一个节点 next
final Node<E> next = f.next;
将第一个元素的 item 置为 null，不便垃圾回收
f.item = null;
// next 指针也置为 null
f.next = null; // help GC
// 将 first 置为下一个元素
first = next;
// 如果下一个节点是 null，那么阐明删掉第一个元素之后，链表是空的
if (next == null)
last = null;
else
// 否则 next 的前节点须要只为空
next.prev = null;
// 大小减小
size--;
// 批改次数减少
modCount++;
return element;
}移除最初一个元素：
public E removeLast() {
// 取出最初一个节点
final Node<E> l = last;
// 如果最初一个节点是 null，则不非法
if (l == null)
throw new NoSuchElementException();
// 真正从链表中移除最初一个元素
return unlinkLast(l);
} private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
// 保留 item
final E element = l.item;
// 取出后面一个节点
final Node<E> prev = l.prev;
// 将以后节点的 item 置空
l.item = null;
// 前置节点置空
l.prev = null; // help GC
// 将最初一个节点置为刚刚保留的前置节点
last = prev;
// 如果后面一个节点是空的，那么证实之前的链表只有一个元素，删掉之后，链表曾经是空的了。if (prev == null)
first = null;
else
// 否则须要将 next 只为 null
prev.next = null;
// 大小减小
size--;
// 批改次数增多
modCount++;
return element;
}移除指定的对象，这里指的是节点外面的 item，从源码中能够看出，只会移除第一个满足条件的元素，胜利移除则返回 true，否则将返回 false。
public boolean remove(Object o) {
// 如果是 o 为 null
if (o == null) {for (Node<E> x = first; x != null; x = x.next) {
// 判断 item 是不是 null
if (x.item == null) {
// 满足条件则移除 x 节点
unlink(x);
return true;
}
}
} else {for (Node<E> x = first; x != null; x = x.next) {
// 这里应用 equal 办法判断是否相等
if (o.equals(x.item)) {
// 满足条件则移除 x
unlink(x);
return true;
}
}
}
return false;
}默认移除第一个元素，因为 LinkedList 是双向链表，所以，pop()和 reomve()都是默认删除第一个元素。
public E pop() {return removeFirst();
}
public E remove() {return removeFirst();
}移除索引下标为 index 的元素，思路是先查找到该节点，而后调用 unlink(node) 移除节点即可。
public E remove(int index) {
// 查看合法性
checkElementIndex(index);
return unlink(node(index));
}移除所有的节点：
public void clear() {
// 循环将元素置空
for (Node<E> x = first; x != null;) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
// 第一个元素和最初一个元素置空
first = last = null;
// 大小置 0
size = 0;
// 批改次数减少
modCount++;
}3.2.4 小结一下
LinkedList底层就是双向链表，实现了 List 和Queue接口，容许蕴含所有的元素，元素能够为 null。LinkedList外面的节点为 null 怎么保留数据？节点为 null 的确不能保留数据，然而数据是保留在节点上面的 item 外面的，所以，item 能够为 null。
每一个节点都保留了前一个节点的援用和下一个节点的援用，以及以后节点的数据。
因为底层是双向链表以及实现了 Queue 接口，所以它也能够当成双向队列来应用。
线程不平安，多线程环境下操作很容易呈现底层链表错误操作。
3.3 Vector
Vector和 ArrayList 差不多，区别就是 Vector 是线程平安的。继承于 AbstractList，实现了List, RandomAccess, Cloneable 这些接口，能够随机拜访，也能够克隆。
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable3.3.1 成员变量
底层是数组，减少元素，数组空间不够的时候，须要扩容。
- elementData：真正保留数据的数组
- elementCount：理论元素个数
- capacityIncrement：容量减少系数
- serialVersionUID：序列化 id
// 真正保留数据的数组
protected Object[] elementData;
// 元素个数
protected int elementCount;
// 容量减少系数
protected int capacityIncrement;
// 序列化 id
private static final long serialVersionUID = -2767605614048989439L;3.3.2 构造函数
指定容量和增长系数构造函数
public Vector(int initialCapacity, int capacityIncrement) {super();
// 非法判断
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity:"+
initialCapacity);
// 初始化数组
this.elementData = new Object[initialCapacity];
// 指定增长系数
this.capacityIncrement = capacityIncrement;
}指定初始化容量，增长系数默认为 0
public Vector(int initialCapacity) {this(initialCapacity, 0);
}什么都不指定，默认给的容量是 10：
public Vector() {this(10);
}指定汇合初始化：
public Vector(Collection<? extends E> c) {
// 转换成为数组
Object[] a = c.toArray();
// 大小为数组的大小
elementCount = a.length;
// 如果是 ArrayList，则间接复制
if (c.getClass() == ArrayList.class) {elementData = a;} else {
// 否则须要进行拷贝
elementData = Arrays.copyOf(a, elementCount, Object[].class);
}
}3.3.3 罕用办法
减少
减少元素，默认是在最初增加
public synchronized void addElement(E obj) {
// 批改次数减少
modCount++;
// 确保容量足够（如果须要，外面会有扩容，复制操作）ensureCapacityHelper(elementCount + 1);
// 将新元素放在最初一个元素，个数减少
elementData[elementCount++] = obj;
}那么它是如何确保容量的呢？
能够看到 ensureCapacityHelper() 外面判断减少后的元素个数是否大于当初数组的长度，如果不满足，就须要扩容。调用 grow() 函数扩容。
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 扩容，传入的是须要最小的容量
private void grow(int minCapacity) {
// overflow-conscious code
// 以前的容量
int oldCapacity = elementData.length;
// 当初的容量，是以前的容量加上扩大系数，如果扩大系数小于等于 0，那么，就是以前的容量的两倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
// 如果新的容量大于最小须要容量，就满足了
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新的容量比最大的容量还要打
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 须要解决把最大的容量升高一些
newCapacity = hugeCapacity(minCapacity);
// 拷贝数据
elementData = Arrays.copyOf(elementData, newCapacity);
}在指定的索引 index，插入数据，实际上调用的是insertElementAt(element, index).
public void add(int index, E element) {insertElementAt(element, index);
}
// 调用插入元素的函数
public synchronized void insertElementAt(E obj, int index) {
// 批改次数减少
modCount++;
// 判断索引是否非法
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ ">" + elementCount);
}
// 确保容量足够
ensureCapacityHelper(elementCount + 1);
// 拷贝数据，将前面的元素，往后挪动一位
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
// 将理论的数据插入
elementData[index] = obj;
// 个数减少
elementCount++;
} 将一个汇合所有元素增加进去：
public synchronized boolean addAll(Collection<? extends E> c) {
// 批改次数减少
modCount++;
// 转成数组
Object[] a = c.toArray();
// 数组的长度
int numNew = a.length;
// 确保容量足够
ensureCapacityHelper(elementCount + numNew);
// 拷贝
System.arraycopy(a, 0, elementData, elementCount, numNew);
// 更新个数
elementCount += numNew;
// 返回增加的数组是不是有数据
return numNew != 0;
}指定 index，插入一个汇合，和后面不一样的中央在于复制之前，须要计算往后面挪动多少位，不是用 for 循环去插入，而是一次性挪动和写入。
public synchronized boolean addAll(int index, Collection<? extends E> c) {
// 批改次数减少
modCount++;
// 非法判断
if (index < 0 || index > elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// 转换数组
Object[] a = c.toArray();
// 插入数组长度
int numNew = a.length;
// 确保数组的长度是否非法
ensureCapacityHelper(elementCount + numNew);
// 挪动的步长计算
int numMoved = elementCount - index;
if (numMoved > 0)
// 挪动前面的元素，腾出地位给插入的元素
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 插入元素
System.arraycopy(a, 0, elementData, index, numNew);
// 更新个数
elementCount += numNew;
// 插入元素个数是否为 0
return numNew != 0;
}删除
删除指定元素
public boolean remove(Object o) {return removeElement(o);
}
// 理论调用的是 removeElement()
public synchronized boolean removeElement(Object obj) {
// 批改次数减少
modCount++;
// 获取第一个满足条件的元素缩影
int i = indexOf(obj);
// 索引如果满足条件
if (i >= 0) {
// 将索引为 i 的元素从数组中移除
removeElementAt(i);
return true;
}
return false;
}
// 操作数组删除元素
public synchronized void removeElementAt(int index) {
// 批改次数减少
modCount++;
// 是否非法
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + ">=" +
elementCount);
}
else if (index < 0) {throw new ArrayIndexOutOfBoundsException(index);
}
// index 前面的元素个数
int j = elementCount - index - 1;
if (j > 0) {
// 往前面挪动一位（复制，笼罩）System.arraycopy(elementData, index + 1, elementData, index, j);
}
// 更新个数
elementCount--;
// 原来最初一个元素的地位置空
elementData[elementCount] = null; /* to let gc do its work */
}依照索引删除元素：
public synchronized E remove(int index) {
// 批改次数减少
modCount++;
// 合法性判断
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// 保留原来的数据
E oldValue = elementData(index);
// 挪动的个数
int numMoved = elementCount - index - 1;
// 如果挪动个数大于 0
if (numMoved > 0)
// 前面的元素往前面挪动一位，赋值，笼罩
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 最初一个元素置空
elementData[--elementCount] = null; // Let gc do its work
// 返回旧的元素
return oldValue;
}批改
上面两个 set 函数都是，批改索引为 index 的元素，区别就是一个会返回旧的元素，一个不会返回旧的元素。
public synchronized E set(int index, E element) {
// 合法性判断
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// 取出旧的元素
E oldValue = elementData(index);
// 更新
elementData[index] = element;
// 返回旧的元素
return oldValue;
}
public synchronized void setElementAt(E obj, int index) {
// 非法哦性判断
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + ">=" +
elementCount);
}
// 间接更新
elementData[index] = obj;
}查问
public synchronized E get(int index) {
// 非法判断
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// 返回数组的元素
return elementData(index);
}3.3.4 小结一下
Vector的思路和 ArrayList 根本是雷同的，底层是数组保留元素，Vector 默认的容量是 10，有一个增量系数，如果指定，那么每次都会减少一个系数的大小，否则就扩充一倍。
扩容的时候，其实就是数组的复制，其实还是比拟耗时间的，所以，咱们应用的时候应该尽量避免比拟耗费工夫的扩容操作。
和 ArrayList 最大的不同，是它是线程平安的，简直每一个办法都加上了 Synchronize 关键字，所以它的效率绝对也比拟低一点。
3.4 顺便说说 AbstractList
AbstractList是一个抽象类，实现了 List 接口，继承了 AbstractCollection 类。其外部实现了一些增删改查的操作，
我在想为什么须要 AbstractList 实现 List，再让ArrayList 去继承 AbstractList。为啥要这样子干，间接继承List 不行么？
这里次要是因为要遵循一个准则，接口中只能有形象的办法，然而抽象类除了形象办法之外，还能够有具体的实现办法。而 List 的实现类比拟多，比方 ArrayList,LinkedList,Vector 等等，必定有共同之处，有通用的办法。
要是它们都间接实现 List 接口，那么就会产生一些冗余反复的代码。而要是这些共同之处，通用的办法，被形象进去实现放在 AbstractList 外面，多简洁，香不香？香！！！
这样一来，就相当于加了一层中间层，计算机设计的原理也是动不动就加一个缓冲层。（手动狗头）
上面咱们来大略介绍一下AbstractList:
3.4.1 定义以及成员变量
实现了 List 接口，继承了 AbstractCollection 类,AbstractList 无参数结构 protected 润饰。
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {protected AbstractList() {}}成员变量: 批改次数
protected transient int modCount = 0;外面只有一个形象办法get()
abstract public E get(int index);3.4.2 罕用办法
减少
定义了一套 add 办法实现的规范，一个默认在最初增加，一个是在指定索引地位的，然而思考到不同的子类实现不一样，这个办法必须实现，要不就会抛出异样。
public boolean add(E e) {add(size(), e);
return true;
}
public void add(int index, E element) {throw new UnsupportedOperationException();
}指定索引的地位，增加汇合外面所有的元素
public boolean addAll(int index, Collection<? extends E> c) {
// 查看 index 是否非法
rangeCheckForAdd(index);
boolean modified = false;
// 循环增加
for (E e : c) {add(index++, e);
modified = true;
}
return modified;
}批改
public E set(int index, E element) {throw new UnsupportedOperationException();
}删除
删除指定索引的元素，不做实现，要求子类自实现
public E remove(int index) {throw new UnsupportedOperationException();
}// 删除所有的元素
public void clear() {removeRange(0, size());
}删除指定范畴的元素
protected void removeRange(int fromIndex, int toIndex) {
// 获取迭代器到开始删除的地位
ListIterator<E> it = listIterator(fromIndex);
// 循环删除
for (int i=0, n=toIndex-fromIndex; i<n; i++) {it.next();
it.remove();}
}查问
形象办法，不做实现。
abstract public E get(int index);查问索引地位
// 查问 object 的索引的地位
public int indexOf(Object o) {
// 获取迭代器
ListIterator<E> it = listIterator();
if (o==null) {
// 如果对象为空
while (it.hasNext())
// 不能应用 null，这里因为 cursor+1，须要取后面一个索引值
if (it.next()==null)
return it.previousIndex();} else {while (it.hasNext())
// 应用 equal 判断
if (o.equals(it.next()))
return it.previousIndex();}
return -1;
}
// 和下面一个相同，从前面倒着向后面遍历
public int lastIndexOf(Object o) {ListIterator<E> it = listIterator(size());
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;
}截取 list
public List<E> subList(int fromIndex, int toIndex) {
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}3.4.3 迭代器
咱们其实能够看到 AbstractList 外面定义了两个迭代器，别离是 Itr 和ListItr,Itr实现了 Iterator 接口，ListItr实现了ListIterator，继承了Itr.
仔细点咱们就会发现，这外面有几个办法都是操作 Iterator 相干的。
public Iterator<E> iterator() {return new Itr();
}
public ListIterator<E> listIterator() {return listIterator(0);
}
// 返回指定索引处的迭代器
public ListIterator<E> listIterator(final int index) {rangeCheckForAdd(index);
return new ListItr(index);
}为什么须要两个迭代器呢？这个问题始终在我的脑海里，挥之不去 …
暂且来看看源码：
private class Itr implements Iterator<E> {
// 下一次调用 next 将返回的索引
int cursor = 0;
// 上一次调用 next 或者 previous 返回的索引
int lastRet = -1;
// 期待被批改的次数
int expectedModCount = modCount;
// 只有 curse（游标）不等于 size 大小，就示意还有元素
public boolean hasNext() {return cursor != size();
}
// 获取下一个元素
public E next() {
// 查看是否被批改
checkForComodification();
try {
// 保留游标
int i = cursor;
// 获取元素
E next = get(i);
// 将最初一次返回的索引批改成最新的 i
lastRet = i;
// 将下次行将返回的游标索引更新
cursor = i + 1;
// 返回元素
return next;
} catch (IndexOutOfBoundsException e) {checkForComodification();
throw new NoSuchElementException();}
}
// 删除操作
public void remove() {
// 上一次返回的
if (lastRet < 0)
throw new IllegalStateException();
// 查看批改次数
checkForComodification();
try {
// 调用内部的办法 remove
AbstractList.this.remove(lastRet);
// 元素被删除了，游标须要倒走一步
if (lastRet < cursor)
cursor--;
// 删除后，lastRet 上一次拜访的元素不存在了，须要只为 -1
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {throw new ConcurrentModificationException();
}
}
// 判断操作后的批改次数，是否等于期待批改次数
final void checkForComodification() {if (modCount != expectedModCount)
throw new ConcurrentModificationException();}
}上面这段代码让我好纳闷，为什么须要判断上一次拜访的 index 是不是小于下一次执行 next 返回的 index 才执行 -1 的操作
if (lastRet < cursor)
cursor--;起初我在 ListItr 的代码中找到了答案，因为 ListItr 有一个办法是 previous()，会倒回迭代器的上一个元素，如果执行了previous()，那么上一次返回的元素，和下一次执行 next 返回的元素就是同一个，所以这个时候是可能呈现lastRet= cursor 的。
看看 ListItr 源码：
private class ListItr extends Itr implements ListIterator<E> {ListItr(int index) {cursor = index;}
// 是否后面有元素
public boolean hasPrevious() {return cursor != 0;}
public E previous() {
// 查看批改次数
checkForComodification();
try {
// 获取后面的元素 index
int i = cursor - 1;
// 获取后面的元素
E previous = get(i);
// 上一次拜访的元素 index 和下一次调用 next 的 index，都须要赋值为 i（相当于 cursor-1）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);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();
}
}
// 新增元素
public void add(E e) {checkForComodification();
try {
int i = cursor;
// 在迭代器的以后地位增加元素
AbstractList.this.add(i, e);
// 不关怀 lastRet
lastRet = -1;
// 下一个元素的索引须要 +1
cursor = i + 1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();
}
}
}为什么须要两个迭代器呢？
咱们发现 Itr 其实只有 next() 和remove()两个办法，这是实用于一般的大部分的子类的，而 ListItr 则多了一个回溯上一个元素的 hasPrevious 以及 set() 和add()办法，属于降级版本。Itr属于公共的迭代器，继承它的有 ListIterator 和PrimitiveIterator。
两个迭代器之间的区别：
应用 iterator 只能向前挪动，然而应用 ListIterator 能够在读取元素时也挪动后退字词。
应用 ListIterator，您能够在遍历时随时获取索引，而迭代器则无奈实现。
应用 iterator，您只能查看下一个元素是否可用，然而在 listiterator 中，您能够查看上一个和下一个元素。
应用 listiterator，您能够在遍历的任何工夫增加新元素。应用迭代器是不可能的。
应用 listiterator，您能够在遍历时批改元素，而迭代器则不能。
查了一下 Stack Overflow，答案链接：https://stackoverflow.com/que…
这个有可能是答案：
Since Java 5 it is simply possible to override a method with a more specific return type (called covariant return type). But ListIterator has been introduced with Java 1.2. To avoid casts on usage of iterator() there has to be a new method.
The API could not have been changed from Java 5 on because that would have broken all implementations of List which do not declare iterator() returning ListIterator also if most implementations return a ListIterator instance in real.
A similar dilemma is Enumeration and Iterator. Nowadays Iterator would extend Enumeration and simply add the remove() method. Or better Iterator would have replaced Enumeration and a ModifiableIterator with an additional remove() would have been added.
中文就是：
因为 Java 5 能够用更特定的返回类型 (称为协变返回类型) 重写办法。然而 ListIterator 是在 Java 1.2 中引入的。为了防止对 iterator()的应用进行强制类型转换，必须有一个新办法。
API 不可能从 Java 5 开始扭转，因为这将毁坏所有没有申明 iterator()返回 ListIterator 的 List 实现，如果大多数实现在理论中返回 ListIterator 实例。
相似的窘境是枚举和迭代器。当初迭代器将扩大枚举并简略地增加 remove()办法。或者更好的迭代器会替换枚举，并且会增加一个额定的 remove()来增加一个 ModifiableIterator。
个人观点：这是迭代版本的过程中，基于兼容性和可拓展性来做的。也有人说是基于单向链表和双向链表来思考的，貌似也有一点情理。
3.4.4 小结一下
AbstractList是实现 List 接口的抽象类，AbstractList抽象类与 List 接口的关系有点像 AbstractCollection 抽象类与 Collection 接口的关系。
领有一部分形象办法和一部分实现的办法，属于 List 和具体容器实现类比方 ArrayList 两头的一层。
4. 总结
List接口, 次要是实现了列表的接口标准，罕用的三个子类是：
-
ArrayList
- 底层是数组，扩容就是申请新的数组空间，复制
- 线程不平安
- 默认初始化容量是 10，扩容是变成之前的 1.5 倍
- 查问比拟快
-
LinkedList
- 底层是双向链表，能够往前或者往后遍历
- 没有扩容的说法，能够当成双向队列应用
- 增删比拟快
- 查找做了优化，index 如果在后面一半，从后面开始遍历，index 在前面一半，从后往前遍历。
-
Vector
- 底层是数组，简直所有办法都加了 Synchronize
- 线程平安
- 有个扩容增长系数，如果不设置，默认是减少原来长度的一倍，设置则增长的大小为增长系数的大小。
AbstractList，是 List 拓展进去的抽象类，定义了一部分通用的办法，补救了 List 是接口，不能对办法有所实现的有余，相当于加了一个中间层。外面定义了两个迭代器 Iterator 类，也提供了获取它们的办法，能够供不同的子类应用。
【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。这个世界心愿所有都很快，更快，然而我心愿本人能走好每一步，写好每一篇文章，期待和你们一起交换。
此文章仅代表本人（本菜鸟）学习积攒记录，或者学习笔记，如有侵权，请分割作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有谬误之处，还望指出，感激不尽~
