LinkedList源码解析
上篇文章我们分析了ArrayList的源码，LinkedList作为ArrayList的兄弟，怎么能少呢？今天我们就一起来看下LinkedList。LinkedList底层数据结构为双向链表，由于链表的特性，使得LinkedList增删操作比较快，查询操作稍慢一些。
既然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;
}
}
可以看到一个Node结点包含三部分：item、prev、next。item为数据域，存放当前结点的数据元素。prev和next为地址域，prev中存放的是pre结点的内存地址，而next中存放的是next结点的内存地址。
接着让我们来看下LinkedList中的一些重要属性：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
/**
* 当前LinkedList的大小
*/
transient int size = 0;
/**
* 头指针
*/
transient Node<E> first;
/**
* 尾指针
*/
transient Node<E> last;
可以看到，LinkedList继承了AbstractSequentialList，实现了Serializable接口，支持序列化操作。LinkedList中的重要属性无非就上述三个，size表示当前LinkedList的大小，first和last分别代表头指针和尾指针。
我们在工作中创建LinkedList时一般是这么创建的：
List mList = new LinkedList<String>();
那我们就点进去它的构造方法去看下：
/**
* Constructs an empty list.
*/
public LinkedList() {
}
确定不是在逗我？ ？ ？LinkedList的构造方法竟然是个空实现，好吧，我们接下来看下它的add系列的操作方法：
/**
* 方式一：添加数据元素到当前linkedlist的首部
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* 方式二：添加数据元素到当前linkedlist的尾部
*/
public void addLast(E e) {
linkLast(e);
}
/**
*方式三：添加数据元素到当前linkedlist中，默认添加到尾部
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 方式四：添加数据元素到当前linkedlist中的指定位置
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
我们先来看下方式一，添加数据元素到当前linkedlist的首部，可以看到方法中直接调用了linkFirst方法，将要添加的元素作为参数传递过去，我们跟进去linkFirst方法看下：
/**
* Links e as first element.
*/
private void linkFirst(E e) {
// 1.将头指针赋值给 f 结点
final Node<E> f = first;
// 2.创建新结点，由于当前操作是将数据元素添加到linkedlist的首部，所以新结点 newNode将作为头结点，
// newNode的prev为null，数据域为e，next为f
final Node<E> newNode = new Node<>(null, e, f);
// 3.将新结点newNode的内存地址赋值给first，新结点 newNode作为头结点
first = newNode;
// 4.判断 f 是否为 null
if (f == null)
// f == null满足，说明当前linkedlist中只有一个新结点 newNode，则将newNode的内存地址赋值给last，此时头指针first和尾指针last均指向newNode结点
last = newNode;
else
// 由于当前链表为双向链表，所以将newNode的内存地址赋值给f.prev
f.prev = newNode;
// 5.size的值自增1
size++;
// 6. modCount的值自增1
modCount++;
}
上述代码中的注释已经很清楚了，相信大家都能理解。接着我们直接看下方式四，添加数据元素到当前linkedlist中指定的位置。简单说下方法中首先调用到checkPositionIndex方法用来检测位置index是否有效，接着判断index的值，如果index == size，则直接调用linkLast方法，将数据元素添加到当前linkedlist的尾部，否则调用linkBefore方法，添加数据元素到当前linkedlist中的指定位置。我们先来看下checkPositionIndex方法：
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
接着跟进去isPositionIndex方法：
/**
* Tells if the argument is the index of a valid position for an
* iterator or an add operation.
*/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
可以看到位置index的有效范围为index >= 0 && index <= size。我们回到add方法接着往下看，如果index == size，则直接调用linkLast方法，我们跟进去看下：
/**
* Links e as last element.
*/
void linkLast(E e) {
// 1.将尾指针赋值给 l 结点
final Node<E> l = last;
// 2.创建新结点newNode
final Node<E> newNode = new Node<>(l, e, null);
// 3.将新结点newNode的内存地址赋值给last，新结点 newNode作为尾结点
last = newNode;
// 4.判断 l 是否为 null
if (l == null)
// l == null满足，说明当前linkedlist中只有一个新结点 newNode，则将newNode的内存地址赋值给first，此时头指针first和尾指针last均指向newNode结点
first = newNode;
else
// 由于当前链表为双向链表，所以将newNode的内存地址赋值给l.next
l.next = newNode;
// 5.size自增1
size++;
// 6.modCount自增1
modCount++;
}
linkLast方法中的注释已经标注清楚了。当index != size时，会调用到linkBefore方法，linkBefore方法接收两个参数，第一个参数为将要添加的数据元素，第二个参数为当前index位置对应的结点。我们先来看下node方法，如何获取到当前index位置对应的结点的呢？
/**
* Returns the (non-null) Node at the specified element 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;
}
}
可以看到方法中同样是使用for循环来遍历的，只不过为了提高代码性能，首先将index位置的值和当前linkedlist的中间位置进行比较，将当前linkedlist分成了左右两部分，利用双向链表的特性，从前向后遍历或者从后向前遍历，获取到当前index位置对应的结点。接着我们看下linkBefore方法：
/**
* Inserts element e before non-null Node succ.
* e :将要添加的数据元素 succ :当前index位置对应的结点
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 1.将当前index位置对应的结点succ的prev赋值给pred，用来表示pre结点
final Node<E> pred = succ.prev;
// 2.创建新结点newNode，先进行新结点“连接”操作
final Node<E> newNode = new Node<>(pred, e, succ);
// 3.断开原有“连接” 后一端
succ.prev = newNode;
if (pred == null)
// 4.当 pred == null，说明当前操作为“插入头结点”，则将新结点newNode的内存地址赋值给first，新结点newNode作为头结点
first = newNode;
else
// 5.断开原有“连接” 前一端
pred.next = newNode;
// 6.size自增1
size++;
modCount++;
}
linkBefore方法中的注释已经很清楚了，我们需要明确，添加数据元素到linkedlist中指定的位置，涉及到链表的“中断重连”操作，必须先“连接”再“断开”。
上述我们分析了LinkedList的add一系列的操作方法，下面我们接着看下remove相关的方法：
/**
* 删除linkedlist的首部元素，并返回被删除的首部元素
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* 删除linkedlist的尾部元素，并返回被删除的尾部元素
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* 删除linkedlist中指定的元素
*/
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;
}
/**
* 删除linkedlist中指定位置的元素
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
在这里我们选择最后一个方法进行分析下，删除linkedlist中指定位置的元素。可以看到方法中同样先调用checkElementIndex方法进行index位置有效判断。接着调用到node方法，获取到指定index位置对应的结点，最后调用unlink方法，将对应结点作为参数传递过去。checkElementIndex方法和node方法我们已经分析过了，我们直接看下unlink方法：
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
// 1.获取到待删除结点的数据域和地址域
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 2.判断prev 是否为null
if (prev == null) {
// prev == null，则说明当前待删除的结点为头结点，需要将next结点的内存地址赋值给first 删除完毕后，next结点作为头结点
first = next;
} else {
// 将next结点的内存地址赋值给prev.next 并将删除结点的prev置为null 相当于“断开”双向链表的前一端
prev.next = next;
x.prev = null;
}
// 3.判断next是否为null
if (next == null) {
// next == null，则说明当前待删除的结点为尾结点，需要将prev结点的内存地址赋值给last 删除完毕后，prev结点作为尾结点
last = prev;
} else {
// 将prev结点的内存地址赋值给next.prev 并将删除结点的next置为null 相当于“断开”双向链表的后一端
next.prev = prev;
x.next = null;
}
// 4.将删除结点的数据域置为null
x.item = null;
// 5.size自减1
size--;
modCount++;
return element;
}
unlink方法中的注释已经标注的很清楚了。
下面我们看下set方法：
/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
可以看到set方法很简单，我们一起分析下。set方法接收两个参数，第一个参数为 位置index，第二个参数为index位置处需要设置的数据元素。方法中同样先对index位置做有效判断，然后调用node方法，获取到指定位置index处对应的结点 x，接着获取到 x 原有数据，并赋值给oldVal，之后将结点 x 的数据域重新赋值为element，最后return掉原有数据。
下面接着看get系列方法：
/**
* 获取当前linkedlist中的第一个数据元素
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* 获取当前linkedlist中的最后一个数据元素
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
/**
* 获取指定index位置对应的数据元素
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
在这里我们分析下getFirst方法，获取当前linkedlist中的第一个数据元素。可以看到，方法中直接使用到first头结点，如果头结点为null，则说明当前linkedlist中还没有数据元素，会直接抛出NoSuchElementException异常。否则直接将头结点数据元素return掉。
接着看下常用的contains方法：
/**
* Returns {@code true} if this list contains the specified element.
* More formally, returns {@code true} if and only if this list contains
* at least one element {@code e} such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return {@code true} if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
有没有很眼熟，其实linkedlist的contains方法和arraylist的contains方法差不多，在这里就不再赘述了。下面我们看下clear方法：
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
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++;
}
其实linkedlist中的clear操作就是从头结点开始进行一个for循环，分别将Node结点的数据域和地址域都置为null，最后将size归0。
关于linkedlist的源码分析到这里就结束了，其实linkedlist中还有好多方法没有讲到，比如peek()、poll()、offer()等方法，其实都大同小异，本质上都是对链表的操作，有兴趣的朋友可以翻看下。
