LinkedList源码分析（JDK1.8）
2018-04-12 本文已影响19人
阿狸404
前面分析过ArrayList的源码，现在来看看LinkedList的实现原理。首先要知道为什么有了ArrayList的存在，为什么还需要LinkedList呢？
-
LinkedList设计目的。
从上面知道ArrayList源码知道，ArryaList通过数组下标访问元素，查询效率快，但是ArrayList由于底层是数组实现的，物理地址是连续的，因此删除和添加由于都要移动复制数据，时间复杂度就提高了。为了解决这个问题，一次才有了这种物理地址不连续的数据结构的出现。LinkedList底层是结点，不要求物理地址连续，因此在删除，添加等操作效率比较高，但是查找元素效率么有ArrayList高，因为在LinkedList中查找元素基本上需要遍历整个链表。
我们来具体看看LinkedList具体实现。
-
LinkedList设计原理
- 结点定义
LinkedList的底层实现是由结点构成的，而java实现的LinkedList是双向链表。我们来看看结点的定义：
/**
* 结点，可以看做一个人，拥有左右手，左手表示上一个结点，右手表示下一个结点
*
* @author wxe
* @since 1.0.0
*/
private static class Node<E> {
E item;// 结点保存的元素
Node<E> next; // 指向下一个结点
Node<E> prev; // 指向上一个结点
Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.item = element;
this.next = next;
}
}
结点如图所示：
图片.png
- 链表定义--成员变量
transient Node<E> first;// 头结点
transient Node<E> last; // 尾结点
transient int size = 0;// 链表大小
protected transient int modCount = 0;
public LinkedList() {
}
结构如下图所示：
1.0.png
-
尾结点处插入结点
比如说我们要图1.0的尾结点处添加一个元素项8，首先要创建出这个新的结点，而我们知道这个新的结点即将成为这个链表新的尾结点，因此它的next指向null,而添加到尾结点处，所以新节点的pre指向原来的last，如图所示：
图片.png
而此时我们的last就指向了这个新的结点：
图片.png
然后我们的l指向新的结点就，这样添加就完成了：
图片.png
代码实现如下：
/**
* 添加元素，一般都是像尾结点处添加
*/
public boolean add(E e) {
linkLast(e);// 由此可以看出，添加不需要扩容，不需要复制操作，因此其添加元素效率高于ArrayList
return true;
}
添加结点到尾结点处，我们首先需要创建这个新的结点final Node<E> newNode = new Node<E>(l, e, null);而这个新的结点即将作为链表的尾结点。
public void linkLast(E e) {
final Node<E> l = last;// 获取最后一个结点,防止修改last，因此定义一个final域
final Node<E> newNode = new Node<E>(l, e, null);// 创建即将添加的结点，也就是即将成为的最后一个结点
last = newNode;// 尾指针指向新的结点
if (l == null) {
// 如果之前是空链表， 新建的节点也是第一个节点，相当于添加了一个头结点
first = newNode;
} else {
// 如果原来有尾结点，则更新尾结点
l.next = newNode;
}
size++;
modCount++;
}
-
头结点处插入结点
那我们也有可能在头结点处添加元素，比如向图1.0的头结点处添加数据项为8的结点。首先要创建新的结点，而插入到头结点出，这个结点即将成为新的头结点，因此新节点的next指向原来的头结点first.如图所示：
图片.png
而我们新节点就成为了头结点：
图片.png
原来的头结点就要指向新的头结点了：
图片.png
实现代码如下：
public void linkFirst(E e) {
final Node<E> f = first;
// 第一步：创建新节点
Node<E> newNode = new Node<E>(null, e, f);
// 第二步：添加的结点成为新的头结点
first = newNode;
// 第三步：新的结点指向下一个结点
if (f == null) {
// 空链表的时候
last = newNode;
} else {
f.prev = newNode;
}
size++;
modCount++;
}
-
在指定位置插入结点
上面讲述了两种特殊位置的插入，现在讲讲一般化的插入到指定位置。
比如，在index=1的地方插入数据项为8的结点：
图片.png
那么首先我们必须知道index=1位置上的结点，java1.8版本中采用二分搜索，这里不做重点介绍了。我们找到了index = 1位置上的结点oldNode：
图片.png
那么我们现在可以创建这个新节点了，新节点的上一个结点就是index位置上结点的上一个结点，而下一个结点就是index位置上的结点，Node<E> newNode = new Node<E>(oldNode.prev, element, oldNode);
图片.png
然后我们原来的头结点的前驱结点的next应该指向新的结点：
图片.png
然后oldNode的前驱结点指向新的结点：
图片.png
这样，我们就完成了在任意位置处添加结点的操作。但是应该注意这个index的合理性。
实现代码如下：
/**
* 指定位置添加元素，就只能遍历链表
*/
public void add(int index, E element) {
// 第一步：检查index是否越界
checkPositionIndex(index);
// 第二步：添加。如果是向尾结点添加元素，直接添加
if (index == size) {
linkLast(element);
} else {
// 如果不是向尾结点添加
linkBefore(element, index);
}
}
private void checkPositionIndex(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("越界！");
}
}
/**
* 向指定位置添加元素
*
* @param element
*/
public void linkBefore(E element, int index) {
// 第一步：先找到index位置处的结点
Node<E> oldNode = node(index);
// 第二步：查找到index位置处的前后结点
Node<E> prev = oldNode.prev;
// 第三步：创建一个新结点,新节点的前驱结点是oldNode的前驱结点，后驱结点就是oldNode
Node<E> newNode = new Node<E>(prev, element, oldNode);
// 第四步：添加结点。主要分为四个动作：新建结点的时候：newNode指向oldNode的前驱结点，newNode后去结点指向oldNode。
// 而oldNode的前驱结点指向新建结点newNode。oldNode结点原来的前驱结点的后去结点必须指向newNode
oldNode.prev = newNode;
if (prev == null) {
// 如果添加的正好是头结点
first = newNode;
} else {
// 添加的不是头结点
prev.next = newNode;
}
// 第五步：容量大小+1
size++;
modCount++;
}
/**
* 查找指定位置index处的结点，采用二分查找
*
* @param index
* @return
*/
public Node<E> node(int index) {
// 采用二分搜索查找:如果index在size/2的前半部分，则从前向后开始遍历。否则，从后向前开始遍历
int right = size >> 1;// 相当于size/2，采用>>主要考虑到效率
if (index < right) {
// 如果小于size/2，则在0-index之间查找
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next; // 将x指针向后移动，开始遍历
}
return x;
} else {
// 如果大于size/2,则在index-size之间查找
Node<E> x = last;
for (int i = size - 1; i < index; i++) {
x = x.prev;// 将x指针向前移动，开始遍历
}
return x;
}
}
-
删除指定数据项
比如我们要删除数据项8，那我们肯定必须得通过遍历链表找到这个结点，然后得到这个结点的前驱结点和后驱结点。
图片.png
首先通过遍历链表的方式找到这个结点：
图片.png
根据结点的定义，我们知道了它的前驱结点和后驱结点，然后将前驱结点的next指向x的后驱结点。将后驱结点的prev指向前驱结点：
图片.png
最后把x的前驱引用和后驱引用置null，便于垃圾回收期回收，结果如下：
图片.png
实现代码如下：
/**
* 移除指定元素
*/
public boolean remove(Object o) {
//LinkedList允许放置null元素，因此需要分两种情况
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 true;
}
return false;
}
E unlink(Node<E> x){
final E element = x.item;
Node<E> prev = x.prev;
Node<E> next = x.next;
//第一步：处理前驱结点的引用
if (prev == null) {
//删除的是第一个结点
first = next;
} else {
//删除的不是第一个结点，则x的前驱结点需要指向x的后驱结点，并且删除掉x前驱结点指向的prev
prev.next = next;
x.prev = null;
}
//第二步：处理后驱结点的引用
if (next == null) {
//如果删除的是尾结点,则当前尾结点是x的前驱结点
last = prev;
} else {
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;
x.item = element;
return oldVal;
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- 查找数据项指定位置
查找元素这种一般都通过遍历链表完成，看每个结点的数据项是否和待查找的数据项是否相等。但是我们的链表因为允许存放null值，因此在判断相等的时候，需要根据情况把数据项分为null和非null。如果为null元素，则==判断相等，如果非null，则根据equals方法来判断。
实现代码如下：
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;
}
- 找到数据项最后出现的位置
由于我们的LinkedList允许放置重复元素，因此，有时候需要找到最后出现的位置。这里由于双端链表的特性，我们可以采用从后向前遍历的方式找到这个数据项。
代码实现如下：
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;
}
-
LinkedList特性
LinkedList不仅实现了Collection接口，同时也实现了Queue，说明我们的LinkedList也是一种队列。队列的特性就是先进先出。而LinkedList由于结点的特殊定义，本身结点既知道下一个结点，也知道上一个结点，因此想要实现队列这种先进先出的特性，push的时候，调用addFirst(e)方法，而pop的时候，调用removeFirst(e)方法即可。
实现代码如下：
public void push(E e) {
addFirst(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++;
}
出队列：
public E pop() {
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) {
// 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;
}
-
fail-fast机制
先来看看迭代器的源码：
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();
}
}
这个迭代器的存在，主要是为了方便我们访问元素的。而我们知道LinkedList是线程不安全的。一旦有一个线程在改变LinkedList中的元素，而我们在访问的时候，就会通过modCount != expectedModCount比较知道当前多线程环境下集合元素又被修改了。主要原理就是我们在删除，修改LinkedList等操作时，修改了modCount ，而expectedModCount在迭代器中定义的，你访问的时候这个值还是以前的那个值，比较的时候两者不一致。就会导致抛出异常了。
-
LinkedList的特点
- 内部结点定义使用静态内部类，这种方式创建对象不依赖外部对象，所以用起来更方便。
- 添加元素的时间为时间常数O(1)，删除元素，不需要移动数据，单纯删除操作也是时间常数，所以删除，添加性能优于ArrayList。
-
随机访问指定下标的时间常数是线性的O(n)，所以性能没有ArrayList的好。
图片.png
