LinkedList是java集合框架下的成员，底层数据基础为双向链表，非线程安全集合
从源码看LinkedList
- 1 LinkedList的继承实现
- 2 LinkedList的数据基础
- 2 LinkedList的初始化
-
- 2.1 无参构造
- 2.1 带有初始元素集合的构造
- 3 LinkedList的元素新增示例
-
- 3.M.1 addAll(int index, Collection<? extends E> c)
- 3.M.2 add(int index, E element)
- 4 LinkedList的元素删除示例
-
- 4.M.1 remove(int index)
- 5 LinkedList的元素获取示例
-
- 5.M.1 get(int index)
- 5.M.2 getFirst()
- 6 LinkedList的元素修改示例
-
- 6.M.1 set(int index, E element)
- 7 LinkedList的迭代器
-
- 7.1 双向迭代器
- 7.2 逆向迭代器
- 7.3 可分割迭代器
- 8 总结
1 LinkedList的继承实现
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
AbstractSequentialList
对仅允许顺序访问的数据存储方式（如链表，不支持随机访问）提供了最低限度的随机访问框架实现，当然对于允许随机访问的数据存储形式（如数组，支持随机访问），
AbstractSequentialList
是劣于
AbstractList
的。LinkedList继承了
AbstractSequentialList
抽象类，因此LinkedList也具有可以随机访问的特性。
List
接口为List集合基础接口。
Cloneable
接口的实现说明LinkedList能够被克隆
java.io.Serializable
接口的实现说明LinkedList能够被序列化
Deque
为双向队列的基础接口，实现
Deque
意味着LinkedList可以作为一个双向队列使用。
2 LinkedList的数据基础
LinkedList采用双向链表进行数据存储。
LinkedList定义了
first
记录双向链表的头节点：
last
双向链表的尾节点：
双向链表的节点类型为内部类
Node
：
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;
}
}
定义了
size
实时记录元素数量
2 LinkedList的初始化
2.1 无参构造
/**
* Constructs an empty list.
*/
public LinkedList() {
}
LinkedList的无参构造没有进行任何动作。
2.1 带有初始元素集合的构造
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
调用无参构造，然后调用
addAll
方法进行元素新增。
addAll
为一个公共方法，留到下面元素新增环节再分析。
3 LinkedList的元素新增示例
元素新增方面选用单条新增方法
add(int index, E element)
与批量新增方法
addAll(int index, Collection<? extends E> c)
作为新增逻辑的示例方法：
3.M.1 addAll(int index, Collection<? extends E> c)
描述：从指定位置，将指定集合中的所有元素按照指定集合的迭代器返回的顺序追加到当前LinkedList的末尾
源码：
public boolean addAll(int index, Collection<? extends E> c) {
// index的合法性校验，要求index >= 0 && index <= size,否则抛出IndexOutOfBoundsException:
checkPositionIndex(index);
// 转为数组形式
Object[] a = c.toArray();
// 获得元素数量
int numNew = a.length;
// 指定集合为空的话就直接返回
if (numNew == 0)
return false;
// pred为插入点的前一个元素
// succ为原插入点元素
Node<E> pred, succ;
// index == size意味着从尾巴链入
if (index == size) { // 刚好在末尾的话
succ = null; // size处元素是null
pred = last; // size上一个就是size-1，也就是last
} else { // 从中间链入
succ = node(index); // 获取node处的元素，见3.M.5.1 node(int index)
pred = succ.prev; // 记录pred
}
// 遍历数组o
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// 构造新节点，前一个节点就是pred，后一个节点还未生成，暂定null
Node<E> newNode = new Node<>(pred, e, null);
// 如果pred为空，也就是原来集合内没有元素，那么这个节点就是头节点
if (pred == null)
first = newNode;
else // 否则的话newNode链接到pred的next上
pred.next = newNode;
pred = newNode; // 重置pred,新元素成为pred,作为下一个元素的上一个元素
}
// succ是断开处，如果断开处为空，说明是从末尾插入的，就要修正last
if (succ == null) {
last = pred;
} else { // 否则的话就要把succ链接上
pred.next = succ;
succ.prev = pred;
}
size += numNew; // 修正size
modCount++; // modCount记录
return true;
}
3.M.1.1 node(int 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;
}
}
备注：通过一次中分遍历减少遍历次数，可以看到双向链表的随机访问只能从头节点或者尾节点一步步遍历过去，效率较低
3.M.2 add(int index, E element)
描述：在指定位置插入指定元素
源码：
public void add(int index, E element) {
// index的合法性校验，要求index >= 0 && index <= size,否则抛出IndexOutOfBoundsException:
checkPositionIndex(index);
// ==size就是从末尾插入，直接调用3.M.2.1 linkLast(E e)
if (index == size)
linkLast(element);
else // 否则调用linkBefore
linkBefore(element, node(index));
}
3.M.2.1 linkLast(E e)
描述：将e作为最后一个元素连入集合
源码：
void linkLast(E e) {
// 记录原末尾last
final Node<E> l = last;
// 创建节点：因为是首元素，所以上一个节点为原last，下一个节点为null
final Node<E> newNode = new Node<>(l, e, null);
// last属性指向新的尾节点
last = newNode;
// 如果是第一个元素，那么他即是尾节点，又是首节点
if (l == null)
first = newNode;
else // 修正原last节点的next为新节点
l.next = newNode;
size++; // 修正size
modCount++; // modCount记录
}
3.M.2.2 linkBefore(E e, Node<E> succ)
描述：在非空节点succ之前插入元素e
源码：
void linkBefore(E e, Node<E> succ) {
// succ一定要不为空，否则就NullPointerException了
final Node<E> pred = succ.prev;
// newNode的后一个元素就是succ,前一个元素就是succ的prev
final Node<E> newNode = new Node<>(pred, e, succ);
// 修正succ的prev
succ.prev = newNode;
// pred为空说明succ原来是第一个元素，那么在succ前插入元素也要修改first
if (pred == null)
first = newNode;
else //否则的话要修正pred的next，由succ改为newNode
pred.next = newNode;
size++; // 修正size
modCount++; // modCount记录
}
备注：可以看到，链表的插入只是一个断链与链接的过程，比数组的复制移位效率高多了
4 LinkedList的元素删除示例
元素移除方面选用定点移出方法
remove(int index)
作为移除逻辑的示例方法：
4.M.1 remove(int index)
描述：删除此集合中指定位置的元素
源码：
public E remove(int index) {
// index合法性校验，要求index >= 0 && index < size，否则抛出IndexOutOfBoundsException
checkElementIndex(index);
// node方法即为3.M.1.1 node(int index)，获得指定位置的元素
return unlink(node(index));
}
4.M.1.1 unlink(Node<E> x)
备注:断开非空节点x
源码：
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
// 获得x的next和prev
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// prev 为null说明x是首元素
if (prev == null) {
first = next;
} else { // 否则的话prev的next由x改为x的next， x.prev也要断链
prev.next = next;
x.prev = null;
}
// next同理
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 断开x对实际数据的强链接
x.item = null;
size--; //修正size
modCount++; // modCount记录
return element;
}
备注：移除操作，只需重置前一个元素的next和后一个元素的prev，并清除x的指向，即可移除一个元素，无需移动元素。
5 LinkedList的元素获取示例
元素新增方面选用随机访问方法
get(int index)
以及首节点访问方法
getFirst()
作为获取逻辑的示例方法：
5.M.1 get(int index)
备注：返回此集合中指定位置的元素
源码：
public E get(int index) {
// index合法性校验，要求index >= 0 && index < size，否则抛出IndexOutOfBoundsException
checkElementIndex(index);
// 直接调用3.M.1.1 node(int index)
return node(index).item;
}
备注：随机访问需要从端部进行遍历，相较于数组的直接找到目标位置，是一个比较耗时的操作
5.M.2 getFirst()
备注：返回此集合中的第一个元素
源码：
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item; //直接返回firs
}
备注：因为LinkedList分别用
first
与
last
记录了首尾元素，因此LinkedList的端部访问还是很迅速的，LinkedList的查询慢仅限于随机访问。
6 LinkedList的元素修改示例
元素修改方面选用
set(int index, E element)
作为修改逻辑的示例方法：
6.M.1 set(int index, E element)
描述：用指定的元素替换此集合中指定位置的元素
源码：
public E set(int index, E element) {
// index合法性校验，要求index >= 0 && index < size，否则抛出IndexOutOfBoundsException
checkElementIndex(index);
// 直接调用3.M.1.1 node(int index)获得目标元素x
Node<E> x = node(index);
// 直接修改x.item,连断链与重见node都不需要
E oldVal = x.item;
x.item = element;
return oldVal;
}
7 LinkedList的迭代器
7.1 双向迭代器
LinkedList中可以通过
listIterator(int index)
方法获得集合的双向迭代器：
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
LinkedList的双向迭代器是通过内部类
ListItr
实现的：
private class ListItr implements ListIterator<E> {
// 上一个返回的节点
private Node<E> lastReturned;
// 下一个要返回的节点
private Node<E> next;
// 下一个要返回的节点下标
private int nextIndex;
// modCount记录
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
// index == size的话直接就是尾端了,next就null
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
// 通过next.next覆盖next的操作后移
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
... ... // 后续省略
}
可以看到ListItr是通过记录
next
节点，然后通过
next
节点的
next
属性与
prev
属性进行前移或者后移。
lastReturned
节点的记录主要是用来remove。
ListItr设置有
expectedModCount
属性，这说明LinkedList在迭代期间也是不允许修改集合元素的，若要修改只能通过ListItr的相关方法操作，逻辑思路和LinkedList相关方法类似，只是多了
expectedModCount
修正，使得修改之后ListItr可以继续迭代，而不会抛出
ConcurrentModificationException
。
7.2 逆向迭代器
LinkedList中可以通过
descendingIterator()
方法获得集合的逆向迭代器：
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
逆向迭代器通过内部类
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();
}
}
DescendingIterator
是直接使用的双向迭代器
ListItr
实现的。
7.3 可分割迭代器
LinkedList中可以通过
spliterator()
方法获得集合的可分割迭代器：
@Override
public Spliterator<E> spliterator() {
return new LLSpliterator<E>(this, -1, 0);
}
可分割迭代器通过内部类LLSpliterator实现，但是LLSpliterator并不是采用记录头和尾节点，并在
trySplit
时修改头尾节点的方式进行切割，而是通过LLSpliterator+ArraySpliterator方式实现的，
通过LLSpliterator的源码进行分析：
7.3.M.1 构造方法
先看其构造方法：
LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
this.list = list;
this.est = est;
this.expectedModCount = expectedModCount;
}
赋值了三个属性，这三个属性被定义为：
final LinkedList<E> list; // null OK unless traversed
int est; // size estimate; -1 until first needed
int expectedModCount; // initialized when est set
-
list
-
est
-
expectedModCount
而
spliterator()
方法调用构造方法时是
new LLSpliterator<E>(this, -1, 0)
。可以看到，除了第一个入参
list
入参为
this
表面时当前LinkedList集合，后面的
est=-1
与
expectedModCount=0
其实只是相当于一个标记，标记着这个LLSpliterator还没有初始化，和ArrayList的
ArrayListSpliterator
是一样的，采用懒加载的方式，这么做的好处是在spliterator实际使用前，LinkedList依然可以任意的修改自己的元素。
est
和
expectedModCount
的实际初始化时在LLSpliterator第一次使用时，通过
getEst()
方法进行初始化.
7.3.M.2 获取剩余元素数 - getEst()
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; // 赋值est
}
}
return s;
}
可以看到如果
est
小于0，意味未初始化，就执行
expectedModCount = lst.modCount;
，
current = lst.first;
，
est = lst.size;
就是很简单的初始化，经历这一步，LinkedList自身已经不可任意修改元素了。
最后返回s,也就是est
7.3.M.3 切割-trySplit() - 核心方法
接下来看核心的
trySplit()
方法：
但是在分析切割逻辑之前先看一下LLSpliterator内的几个属性：
static final int BATCH_UNIT = 1 << 10; // batch array size increment
static final int MAX_BATCH = 1 << 25; // max batch array size;
int batch; // batch size for splits
Node<E> current; // current node; null until initialized
-
BATCH_UNIT
BATCH_UNIT
-
MAX_BATCH
MAX_BATCH
-
batch
-
current
了解了这个，接下来继续分析
trySplit()
方法：
public Spliterator<E> trySplit() {
Node<E> p;
int s = getEst(); // getEst()上面已经分析过了，实际初始化以及获得长度est
if (s > 1 && (p = current) != null) {
int n = batch + BATCH_UNIT; // 上一批的量加批次单元量，就得出这次的批次量
if (n > s) // 如果剩余的元素小于这次的批次量，那么批次量就重置为剩余量
n = s;
if (n > MAX_BATCH) // 保证批次量最大为MAX_BATCH
n = MAX_BATCH;
Object[] a = new Object[n]; // n长度的数组
int j = 0; // 遍历下标
// 前面有p = current，这里就是从current开始找n个数据放到数组a里面
do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
current = p; // 修正current到新的节点
batch = j; // 这一批的元素量
est = s - j; // 修正剩余元素量
// 返回的是ArraySpliterator
return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
}
return null;
}
可以看到LLSpliterator的每次
trySplit()
,批次量都会以
BATCH_UNIT
为单元量进行递增，直到
MAX_BATCH
或者剩余元素量低于批次量
n
，也就是说在元素量足够大的情况下：
- 那么第一次调用
LLSpliterator.trySplit()
- 第二次调用
LLSpliterator.trySplit()
为什么LLSpliterator对于已经切出去的数据使用ArraySpliterator管理而不是继续自己管理呢，还是因为链表随机访问能力效率较低的原因，Spliterator的切割方式采用中位切割的方式，切割时很重要的一步就是找到中位，数组可以通过计算下标直接锁定中位，但是链表不行，链表必须从头遍历，遍历一半的元素才能锁定中位，Spliterator一旦使用，很大可能会经历不只一次切割，因此使用ArraySpliterator以获得更高的切割效率，这是一种以空间换效率的方式。
7.3.M.4 forEachRemaining与tryAdvance
源码：
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; // 全遍历的current就到头了，就不一步步修改了，直接一步到位
est = 0; // est也是直接没了，一步到位设为0
do {
E e = p.item;
p = p.next; // 用next遍历
action.accept(e);
} while (p != null && --n > 0);
}
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
}
分析：这里只放了
forEachRemaining
的源码，是因为
forEachRemaining
与
tryAdvance
的逻辑差异不大，都是通过节点的
next
属性后移执行，属于链表遍历的基本方式，并没有特别的地方。
8 总结
- LinkedList以双向链表作为底层数据结构进行数据存储，这使得其增删快速且无需扩容操作，但是随机访问的效率较差
- LinkedList是一个有序集合，这个有序是指其元素顺序与插入顺序一致
- LinkedList不是线程安全的集合
- LinkedList不允许在迭代的过程中直接修改集合数据，但是可以通过迭代器进行间接修改
- LinkedList的可分割迭代器通过ArraySpliterator + LLSpliterator共同实现，以获得更高的切割效率
- LinkedList可以作为一个双向队列使用，可以进行双向遍历
- LinkedList可以实现FIFO（先进先出）与LIFO（后进先出）
PS：
【JAVA核心知识】系列导航 [持续更新中…]
上篇导航：7: 从源码看ArrayList:一文看懂ArrayList
下篇导航：9: 从源码看HashMap:一文看懂HashMap
欢迎关注
![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)