Java容器类源码-LinkedList的最全的源码分析

时间:2021-06-25 16:20:42

一、概述

我们都知道,在Java中容器类里面包含了Collections(单列集合)和Map(双列集合),而Collections中又包含了List(有序,元素可以重复)和Set(无序,元素不重复),而List中又包含了ArrayList、LinkedList和Vector(JDK1.2之后已经过时),所以ArrayList和LinkedList就作为了我们常用的List集合,它们都有共同点, 都是线程不安全的,但是效率相对比较高。但是它们也有不同的地方,ArrayList是查询速度比较快,增删速度比较慢,而LinkedList就是查询速度比较慢,增删速度比较快,到底是什么原因导致了它们的不一样呢?只要大家有了解过它们的底层实现,我们就可以知道,ArrayList底层是由数组实现的,我们知道数组就是在内存里面申请一段连续的内存,然后在里面读写数据,它查询的时间复杂度是O(1),但是我们都知道如果要往数组里面添加或者删除数据的话,在添加(删除)位置后面数都要往前或者往后相应的位置,所以它增删的时间复杂度是O(n)。然而,LinkedList的底层是由链表实现的,而链表查询数据的时间复杂度是O(n),而增删数据的时间复杂度是O(1)。由此可见,它们在查询和增删数据两个维度上有着不同的差异,所以我们在具体使用时,可以根据自己的需要选择不同的数据结构。
那么假如我们没有了解过它的底层实现,那我们怎么会了解到它们的差异呢?即便我们了解了它们的差异,那么我们有没有思考过,例如,ArrayList是数组实现的,按理来说它是固定长度的,但是为什么我们可以不断地往ArrayList里面添加数据,从来不需要考虑它的长度呢?这就是ArrayList的底层源码里面写了一个比较好的扩容算法,在添加数据时判断是否需要扩容,如果需要的话就把数组的空间长度扩容至原来的1.5倍,所以我们在使用上不需要考虑它的容量。而这些都是通过阅读ArrayList的源码才能发现到的,当然,如果大家想阅读ArrayList的源码,可以移步 《 Java容器类源码-ArrayList的最全的源码分析》。当然,功利性一点来说,阅读源码对于我们面试来说也是非常有帮助的。
鄙文主要给大家介绍一下JDK1.8版本的LinkedList源码,能力有限,如有错误不足之处,恳请大神们指出。

二、源码解读

打开LinkedList的源码,我们可以看到了一堆注释,别以为注释没有用,其实它是给我们做了简要概括,方便我们更容易理解LinkedList,我大概将其中的重点列出来,如下:

LinkedList的底层实现是由一个双向链表实现的,可以从两端作为头节点遍历链表。
LinkedList在查找元素时,会根据索引更加接近列表头或者尾来选择列表的头或者尾进行遍历,以提升查找效率。
LinkedList在实现上是不同步的,即线程不安全,当有多个线程同时操作LinkedList时,有可能会导致数据错误,所以如果需要多线程共享LinkedList时,最好使用synchronizedList来初始化:List list = Collections.synchronizedList(new LinkedList(...));
当使用LinkedList迭代器时,有可能会迭代失败并提示java.util.ConcurrentModificationException。如果我们在初始化了LinkedList的迭代器之后,使用Iterator自身以外的remove或者add方法进行增删数据,使LinkedList的结构发生改变,再通过Iterator进行遍历,就会产生这个问题。所以我们使用Iterator遍历时,最好在LinkedList的结构不再发生改变后,再初始化Iterator。

我们先来看一下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;
}
}

1.继承、接口

LinkedList继承了AbstractSequentialList,实现了List接口,Deque接口,Cloneable接口,Serializable接口。
那么,AbstractSequentialList是什么呢?AbstractSequentialList 继承自 AbstractList,是 List 接口 的简化版实现。AbstractSequentialList 只支持按顺序访问,而不像 AbstractList 那样支持随机访问。我们都知道LinkedList作为链表,是按顺序访问的, 所以它继承了AbstractSequentialList 。实现的接口重点说一下Deque,Deque就是双向队列的接口,它继承于Queue(队列),里面有一系列双向队列的空实现方法,如增、删、改、查、获取删除第一个和最后一个元素等;至于其他接口就不说了,比较简单。

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

2.全局变量

(1) 大小
// 不可序列化
transient int size = 0;

(2) 头结点

transient Node<E> first;

(3) 尾结点

transient Node<E> last;

(4) LinkedList结构变化的次数

protected transient int modCount = 0;

3.构造函数

(1) 不带参数的构造函数
public LinkedList() {}

(2) 带有Collection c参数的构造函数
public LinkedList(Collection<? extends E> c) {
this();
addAll(c); // 调用addAll()方法,把传入的c复制给该LinkedList,addAll()具体实现后面讲
}

4.方法

由于LinkedList里面有一些方法是公开的(即我们在API里面可以看到的,日常使用的一些接口),有一些方法是私有的(即内部使用的一些方法),这里我们先讲一下公开的方法。

(1) getFirst():获取LinkedList的首元素
源码解释:
获取到LinkedList的首元素,如果为空,抛出NoSuchElementException异常,否则返回首元素。
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}

(2)getLast():获取LinkedList的尾元素
源码解释:
获取到LinkedList的元素,如果为空,抛出NoSuchElementException异常,否则返回元素。
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}

(3)removeFirst():把首元素移除,并返回该元素
源码解释:
获取到LinkedList的首元素,然后判断是否为空,如果为空,则抛出NoSuchElementException异常,否则通过调用unlinkFirst(Node<E> f)方法来移除首元素。
unlinkFirst这个方法是LinkedList的内部方法,源代码如下。首先拿到首元素的下一个元素(新的首元素),然后将首元素的值,和指向下一个元素的变量都置为空,然后等待垃圾回收器空闲的时候把首元素GC掉,然后判断新的首元素是否为空,如果为空,则置尾元素也为空,并且新的首元素的前指向也置空,size(列表存储个数)减一,modeCount(结构变化次数)也减一,返回新的首元素。

Java容器类源码-LinkedList的最全的源码分析
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f); // 调用unlinkFirst(Node<E> 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++;    return element;}

(4) removeLast():移除尾部元素
源码解释:
获取到LinkedList的元素,然后判断是否为空,如果为空,则抛出NoSuchElementException异常,否则通过调用unlinkLas t(Node<E> f)方法来移除首元素。
unlinkLast()方法和unlinkFirst方法的原理是一样的,其实就是反过来,只要你把上图的首元素改为尾元素,道理就是一样的,不赘叙。

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;}

(5) addFirst(E e):把元素加到列表的首部
源码解释:
调用内部方法linkFirst(E e),把元素加到首部。
public void addFirst(E e) {
linkFirst(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;		// 则尾元素也是新建的元素    else			// 否则        f.prev = newNode;	// 原首元素的前指针指向新的首元素    size++;    modCount++;}



(6) addLast(E e):把元素加到列表的尾部
源码解释:
调用内部方法linkLast(E e),把元素加到尾部。linkLast和linkFirst道理一样,不赘叙。
public void addLast(E e) {
linkLast(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++;}

(7) contains(Object o):是否包含该元素
源码解释:
调用内部方法indexOf(Object o)方法,判断是否包含该元素。
public boolean contains(Object o) {
return indexOf(o) != -1;
}
public int indexOf(Object o) {    int index = 0;    if (o == null) {	// 判断是否包含元素值为null的元素        for (Node<E> x = first; x != null; x = x.next) {            if (x.item == null)                return index;            index++;        }    } else {		// 通过equals方法判断是否包含该不为null的元素,不能通过值比较,而是通过对象是否equals来比较        for (Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item))                return index;            index++;        }    }    return -1;}
public int indexOf(Object o) {    int index = 0;    if (o == null) {	// 判断是否包含元素值为null的元素        for (Node<E> x = first; x != null; x = x.next) {            if (x.item == null)                return index;            index++;        }    } else {		// 通过equals方法判断是否包含该不为null的元素,不能通过值比较,而是通过对象是否equals来比较        for (Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item))                return index;            index++;        }    }    return -1;}

(8) size():返回元素个数
public int size() {	return size;}

(9) add(E e):增加元素(默认加到尾部)
源码解释:
直接调用linkLast()方法,把元素加到尾部,实现原理上面已讲,不赘叙。
public boolean add(E e) {	linkLast(e);
return true;
}


(10) remove(Object o):移除元素
源码解释:

首先通过查找是否包含该元素,实现原理和contains方法一致,在找到的时候,调用unlink方法,移除元素。
unlink方法就是将,要移除元素的前一个元素的后指针指向移除元素的下一个元素,要移除元素的下一个元素的前指针指向要移除元素的上一个元素,当然,要判断前后元素是否为空的状态。

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;
}
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 {		prev.next = next; // 要移除元素的上一个元素的后指针指向要移除元素的下一个元素		x.prev = null;	}	if (next == null) {		last = prev;	} else {		next.prev = prev; // 要移除元素的下一个元素的后指针指向要移除元素的上一个元素		x.next = null;	}	x.item = null; // 移除元素置空,等待gc	size--;	modCount++;	return element;}

(11) addAll(Collection<? extends E> c):把集合c加到列表尾部
源码解释:

调用addAll(int index, Collection<? extends E> c)方法,把集合c加到列表尾部。
public boolean addAll(Collection<? extends E> c) {	return addAll(size, c);
}

(12) addAll(int index, Collection<? extends E> c):把集合c插入到第index个位置前
源码解释:

将集合c插入到原来的LinkedList的index位置,并使它们结合在一起。

public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); // 检查是否越界

Object[] a = c.toArray(); // 将集合转为数组
int numNew = a.length; // 获取到集合的大小
if (numNew == 0)
return false;

Node<E> pred, succ; // pred:中间变量, succ:插入位置的后一个元素
if (index == size) { // 如果插入位置为尾元素的下一个位置
succ = null; // 插入位置后面没有元素了
pred = last; // 新插入集合的前一个元素为原来的尾元素
} else { // 如果不是在尾部的下一个元素插入
succ = node(index); // 通过node()方法获取到index位置的元素
pred = succ.prev; // 插入集合的首元素的前指向为index位置的前一个元素
}

for (Object o : a) { // 循环遍历,使新插入集合元素的排列起来,并使pred指向新插入集合的最后一个元素
@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; // 否则将插入集合的尾元素后指向为插入位置的下一个元素
succ.prev = pred; // 插入位置的下一个元素的前指向为插入集合的尾元素
}

size += numNew;
modCount++;
return true;
}
private void checkPositionIndex(int index) {	if (!isPositionIndex(index))		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
private boolean isPositionIndex(int index) {	return index >= 0 && index <= size; // 判断index是否越界}

(13) clear():将LinkedList的每一个结点移除。
源码解释:

通过遍历链表,将每一个结点的结构体内的变量置为空,等待垃圾处理器进行回收,并置size为0。
public void clear() {	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++;
}

(14) get(int index):返回index位置的元素。
源码解释:
首先判断是否越界,然后调用node(int index)方法返回index位置的元素。我们都知道LinkedList底层是由双向链表来实现的,而node(int index)方法作为检索元素的一个方法,它是利用了双向链表的特性,在index下标小于LinkedList的一半长度时,是从首结点开始检索,而如果index下标大于LinkedList的一半长度时,是从尾结点开始从后向前检索。
public E get(int index) {	checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {	if (index < (size >> 1)) { // size>>1,即size右移1位,即size / 2		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;	}}

(15) indexOf(Object o):从首元素开始,找到结点对应的第一个位置
源码解释:

从首元素开始,获取到结点对应的第一个位置,不存在则返回-1
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;
}

(16) lastIndexOf(Object 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;
}

(17) peek():返回首元素
源码解释:

返回首元素,如果为空,则返回null

public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}

(18) element():返回首元素
源码解释:

调用getFirst(),列表不存在抛出NoSuchElementExeption。

public E element() {
return getFirst();
}

(19) poll():移除并返回首元素
源码解释:

调用unlinkFirst()方法移除首元素。

public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

(20) remove():移除首元素,并返回
源码解释:

调用unlinkFirst移除首元素,列表不存在抛出NoSuchElementExeption。

public E remove() {
return removeFirst();
}

(21) offer(E e):在尾部添加元素
源码解释:

调用add()方法添加元素,而add方法则是调用我们前面所说的linkLast()方法。

public boolean offer(E e) {
return add(e);
}
public boolean add(E e) {	inkLast(e);	return true;}

(22) offerFirst(E e):添加元素到首部
源码解释:

调用addFirst方法添加元素到首部。

public boolean offerFirst(E e) {
addFirst(e);
return true;
}

(23) offerLast(E e):添加元素到尾部
源码解释:
调用addLast方法添加元素到尾部
public boolean offerLast(E e) {
addLast(e);
return true;
}

(24) peekFirst():检索首结点,但不删除
源码解释:
如果首结点存在,则返回,不存在则返回null。
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}

(25) peekLast():检索尾结点,但不删除
源码解释:
如果尾结点存在,则返回,不存在则返回null。
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}

(26) pollFirst():检索首结点,并删除
源码解释:
如果首结点存在,则调用unlinkFirst移除首结点,并返回,否则返回null。
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

(27) pollLast():检索尾结点,并删除
源码解释:
如果尾结点存在,则调用unlinkLast移除首结点,并返回,否则返回null。
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}

(28) push(E e):把一个结点放到LinkedList的首结点位置
源码解释:
调用addFirst方法把一个结点放到LinkedList的首结点位置。
public void push(E e) {
addFirst(e);
}

(29) pop():把LinkedList的首结点移除并返回
源码解释:
调用pop 方法把一个结点放到LinkedList的首结点位置。
public E pop() {
return removeFirst();
}

(30) removeFirstOccurrence(Object o):从首结点开始,移除第一个内容为o的结点
源码解释:
调用remove 方法,从首结点开始,移除第一个内容为o的结点。
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}

(31) removeLastOccurrence(Object o):从尾结点开始,移除第一个内容为o的结点
源码解释:
通过判断o是否为null,然后调用unlink方法移除元素。
public boolean removeLastOccurrence(Object o) {
if (o == null) {
// 如果o为null,则检索第一个值为null的结点,并调用unlink方法移除该元素
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// 如果o不为null,则检索第一个值为o的结点,并调用unlink方法移除该元素
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}



(32) listIterator(int index):返回index位置的interator
源码解释:
检查是否越界,然后new一个ListItr。那么ListItr是什么东西呢?它其实是LinkedList的一个内部类,类似Iterator,可以帮我们对List进行遍历,增删改查等,我们看一下它的实现。它的在new的时候初始化完成,同时提供了next(),hasPrevious(),remove(),set(E e),add(E e)等方法,所以我们通过listIterator方法拿到ListItr对象后,可以调用ListIterator内部的方法, 可以对从index位置到尾结点这一段长度的LinkedList进行数据操作。这里比较难理解就是forEachRemaining这个方法,它是JDK1.8之后的方法,其实它也是遍历LinkedList的一种效率比较高的实现。
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();    }}

(33) descendingIterator():返回一个DescendingIterator对象。
源码解释:
实例化一个DescendingIterator对象,并返回。DescendingIterator是逆序的ListItr,我们可以看到它的实现,当求他的next元素时,就是调用ListItr的previous方法,即返回它的前一个元素,所以当要从尾部开始遍历时,可以使用DescendingIterator来进行遍历。DescendingIterator的实现也比较简单,只有hasNext,next,remove三个方法。
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
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();    }}

(34) spliterator():返回一个LLSpliterator对象。
源码解释:
实例化一个LLSpliterator对象,并返回。LLSpliterator是JDK1.8之后LinkedList新增的内部类,大概用途是将元素分割成多份,分别交于不于的线程去遍历,以提高效率。具体不深入研究。这里贴出LLSpliterator的源码,大家感兴趣可以自行深入研究,因为用得比较少,我就不在这里班门弄斧了。
public Spliterator<E> spliterator() {
return new LLSpliterator<E>(this, -1, 0);
}
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;              // size estimate; -1 until first needed    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;            do { a[j++] = p.item; } while ((p = p.next) != null && j < n);            current = p;            batch = j;            est = s - j;            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;    }}

三、总结

其实看了一遍LinkedList源码之后,觉得实现原理比较简单,就是一个双向链表,有学过数据结构,了解过链表的同学相信一次就看懂了,其中发现Oracle在接手Java之后还是有继续对LinkedList进行维护,我们可以看到JDK1.8之后还是加入了一些新的东西,但是也还是发现有一些代码还是比较重复的了,估计是很多人一起维护所造成的的结果,例如移除首元素就有好几个方法,而且都是大同小异,所以又觉得它的api太过冗余了。

public E removeFirst() {    final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}

public E remove() {
return removeFirst();
}

public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}

public E pop() {
return removeFirst();
}

LinkedList的源码讲解就到这里,相信很多同学阅读完之后都对LinkedList的理解上到了更高的一个层次,所以我们应该做到不仅能够熟用一个类的api,更要有探索源码的精神,我想这样对我们的提高会是更大的。