Jdk源码——LinkedList解析
前言
本文主要针对 JDK1.8 的 LinkedList 源码进行解析，主要看源码注释，代码说明了全部实现细节。
ArrayList 相关解析可以参考 Jdk源码——ArrayList解析
I. 继承结构
LinkedList 的继承结构如下，和 ArrayList （上一篇文章）相比，它们都实现了 Cloneable 和 Serializable 接口，都是 AbstractList 的子类，只不过 LinkedList 继承自 AbstractSequentialList，AbstractSequentialList 继承自 AbstractList。LinkedList 不支持随机访问，所以没有实现 RandomAccess 接口。
LinkedList 还额外实现了 Deque 双向队列接口，所以我们也可以把 LinkedList 当作队列使用。
Queue
Queue 接口与 List 、Set 同一级别，都是继承了 Collection 接口。
/**
* 通常队列都是FIFO，优先队列的元素顺序则是根据比较器进行排序的，栈是LIFO
* 不管是什么顺序，head元素都是使用remove或者poll方法移除
*
* Queue接口没有定义阻塞队列方法，而是定义在java.util.concurrent.BlockingQueue接口中
*
* Queue的实现类通常不允许添加null元素，尽管LinkedList不禁止插入null
* 即使允许, null也不应该被插入到Queue, 因为null是poll等方法在队列为空时的返回值，会产生歧义
*/
public interface Queue<E> extends Collection<E> {
/**
* 插入元素，成功返回true，容量不足则抛出异常
*/
boolean add(E e);
/**
* 添加一个元素并返回true，如果队列已满，则返回false
*/
boolean offer(E e);
/**
* 移除并返回队列头部的元素。如果队列为空，则会抛出一个NoSuchElementException异常
*/
E remove();
/**
* 移除并返回队列头部的元素。如果队列为空，则返回null
*/
E poll();
/**
* 返回队列头部的元素。如果队列为空，则抛出一个NoSuchElementException异常
*/
E element();
/**
* 返回队列头部的元素。如果队列为空，则返回null
*/
E peek();
}
Deque
Deque 是继承自 Queue，Queue 是一种队列，而 Deque 则是双向队列，支持从两个端点方向检索和插入元素，因此 Deque 既可以支持 FIFO 形式也可以支持 LIFO。
/**
* deque："double ended queue" 双端队列
* 和List不一样，队列不能通过索引进行访问元素
*
*/
public interface Deque<E> extends Queue<E> {
// *** 添加 ***
/**
* 向队列头部插入一个元素,没有空间时抛出IllegalStateException异常
*/
void addFirst(E e);
/**
* 向队列尾部插入一个元素,没有空间时抛出IllegalStateException异常
*/
void addLast(E e);
/**
* 向队列头部加入一个元素,失败时返回false
*/
boolean offerFirst(E e);
/**
* 向队列尾部加入一个元素,失败时返回false
*/
boolean offerLast(E e);
// *** 删除 ***
/**
* 弹出队列头部元素,队列为空时抛出NoSuchElementException异常
*/
E removeFirst();
/**
* 弹出队列尾部元素,队列为空时抛出NoSuchElementException异常
*/
E removeLast();
/**
* 弹出队列头部元素,队列为空时返回null
*/
E pollFirst();
/**
* 弹出队列尾部元素,队列为空时返回null
*/
E pollLast();
// *** 获取 ***
/**
* 获取队列头部元素,队列为空时抛出NoSuchElementException异常
*/
E getFirst();
/**
* 获取队列尾部元素,队列为空时抛出NoSuchElementException异常
*/
E getLast();
/**
* 获取队列头部元素,队列为空时返回null
*/
E peekFirst();
/**
* 获取队列尾部元素,队列为空时返回null
*/
E peekLast();
/**
* 删除第一次出现的指定元素,不存在时返回false
*/
boolean removeFirstOccurrence(Object o);
/**
* 删除最后一次出现的指定元素,不存在时返回false
*/
boolean removeLastOccurrence(Object o);
// *** 队列方法 ***
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// *** 栈方法 ***
// 向队列头部插入一个元素,失败时抛出异常
void push(E e);
// 弹出队列头部元素,队列为空时抛出异常
E pop();
// *** Collection 方法 ***
boolean remove(Object o);
boolean contains(Object o);
public int size();
Iterator<E> iterator();
/**
* 返回队列反向迭代器，元素将从尾到头进行返回
*/
Iterator<E> descendingIterator();
}
AbstractSequentialList
AbstractSequentiaList 和其他 RandomAccess 主要的区别是 AbstractSequentiaList 的主要方法都是通过迭代器实现的，而不能支持随机访问，通过下标索引方式。因为迭代器移动需要一定代价，所以对于遍历访问性能上会低一些。
/**
* 定义一个List可以继承该类，实现listIterator和size方法.
* 实现一个可修改的列表，则需要实现list iterator的hasNext, next, hasPrevious,
* previous 和index 方法
*/
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
protected AbstractSequentialList() {}
/**
* 利用迭代器访问指定位置的元素
*/
public E get(int index) {
try {
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
/**
* 利用迭代器更新指定位置的元素，返回旧值
*/
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);
}
}
/**
* 利用迭代器在指定位置添加元素
*/
public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
/**
* 利用迭代器删除元素并返回
*/
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
/**
* 利用迭代器添加集合c
*/
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);
}
}
// Iterators
/**
* 返回迭代器，AbstractList中的方法，返回的是AbstractList.ListItr实例
*/
public Iterator<E> iterator() {
return listIterator();
}
/**
* 抽象方法，返回指定位置迭代器，类型为java.util.ListIterator
*/
public abstract ListIterator<E> listIterator(int index);
}
II. LinkedList源码
LinkedList 和 ArrayList 的功能基本相像，此外还多了队列的功能，而且是一个双端队列，既能FIFO，也能LIFO。从实现角度上来说，LinkedList 底层数据结构是链表，所以大多数API的实现都是利用链表的遍历去实现的。
数据结构如下图所示。
下面直接分析源码，有了 ArrayList 和前面的讲解，LinkedList 的源码应该相对简单。
/**
* 实现了List和Queue接口的双端列表，实现了所有的list操作，允许null元素
*
* LinkedList也是线程不安全的，并发修改list结构时需要手动同步
* 和ArrayList一样，也可以利用Collections.synchronizedList(new LinkedList(...))同步
*
* 该类中iterator()和listIterator()方法返回的迭代器是fail-fast的
*/
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() {}
/**
* 创建一个包含c的LinkedList，顺序按照c的顺序
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/**
* 头部连接一个元素e
*/
private void linkFirst(E e) {
final Node<E> f = first; // 原来头部
final Node<E> newNode = new Node<>(null, e, f); // 构造新节点
first = newNode; // 更新头部
if (f == null)
last = newNode; // 初始列表元素为空情况，头尾都指向newNode
else
f.prev = newNode; // 双向链表，维护前驱指针
size++;
modCount++;
}
/**
* 尾部连接一个元素e
*/
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++;
}
/**
* 在非空节点succ前插入e元素
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev; // 获得succ的前驱
final Node<E> newNode = new Node<>(pred, e, succ); // 创建节点维护前驱后继
succ.prev = newNode; // 更新succ的前驱
if (pred == null)
first = newNode;
else
pred.next = newNode; // 更新prev的后继
size++;
modCount++;
}
/**
* 去除非空头节点f的连接
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
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++;
return element;
}
/**
* 去除非空尾节点l的连接
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
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;
}
/**
* 去除非空节点x
*/
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;
}
/**
* 获取头节点的元素值，列表为空抛出NoSuchElementException
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* 获取尾节点的元素值，列表为空抛出NoSuchElementException
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
/**
* 去除并返回头结点元素，列表为空抛出NoSuchElementException
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* 去除并返回尾结点元素，列表为空抛出NoSuchElementException
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* 头插
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* 尾插
*/
public void addLast(E e) {
linkLast(e);
}
/**
* 返回是否包含元素o
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/**
* 返回列表元素数目
*/
public int size() {
return size;
}
/**
* 尾插，等同addLast(E e)，不过有返回值
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 删除第一个o元素节点
*/
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;
}
/**
* 在尾部插入c集合
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* 在index位置前插入c
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 检验index是否合法，是否属于[0，size]
checkPositionIndex(index);
Object[] a = c.toArray(); // c转为数组，转为数组后遍历效率就更高了
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index); // index所在的节点
pred = succ.prev; // index - 1所在的节点
}
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 {
pred.next = succ; // 维护插入最后一个节点与原本index节点的链
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
/**
* 清空列表所有元素
*/
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;
}
first = last = null;
size = 0;
modCount++;
}
// Positional Access Operations
/**
* 返回指定位置节点的元素
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* 更新并返回指定位置节点的元素值
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
/**
* 在指定位置插入元素
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* 去除index位置的节点
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* 元素的index是否合法
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* 插入位置的index是否合法
*/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
/**
* Constructs an IndexOutOfBoundsException detail message.
* Of the many possible refactorings of the error handling code,
* this "outlining" performs best with both server and client VMs.
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
// 检查元素的index是否合法，不合法抛出异常
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 检查插入位置的index是否合法，不合法抛出异常
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 返回index位置的非空节点
*/
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;
}
}
// Search Operations
/**
* 链表遍历的方式，支持null元素的节点
*/
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;
}
/**
* 链表遍历的方式，支持null元素的节点
*/
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;
}
// Queue operations. 队列操作实现
/**
* 查询头结点，列表为空则返回null
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* 查询头结点，列表为空则抛出NoSuchElementException
*/
public E element() {
return getFirst();
}
/**
* 删除并返回头结点，列表为空则返回null
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* 删除并返回头结点，列表为空则抛出NoSuchElementException
*/
public E remove() {
return removeFirst();
}
/**
* 尾插元素
*/
public boolean offer(E e) {
return add(e);
}
// Deque operations 双向队列操作
/**
* 头插
*/
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/**
* 尾插
*/
public boolean offerLast(E e) {
addLast(e);
return true;
}
/**
* 查询头
*/
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* 查询尾
*/
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
/**
* 删除并返回头结点，空列表返回null
*/
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* 删除并返回尾结点，空列表返回null
*/
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
/**
* 头插
*/
public void push(E e) {
addFirst(e);
}
/**
* 去头
*/
public E pop() {
return removeFirst();
}
/**
* 去除第一个o
*/
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
/**
* 去除最后一个o
*/
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
/**
* 返回一个指定位置的列表迭代器
* fail-fast机制
*/
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
// 定义的列表迭代器
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int 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;
nextIndex++;
return lastReturned.item;
}
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
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();
}
}
// 节点内部类的定义
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;
}
}
/**
* 反向迭代器
*/
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
/**
* 适配器，通过ListItr.previous提供降序迭代器
* next方法实际的都是往前调用
*/
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();
}
}
@SuppressWarnings("unchecked")
private LinkedList<E> superClone() {
try {
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
/**
* LinkedList的浅拷贝 (元素内容不拷贝)
*/
public Object clone() {
LinkedList<E> clone = superClone();
// 将克隆list置为初始状态
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// 将元素添加的方式进行克隆list
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
/**
* 链表遍历的方式转成数组
*/
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;
}
/**
* 以正确的顺序返回一个包含此列表中所有元素的数组
* 返回的数组的运行时类型是指定数组的运行时类型
* 如果入参a数组的大小足够容纳列表的size，则列表的数据直接复制进入a数组即可
* 如果a数组容量不够，则需要开辟新数组，复制完成后返回新数组，而a数组还是原来的样子
*/
@SuppressWarnings("unchecked")
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;
}
private static final long serialVersionUID = 876323262645176354L;
/**
* 列表序列化时调用，写入流中
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// 写入真实数据个数
s.writeInt(size);
// 写入“数组的每一个元素”
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
/**
* 反序列化时调用
*/
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// 从输入流中读取ArrayList的“容量”
int size = s.readInt();
// 从输入流中将“所有的元素值”读出
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
}
III. LinkedList相关
遍历方式
- 迭代器方式（性能好）
- 索引值遍历方式 （性能最差）
- foreach 遍历（性能最好，本质还是迭代器）
示例：
// 迭代器遍历
long start = System.currentTimeMillis();
Iterator<Integer> iterator = linkedList.iterator();
while (iterator.hasNext()) {
iterator.next();
}
long end = System.currentTimeMillis();
System.out.println("Iterator：" + (end - start) + " ms");
// 顺序遍历(随机遍历)
start = System.currentTimeMillis();
for (int i = 0; i < linkedList.size(); i++) {
linkedList.get(i);
}
end = System.currentTimeMillis();
System.out.println("for：" + (end - start) + " ms");
// foreach循环遍历
start = System.currentTimeMillis();
for (Integer i : linkedList)
;
end = System.currentTimeMillis();
System.out.println("foreach：" + (end - start) + " ms");
// 输出
Iterator：17 ms
for：3318 ms
foreach：1 ms
迭代删除问题
和 ArrayList 的删除问题是相似的，因为也都是 fail-fast 机制。