List之LinkedList源码
<h1>LinkedList简介</h1>
<pre><code>LinkedList最大的特点是它的数据结构，它的底层是使用链表结构实现。链表是线性表的一种。而链表又分为单向链表和双向链表，
链表又有循环与非循环之分，在jdk1.6中就是使用了双向循环链表的结构，而在jdk1.7和jdk1.8中改成了双向链表，也就是取消循环了。</code></pre>
<h2>链表结构</h2>
<pre><code>既然LinkedList的底层是链表结构 那就来看看各种链表把</code></pre>
<h3>单向链表</h3>
<pre><code>单向链表中每个节点都有一个指向下一个节点的指针next，最后一个节点的指针next指向null</code></pre>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/aba002e88fa9f15a23644ce58fd96c16" alt="" /></p>
<h3>单向循环链表</h3>
<pre><code>单向循环链表是通过最后一个节点（tail）的指针指向第一个节点（head），形成一个闭环</code></pre>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/5aa5f4af93ceb080d7eaa049b6e71dca" alt="" /></p>
<h3>双向链表（jdk1.6之后使用）</h3>
<pre><code>双向链表中每个节点都会有两个指针，pre指向前一个节点，next指向下一个节点，第一个节点的pre指向null，最后一个节点的next指向null，达到两个方向互通</code></pre>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/c0335c843faa745ee7877a5862ea32eb" alt="" /></p>
<h3>双向循环链表（jdk1.6）</h3>
<pre><code>第一个节点中的pre指向最后一个节点，最后一个节点中的next指向第一个节点，形成一个闭环，且双向互通</code></pre>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/f0ae0ea6198f712719d39ab3f94ab600" alt="" /></p>
<h1>LinkedList源码</h1>
<pre><code>先看看他的继承图</code></pre>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/1a5baab96634c6d0a3dd9b93e60a4a55" alt="" /></p>
<ul>
<li>继承AbstractSequentialList，该类对AbstractList进一步抽象，在迭代器的基础上实现增删改查，只能按次序访问，无法随机访问</li>
<li>实现Deque，Deque是一个双向队列，既可以先进先出，又可先进后出</li>
<li>实现Cloneable，实现Cloneable接口，就可以使用Object.clone()进行克隆了。</li>
<li>实现Serializable，实现序列化接口，说明该类能够启用其序列化功能。序列化其实就是持久化，将class转变为字节流传输，然后保存，反序列化就是读取
<h2>LinkedList的节点</h2></li>
</ul>
<hr />
<pre><code> LinkedList 是node节点有三个属性；</code></pre>
<hr />
<blockquote>
<ul>
<li>item 存储该节点的元素element</li>
<li>next 存储该节点指向下个节点的指针next</li>
<li>prev 存储该节点指向上个节点的指针prev</li>
</ul>
</blockquote>
<h2>LinkedList的构造方法</h2>
<pre><code> LinkedList 有两种构造方法 一种是无参构造，另一种是LinkedList(Collection<? extends E>) 允许传入一个集合</code></pre>
<h2>LinkedList的add（六种）</h2>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/fbe069403832ce4128c10bae9490fd96" alt="" /></p>
<pre><code>1. 第一种add(E)方法默认往linkedList末尾添加新元素</code></pre>
<p><strong> 过程就是：new一个新的节点 newNode，将 prev 指针指向 l ，e 作为新节点元素，next 指向 null，新添加的 newNode 变为该 LinkedList 的最后一个节点 last 若 l 节点不存在，则将新节点 newNode 作为第一个节点 first 若 l 节点存在，将 l 节点的 next 指针指向 新节点 newNode </strong></p>
<ol>
<li>
<p>第二种add(int, E) 方法在指定位置添加新的元素
在调用linkBefore之前。node（index）会有一些处理</p>
<pre><code class="language-java">
public void add(int index, E element) {
checkPositionIndex(index); //对指定元素位置进行合理性检查
if (index == size)
linkLast(element); //index == size 时，调用 linkLast 方法将元素添加到 linkedList 末尾
else
linkBefore(element, node(index)); //调用 linkBefore 方法
}
//元素位置越界检查异常处理
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//判断元素位置是否合理
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}</code></pre>
</li>
</ol>
<pre><code>再看看 linkBefore() 方法的实现：
```java
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
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++;
}</code></pre>
<pre><code>在linkedList中没有下标的概念，但是它又能够在指定的位置插入元素，看完上面的代码，
很显然它是通过遍历找到指定位置的元素，这里作者巧妙的利用了二分法，让遍历的效率提高一倍</code></pre>
<p><strong>这个 linkBefore 方法实现原理与 linkLast 方法类似，将新节点 newNode 的 prev 指针指向指定位置的节点 succ 的前一个节点 pred ，而 succ 的 prev 指针变为指向新节点 newNode， 而新节点 newNode 的 next 指针则指向 succ ，pred 节点的 next 指针指向 newNode ； 这里文字有点绕， 简单点讲: 就是将新节点 newNode 插入 指定节点 succ 的位置，再将它们的指针重整。</strong></p>
<pre><code>3. 第三种addAll(Collection<? extends E> c)</code></pre>
<p>方法内部调用的是addAll(int index, Collection<? extends E> c) 方法，这里只分析后一个addAll(int index, Collection<? extends E> c) 方法： 在指定位置插入一个集合，linkList有改动返回true，否则返回false</p>
<pre><code class="language-java"> public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); //指定位置合理性检查
Object[] a = c.toArray(); // 将指定集合转换成数组 a
int numNew = a.length; // 保存数组的长度
if (numNew == 0)
return false; // 数组没有元素返回false
Node<E> pred, succ; // 定义 pred 和 succ 节点，将要在这两个节点中间插入新的节点
if (index == size) {
succ = null; // 当指定位置 index 等于链表长度时，该插入位置为链表末端，不存在 succ 节点
pred = last; // 则 pred 为最后一个节点 last
} else {
succ = node(index); // 将指定位置index的节点赋值给 succ
pred = succ.prev; // succ 的 prev 指针指向 pred
}
for (Object o : a) { // for 循环遍历 a 数组
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null); // 将新节点 e 的 prev 指针指向 pred 节点，next 指针先指向 null ，得到新节点 newNode
if (pred == null) // 不存在前一个节点 pred 时
first = newNode; // 则新节点 newNode 为链表头一个节点 first
else
pred.next = newNode; //存在前一个节点 pred 时，pred 的 next 指针指向新节点 newNode
pred = newNode; // 最后将新节点赋值为 pred 供下次循环使用，逐个将数组 a 中的元素插入到链表中
}
if (succ == null) { // 遍历完后，如果不存在 succ 节点
last = pred; // 则数组 a 中最后一个元素 pred 就是链表末端最后一个节点 last
} else { // 如果存在 succ 节点
pred.next = succ; // 则数组 a 中最后一个元素 pred 节点的 next 指针指向 succ 节点
succ.prev = pred; // succ 的 prev 指针指向 数组 a 中最后一个元素 pred 节点
}
size += numNew; // 更新链表长度
modCount++;
return true; // 链表改动，返回 true
}</code></pre>
<p><strong>小结： addAll 方法实现步骤：①传入指定的集合转换为数组；②遍历该数组逐个插入到链表中</strong></p>
<ol>
<li>第四种addFirst(E) 和 addLast(E) 一个是头插，一个是尾插 分别调用了 linkFirst(E) 和 linkLast(E)
<strong>只要读懂前面的分析过程，这里就很容易了，当我们要往链表头部插入一个新的节点时，我们只要将新节点的 prev 指针指向 null ，next 指针指向原链表的第一个节点，如此，指定的新元素就成为链表的第一个节点 first ；在链表尾部插入新元素也是同理，只是指针的方向改为指向 last 节点就可以了</strong>
<h2>LinkedList的删除（七种）</h2>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/9f54db87b131ff185a2dafed43d3a6a5" alt="" /></p></li>
<li>
<p>第一种 remove() remove() 方法删除链表的第一个元素</p>
<pre><code class="language-java">/**
* Retrieves and removes the head (first element) of this list.
* 检索并删除列表的头部第一个元素
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
public E remove() {
return 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(); //first 节点为 null 时，说明该链表上没有元素，抛出异常
return unlinkFirst(f);
}
/**
* first 节点不为空时，断开 first 节点指针
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item; // 将指定删除节点的元素 item 赋值给新定义的 element ，在方法结束时返回 element
final Node<E> next = f.next; // 将 f 节点的 next 指向的节点赋值给新定义的 next 节点
f.item = null; // first 节点的 item 设置为 null
f.next = null; // first 节点的 next 设置为 null
first = next; // first 节点的下一个节点 next 作为第一个节点 first
if (next == null)
last = null; // next 节点为 null 时，说明链表只有一个节点 first ，不存在节点 last ，所以 last 要设置为 null
else
next.prev = null; // next 在这里作为删除 first 节点后的第一个节点，故 next 的 prev 指针应该指向 null
size--; // 链表长度减一
modCount++;
return element; // 最后返回指定删除的元素 element
}</code></pre>
<p>remove() 方法实现大致分为三步：
<strong>1. 将第一个节点保存起来，方法结束时返回</strong>
<strong>2. 断开第一个节点的所有指针</strong>
<strong>3. 将第一个节点的下一个节点 next 设置为第一个节点 first</strong></p>
</li>
<li>第二种 remove(int) remove(int) 方法删除指定位置的一个元素</li>
</ol>
<pre><code class="language-java"> public E remove(int index) {
checkElementIndex(index); //指定位置的合理性检查
return unlink(node(index)); // node(index) 上面分析过，返回 index 位置的的节点，接着调用 unlink 方法
}
/**
* 删除指定不为空的元素
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item; // 将指定位置节点 x 的属性 item 保存为 element ，方法结束时返回 element
final Node<E> next = x.next; // 将 x 节点的 next 指针指向新定义的 next 节点
final Node<E> prev = x.prev; // 将 x 节点的 prev 指针指向新定义的 prev 节点
if (prev == null) {
first = next; // 当 prev 指针指向 null 时，说明指定删除的节点位置为链表首节点 first ,将 next 节点设置为 first 节点
} else {
prev.next = next; // 否则将 next 节点设置为新定义的 prev 节点的 next 节点
x.prev = null; // 断开指定删除节点的 prev 指针指向的节点
}
if (next == null) {
last = prev; // 当 next 指针指向的节点为 null 时，prev 节点作为最后一个节点 last
} else {
next.prev = prev; // 否则将 prev 节点设置为新定义的 next 节点的 prev 节点
x.next = null; // 断开指定删除节点的 next 指针指向的节点
}
x.item = null; // 将指定删除的节点的 item 属性设置为 null，让 GC 清理
size--; // 链表长度减一
modCount++;
return element; // 最后返回 element 元素
}</code></pre>
<pre><code>remove(int index) 方法大致分为以下五步：</code></pre>
<p><strong>1. node(index) 获取到指定位置的节点</strong>
<strong>2. 调用 unlink 方法，将指定位置节点传入</strong>
<strong>3. 将指定位置节点的 item 属性保存为 element ，方法调用完毕返回该元素</strong>
<strong>4. 断开指定位置节点的所有指针</strong>
<strong>5. 将指定位置节点的左右节点连接</strong></p>
<pre><code>3. remove(Object o) LinkedList remove(o) 方法支持传入一个Object类型，如果链表中包含指定元素，则删除，返回 true；如果不包含则返回 false</code></pre>
<pre><code class="language-java"> public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) { // 传入的参数为 null 时，从 first 节点开始 for 循环遍历整个链表
if (x.item == null) { // 当节点的 item 属性为 null 时
unlink(x); // 删除该节点（unlink方法上面分析过）
return true; // 返回 true
}
}
} else { // 要删除的元素不为 null 的情况
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) { // equals 方法判断元素是否同一元素
unlink(x); // 同一个元素，则删除该元素
return true; // 返回 true
}
}
}
return false; // 如果指定删除的元素在链表中不存在时，返回false
}
</code></pre>
<p><strong>这里需要注意的是，在LinkedList 中可以存在 null 值的，而这个 null 值是存储在节点的 item 属性中，节点还有 prev 和 next 指针分别指向前一个元素和后一个元素，prev 和 next 不是空的，所以这也是LinkedList 中可存放 null 值的合理性因素。</strong></p>
<pre><code>4. 其余几种removeFirst() 和 removeLast() 首尾删除与首尾插入对应</code></pre>
<blockquote>
<p>removeFirstOccurrence(Object o) 和 removeLastOccurrence(Object o)</p>
</blockquote>
<p><strong>这两个方法与 remove(Object o) 方法相似，只不过remove(Object o) 默认从链表头部开始遍历删除第一次出现的指定元素，removeFirstOccurrence(Object o) 就是调用了remove(Object o) 方法；而removeLastOccurrence(Object o) 实现了从链表尾部开始遍历删除指定元素，看到源码，我们可以知道它的实现方式与 remove(Object o) 相似，不同的是遍历的方向相反而已。</strong></p>
<p><strong>
总的来说：
LinkedList 支持链表首末添加/删除元素操作
LinkedList 支持指定位置插入/删除元素
LinkedList 允许删除指定元素
LinkedList 支持存放 null 值</strong></p>
<h2>LinkedList的修改</h2>
<pre><code>set(int index, E element) 将链表中指定位置 index 的元素替换成指定元素 element
LinkedList 的数据都是存储在每个节点的 item 属性当中，我们修改数据时，只要修改对应位置节点的 item 属性就行了。</code></pre>
<h2>LinkedList的查</h2>
<pre><code>get(int) 方法允许获取链表中指定位置的元素。</code></pre>
<blockquote>
<p>get(int) 方法的实现调用了 node(index) 方法。方法内部主要是根据指针 for 循环遍历找到对应位置的节点，显然这种查找方式效率很慢，任何事情都不能做的完美，在这种数据结构下，已经决定了它自身的查找效率是个短板。作者希望能够尽可能的提高它的查询效率，在遍历之前使用了二分法，查找效率提高了一倍。</p>
</blockquote>
<h3>总结：</h3>
<p><strong>LinkedList 在头部或尾部添加元素，复杂度为 O(1)
LinkedList 随机添加元素，涉及到指针的指向操作（参考本文3.4.2 node(index) 方法分析），复杂度为 O(n)
LinkedList 删除元素，在头部尾部删除元素，复杂度为 O(1)
LinkedList 指定位置删除元素，需要先查找到该位置的元素，涉及到指针的指向操作，复杂度为 O(n)
LinkedList 改操作（set方法），需要先查找到该位置的元素，涉及到指针的指向操作，复杂度为 O(n)
LinkedList 查操作（get(int)方法），需要先查找到该位置的元素，涉及到指针的指向操作，复杂度为 O(n)
linkedList 所有操作都不是原子操作，线程不安全。
</strong></p>