共计 9411 个字符，预计需要花费 24 分钟才能阅读完成。
LinkedList 源码深度分析
LinkedList 继承体系
首先先直观的看一下 LinedList 的继承体系和实现的接口
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable- 实现了
List接口，这个接口定义了一些常见的容器的办法，比方add、addAll、get、set、contains、sort等等。 - 实现了
Deque接口，这个接口你能够简略的认为是一个双端队列，中间都能够进能够出，它定义的办法有getFirst、getLast、addFirst、addLast、removeFirst、removeLast等等。 - 实现
Cloneable和Serializable接口次要是为了可能进行深拷贝和序列化，这个问题咱们后续再谈。 AbstractSequentialList次要是给一些接口办法提供默认实现。
依据上篇文章的剖析，咱们很容易晓得链表作为一个容器必定须要将数据退出到容器当中，也须要从容器当中失去某个数据，判断数据是否存在容器当中，因而有 add、addAll、get、set、contains、sort 这些办法是很天然的。此外 LinedList 实现的是双向链表，咱们很容易在链表的任意地位进行插入和删除，当咱们在链表的头部和尾部进行插入和删除的时候就能够满足 Deque 的需要了（双端队列须要可能在队列的头和尾进行出队和入队，就相当于插入和删除），因而 LinedList 实现 getFirst、getLast、addFirst、addLast、removeFirst、removeLast 也就很容易了解了。
LinkedList 整体构造
LinkedList次要几个字段
transient int size = 0; // 用于记录链表当中节点的个数，也就是有几个数据
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first; // 指向双向链表的头结点
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last; // 指向双向链表的尾节点
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;
}
}依据下面的字段剖析，LinkedList内部结构次要如下：
链表当中有 first 和last字段次要指向链表当中第一个节点和最初一个节点，如果链表当中没有节点，那么他们都是null，如果链表当中有一个节点他们指向同一个节点，如果链表中节点个数大于 2，他们别离指向第一个节点和最初一个节点。
LinkedList 重要办法
add办法，这个办法次要是向链表尾部减少一个元素，作用和linkLast统一。
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 这个办法次要是向链表尾部减少一个元素，作用和 linkLast 统一
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
// 这个办法和咱们上篇本人的写的办法根本截然不同
final Node<E> l = last;
// l 作为新节点的前驱节点，因为是在链表最初减少一个元素，因而它的下一个元素是 null
final Node<E> newNode = new Node<>(l, e, null);
// 新节点是最初一个节点，因为是往链表节点插入
last = newNode;
if (l == null) // 如果是第一个退出一个节点（初始是 first 和 last 节点都是空），给 first 赋值
first = newNode;
else
l.next = newNode;
size++; // 因为是往链表当中减少一个节点，因而链表中数据的个数 +1
modCount++; // 这个字段次要是用于 fast-fail 的，这个咱们在前面将持续谈到
}
linkBefore和linkLast的作用相同，是在某个节点后面插入数据e，大体和后面的linkLast办法统一。
/**
* Inserts element e before non-null Node succ.
*/
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++;
}
unlink次要是用于删除某个节点。
/**
* Unlinks non-null node x.
*/
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;
// 如果前一个节点为 null 阐明被删除的就是首节点，因而须要跟新首节点为原来节点的下一个节点，也就是 next
if (prev == null) {first = next;} else {
prev.next = next;
x.prev = null;
}
// 同样的，如果 next 为 null，那么被删除的节点就是为节点，因而须要更新 last 为被删除节点的上一个节点
if (next == null) {last = prev;} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
unlinkFirst，删除链表当中第一个节点
private E unlinkFirst(Node<E> f) {
// f 示意头结点，且 f 不等于 null
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next; // 头结点变成 f 的下一个节点
if (next == null)
last = null;
else
next.prev = null;
size--; // 删除一个节点链表当中数据少了一个，因而 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;
}
remove办法，删除链表当中的某个元素
public boolean remove(Object o) {
// 如果元素为 null，就删除链表当中第一个值为 null 的元素
// 从这里也能够看出 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 false;
}
node办法，依据下标找到对应的元素
Node<E> node(int index) {
// 找到第 index + 1 个元素
// 判断对应地位的元素是离链表头部近还是离链表尾部近，哪头近就从哪头遍历
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;
}
}
get办法，通过下标index失去对应的元素
public E get(int index) {
// 这个函数的次要目标是查看 index 是否非法，次要判断是否小于 0 或者大于等于链表当中元素的个数
checkElementIndex(index);
return node(index).item; // node 函数在下面曾经提到了
}
private void checkElementIndex(int index) {if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {return index >= 0 && index < size;}
addAll办法，将一个汇合中的所有元素退出到链表的指定地位当中
public boolean addAll(int index, Collection<? extends E> c) {checkPositionIndex(index); // 这个函数和 checkElementIndex 一样都是用于检测 index 是否非法的
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
// 首先找到 index 对应地位的节点 succ 和他的前驱节点 pred
if (index == size) {
succ = null;
pred = last;
} else {succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
// 遍历每个数据产生新的节点 节点的前驱节点为 pred 后驱节点为 null
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
// 更新 pred 节点为 新退出的节点，而后持续插入
pred = newNode;
}
// 将新插入的所有节点和原来的节点拼接上
if (succ == null) {last = pred;} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
整个过程如下图所示：
进行插入之前：
插入之后：
set办法，更新某个下标的数据item
public E set(int index, E element) {checkElementIndex(index); // 判断下标是否非法
Node<E> x = node(index);
E oldVal = x.item;
x.item = element; // 更新数据
return oldVal; // 返回旧数据
}get办法，通过下标获取数据
public E get(int index) {checkElementIndex(index); // 判断下标是否非法
return node(index).item; // 取出对应的数据
}以上次要介绍了 LinkedList 当中次要的一些办法和其次要的工作机制，其余的一下办法都比较简单，大家能够自行参考 LinkedList 源代码。
LinkedList 类杂谈
本大节次要介绍在 LinkedList 当中除了链表之外的其余的比拟重要的知识点，帮忙大家了解一些司空见惯然而又可能没有认真思考过的点！！！
toString 办法重写
咱们首先来看一下上面代码的输入
public class CodeTest {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10; i++) {list.add(i);
}
System.out.println(list);
}
}
// 输入后果：// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]执行下面一段代码咱们能够在控制台看见对应的输入，咱们晓得最终打印在屏幕上的是一个字符串，那这个字符串怎么来的呢，咱们打印的是一个对象，它是怎么失去字符串的呢？咱们能够查看 System.out.println 的源代码：
public void println(Object x) {String s = String.valueOf(x);
synchronized (this) {print(s);
newLine();}
}从上述代码当中咱们能够看见通过 String s = String.valueOf(x); 这行代码失去了一个字符串，而后进行打印，咱们在进入 String.valueOf 办法看看是如何失去字符串的：
public static String valueOf(Object obj) {return (obj == null) ? "null" : obj.toString();}
咱们能够看到如果对象不为 null 最终是调用对象的 toString 办法失去的字符串。因而当打印一个对象的时候，最终会打印这个对象的 toString 办法返回的字符串。
咱们在 LinkedList 类中搜寻 toString 办法，发现这个办法是存在于 AbstractCollection 类当中，也就是上面这个类，LinkedList继承于它：
toString办法的源代码如下所示：
public String toString() {
// 失去链表的迭代器
Iterator<E> it = iterator();
// 如果链表当中没有数据则返回空
if (! it.hasNext())
return "[]";
// 额，写这个代码的工程师应该不懂中文 哈哈哈
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {E e = it.next();
// 将对象退出到 StringBuilder 当中，这里退出的也是一个对象
// 然而在 append 源代码当中会同样会应用 String.ValueOf
// 失去对象的 toString 办法的后果
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
}
从下面的代码咱们能够看出所有继承自 AbstractCollection 的类的 toString 办法都是在方括号外面填入汇合中对象的 toString 后果。
equlas 办法重写
当咱们去比拟两个链表是否相等的时候咱们通常去应用 equlas 办法。比方比拟两个字符串对象是否相等：
public static void stringEqualsTest() {String s1 = new String("一无是处的钻研僧");
String s2 = new String("一无是处的钻研僧");
System.out.println(s1 == s2);
System.out.println(s1.equals(s2));
}
// 输入
// false
// true其中 == 比拟的是两个对象的内存地址（也就是 s1 和s2指向的两个对象）是否雷同，也就是 s1 和s2是否是同一个对象，equals比拟的是两个字符串对象的内容是否雷同（不同的类实现形式不一样可能有差别，字符串 String 实现形式是只有内容雷同 equlas 办法就返回true，否则返回false），上述代码在内存当中的布局大抵如下：
==比拟的是两个箭头指向的内容的内存地址是否统一，equlas依据具体的类的实现有所差别。
当初咱们来看一下 LinkedList 类是如何实现 equlas 办法的，和 toString 办法一样，equlas办法也是在类 AbstractCollection 当中实现的。
public boolean equals(Object o) {if (o == this)
return true;
if (!(o instanceof List))
return false;
ListIterator<E> e1 = listIterator();
ListIterator<?> e2 = ((List<?>) o).listIterator();
while (e1.hasNext() && e2.hasNext()) {E o1 = e1.next();
Object o2 = e2.next();
if (!(o1==null ? o2==null : o1.equals(o2)))
return false;
}
return !(e1.hasNext() || e2.hasNext());
}
下面代码的次要流程：
- 首先判断
o和this是否是同一个对象，如果是则返回true，比方上面这种状况：
LinkedList<Object> list = new LinkedList<>();
list.equals(list);- 如果对象没有实现
List接口返回false。 - 一一判断链表外面的对象是否相等（调用链表当中存储的对象的
equals办法），如果两个链表当中节点数目一样而且都相等则返回true否则返回false。
通过下面的剖析咱们能够发现 LinkedList 办法并没有让比拟的对象是 LinkedList 对象，只须要实现 List 接口并且数据数目和内容都雷同，这样 equals 办法返回的后果就是true，比方上面代码就验证的这个后果：
LinkedList<Integer> list = new LinkedList<>();
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 10; i++) {list.add(i);
arrayList.add(i);
}
System.out.println(list.equals(arrayList)); // 后果为 true克隆 (clone) 办法重写
当咱们想要克隆一个对象的时候咱们通常会应用到这个办法，这个办法通常是将被克隆的对象复制一份，咱们来看一下 LinkedList 的clone办法。
@SuppressWarnings("unchecked")
private LinkedList<E> superClone() {
try {
// 这里返回一个新的 LinkedList 空对象
return (LinkedList<E>) super.clone(); // 这里的 super.clone() 是 protected native Object clone() throws CloneNotSupportedException; 本地办法} catch (CloneNotSupportedException e) {throw new InternalError(e);
}
}
public Object clone() {
// 这里失去一个新的 LinkedList 空对象
LinkedList<E> clone = superClone();
// 空对象初始化
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// 将所有的元素退出到新的 LinkedList 对象
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
通过下面的代码咱们能够晓得 LinkedList 的克隆办法创立了一个新的链表然而没有扭转外面的数据，因而如果你批改克隆链表中的数据的话，原来的链表外面的数据也会改，比方：
import java.util.LinkedList;
class Person {
String name;
public String getName() {return name;}
public void setName(String name) {this.name = name;}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
'}';
}
}
public class LinkedListTest {public static void main(String[] args) {LinkedList<Person> list = new LinkedList<>();
Person person = new Person();
person.setName("一无是处的钻研僧");
list.add(person);
LinkedList<Person> o = (LinkedList) list.clone();
System.out.println(o.get(0) == list.get(0));
System.out.println(o.get(0));
System.out.println(list.get(0));
o.get(0).setName("LeHung");
System.out.println(o.get(0) == list.get(0));
System.out.println(o.get(0));
System.out.println(list.get(0));
}
}
// 输入后果：true
Person{name='一无是处的钻研僧'}
Person{name='一无是处的钻研僧'}
true
Person{name='LeHung'}
Person{name='LeHung'}以上就是对 LinkedList 的源码剖析，我是 LeHung，咱们下期再见！！！
关注公众号：一无是处的钻研僧，理解更多计算机常识
正文完