昨天大概看了ArrayList的源码实现，其实还是比较简单的。主要就是操作内部的数组，而用的也比较多的就是今天要看的LinkedList了，它相对于ArrayList具有更高的增加/删除效率，适合作为经常变动的列表使用，其读取的时间复杂度为O(n)。而ArrayList的读取时间复杂度为O(1)，变动多的话经常会导致数组的复制操作，所以更适合作为不经常变动的列表。
源码分析
不得不提的Node节点
/**
* 作为整个链表实现的核心封装，Node节点作为一个静态内部类使用，每一个插入的数据元素都被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;
}
}
之后所有关于LinkedList的操作其实都是关于Node的操作，理解Node节点就是理解LinkedList的基础，接下来我们还是从基本的类定义开始看。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
AbstractSequentialList ：为实现序列访问的数据储存结构的提供了所需要的最小化的接口实现(这接口主要是说明他是希望实现者通过顺序访问的)
Deque：双向列表(就是支持链表两头操作的意思)
接口不是讲解的重点，只有在需要的时候我才会去解读接口中的具体方法含义，如果一个一个接口跟进去的内容比较繁琐，而且意义也不大
属性值
//transient 关键字表示在序列化的时候并不会随着链表序列化为二进制数存储，可以这么做是因为即使反序列化后没有这些值，
//但是在改变链表结构的时候这些值又会重新生成，减少了不必要的字段也就减少了序列化的开销。
//源码编写者确实很精打细算。非常细微的地方都考虑到了
transient int size = 0; //链表长度
transient Node<E> first; //链表头节点
transient Node<E> last; //链表尾节点
构造函数
/**
* 其中空的构造函数我就不说了。。这个构造函数就是直接将Collection中的数据插入到链表中
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); //插入位置必须在[0,size]之间
//为了便利方便所以转换为数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//succ:index所在位置的Node引用,pred:index所在位置的前一个Node引用
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 //上一句已经将newNode的前节点指向pred，这次要将pred的后节点指向newNode了(注意是双向认定)
pred.next = newNode;
pred = newNode;//节点后移
}
if (succ == null) {
last = pred; //注意经过移动之后现在pred已经指向了新链表末尾的Node节点
} else { //因为是在succ这个节点原来的位置进行插入的，所以现在succ其实已经抛离整个链表了，需要跟新的前段链表重新连接一下
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++; //作用与ArrayList中的modCount一样
return true;
}
/**
* 即使一个简单的取下标的方法都很精致，考虑的前半段还是后半段(返回节点一定非空)
*/
Node<E> node(int index) {
if (index < (size >> 1)) { //如果index在链表的前半段就从头部开始查找，这里不用size/2是因为移位操作更快
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { //如果index在链表的后半段就从尾部开始查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
基本方法
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> oldTail = last;
final Node<E> newNode = new Node<>(oldTail , e, null);
last = newNode; //这里其实只要注意一下原来的链表是不是空链表就行
if (oldTail == null)
first = newNode;
else
oldTail.next = newNode; //没有if判断的话这里就报NPE了
size++;
modCount++;
}
因为linkFirst跟linkLast一模一样，所以我就不看了。
void linkBefore(E e, Node<E> succ) {
// 因为这是一个内部调用的方法，所以已经保证succ不为null
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)//如果succ是头结点
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
private E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // 是f没有其他的引用链，促进垃圾回收
first = next;
if (next == null) //如果原来链表只有一个节点的话
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
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) { //如果x节点是头结点
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) { //如果x节点是尾节点
last = prev;
} else {
next.prev = prev;
x.next = null; //取消x节点对于前后节点的引用
}
x.item = null;//还是使用置空的方式促进GC
size--;
modCount++;
return element;
}
现在为止基本的变更操作已经介绍完了，像removeLast，removeFirst，addFirst，addLast等等这些方法其实只要明白上面操作就完全够了。还有一些poll，take等方法都是基于以上的方法所讲，基本没有其他内容，就是有的报错有的不报错之类的差别。看一下其他典型的方法
public boolean removeLastOccurrence(Object o) {
//这里的核心内容就是判断所移除的对象是不是null，因为是null的话就没法使用equals方法比较
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//无参的toArray()没啥可看的，就是遍历然后赋值就可以
public <T> T[] toArray(T[] a) {
if (a.length < size) //如果a转不下链表内容的话就创建一个包含T类型元素的数组
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size) //注意这里的置空操作
a[size] = null;
return a;
}
public Object clone() {
LinkedList<E> clone = superClone();
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
//从这里看到这个克隆还是浅克隆,因为x.item还是原来的地址
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
接下来我们看一下Iterator的详细实现，通常遍历有两种方式，一种是通过for循环进行遍历，另外一种就是通过Iterator了，而且Iterator可以在遍历的过程中改变链表节点，但是在for循环过程中改变链表节点的话会有你喜欢的东西出现噢。。
private class ListItr implements ListIterator<E> //内部类ListItr
private Node<E> lastReturned = null; //记录本次操作的目标对象(next()返回是它，删除的话也是它)
private Node<E> next; //下一个遍历出的节点
private int nextIndex; //下一个节点的下标
private int expectedModCount = modCount; //用来判断在遍历过程中有没有节点变更
ListItr(int index) {//初始化的时候从下标为index的位置开始
next = (index == size) ? null : node(index);
nextIndex = index;
}
//下面这两个方法应该是我们最常调用的方法了
public boolean hasNext() {
return nextIndex < size;
}
//从这里我们就知道modCount的用途了，如果是for循环的话，循环过程中改变节点会改变modCount.
//因为for循环本质上还是靠Iterator来实现的，所以在遍历过程中发现节点变化就立马报错了
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next; //这个lastReturned主要是用来保存返回结果的
next = next.next;
nextIndex++;
return lastReturned.item;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
//这就解释了为什么遍历过程之中Iteraort的remove是可以的
public void remove() {
checkForComodification(); //操作开始时候的modCount与expectedModCount的相等还是要保证的
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
//正常情况两者是不会相等的，但是为了保证代码的健壮性我们要考虑这种操作，例如我在多线程情况下进行操作，调用next()方法到了
//第四行时候忽然切到另外一个线程，这时候其实next = lastReturned而且由于next()还没有运行到nextIndex++所以这里也就不用nextIndex--
//虽然LinkedList不是线程安全的，但是在这里尽量去保证其在多线程运行环境下的安全性
if (next == lastReturned)
next = lastNext;
else
nextIndex--; //删除了一个next前的元素,nextIndex--是必要的
lastReturned = null;
expectedModCount++; //在unlink中modCount++了，所以expectedModCount在这里也自增
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null) //如果插入位置在链表末尾的话
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
当然LinkedList内部还有一个DescendingIterator作为逆向遍历使用的，因为LinkedList是双向链表，所以不管正向还是逆向其实内部实现都是一样的，不需要再进行过多的关注了。
<strong>到这里其实LinkedList的整个实现都已经讲解清楚了，没有提到的方法往往是因为太过简单或者内容重复，凡是我觉得值得注意的地方我都进行了清晰的注释，如果有哪些大家觉得我理解有误的地方一定要在评论的时候写出来，我会积极参与讨论。</strong>
网友评论