Java源码学习--LinkedList
Java源码学习--LinkedList
上次我们分析了ArrayList的源代码，今天就来分析一下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;
}
}
嗯，好像没啥出奇的样子，朴素至极。
重要属性：
- size：同ArrayList中的size，代表该List中元素的个数
- first：为一个Node对象，代表双向链表的头部
- last：为一个Node对象，代表双向链表的尾部
LinkedList和ArrayList相比，在属性上面少了很多。
二、重要方法及其详情
1. 链点的操作方法
和ArrayList不同的是，由于LinkedList内部维护了一个双向链表，所以几乎所有操作都需要操作链点，所以LinkedList的源代码中刚开始就是一系列的链点的添加和删除的操作：linkXXX代表添加节点，unLinkXXX代表删除节点。
linkFirst
该方法是将加入的链点作为表头：
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++;
}
需要注意的是当first为null的时候，说明此时LinkedList中还没有元素，所以加入的这个元素不仅是表头还是表尾。
linkLast
该方法是将加入的链点作为表尾：
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++;
}
和linkFirst是一个模子里刻出来的。
linkBefore
看名字就能够猜出来，是将节点插入到指定节点之前：
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
看到这里我们就能够发现LinkedList中的双向链表的性质了。
LinkedList中双向链表的性质：
1. 初始时first和last都为空
2. first的prev以及last的next永远都是null
3. 除了first和last外，其他所有节点的prev和next永远不可能为null；反之，如果有一个节点的prev为null则它为first节点；如果是next为null，那么它是last节点
据此，实际上只有两种情况需要特别注意：
- 当添加链点后，LinkedList只有一个元素，此时需要注意last的值
- 当删除链点时，LinkedList此时只有一个元素，此时需要注意first的值
unlinkFirst
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;
}
unlinkLast
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;
}
unlink
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;
}
2. 重点方法
add(E e)
上面列出所有链点的操作之后其实add操作已经开始变得索然无味了：
public boolean add(E e) {
linkLast(e);
return true;
}
没有任何自己的特色，完全就是linkLast，该操作几乎不耗时，因为就是单个元素的操作。
node方法--根据索引查找元素的根本方法
这个方法在LinkedList中被调用的次数很多，它可以根据索引来从链表中得到元素：
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;
}
}
刚开始没看明白那个if条件是啥意思，一直以为是保证index不会越界，但是查资料才发现这里是一个优化会根据index的大小决定从后往前还是从前往后进行遍历所以理论上这里的复杂度是n/2
addAll
这个方法用来批量添加元素：
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
// 第一个参数代表collection中第一个元素插入的位置
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;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
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;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
注意，由于这里用到了node(index)方法，所以在元素大量的情况下还是有一定的耗时的。
add--在指定位置添加
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
当插入的位置不是末尾时，耗时还是集中在node(index)上
remove
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;
}
根据对象进行删除的方法是有一些耗时的，其原因和ArrayList一样，都是因为需要for循环来遍历所有的元素找到需要删除的对象才能删除，同样LinkedList中的泛型类需要实现equals方法
remove--删除指定位置的元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
耗时是因为执行了node(index)
get与set
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;
}
耗时是因为执行了node(index)
clear
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++;
}
我没看之前相当然的认为直接把first和last都赋值为null不就行了啊，但是人家还是一个for循环将List中所有的节点都设置为了null，从而使得GC能够快点释放资源，值得学习。
3. 重要方法--二
上面的方法都是我们将它作为一个List看待时常用到的方法，同时上面的方法没能体现其内部是一个双向链表的特点，而这里的方法就充分利用了双向链表的优点，可以认为我们使用LinkedList就是为了调用这些方法来实现我们的要求，而不是上面那些ArrayList就能够做到的方法。
获取头节点
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E element() {
return getFirst();
}
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
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);
}
获取头结点的方法有这么多，其中有一半完全和另一半没啥区别，也不知道这么做的原因是啥。
首先getFirst和element都是返回头结点，但是当List中没有元素的时候会抛出异常，而peek、peekFirst、poll、pollFirst在list中没有元素的时候返回null；但是poll、pollFirst在返回头结点的同时会将头结点删除
获取尾节点
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
他们三个的关系和获取头结点时是相同的。
添加节点
public void addFirst(E e) {
linkFirst(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public void push(E e) {
addFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
public boolean offer(E e) {
return add(e);
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
删除节点
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
public E remove() {
return removeFirst();
}
public E pop() {
return removeFirst();
}
上面的添加和删除节点方法根据特性结合使用可以实现队列、栈等数据结构。
小结：这里的方法充分利用了双向链表的优势，只从头和尾节点进行操作，其时间复杂度都是O(1)
三、迭代器实现
LinkedList的迭代器和ArrayList相比，思想如出一辙：
- lastReturned：该属性是一个Node对象，表示上一次执行next()方法返回的值。
- next：该属性是一个Node对象，表示下一个元素
- nextIndex：该属性是一个int，表示next属性对应的位置
- expectedModCount：该属性和ArrayList的同名属性是一个意思
private class ListItr implements ListIterator<E> {
...
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++;
}
.....
}
实际上和ArrayList对比会发现，LinkedList的迭代器没有什么特色之处，同样使用迭代器遍历的时候，只能够调用迭代器的add、remove方法进行增删操作，不能直接调用LinkedList对象进行操作
3. LinkedList遍历方法对比
在ArrayList中手动for循环进行是最快的(因为不用对index进行检查)；但是在LinkedList中，这是最慢的，因为node(index)会遍历所有元素，这大大增加了开销。
四、总结
我们应该倾向于在构建栈、队列两种数据结构时使用LinkedList，而且是使用其特色方法(体现了双向链表特点的方法，peek、push等)，尽可能避免使用参数中需要指定位置的方法(其内部的node(index)方法是for循环查找，效率低下，并没有体现双向链表的优势)，最后，严禁对LinkedList使用for循环遍历。
再者，对于需要频发插入数据而不需要取出数据的线性数据结构，LinkedList是一个好的选择，因为它的插入操作就是链表的插入操作，时间复杂度为O(1)，但是它的node(index)却耗时为O(n)
