集合类顶层接口
Java 集合类中有大量数据迭代操作，所以底层都需要实现Iterable接口。迭代器是一种模式，它可以使得对于序列类型的数据结构的遍历行为与被遍历的对象分离，即我们无需关心该序列的底层结构是什么样子的。只要拿到这个对象,使用迭代器就可以遍历这个对象的内部。
1.Iterable接口
Iterable
--iterator()
--forEach(Consumer<? super T> action)
--spliterator()
-
iterator()
Iterable接口最初只有iterator()方法，返回一个Iterator用于迭代遍历元素。
Iterator也是一个接口包含了以下方法。
Iterator接口 --hasNext() 返回是否还有下一个元素 --next() 返回下一个元素 --remove() 移除元素 --forEachRemaining(Consumer<? super E> action) 自动遍历剩下的元素Consumer 也是一个接口，可实现对每个元素做指定操作。
Consumer接口 --accept(T t) 可实现对传入的t做特定处理 --andThen(Consumer<? super T> after) 将两个Consumer合成一个 -
forEach(Consumer<? super T> action)
遍历元素，并对每个元素应用action的accept方法。
-
spliterator()
返回一个可分割迭代器 Spliterator，这是为并行遍历元素而设计的一个迭代器接口。
public interface Spliterator<T> { // 给单个元素执行一个action，之后如果还有元素返回true，之后没有元素返回false boolean tryAdvance(Consumer<? super T> action); // 遍历集合元素，执行指定action default void forEachRemaining(Consumer<? super T> action) { do { } while (tryAdvance(action)); } // 对迭代分割，返回一个新的Spliterator迭代器 Spliterator<T> trySplit(); // 预估剩余还有多少个元素需要遍历 long estimateSize(); // 当迭代器拥有SIZED特征时返回预估剩余元素，否则返回-1 default long getExactSizeIfKnown() { return (characteristics() & SIZED) == 0 ? -1L : estimateSize(); } // 返回当前迭代器拥有的特征 int characteristics(); // 返回当前迭代器是否拥有指定特征 default boolean hasCharacteristics(int characteristics) { return (characteristics() & characteristics) == characteristics; } // 如下是一些特征常量，只列举部分 public static final int SIZED = 0x00000040; public static final int SORTED = 0x00000004; // 针对int的迭代并行迭代器，还有long 和 double public interface OfInt extends OfPrimitive<Integer, IntConsumer, OfInt> {...} }
小结：Iterable接口定义了迭代过程中需要的方法，通过具体Iterator和Spliterator提供实现细节。
2.Collection接口
public interface Collection<E> extends Iterable<E>
Collection接口是集合类的根接口，规定了集合子类该有的基本功能，并且继承了Iterable接口。
Collection
--size() 集合尺寸
--isEmpty() 判空
--contains(Object o) 是否包含指定元素
--iterator() 返回迭代器
--toArray() 返回对象数组
--toArray(T[] a) 返回指定类型的数组
--add(E e) 添加元素，如果不能添加或者已经有了该元素则返回false，添加成功返回true
--remove(Object o) 移除指定元素，如果本集合中存在一个或多个则返回true，否则返回false
--containsAll(Collection<?> c) 是否包含传入集合中的元素
--addAll(Collection<? extends E> c) 添加传入集合中的元素，如果有修改则返回true
--removeAll(Collection<?> c) 原因集合有修改则返回true
--removeIf(Predicate<? super E> filter) 移除过滤器中筛选出的元素
--retainAll(Collection<?> c) 保留传入集合中的元素,原有集合有变动则返回true
--clear() 清空原有集合
--equals(Object o)
--hashCode()
--spliterator()返回一个可分割迭代器
--stream() 返回一个流
--parallelStream()返回一个并行流
3.AbstractCollection抽象类
以上几个接口规定的一个集合类应该拥有的功能，其中有很多方法不同子类的实现是相同的，此时通过一个抽象类为其中的共有方法提供一个基本的实现，留下个别特殊方法给子类实现。这样通过子类继承抽象类可以快速实现一个集合类。
public abstract class AbstractCollection<E> implements Collection<E>{
// 只需要实现iterator()和size()就可以构造一个基本的集合类。
public abstract Iterator<E> iterator();
public abstract int size();
// 判空方法也依赖于size()的实现，公共方法依赖特定方法的实现。
public boolean isEmpty() {
return size() == 0;
}
public <T> T[] toArray(T[] a) {
// 创建目标数组，使用传入集合类a和本集合类中 更大的size
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()) {
if (a == r) {
// 原有列表size小于传入a大小，将a中多出来的位置赋值为null
r[i] = null; // null-terminate
} else if (a.length < i) {
// 原有列表size大于a,但实际i后面已经没有元素了，
// 此时就截断遍历返回有元素的部分
return Arrays.copyOf(r, i);
} else {
// 原有列表size等于a大小，还是按a大小返回，但要把最后一个元素置null
System.arraycopy(r, 0, a, 0, i);
if (a.length > i) {
a[i] = null;
}
}
return a;
}
// 还有元素则继续赋值
r[i] = (T)it.next();
}
// 如果迭代器中还有元素，及实际元素数量大于原列表size，直接重新创建一个更大的数组。
return it.hasNext() ? finishToArray(r, it) : r;
}
// 这就有意思了，虽然实现了方法，但给你抛个不支持的异常。
// 因为此抽象类中数据遍历都依赖Iterator,但这个接口不支持写入数据。
public boolean add(E e) {
throw new UnsupportedOperationException();
}
// 清空集合，遍历迭代移除数据就好
public void clear() {
Iterator<E> it = iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** 其他方法实现就不在此列举了 **/
}
小结一下：
（1）AbstractCollection抽象类中实现的方法基本都依赖未实现的 size()和iterator()。
（2）学习到了使用反射生成数组的方式，String[] a = (String[]) java.lang.reflect.Array.newInstance(String.class.getComponentType(), 100);
（3）迭代器中的next()是可以返回null的。
（4）Integer.MAX_VALUE - 8 是集合类容器上限，0x7fffffff - 8
List类
1.List接口
public interface List<E> extends Collection<E>
列表类的根接口是List 继承了Collection接口中的方法，还增加了部分新的方法，主要是涉及针对索引的操作。
List
--get(int index) 根据索引获取指定元素
--set(int index, E element) 替换指定位置的元素，返回先前位置的元素
--add(int index, E element) 在指定位置添加元素
--remove(int index) 删除指定位置元素
--indexOf(Object o) 返回指定元素位置，不存在返回-1
--lastIndexOf(Object o) 返回列表中和指定元素相同的最后一个位置的索引，不存在返回-1
--listIterator() 返回ListIterator
--listIterator(int index) 返回ListIterator，从指定位置开始索引的
--subList(int fromIndex, int toIndex)
2.AbstractList抽象类
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>
首先AbstractList 是为了方便后续创建具体列表类，接口中的的方法不是每个子类都会调用的，所以很多方法都是空实现；重点关注其中非空实现和抽象方法。
继承AbstractCollection抽象类需要实现iterator() 和size()方法，而List接口又需要实现新增的接口方法。
get 和size方法是必须要实现的，但仅实现这两个方法只是一个不可修改的集合类。
AbstractList
-- get(int) 根据指定索引获取元素
-- size() List 接口中的方法，留作用户实现
在AbstractList中添加了一个变量modCount 记录该集合中结构性修改的次数（元素替换不算在内），相当于一个版本号记录当前列表的数据版本，该变量不参与序列化。
protected transient int modCount = 0;
作为一个列表类，迭代遍历是很重要的操作，AbstractList中有三个提供迭代器的方法。
// 返回一个基本迭代器
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);
}
Itr迭代器
这里Itr中一个内部类，实现了Iterator接口，这里看一下基本实现
private class Itr implements Iterator<E> {
// 向下遍历时将要返回的下一个元素的游标
int cursor = 0;
// 记录了上一次调用next或者previous时的索引，当调用一次remove后会被置为-1，
// 重新调用next或者previous时又会重新赋值
// lastRet 是在数组长度不变的情况下（没执行add or remove）上一次读取元素的位置。
int lastRet = -1;
// 迭代器当前数据版本号，迭代前需要判断是否和列表类版本是否一致
int expectedModCount = modCount;
// 根据size 判断是否还有下一个元素。
public boolean hasNext() {
return cursor != size();
}
// 获取当前游标所在元素
public E next() {
// 判断版本是否一致
checkForComodification();
try {
// 先获取位置再修改游标
int i = cursor;
E next = get(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 {
// 先删除元素
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();
}
小结一下：Itr迭代器提供了基本的迭代能力，使用两个游标记录的当前位置和上一次访问的位置，使用expectedModCount记录迭代器的版本号，因为数据没有存储在迭代器中，需要和数据源的版本号做同步。迭代器方法底层实现都依赖列表类中的方法。
ListItr 迭代器
ListItr扩展了基本的迭代器，实现了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);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// 在游标所在位置添加元素，此处lastRet置为-1是因为add修改了数据存储结构，需要置为-1，
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();
}
}
}
小结：（1） lastRet这个变量在向下遍历next，向上遍历previous，添加元素add，删除元素remove 都会修改，但当修改了数据存储结构尺寸时会置为-1。
“非结构性修改”，是指不涉及到list的大小改变的修改。相反，结构性修改，指改变了list大小的修改 。
查找指定元素索引
依赖ListIterator向前遍历的能力，我们可以根据元素来找出该元素在list中的位置。
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()))
// 此时cursor已经是当前元素的下一位置，所以要返回前一个索引。
return it.previousIndex();
}
return -1;
}
当然列表类中还有两个比较重要的方法hashCode和equals
public int hashCode() {
int hashCode = 1;
for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}
列表类的hashcode结合了每个元素的hashcode，当然会跳过null元素。
public boolean equals(Object o) {
// 判断地址是否一致
if (o == this)
return true;
// 判断类型是否一致
if (!(o instanceof List))
return false;
ListIterator<E> e1 = listIterator();
ListIterator<?> e2 = ((List<?>) o).listIterator();
// 同步遍历比较元素是否一致
while (e1.hasNext() && e2.hasNext()) {
E o1 = e1.next();
Object o2 = e2.next();
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
// 两个集合同时遍历完才会判等
return !(e1.hasNext() || e2.hasNext());
}
3.ArrayList
终于讲到了具体的列表类，具体的列表类需要实现数据存储结构，以及围绕该存储结构的一系列外部方法的实现。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
存储结构
ArrayList的内部存储结构是一个数组， 使用elementData存储数据。
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;
// 当指定数组容量为0时，使用该地址作为共享数组地址
private static final Object[] EMPTY_ELEMENTDATA = {};
// 当未指定数组容量，无参构造函数创建列表指定的默认地址
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 实际存储数据的数组，不支持序列化
transient Object[] elementData;
// 数据中存储的元素数量（包含null），非线程安全
private int size;
// 列表所能容纳的最大元素个数
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 无参构造函数，使用默认空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 指定容量的构造函数，如果有预期容量，可一次分配到位，减少扩容
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(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;
}
}
}
从源码中可以看出：
- 无参构造函数使用的默认空数组，数组size为0，并不会直接分配容量为10的数组。
- 当有预期容量时会按指定容量初始化数组，如果指定为0则一次初始化到位。
- 当传入集合初始化列表时，实际使用Arrays工具类复制了一个新数组
增删改查
通常我们使用ArrayList总是调用无参构造函数，然后再添加元素，这个过程就涉及扩容。
List<String> list1 = new ArrayList<>();
list1.add("a");
首先我们看看add方法：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// 从原始数组index开始将内部元素向后移动一位，移动数量为size - index
System.arraycopy(elementData, index, elementData, index + 1,size - index);
// 空出位置后赋值
elementData[index] = element;
// 赋值成功后修改列表尺寸
size++;
}
以上扩容的逻辑在ensureCapacityInternal中，之后再修改size并赋值。
// 如果使用默认空数组，则首次扩容最少为DEFAULT_CAPACITY
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
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;
// 实际扩容容量为原始容量1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 当首次扩容oldCapacity=0，则会出现负值
// 或者newCapacity大于oldCapacity的1.5倍（以前是10*1.5=15，而新插入16个）
// 此时就按实际需求数量进行扩容。
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);
}
// 这是个一步到位的方法，当当前的minCapacity<MAX_ARRAY_SIZE直接扩容到minCapacity
// 如果minCapacity>MAX_ARRAY_SIZE 则直接扩容到 Integer.MAX_VALUE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
总结一下：
- 初次最少的扩容容量为10
- 每次扩容后总量是旧容量的1.5倍
- 使用Arrays.copyOf方法完成数组拷贝
- hugeCapacity方法可以直接申请到上限数量MAX_ARRAY_SIZE，也可以突破上限到Integer.MAX_VALUE，虽然只多了8个元素。
扩容后要进行数组拷贝使用Arrays.copyOf方法，底层实现是System.arraycopy
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
- src 是原数组
- srcpos 是开始从原数组中拷贝的位置
- dest 是目标数组
- destPos是从目标数组中复制的位置
- length 是要拷贝长度
remove
删除元素可以根据位置也可以根据元素来删除，其中核心实现还是System.arraycopy方法。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 向前移动一位，并将倒数第一位的位置置为null
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// 数组最后一个元素size-1，故--size 就是最后一个元素，将其置为null。
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
根据元素删除的方法实现和索引是一样的，遍历找到相等对象（考虑null的情况），再调用fastRemove方法移动删除尾部元素。
set
set方法可以修改list中的元素，逻辑很简单，返回旧元素替换新元素。
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
get
get是list中根据索引获取元素的方法，这里值得注意的是涉及索引操作都会rangeCheck 检查索引是否合适，在平时开发业务代码可以借鉴这种思想，将问题尽早暴露出来。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
遍历
forEach
Java8在Iterator接口中新增了forEach方法，接口提供的默认实现使用迭代器进行遍历。
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
// 确保在遍历时没有修改存储结构
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
removeIf
这个方法可以按指定条件删除集合中的元素，需要传入一个过滤器。以下筛选分为两部分：
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// 1. 遍历查找要删除元素的索引
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
// 判断是否要删除，test返回true则删除该元素
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// 2.遍历移动覆盖被删除的元素
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
// 这个方法是遍历覆盖元素的主要方法，传入一个索引i
// 如果i不是要删除的索引,就返回i
// 如果i是要删除的索引，就返回最近的不删除的索引。
// 本质上就是跳过了要删除的那些索引。
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
// 将原数组中尾部的元素置为空
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
小结：上面两个遍历方法可以帮助我们筛选元素和对数据做处理。
4.LinkedList
LinkedList 是一个双端链表，适用于大量顺序读取的场景，从定义中可以看出其继承了AbstractSequentialList抽象类并实现了Deque接口，下面我们将简要介绍一下：
public class LinkedList<E>extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
AbstractSequentialList 抽象类 是为了方便创建“顺序读取”的列表。
AbstractSequentialList
--get()
--set()
--add()
--remove()
--addAll()
--Iterator()
--listIterator()
这个抽象类中只有listIterator 是抽象方法，剩下实现的都是基于listIterator方法实现的。
该方法返回一个ListIterator迭代器，支持双向遍历和基本的增删改查功能，可以参照ListItr类的实现。
Deque接口定义了作为一个双端队列该有的功能，在实现中讲解具体接口方法。
存储结构
Linkedlist底层数据结构是链表，这就需要Node，其中item用于持有数据，next指向下一个节点，prev指向后一个节点。
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;
}
}
// 元素个数，虽然可以无限大，但int决定了其上限。
transient int size = 0;
// 头部节点
transient Node<E> first;
// 尾部节点
transient Node<E> last;
增删改查
add 方法，链表增加元素默认是从尾部插入
public boolean add(E e) {
linkLast(e);
return true;
}
// 在指定位置插入元素
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
尾部插入法，新插入的节点成为新的尾节点。
void linkLast(E e) {
final Node<E> l = last;
// 其实创建新节点的过程就完成了连起来的过程
final Node<E> newNode = new Node<>(l, e, null);
// 重新设置尾节点
last = newNode;
// 尾节点为空，说明之前没有元素，新加入的节点需要作为头结点。
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
头部插入法，和尾部插入类似
private void linkFirst(E e) {
// 因为要修改头部节点first，先暂存之前头部节点
final Node<E> f = first;
// 创建新节点并将新节点尾部指向原有头部节点。
final Node<E> newNode = new Node<>(null, e, f);
// 更新头部节点
first = newNode;
// 原有尾部节点为空则说明之前没有尾部节点，新加入的节点需要作为尾部节点。
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
在中间位置插入元素，需要先在对应位置创建新连接再更改之前的链接。
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 先暂存前置节点
final Node<E> pred = succ.prev;
// 创建新节点并和前后节点建立链接
final Node<E> newNode = new Node<>(pred, e, succ);
// 修改后置节点的头节点
succ.prev = newNode;
// 当succ就是原有头结点时，重置整个链表的头结点为新创建节点
if (pred == null)
first = newNode;
else
// 否则就修改前置节点last
pred.next = newNode;
size++;
modCount++;
}
上面列举了向链表中插入元素的三种方式，基本有如下步骤：
- 先暂存要修改的节点，头插法暂存头结点，尾插法暂存尾节点，中间位置插入暂存插入位置前后两个节点。
- 创建新节点的过程就是建立连接的过程。
- 修改原有链条上的连接
remove方法
不论是remove 索引还是对象都需要先找到要删除的节点，此处重点看下unlink方法，学习如何中链表中间删除节点。
E unlink(Node<E> x) {
// assert x != null;
// 先暂存被删节点前后的节点，和被删除的值
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 如果原有头结点被删了，重新设置头结点
if (prev == null) {
first = next;
} else {
// 前置节点的尾部直接指向后置节点
prev.next = next;
// 清空被删节点和链表的连接，方便GC
x.prev = null;
}
// 如果原有尾节点被删了，重新设置尾节点。
if (next == null) {
last = prev;
} else {
// 将后置节点的头与前置节点相连接。
next.prev = prev;
x.next = null;
}
// 清空被删节点与原数据的连接
x.item = null;
size--;
modCount++;
return element;
}
set方法
修改元素只需要使用node方法找到索引对应节点，则只需替换节点item 即可。
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
get方法
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
上面几个方法都用到了node() ，这里也看下其实现逻辑。
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
上面使用了一层二分法来定位元素，减少了一半遍历范围，提高了查找效率。
