1.LinkedList 介绍
咱们除了最最罕用的 ArrayList 之外，还有 LinkedList，这到底是什么货色？从 LinkedList 官网文档，咱们能够理解到，它其实是实现了List 和Queue的双向链表构造，而 ArrayList 底层则是数组构造。
上面的解说基于jdk 1.8:
继承了AbstractSequentialList，实现了List,Queue,Cloneable,Serializable，既能够当成列表应用，也能够当成队列，堆栈应用。次要特点有：
- 线程不平安，不同步，如果须要同步须要应用
List list = Collections.synchronizedList(new LinkedList()); - 实现
List接口，能够对它进行队列操作 - 实现
Queue接口，能够当成堆栈或者双向队列应用 - 实现 Cloneable 接口，能够被克隆，浅拷贝
- 实现
Serializable，能够被序列化和反序列化
上面是 LinkedList 的构造，留神：指针完结指向的是 node，开始的是 prev 或者next
源码定义如下：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}2. 成员变量
成员变量绝对比较简单，因为不像 ArrayList 一样，须要应用数组保留元素，LinkedList是靠援用来关联前后节点，所以这里只有大小，第一个节点，最初一个节点, 以及序列化的 uid。
// 大小
transient int size = 0;
// 第一个节点
transient Node<E> first;
// 最初一个节点
transient Node<E> last;
// 序列化 uid
private static final long serialVersionUID = 876323262645176354L;咱们来看看 Node 到底是何方神圣？
其实就是外部类，外面的 item 是真正保留节点的中央，next 是下一个节点的援用，prev是上一个节点的援用。这里也体现了 LinkedList 其实就是双线链表。
只有一个构造函数，三个参数别离对应三个属性。
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. 构造函数
构造函数有两个，一个是无参数构造函数，另一个是初始化汇合元素，外面调用的其实是addAll，一看就是将外面所有的元素退出到汇合中。
public LinkedList() {}
public LinkedList(Collection<? extends E> c) {this();
addAll(c);
}4. 罕用 List 办法解析
4.1 查找相干
4.1.1 getFirst()
获取第一个元素：
public E getFirst() {
// 保留第一个元素为 f，留神是 final 的，final Node<E> f = first;
if (f == null)
// 如果没有第一个元素，那么就会抛出异样
throw new NoSuchElementException();
// 返回第一个元素的 item
return f.item;
}4.1.2 getLast()
获取最初一个元素, 和获取第一个的原理差不多
public E getLast() {
// 保留最初一个元素的援用为 l
final Node<E> l = last;
// 如果为空，抛出谬误
if (l == null)
throw new NoSuchElementException();
// 返回 item
return l.item;
}4.1.3 get(int index)
通过索引来获取元素, 外面是调用了另外一个办法先获取节点，再获取该节点的 item, 在此之前，做了index 安全性校验。
public E get(int index) {checkElementIndex(index);
return node(index).item;
}在???? 下面的代码中调用了通过索引地位查找节点地位的函数，上面咱们来剖析一下这个函数, 因为底层是链表实现的，所以呢？遍历起来不是很不便，就思考到位运算，如果索引地位在前面一半，就从后往前遍历查找，否则从前往后遍历。
Node<E> node(int index) {// assert isElementIndex(index);
// size>>1 示意除以 2，相当于 index 小于 size 的一半
if (index < (size >> 1)) {
// 从后面开始遍历，取出 first 节点，因为两头过程援用会变动，所以不可间接操作 first
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;
}
}4.1.4 indexOf(Object o)
查找某一个元素的索引地位, 分为两种状况探讨，如果要查找的元素为空，那么就应用 ==，否则应用equals()，这也从侧面印证了LinedList 实际上是能够存储 null 元素的。应用计数查找：
public int indexOf(Object o) {
int index = 0;
// 如果须要查找 null 元素
if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)
return index;
index++;
}
} else {
// 查找元素不为空
for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}4.1.5 lastIndexOf(Object o)
和后面的 indexOf 差不多，区别就是这个是前面开始查找，找到第一个合乎的元素。
public int indexOf(Object o) {
int index = 0;
// 查找元素
if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)
return index;
index++;
}
} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}4.2 增加元素
4.2.1 addFirst(E e)
将元素 e，增加到第一个节点，私有办法是 addFirst()，然而其实外部调用是linkFirst()，这是private 办法。
public void addFirst(E e) {linkFirst(e);
}
private void linkFirst(E e) {
// 先保留第一个节点
final Node<E> f = first;
// 初始化一个新节点，prev 是 null，next 是 f（之前的首节点）final Node<E> newNode = new Node<>(null, e, f);
// 更新 first 为新节点
first = newNode;
// 如果之前的第一个节点是空的，那么就阐明外面是空的，没有元素
if (f == null)
// 最初一个元素也是新退出的元素
last = newNode;
else
// f 的 prev 前置节点的援用更新为新的节点
f.prev = newNode;
// 个数减少
size++;
// 批改次数减少
modCount++;
}4.2.2 addLast(E e)
将元素增加在链表最初，其实外部也是间接调用的 private 办法linkLast():
public void addLast(E e) {linkLast(e);
}
void linkLast(E e) {
// 保留最初一个节点的援用
final Node<E> l = last;
// 初始化一个节点，前置节点指针援用指向之前的最初一个节点，后续节点的援用是 null
final Node<E> newNode = new Node<>(l, e, null);
// 将最初一个节点更新
last = newNode;
// 如果之前的最初一个节点是 null，阐明链表是空的
if (l == null)
// 新节点同时是第一个节点
first = newNode;
else
// 否则之前的最初一个节点的后续节点援用更新为新的节点
l.next = newNode;
// 大小 +1
size++;
// 批改次数 +1
modCount++;
}4.2.3 add(E e)
减少元素，默认也是在链表的最初增加，实现返回 true：
public boolean add(E e) {linkLast(e);
return true;
}4.2.4 addAll(Collection<? extends E> c)
往链表外面批量增加元素, 外面默认是在最初面批量增加，外部调用的是 addAll(int index, Collection<? extends E> c), 增加之前会判断索引地位是不是非法的。
而后查找须要插入的地位的前后节点，循环插入。
public boolean addAll(Collection<? extends E> c) {return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 查看增加地位
checkPositionIndex(index);
// 将须要增加的汇合转换成为数组
Object[] a = c.toArray();
// 获取数组的大小
int numNew = a.length;
// 如果数组长度为 0，阐明没有须要增加的元素，返回 false
if (numNew == 0)
return false;
// 插入地位的前节点和后续节点
Node<E> pred, succ;
// 如果插入地位索引大小等于链表大小，那么就是在最初插入元素
if (index == size) {
// 最初插入元素没有后续节点
succ = null;
// 前一个节点就是之前的最初一个节点
pred = last;
} else {
// 查找到索引为 index 的节点
succ = node(index);
// 获取前一个节点
pred = succ.prev;
}
// 循环插入节点
for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;
// 初始化新节点，上一个节点是 pred
Node<E> newNode = new Node<>(pred, e, null);
// 如果前一个节点是 null，那么第一个节点就是新的节点
if (pred == null)
first = newNode;
else
// 否则 pred 的 next 置为新节点
pred.next = newNode;
pred = newNode;
}
// 如果插入地位没有后续节点，也就是 succ 为 null
if (succ == null) {
// 最初一个节点也就是 pred，刚刚插入的新节点
last = pred;
} else {
// 退出所有元素之后的最初一个节点的下一个节点指向 succ（后续元素）pred.next = succ;
// 插入地位的后续元素的上一个节点援用指向 pred
succ.prev = pred;
}
// 大小扭转
size += numNew;
// 批改次数减少
modCount++;
return true;
}下面的代码调用了node(index)，这个在后面查找的时候曾经说过了，不再解释。
4.2.5 addAll(int index, Collection<? extends E> c)
在指定地位批量插入节点：
public boolean addAll(int index, Collection<? extends E> c) {
// 查看索引合法性
checkPositionIndex(index);
// 将须要插入的汇合转换成为数组
Object[] a = c.toArray();
// 数组的长度
int numNew = a.length;
// 为 0 则不须要插入
if (numNew == 0)
return false;
// 插入地位的前节点和后节点
Node<E> pred, succ;
// 如果在最初插入
if (index == size) {
// 后节点为空
succ = null;
// 前节点是最初一个
pred = last;
} else {
// 获取插入地位的后节点
succ = node(index);
// 获取前节点
pred = succ.prev;
}
// 遍历
for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;
// 初始化节点，前置节点是插入地位的前节点，后续节点为 null
Node<E> newNode = new Node<>(pred, e, null);
// 如果插入地位前一个节点是 null，阐明插入地位是链表首
if (pred == null)
// 首节点就是新插入的节点
first = newNode;
else
// 前节点的 next 指向新节点
pred.next = newNode;
// 更新插入地位的前一个节点
pred = newNode;
}
// 如果插入地位的后一个节点为空，阐明插入地位是链表尾部
if (succ == null) {
// 最初一个元素就是插入的元素
last = pred;
} else {
// 将插入的最初一个元素 next 指向 succ
pred.next = succ;
// succ 的上一个元素指向 prev
succ.prev = pred;
}
// 大小更新
size += numNew;
// 批改次数扭转
modCount++;
// 返回胜利
return true;
}4.2.6 add(int index,E element)
将元素插入在指定地位, 先判断索引地位，如果索引地位是最初一个，那么间接调用在最初增加元素函数即可，否则须要调用另外一个函数，在某个元素后面插入：
public void add(int index, E element) {
// index 校验
checkPositionIndex(index);
// 索引等于链表大小
if (index == size)
// 间接在最初插入元素
linkLast(element);
else
// 在某个节点前插入元素
linkBefore(element, node(index));
}4.3 删除元素
4.3.1 removeFirst()
删除第一个节点，先获取首节点，判断第一个节点是不是为空，如果为空则证实没有该节点，抛出异样，外部调用的其实是unlinkFirst()。返回值是被移除的节点外面的数值。
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;
// 获取外面的元素
final E element = f.item;
// 保留下一个节点
final Node<E> next = f.next;
// 将之前的首节点前后节点援用置空，有利于 GC
f.item = null;
f.next = null; // help GC
// 首节点更新
first = next;
// 如果首节点是空的，那么链表没有元素了，最初一个节点天然也是 null
if (next == null)
last = null;
else
// 否则以后的第一个节点的前置节点置 null
next.prev = null;
// 链表大小 -1
size--;
// 批改次数减少
modCount++;
return element;
}4.3.2 removeLast()
删除最初一个节点，和下面的删除首节点差不多，先取出最初一个节点，判断是否为空，如果为空则抛出异样，否则会调用另一个解除连贯的函数unLinkLast()。
public E removeLast() {
final Node<E> l = last;
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;
// 前后援用置空，有利于垃圾回收
l.item = null;
l.prev = null; // help GC
// 更新最初一个节点
last = prev;
// 如果前置节点为空，那么链表曾经没有元素了
if (prev == null)
first = null;
else
// 否则将上一个节点的 next 置 null
prev.next = null;
// 大小该表
size--;
// 批改次数减少
modCount++;
// 返回被移除的节点的 item 值
return element;
}
4.3.3 remove(Object o)
删除某个元素分为两种状况，元素为 null 和非 null, 间接遍历判断，外面真正删除的办法其实是unlink(E e)，胜利移除则返回 true，留神这里只会移除掉第一个，后续要是还有该节点，不会移除。
public boolean remove(Object o) {
// 元素为 null
if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);
return true;
}
}
} else {
// 元素不为 null
for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {
// 移除节点
unlink(x);
return true;
}
}
}
return false;
}unLink(E e)办法如下：
E unlink(Node<E> x) {
// assert x != null;
// 保留被移除节点的 item
final E element = x.item;
// 下一个节点
final Node<E> next = x.next;
// 上一个节点
final Node<E> prev = x.prev;
// 如果前置节点为空，那么首节点就是以后节点了
if (prev == null) {first = next;} else {
// 前一个节点的 next 置为下一个节点
prev.next = next;
// 之前的节点的前一个节点置 null
x.prev = null;
}
// 如果 next 是空的，那么上一个节点就是当初最初一个节点
if (next == null) {last = prev;} else {
// next 的上一个节点援用指向 prev
next.prev = prev;
// 被删除的元素的 next 置空
x.next = null;
}
// item 置空
x.item = null;
// 大小扭转
size--;
// 批改次数减少
modCount++;
// 返回被删除的节点外面的 item
return element;
}4.3.4 clear()
移除外面所有的元素：
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null;) {
// 保留下一个
Node<E> next = x.next;
// 以后元素置空
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
// 首节点和尾节点全副置 null
first = last = null;
size = 0;
modCount++;
}4.3.5 remove（int index）
移除指定索引的元素。先通过索引找到节点，再移除指定的节点
public E remove(int index) {
// 查看合法性
checkElementIndex(index);
// 先找到节点，再移除指定节点
return unlink(node(index));
}4.4 更新元素
4.4.1 set(int index,E element)
更新指定索引的地位的元素, 首先通过索引查找到该元素，而后批改 item 值，返回旧的 item 值。
public E set(int index, E element) {
// 查看索引是否非法
checkElementIndex(index);
// 通过索引查找到节点
Node<E> x = node(index);
// 保留旧的值
E oldVal = x.item;
// 批改
x.item = element;
// 返回旧的元素
return oldVal;
}5 queue 相干的办法
因为 LinkedList 也实现了 queue 接口，所以它必定也实现了相干的办法，上面咱们看看：
5.1 peek()
获取队列第一个元素：
public E peek() {
// 拿到第一个元素，final 不可变
final Node<E> f = first;
// 返回 item 值
return (f == null) ? null : f.item;
}5.2 element()
也是获取队列第一个元素，外面调用的是getFirst()。
public E element() {return getFirst();
}5.3 poll()
移除队列第一个节点元素并返回，外面调用的其实是unlinkFirst()
public E poll() {
// 获取到第一个元素
final Node<E> f = first;
// 移除并返回
return (f == null) ? null : unlinkFirst(f);
}5.4 remove()
移除队列第一个元素, 外面调用的是removeFirst():
public E remove() {return removeFirst();
}5.5 offfer(E e)
在队列前面减少元素：
public boolean offer(E e) {return add(e);
}5.6 offerFirst(E e)
往队列的后面插入元素，其实调用的是addFirst()
public boolean offerFirst(E e) {addFirst(e);
return true;
}5.7 offerLast(E e)
往队列的前面增加元素, 其实调用的是addList()
public boolean offerLast(E e) {addLast(e);
return true;
}5.8 peekFirst()
获取第一个节点外面的元素:
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}5.9 peekLast()
获取最初一个节点的元素：
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}5.10 pollFirst()
获取第一个元素，并且移除它, 应用的是unlinkFirst(E e)
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}5.11 pollLast（）
获取队列最初一个元素，并且移除它, 调用的其实是unlinkLast(E e)
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}5.12 push(E e)
像是堆栈的特点，在后面增加元素：
public void push(E e) {addFirst(e);
}5.13 pop()
堆栈的特点，取出队列首的第一个元素
public E pop() {return removeFirst();
}5.14 removeFirstOccurrence(Object o)
移除元素, 从前往后第一次呈现的中央移除掉：
public boolean removeFirstOccurrence(Object o) {return remove(o);
}5.15 removeLastOccurrence（Object o）
移除元素，最初一次呈现的中央移除掉, 和后面剖析的一样，分为两种状况，null 和非 null。
public boolean removeLastOccurrence(Object o) {
// 元素为 null
if (o == null) {for (Node<E> x = last; x != null; x = x.prev) {if (x.item == null) {unlink(x);
return true;
}
}
} else {
// 元素不是 null
for (Node<E> x = last; x != null; x = x.prev) {if (o.equals(x.item)) {unlink(x);
return true;
}
}
}
return false;
}6. 其余办法
是否蕴含某个元素, 其实调用的是 indexOf() 办法，如果返回的索引不为 -1，则蕴含：
public boolean contains(Object o) {return indexOf(o) != -1;
}返回大小：
public int size() {return size;}是否为无效元素下标索引，从 0 到 size-1
private boolean isElementIndex(int index) {return index >= 0 && index < size;}是否为无效地位索引，从 0 到 size
private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}获取指定索引地位的ListIterator:
public ListIterator<E> listIterator(int index) {
// 查看合法性
checkPositionIndex(index);
return new ListItr(index);
}获取倒序的迭代器:
public Iterator<E> descendingIterator() {return new DescendingIterator();
}拷贝克隆函数, 一个是父类的克隆函数，另一个是重写的克隆函数，这里比拟非凡，因为 LinkedList 是链表，自身只保留了第一个和最初一个的援用，所以拷贝的时候须要向外面增加元素的形式进行拷贝。
public Object clone() {LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// 增加元素到拷贝的队列中
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
private LinkedList<E> superClone() {
try {return (LinkedList<E>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError(e);
}
}转换成为数组，通过循环实现
public Object[] toArray() {Object[] result = new Object[size];
int i = 0;
// 循环实现
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}转换成为指定类型的数组, 和后面不同的是，这里初始化的时候应用类型反射创立(T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size)
public <T> T[] toArray(T[] a) {if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}获取可宰割迭代器：
public Spliterator<E> spliterator() {return new LLSpliterator<E>(this, -1, 0);
}7. 迭代器
外面定义了三种迭代器，都是以内部类的形式实现，别离是：
- ListItr：列表的经典迭代器
- DescendingIterator：倒序迭代器
- LLSpliterator：可宰割迭代器
7.1 ListItr
先来说说 ListItr，这个迭代器次要是有next(),hashNext(),hasPrevious(),previous(),nextIndex(),previousIndex(),remove(),set(),add(),forEachRemaining() 办法：
next()：获取下一个元素hashNext(): 是否有下一个元素hasPrevious()：是否有上一个元素previous()：上一个元素nextIndex()：下一个索引地位previousIndex()：上一个索引地位remove()：删除以后索引地位的元素set()：更新元素add()：新增元素forEachRemaining()：遍历剩下的元素
外面次要有汇合重要的属性：
lastReturned: 上一次返回的元素next：下一个返回的元素nextIndex：下一个索引expectedModCount：期待批改的次数
private class ListItr implements ListIterator<E> {
// 上一个返回的元素
private Node<E> lastReturned;
// 下一个元素
private Node<E> next;
// 下一个索引
private int nextIndex;
// 期待的批改次数
private int expectedModCount = modCount;
// 初始化
ListItr(int index) {
// 依据索引地位更新下一个返回的节点
next = (index == size) ? null : node(index);
// 更新索引
nextIndex = index;
}
// 是否有下一个元素：索引是否小于 size
public boolean hasNext() {return nextIndex < size;}
// 获取下一个元素
public E next() {
// 查看批改合法化
checkForComodification();
// 如果没有下一个元素会抛异样，所以应用前须要先判断
if (!hasNext())
throw new NoSuchElementException();
// 上一次返回的元素更新
lastReturned = next;
// 更新下一次返回的元素
next = next.next;
// 更新索引
nextIndex++;
// 返回 item
return lastReturned.item;
}
// 是否有上一个：下一个返回的元素索引是不是大于 0
public boolean hasPrevious() {return nextIndex > 0;}
// 返回上一个元素
public E previous() {
// 查看
checkForComodification();
// 判断是否有上一个元素
if (!hasPrevious())
throw new NoSuchElementException();
// 上一个返回的元素，须要更新
lastReturned = next = (next == null) ? last : next.prev;
// 更新索引
nextIndex--;
return lastReturned.item;
}
// 下一个索引
public int nextIndex() {return nextIndex;}
// 上一个索引
public int previousIndex() {return nextIndex - 1;}
// 移除以后地位的索引
public void remove() {
// 查看批改合法性
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
// 获取下一个元素
Node<E> lastNext = lastReturned.next;
// 移除上一个返回的元素
unlink(lastReturned);
// 如果下一个是上次返回的元素，那么下一个元素须要更新，因为该元素曾经被移除了
if (next == lastReturned)
next = lastNext;
else
// 更新索引
nextIndex--;
lastReturned = null;
expectedModCount++;
}
// 更新
public void set(E e) {if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {checkForComodification();
lastReturned = null;
// 如果下一个元素是空，那就是在队尾增加元素
if (next == null)
linkLast(e);
else
// 否则就是在 next 索引处增加元素
linkBefore(e, next);
// 更新索引
nextIndex++;
expectedModCount++;
}
// 遍历剩下的元素
public void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);
// 应用循环，索引一直后移，遍历
while (modCount == expectedModCount && nextIndex < size) {
// 对每个节点元素执行操作
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();}
final void checkForComodification() {if (modCount != expectedModCount)
throw new ConcurrentModificationException();}
}下面的迭代器没有什么好说的，就是往前面和前面遍历的性能，以及增删改的性能。
7.2 DescendingIterator
这个迭代器有点意思，也很简略，就是一个倒序的性能，性能实现也非常简略：
- hasNext: 是否有下一个元素，实际上是判断上一个元素
- next：获取下一个元素，实际上是获取后面一个元素
- remove：移除元素
倒序就是他人从前往后，它偏偏从后往前遍历，emmmmmmm
private class DescendingIterator implements Iterator<E> {private final ListItr itr = new ListItr(size());
public boolean hasNext() {return itr.hasPrevious();
}
public E next() {return itr.previous();
}
public void remove() {itr.remove();
}
}7.3 LLSpliterator
这个迭代器有点货色，感觉和其它的不太一样，LLSpliterator是在应用 node 的 next 进行迭代，上面剖析一下：次要是为了将元素分为多份，而后再用多线程来解决。
值得注意的是：宰割的时候，LinkedList不是 1 / 2 宰割，而是每一次宰割进去的大小都是递增的，递增的大小是BATCH_UNIT, 然而返回的不是LLSpliterator，而是ArraySpliterator，每次都宰割出更多的元素，转成数组构造，这兴许是出自于性能思考，比拟指针遍历太慢了，我猜的的 … 别打我
static final class LLSpliterator<E> implements Spliterator<E> {
// 宰割长度减少单位
static final int BATCH_UNIT = 1 << 10; // batch array size increment
// 最大宰割长度
static final int MAX_BATCH = 1 << 25; // max batch array size;
final LinkedList<E> list; // null OK unless traversed
// 以后节点
Node<E> current; // current node; null until initialized
// 大小估算
int est;
// 期待批改的次数
int expectedModCount; // initialized when est set
// 宰割长度
int batch; // batch size for splits
LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
this.list = list;
this.est = est;
this.expectedModCount = expectedModCount;
}
final int getEst() {
int s; // force initialization
final LinkedList<E> lst;
if ((s = est) < 0) {if ((lst = list) == null)
s = est = 0;
else {
expectedModCount = lst.modCount;
current = lst.first;
s = est = lst.size;
}
}
return s;
}
// 估算大小
public long estimateSize() { return (long) getEst();}
// 宰割
public Spliterator<E> trySplit() {
Node<E> p;
// 获取大小
int s = getEst();
// 以后节点不为空
if (s > 1 && (p = current) != null) {
// 宰割地位完结：宰割地位 + 宰割单位
int n = batch + BATCH_UNIT;
// 如果大于大小，就限度最初的地位
if (n > s)
n = s;
// 最大的宰割地位
if (n > MAX_BATCH)
n = MAX_BATCH;
// 数组
Object[] a = new Object[n];
int j = 0;
// 将以后地位到 n 的地位循环，寄存到 a 数组中
do {a[j++] = p.item; } while ((p = p.next) != null && j < n);
current = p;
batch = j;
est = s - j;
// ArraySpliterator 每次宰割成一半一半，而 IteratorSpliterator 算术递增
return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
}
return null;
}
// 对剩下的元素进行解决
public void forEachRemaining(Consumer<? super E> action) {
Node<E> p; int n;
if (action == null) throw new NullPointerException();
if ((n = getEst()) > 0 && (p = current) != null) {
current = null;
est = 0;
do {
E e = p.item;
p = p.next;
action.accept(e);
} while (p != null && --n > 0);
}
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();}
// 对前面一个元素进行解决
public boolean tryAdvance(Consumer<? super E> action) {
Node<E> p;
if (action == null) throw new NullPointerException();
if (getEst() > 0 && (p = current) != null) {
--est;
E e = p.item;
current = p.next;
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
public int characteristics() {return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;}
}8. 序列化和反序列化
序列化和反序列化的时候，须要重写，因为咱们保留的只有第一个和最初一个节点的援用，咱们序列化须要保留大小和援用，所以须要重写，要不反序列化回来就找不到next，节点之间的关系就会失落。
序列化的时候如下，写入了 size，以及遍历的时候将节点的item 值写入。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}反序列化的时候，读入大小 size 以及每个节点外面的元素item
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// 默认序列化
s.defaultReadObject();
// 大小
int size = s.readInt();
// 依照程序读入元素
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}9. 总结一下
LinkedList底层是用链表实现的，而且是双向链表，并且实现了Queue接口，能够当成双向队列或者堆栈来应用。也正是因为是链表实现，所以删除元素比拟快，然而查找的时候绝对较慢。当然，也没有什么扩容，除非就是内存不够了。- 双向链表，能够从头往尾遍历，也能够从尾部往前遍历。
LinkedList继承了AbstractSequentialList，AbstractSequentialList实现了get,set,add,remove等办法。- 序列化 / 反序列化的时候重写了办法，能力达到序列化外面每一个节点元素的成果。
- 线程不平安
【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。这个世界心愿所有都很快，更快，然而我心愿本人能走好每一步，写好每一篇文章，期待和你们一起交换。
此文章仅代表本人（本菜鸟）学习积攒记录，或者学习笔记，如有侵权，请分割作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有谬误之处，还望指出，感激不尽~