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)); }}// 输入后果：truePerson{name='一无是处的钻研僧'}Person{name='一无是处的钻研僧'}truePerson{name='LeHung'}Person{name='LeHung'}以上就是对LinkedList的源码剖析，我是LeHung，咱们下期再见！！！
关注公众号：一无是处的钻研僧，理解更多计算机常识