【LinkedList】| 深度剥析Java SE 源码合集Ⅰ

一. 🦁 LinkedList介绍

LinkedList 底层用双向链表实现的存储。特点：查询效率低，增删效率高，线程不安全。
双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前
一个节点和后一个节点。 所以，从双向链表中的任意一个节点开始，都可以很方便地找到所有节点。

今天来探索一下LinkedList的源码分析，以便更熟悉Java容器的结构,了解其是如何存储元素的。
探索环境：jdk 11 & idea 2020

二. 🦁 结构以及对应方法分析

2.1 结构组成

由源码可知，LinkedList 不仅继承了AbstractSequentialList，还实现了List，Deque等接口。所以LinkedList除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用。

2.1.1 节点类

双向链表由节点类前后连接而成，所以源码中肯定存在该Node类。我们从源码中得知其节点类组成：

item：存储当前节点元素的信息
next：存储当前节点的下一个节点地址信息
prev：存储当前节点的前一个节点地址信息

  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;}}

2.1.2 成员变量

这里记录了LinkedList的节点数（size），头节点地址（first），尾节点（last）。

 transient int size = 0;/*** Pointer to first node.*/transient Node<E> first;/*** Pointer to last node.*/transient Node<E> last;

2.2 方法实现

2.2.1 添加add(E e)方法

从这里可知，这个add() 方法调用了linkLast(e)方法，返回一个布尔值。现在我们来看看这个linkLast(e)方法：

  /*** Links e as last element.*/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;elsel.next = newNode;size++;modCount++;}

从这个方法来看，add()方法的插入是尾插法，将last这个成员变量赋值给l（即l指向最当前节点）,新new一个节点变量newNode<>(l,e,null),并且将其前驱节点指向l，如果 l == null,则第一个节点是newNode；否则直接在当前节点l指向新节点newNode。（modCount是指修改次数）。

2.2.2 头尾添加元素

Ⅰ addFirst(E e)

我们可以看到这里直接调用了linkFirst(E e)方法。

 /*** Links e as first element.*/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;elsef.prev = newNode;size++;modCount++;}

这里是运用了头插法，将节点插入链表头部，依旧f和前面的l一样，指向当前节点（第一个节点）；然后new 一个新的Node<>(null,e,f),将新节点的后继节点指向当前节点。当前节点不为null的情况下，将当前节点的前驱节点指向新节点，这样一次插入完成。

Ⅱ addLast(E e)

尾插法同前面的add(E e)。

2.2.3 查找get(int index)方法

这里调用了两个方法，一个是 checkElementIndex(index)，该方法是用来检查用户输入的下标是否存在，如果不合法的话则会抛出 **IndexOutOfBoundsException(outOfBoundsMsg(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;}}

这个方法运用了一个技巧：如果index是小于一半LinkedList长度时，则从头节点开始遍历查找；相反如果index大于一半LinkedList长度时，则从尾节点开始查找，这也是双向链表的一个优点。

2.2.4 删除remove()方法

LinkedList的删除方法比较多，我们就来探索一个常用的remove()，由源码可知，这里调用了removeFirst()方法:

 /*** Removes and returns the first element from this list.** @return the first element from this list* @throws NoSuchElementException if this list is empty*/public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}

这里定义了f——>头节点，如果头节点为空，说明f为空，则说该LinkedList没有任何元素，则返回一个NoSuchElementException()错误。否则调用了unlinkFirst(f)方法。

 /*** Unlinks non-null first node f.*/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 GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}

这里先定义了一个next节点指向头节点的下一个节点，然后赋值头节点的元素和next指针为null（这里主要是减少GC垃圾回收的工作量，提高效率），然后让头节点的指针指向next节点，这样next节点则成为新的一个头节点。就删除了头节点啦，size–，返回element。

三. 🦁 总结

今天介绍了LinkedList源码剥析。分析了常用方法的源码结构组成，LinkedList的源码组成比较简单，只要对双向链表这一数据结构熟悉的话，阅读起源码还是非常轻松的，希望您喜欢，一键三连哦！🐇 😄 🐇