引言
前面我们学习了单链表表和双链表，本篇我们来分析LinkedList源码，重点关注它的迭代器实现。
源码分析
1.节点类:是双向节点，说明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;
}
}
成员变量
LinkedList实现了List和Deque接口，因此可以把它当做双端队列使用.它的成员变量只有三个:
1>first:带数据头节点;
2>last:带数据尾部节点;
3>size:当前大小
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//当前大小
transient int size = 0;
//头节点
transient Node<E> first;
//尾节点
transient Node<E> last;
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
.......
}
构造方法
看addAll(c)的实现,所有E的子类泛型集合都可以加入到列表中:
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);//index合法性校验
Object[] a = c.toArray();//集合转数组
int numNew = a.length;//数组大小
if (numNew == 0)
return false;
Node<E> pred, succ;//succ为插入位置的节点，pred是它的前驱
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;
Node<E> newNode = new Node<>(pred, e, null);//构造新节点,链接前驱
if (pred == null)//前驱为空，说明为空链表
first = newNode;
else //否则前驱节点链接新节点
pred.next = newNode;
pred = newNode;//前驱节点后移
}
if (succ == null) {//从尾部插入
last = pred;//更新尾部指针
} else {//从中间插入,则链接succ和pred节点
pred.next = succ;
succ.prev = pred;
}
size += numNew;//更新大小
modCount++;//这个变量记录list的修改次数，用于迭代器合法操作的检测条件，后面会讲到。
return true;
}
添加元素
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++;//size++
modCount++;//修改次数++
}
public void add(int index, E element) {
checkPositionIndex(index);//index合法性校验
if (index == size)//尾部添加
linkLast(element);
else
linkBefore(element, node(index));//index前加入
}
void linkBefore(E e, Node<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++;
}
获得元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
if (index < (size >> 1)) {//index小于size的一半,则从头结点开始遍历
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//index大于size的一半,则从尾结点开始遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
说明:LinkedList的查找引入size,因此可以判断从哪一端可以更快查到元素。
删除元素
public E remove() {//最终调用的是删除头节点
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;//更新头结点到后继节点
if (next == null)//删除后为空表，尾部节点也置空
last = null;
else
next.prev = null;//断开与旧的头结点的链接
size--;//大小减一
modCount++;//修改次数加1
return element;
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
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
prev.next = null;//断开与旧的尾部节点的链接
size--;
modCount++;
return element;
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {//删除指定索引位置的节点
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {//删除头节点
first = next;
} else {
//断开x与链表的链接
prev.next = next;
x.prev = null;
}
if (next == null) {//删除尾部节点
last = prev;
} else {
//断开x与链表的链接
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
设置元素
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);//找到要修改的节点
E oldVal = x.item;//更新value
x.item = element;
return oldVal;
}
栈方法
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
迭代器
作用:它为容器对象对外提供了另外一种遍历方式，这种方式和for循环不同，它提供了一套标准，我们不需要了解各个集合的内部结构就可以访问集合的元素，实现了访问逻辑和和内部结构的解耦。List、Set、Map等集合都提供了各自的迭代器访问元素。
1.下面先看看迭代器的接口定义:
public interface Iterator<E> {
/**
* 判断是否还有下一个元素
*/
boolean hasNext();
/**
* 返回元素的值
*/
E next();
/**
* 移除元素
*/
default void remove() {
throw new UnsupportedOperationException("remove");
}
/**
* 这是Java8为Iterator新增的默认方法，该方法可使用lambda表达式来遍历集合元素。
* 本篇我们先不分析该方法
* @since 1.8
*/
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
2.LinkedList迭代器的实现:
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned = null;//记录当前遍历的节点，在next()中赋值,它其实就是迭代器当前的访问节点
private Node<E> next;//将要访问的下一个元素的
private int nextIndex;//表示将要访问的下一个元素的下标，也就是游标
private int expectedModCount = modCount;//构造迭代器时，expectedModCount表示当前链表被修改的次数。在遍历过程中，其他线程做修改操作时，modCount发生改变，二者不相等会抛出异常
ListItr(int index) {//index表示开始遍历的位置
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {//是否遍历完整个链表
return nextIndex < size;
}
public E next() {
checkForComodification();//安全校验
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;//next指针前移
nextIndex++;//游标前移
return lastReturned.item;
}
public boolean hasPrevious() {//和hasNext对应
return nextIndex > 0;
}
public E previous() {//和next()对应
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)//当前列表已经为null，无法继续删除，抛出异常
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);//删除lastReturned节点,size减一
if (next == lastReturned)
next = lastNext;
else
nextIndex--;//size-1,游标复原
lastReturned = null;
expectedModCount++;//修改次数+1
}
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
linkBefore(e, next);//next前插入,size++
nextIndex++;//增加元素，游标前移
expectedModCount++;
}
@Override
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();
}
//安全校验，当有其他线程尝试修改链表时,抛出ConcurrentModificationException异常.
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
ListIterator是Iterator的子接口，它提供了向前遍历的操作，先着重研究next和hashNext方法。
1.next()方法返回当前遍历的节点,并且内部的next指针指向下一个节点;
2.hasNext()通过游标nextIndex判断将要被访问的元素是否存在;
3.remove()移除后,同时游标在当前节点被删除之后需要复原，next指针指向删除的元素的后继节点，期望的修改计数+1;
4.add()操作在next指针前插入，由于size加1，游标也要前移,期望的修改计数也+1。
5.在获取构造器的时候，期望的修改计数和list的修改计数相等，当迭代器在访问链表的时候，假如List在其他线程被修改了，大小发生改变，那么链表的修改计数和迭代器的期望的修改计数可能不同,此时抛出异常，终止迭代操作。同样的原因，在迭代器迭代过程中，增删操作只能由迭代器操作，而不能有链表本身操作。
