Java 集合框架_LinkedList(源码解析)
2017-12-21 本文已影响89人
wo883721
上一章进行了ArrayList源码分析，这一章分析一下另一个重要的List集合LinkedList。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
LinkedList与ArrayList对比发现：
- 它们继承的基类不同，LinkedList继承自AbstractSequentialList基类，AbstractSequentialList是AbstractList子类，这个类后面再说。
- LinkedList实现了Deque接口，代表它是一个队列，准确地说它是一个双端队列。
- LinkedList没有实现RandomAccess可随机访问标记接口，表示使用LinkedList的get(int index)获取集合中元素的方法效率非常低。
一. Queue队列接口
队列是一种FIFO(先入先出)的数据结构，和它相对应的是一种叫做栈(LIFO后入先出)的数据结构。
1.1 栈
对于栈来说，我们想一想它应该有哪些方法?
- void push(E e); 向栈顶添加元素。
- E pop(); 移除栈顶元素，并返回它。
- E peek(); 查看栈顶元素。
- boolean isEmpty(); 栈是不是为空。
- int size(); 栈中元素的数量。
要实现一个栈，实现这5个方法就可以了。
1.2 队列
队列与栈的方法应该差不多，只不过每次添加的时候，都是向队列尾新添元素，而不是队列头。
- boolean offer(E e); 向队列尾添加元素。
- E poll();移除队列头元素，并返回它。
- E peek(); 查看队列头元素。
- boolean isEmpty(); 队列是不是为空。
- int size(); 队列中元素的数量。
public interface Queue<E> extends Collection<E> {
// 向队列末尾新添加元素,返回true表示添加成功
// 不会返回false，因为添加失败直接抛出IllegalStateException异常。
// 一般调用offer方法实现。
boolean add(E e);
// 向队列末尾新添加元素，返回true表示添加成功，返回false，添加失败
boolean offer(E e);
// 这个与Collection中的remove方法不一样，因为Collection中的remove方法都要提供一个元素或者集合，用于删除。
// 这里不穿任何参数，就是代表删除队列第一个元素(即队列头)，并返回它
// 还需要注意的时，如果队列是空的，即队列头是null，这个方法会抛出NoSuchElementException异常。
E remove();
// 这个方法也是删除队列第一个元素(即队列头)，并返回它
// 但是它和remove()方法不同的时，如果队列是空的，即队列头是null，它不会抛出异常，而是会返回null。
E poll();
// 查看队列头的元素，如果队列是空的，就抛出异常
E element();
// 查看队列头的元素。如果队列是空的，不会抛出异常，而是返回null
E peek();
}
可以看出继承自Collection接口，那么size()和isEmpty()方法都由Collection接口提供，但是Queue接口还提供了是三个好像重复的方法。
- 向队列尾添加元素的方法：add(E e)与offer(E e)。区别就是队列是满的，添加失败时，add方法会抛出异常，而offer方法只会返回false。
- 移除队列头元素的方法：remove()与poll()。区别就是队列为空的时候,remove方法会抛出异常，poll方法只会返回null。
- 查看队列头元素的方法：element()与peek()。区别就是队列为空的时候，element方法会抛出异常，peek方法只会返回null。
下面是AbstractQueue中的实现
public abstract class AbstractQueue<E>
extends AbstractCollection<E>
implements Queue<E> {
protected AbstractQueue() {
}
// 直接调用offer方法来实现，如果队列是满的，添加失败，
// 则抛出IllegalStateException异常
public boolean add(E e) {
if (offer(e))
return true;
else
throw new IllegalStateException("Queue full");
}
// 直接调用poll方法来实现，如果队列是空的，移除元素失败，
// 则抛出NoSuchElementException异常
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
// 直接调用peek方法来实现，如果队列是空的,查看元素失败，
// 则抛出NoSuchElementException异常
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
......
}
二. 双端队列
它与普通队列相比较，它既可以在队列头添加元素，也可以在队列尾添加元素；既可以在队列头删除元素，也可以在队列尾删除元素。
注意一下，因为双端队列特性，所以它很容易实现一个栈，也就是说它本身可以当做栈使用。
根据双端队列的特性，它比普通队列应该多了三个方法。
- boolean offerFirst(E e); 向队列头添加元素。
- boolean offerLast(E e); 向队列尾添加元素。
- E pollFirst();移除队列头元素，并返回它。
- E pollLast();移除队列尾元素，并返回它。
- E peekFirst(); 查看队列头元素。
- E peekLast(); 查看队列尾元素。
- boolean isEmpty(); 队列是不是为空。
- int size(); 队列中元素的数量。
public interface Deque<E> extends Queue<E> {
// 向队列头添加元素
void addFirst(E e);
// 向队列末尾新添加元素
void addLast(E e);
// 向队列头添加元素,和addFirst(E e)作用一样，就是直接调用addFirst(E e)方法来实现。
boolean offerFirst(E e);
// 向队列末尾新添加元素，和addLast(E e)作用一样，就是直接调用addLast(E e)方法来实现。
boolean offerLast(E e);
// 删除队列第一个元素(即队列头)，并返回它, 如果队列是空的,这个方法会抛出NoSuchElementException异常。
// 注，与Queue接口中remove()作用一样，remove()方法就是调用removeFirst()方法来实现的
E removeFirst();
// 删除队列最后一个元素(即队列尾)，并返回它, 如果队列是空的,这个方法会抛出NoSuchElementException异常。
E removeLast();
// 删除队列第一个元素(即队列头)，并返回它, 如果队列是空的,它不会抛出异常，而是会返回null。
// 注，与Queue接口中poll()作用一样，
E pollFirst();
// 删除队列最后一个元素(即队列尾)，并返回它, 如果队列是空的,它不会抛出异常，而是会返回null。
E pollLast();
// 查看队列头的元素，如果队列是空的，就抛出异常
// 注，与Queue接口中element()作用一样，
E getFirst();
// 查看队列尾的元素，如果队列是空的，就抛出异常
E getLast();
// 查看队列头的元素。如果队列是空的，不会抛出异常，而是返回null
E peekFirst();
// 查看队列尾的元素。如果队列是空的，不会抛出异常，而是返回null
E peekLast();
// 从队列头都开始遍历，找到与o相等的第一个元素删除它，并返回true，如果没找到就返回false，最多只删除一个元素
// 注，与Collection中remove(Object o)方法作用一样
boolean removeFirstOccurrence(Object o);
// 从队列尾都开始遍历，找到与o相等的第一个元素删除它，并返回true，如果没找到就返回false，最多只删除一个元素
boolean removeLastOccurrence(Object o);
// *** Queue methods ***
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// *** Stack methods ***
// 向栈顶添加元素。与addFirst(E e)方法作用一样
void push(E e);
// 移除栈顶元素，并返回它。如果栈为空的话，会抛出NoSuchElementException异常
// 注，与removeFirst()方法一样
E pop();
// *** Collection methods ***
boolean remove(Object o);
boolean contains(Object o);
public int size();
Iterator<E> iterator();
Iterator<E> descendingIterator();
}
可以看出定义的接口中的方法比我们预计的多得多，主要是添加了一些队列为空时，获取元素会抛出异常的方法，还顺便定义了栈的方法，因为双端队列很容易实现一个栈的功能。
双端队列Deque与普通队列Queue相比较，就是多了从队列头插入，从队列尾删除，从队列尾查看的功能。
三. AbstractSequentialList抽样类
AbstractSequentialList这个类表示它的子类是使用链表这种数据结构来存储集合元素的，而不是使用数组这种数据结构。这有什么不同呢？
- 数组的插入和删除的效率都不高，因为可能涉及到数组元素的移动。但是访问效率非常高，它支持随机访问，就是通过数组的下标直接获取对应的元素。
- 链表的插入和删除的效率都很高，因为只需要改变元素之间指向就可以了。但是访问效率不高，它不支持随机访问，必须从链表头或者链表尾开始一次访问。
还记得我们在AbstractList方法中，怎么实现迭代器的么？
使用一个cursor属性来记录索引位置，然后通过调用List集合的get(int index)来获取对应的元素。这里就不行了，因为通过get(int index)方法获取集合元素的效率非常低。
而遍历链表的方式就是获取链表中一个元素，然后通过指向下一个元素的引用，不断获取下一个元素，直到为空，表示已经到了链表尾，而不是通过索引的方式。
所以我们思考一下AbstractSequentialList会做哪些事情。
- 将获取迭代器的方法设置成abstract抽样方法，强制子类提供迭代器方法，因为不能用索引这种低效率的方式获取元素，所以强制子类去实现。
// 调用listIterator方法，返回一个迭代器
public Iterator<E> iterator() {
return listIterator();
}
// 子类必须复写这个方法，提供一个ListIterator迭代器。
public abstract ListIterator<E> listIterator(int index);
- List集合可以通过索引得到集合中的元素，AbstractSequentialList集合也必须支持这种方式，虽然效率低。这时就可以通过ListIterator迭代器实现对应方法。
这里就与AbstractList中内部迭代器ListIterator类不同，AbstractList中迭代器是通过调用AbstractList中get(int index)和set(int index, E element)方法来实现对应功能的，所以AbstractList子类必须复写这些方法。
而AbstractSequentialList是通过迭代器来实现本AbstractSequentialList对应方法，所以子类必须实现一个自定义迭代器。
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
protected AbstractSequentialList() {
}
// 调用迭代器listIterator获取
public E get(int index) {
try {
// 迭代器会先根据index值，从链表头开始遍历，直到移动到index位置，将元素返回，所以效率不高。
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// 调用迭代器listIterator的set设置
public E set(int index, E element) {
try {
ListIterator<E> e = listIterator(index);
E oldVal = e.next();
e.set(element);
return oldVal;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// 调用迭代器listIterator的add方法添加元素
public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// 调用迭代器listIterator的remove方法移除元素
public E remove(int index) {
try {
ListIterator<E> e = listIterator(index);
E outCast = e.next();
e.remove();
return outCast;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// Bulk Operations
public boolean addAll(int index, Collection<? extends E> c) {
try {
boolean modified = false;
ListIterator<E> e1 = listIterator(index);
Iterator<? extends E> e2 = c.iterator();
while (e2.hasNext()) {
e1.add(e2.next());
modified = true;
}
return modified;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// 会调用listIterator方法，返回一个迭代器
public Iterator<E> iterator() {
return listIterator();
}
// 子类必须复写这个方法，提供一个ListIterator迭代器。
public abstract ListIterator<E> listIterator(int index);
}
四. 单向链表和双向链表
4.1 单向链表
简单的说，元素除了包含本身的数据item,还有一个指向下一个元素的引用next。数据结构就像这样：
class Node<E> {
E item;
Node<E> next;
Node( E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
然后我们在看看单向链表插入和删除。
- 插入：单向链表的插入，我们只需要改变两个引用就可以了。
private void insert(Node<E> prevNode, Node<E> node, Node<E> newNode) {
// prevNode表示插入点前一个元素
// node表示插入点元素
// newNode表示要添加的元素，将它放入插入点(即前一个元素的next指向)
// 并将newNode的next指向原来元素node
if (prevNode != null) prevNode.next = newNode;
newNode.next = node;
}
在链表node元素前添加一个元素，就是将node元素前一个元素的next指向新元素newNode，再将新元素newNode的next指向node元素，这样就把新元素newNode插入到链表中了。
注意要做一下前元素非空判断，如果前元素为空表示插入点是链表头。
根据我的经验，先不考虑null的情况，改变对应引用，这里就是prevNode.next = newNode，newNode.next = node。然后我们再看看那些需要考虑null的情况。
比如这里prevNode就需要考虑null情况，否则会发生空指针异常。prevNode为空其实表示在链表头。newNode是不允许为空。而node是不是为空对我们程序没有任何影响。
- 删除：单向链表的删除，也只需要改变两个引用就可以了。
private void delete(Node<E> prevNode, Node<E> node) {
// prevNode表示被删除元素的前一个元素
// node表示被删除的元素
if (prevNode != null) prevNode.next = node.next;
node.next = null;
}
删除一个单向链表元素，就是将它的前一个元素的next指向它的next，这样就在整个链表中查找不到这个元素了，然后将它的next设置为null。
当前一个元素为null，表示被删除元素是链表头，那么需要将表头的next指向被删除元素的next，这里没有体现。
4.2 双向链表
与单向链表相比，它的元素多了一个指向上一个元素的引用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;
}
}
然后我们在看看双向链表插入和删除。
- 插入：双向链表的插入，我们需要改变四个引用。
private void insert(Node<E> node, Node<E> newNode) {
// node表示插入点元素
// newNode表示要添加的元素，将它插入到node元素之前
// 将node前一个元素的next指向新元素newNode
if(node.prev != null) node.prev.next = newNode;
// 将新元素newNode的prev指向node前一个元素
newNode.prev = node.prev;
// 将node的prev指向新元素newNode，现在node的前一个元素变成新元素newNode
node.prev = newNode;
// 将新元素的next指向node，所以新元素的下一个元素是node
newNode.next = node;
}
要在元素node前插入一个新元素newNode。那么就需要四步：
- 将node前一个元素的next指向新元素newNode
- 将新元素newNode的prev指向node前一个元素
- node元素的prev指向新元素
- 新元素newNode的next指向node
- 删除：双向链表的删除，也需要改变四个引用。
private void delete(Node<E> node) {
// node表示要删除的元素
// 将node前一个元素的next指向node下一个元素
if (node.prev != null) node.prev.next = node.next;
// 将node下一个元素的pre指向node前一个元素
if (node.next != null) node.next.prev = node.prev;
// 将node的prev和next都置位null
node.prev = null;
node.next = null;
}
注意只考虑本节点元素情况，没有考虑链表头的赋值。
五. LinkedList 类
5.1 成员属性
// 集合数量
transient int size = 0;
// 双向链表的表头
transient Node<E> first;
// 双向链表的表尾
transient Node<E> last;
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;
}
}
通过一个双向链表来记录集合中的元素。
5.2 构造函数
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
LinkedList的构造函数比较简单，因为它不用想ArrayList那样，要确定初始数组的长度。
5.3 添加元素
public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
向链表尾添加一个新元素newNode,要进行以下几个步骤：
- 将链表尾last赋值给变量l，因为表尾last要指向新元素newNode
- 创建新元素newNode，根据Node的构造函数，我们知道新元素newNode的prev指向l(即表尾),next还是为null。
- 将表尾last指向新元素newNode
- 将原表尾l的next指向新元素，这时要考虑一种情况，原表尾l为null，即整个链表是空的，那么这个时候，我们只需要将表头first也指向新元素newNode就可以了。
- 集合数量size加1，以及modCount自增表示集合已经修改了。
注意，这里好像只改变了三个应用，缺少了新元素newNode下一个元素的prev指向新元素newNode。这是因为在表尾，不存在下一个元素。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
在链表指定索引位置插入元素，如果index等于size，表示在表尾插入元素，直接调用linkLast(element)方法，否则先调用node(index)方法，找到index索引对应元素node，并将要添加元素element插入到元素node之前。
Node<E> node(int index) {
// 如果index小于集合数量的一半，那么从表头开始遍历，一直到index位置。
// 否则从表尾开始遍历，一直到index位置。这样我们每次最多遍历size/2的次数。
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在集合的前一半还是后一半，决定从链表头还是链表尾遍历。
void linkBefore(E e, Node<E> succ) {
// e表示新添加的元素
// succ表示被插入的元素(即新元素插入到这个元素之前)
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
在succ元素之前插入新元素e，要进行以下几个步骤：
- 将元素succ的前一个元素赋值给变量pred
- 创建新元素newNode。 新元素newNode的prev指向pred，next指向succ。
- 将元素succ的prev指向新元素newNode。
- 将元素pred的next指向新元素newNode。但是考虑一种情况，pred为null，即元素succ就是链表头，那么新添加元素就变成新表头了，first = newNode。
- 集合数量size加1，以及modCount自增表示集合已经修改了。
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;
if (numNew == 0)
return false;
// pred表示index位置前一个元素，succ表示index位置元素
Node<E> pred, succ;
if (index == size) {
// 当index == size时，index位置的元素为null，它的前一个元素是表尾last元素
succ = null;
pred = last;
} else {
// 通过ode(index)方法，查找index位置元素
succ = node(index);
pred = succ.prev;
}
// 遍历要插入集合c的元素，将它们插入到本集合中
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// 将新元素的prev指向前一个元素pred
Node<E> newNode = new Node<>(pred, e, null);
// pred为空表示，插入点在表头，所以将新元素设置为表头
if (pred == null)
first = newNode;
else
// 将前一个元素pred的next指向新元素newNode
pred.next = newNode;
// pred指向新元素，然后继续遍历
pred = newNode;
}
// pred现在表示插入集合元素最后一个元素
// succ为空表示在表尾插入集合，那么插入集合中最后一个元素就成为新的表尾
if (succ == null) {
last = pred;
} else {
// 将插入集合中最后一个元素和插入点index位置元素进行联系。
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
在集合index位置前插入一个集合c中所有元素。可以这么做：
- 先找到index位置元素succ，和它前一个元素pred。
- 遍历集合c中元素，将它们插入到元素pred之后，即新元素newNode.prev = pred, pred.next = newNode。然后将 pred = newNode; 再依次遍历集合c。
- 遍历完成之后，pred就指向集合c最后一个添加的元素。这时就要让它和index位置元素发生联系。
当然这个过程中还要考虑表头和表尾的改变。
5.4 删除元素
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
遍历整个集合，找到与o相同元素，调用unlink方法删除这个元素，如果没有找打，就返回false。
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;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
这个方法和我们前面写的双向链表删除方法一样。主要就是
- 被删除元素x的前一个元素的next指向被删除元素后一个元素。
- 被删除元素x后一个元素的prev指向被删除元素x前一个元素。
- 最后将删除元素x的prev与next都设置为null。
- 当然要注意下表头和表尾的判断，如果被删除元素x的prev为null，表示x是表头，那么就要将表头first指向元素x的下一个元素。如果被删除元素x的next为null，表示x是表尾，那么就要将表尾last指向元素x前一个元素。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
通过node(index)方法，获取index索引对应元素，然后调用unlink(Node<E> x) 方法删除这个索引。
public void clear() {
// 遍历链表，将链表中的引用都置位null，方便垃圾回收器释放内存
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;
size = 0;
modCount++;
}
将链表中元素的引用都置位null，方便垃圾回收器回收。
注 boolean removeAll(Collection<?> c)与boolean retainAll(Collection<?> c)都是使用AbstractCollection抽样类的默认实现。也就是通过迭代器Iterator来删除集合中元素。
5.5 替换元素
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
替换元素非常简单，通过node(index)查找出元素，将元素中数据赋值给oldVal，再将新数据element设置到元素中，最后返回老数据oldVal。
5.5 查找元素
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;
}
从表头开始遍历，查找第一个与o值相等元素，返回对应索引，如果没找到就返回-1 。
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
从表尾开始遍历，查找第一个与o值相等元素，返回对应索引，如果没找到就返回-1 。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
通过node(index)方法找到对应索引的元素，然后返回元素的值。
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
返回LinkedList内部的一个迭代器。这个类我们之后会详细介绍。
5.6 其他重要方法
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;
}
将集合转成一个Object[]数组，先创建一个长度为集合数量size的Object[]数组，然后遍历链表，将元素中数据item存放到数组中。
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;
}
将集合转成T类型的数组。如果数组a的长度小于集合数量size，那么就要创建一个新数组，再赋值给a，然后遍历链表，将元素中数据item存放到数组a中。
这里有个很诡异的地方，就是if (a.length > size)这个判断。我们知道数组a中 0 -- size-1 位置的元素都是集合中的，那么从size位置开始之后的元素都是数组a原有的元素，这里不知道为什么单单将size位置元素置位null。
六. LinkedList内部类ListItr
6.1 成员属性
// 代表当前遍历到的元素
private Node<E> lastReturned;
// 表示迭代器开始的元素
private Node<E> next;
// 表示元素next在链表中的位置，与next是相对应的。
private int nextIndex;
private int expectedModCount = modCount;
6.2 构造函数
ListItr(int index) {
// 先通过LinkedList的node方法，查找index索引位置对于的元素，赋值给next
next = (index == size) ? null : node(index);
// 将index赋值给 nextIndex
nextIndex = index;
}
6.3 正向遍历集合
public boolean hasNext() {
return nextIndex < size;
}
当nextIndex小于集合数量size，说明集合还有元素没有遍历到。
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
将next赋值给lastReturned，再将next指向它的下一个元素，然后将nextIndex自增，最后返回当前元素lastReturned的数据item。
6.4 反向遍历
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;
}
这里做了一个处理，还记得在ListItr构造函数中，如果index == size，那么next就赋值为null，所以这里当next == null就从表尾开始向前遍历。
6.5 返回索引
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
这个已经在AbstractList中的详细介绍过了。
6.6 操作集合的方法
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
// 将当前元素下一个元素赋值给lastNext
Node<E> lastNext = lastReturned.next;
// 调用LinkedList集合的unlink方法，删除当前元素
unlink(lastReturned);
// 如果next == lastReturned，表示反向遍历。
// 将next指向lastNext，因为lastNext的前一个就是原lastReturned前一个元素，所以不会有遗漏
if (next == lastReturned)
next = lastNext;
else
// 表示正向遍历，那么删除当前元素，只有一个影响，就是集合数量减少了。
// 而正向遍历结束条件时nextIndex < size，所以要将nextIndex自减。
// 而反向遍历是结束条件是nextIndex > 0，所以不需要处理
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
// 超级简单，就是将当前元素的数据item设置成e
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
// 如果next == null，就在链表尾插入元素e
if (next == null)
linkLast(e);
else
// 不然就在next元素之前插入元素e
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
总结
LinkedList不仅是一个List集合，它还是一个队列，或者说是双端队列。
栈
栈是一个后入先出(LIFO)的数据结构，主要是三个方法：
- void push(E e); 向栈顶添加元素。
- E pop(); 移除栈顶元素，并返回它。
- E peek(); 查看栈顶元素。
队列
队列是一个先入先出(FIFO)的数据结构，主要是三个方法：
- boolean offer(E e); 向队列尾添加元素。
- E poll();移除队列头元素，并返回它。
- E peek(); 查看队列头元素。
双端队列
双端队列与普通队列做比较，它既可以在队列头添加元素，也可以在队列尾添加元素；既可以在队列头删除元素，也可以在队列尾删除元素。
它的主要方法有六个：
- boolean offerFirst(E e); 向队列头添加元素。
- boolean offerLast(E e); 向队列尾添加元素。
- E pollFirst();移除队列头元素，并返回它。
- E pollLast();移除队列尾元素，并返回它。
- E peekFirst(); 查看队列头元素。
- E peekLast(); 查看队列尾元素。
AbstractSequentialList抽样类
AbstractSequentialList这个类表示它的子类是使用链表这种数据结构来存储集合元素的，而不是使用数组这种数据结构。也就是说它没有可随机访问能力。
单向链表和双向链表
注意一下单向链表和双向链表的插入和删除。
单向链表的插入和删除最多改变两个引用，而双向链表的插入和删除最多改变四个引用。
LinkedList 类
使用first表示双向链表的表头，使用last表示双向链表的表尾。
