关于java:JDK成长记5LinkedList初探

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>LinkedList 初探 </span></h3></div>

作为 Java 工程师，LinkedList 你可能用的不多，大多你总是在 new ArrayList。面试很多时候总是拿 LinkedList 和 ArrayList 的做比照。总会问你 ArrayList 和 LinkedList 的区别是什么？它俩是不是线程平安的？等等。很多时候你的习惯了应用 ArrayList，都很少思考应用 LinkedList。你可能都不晓得他能够用作内存队列或者栈。再接下来的几节中，你就能够学习到 LinkedList 的底层各种源码的原理，练习之前学习到办法剖析源码。

首先先让咱们回顾下 LinkedList 的基础知识。

1）LinkedList 基本原理

一句话讲，在 JDK 中，LinkedList 底层基于一个 双向链表 来保护数据，JDK 1.7 以前是一个双向循环链表。

2）LinkedList 优缺点

毛病：

随机拜访性能差

长处：

频繁插入和删除元素性能很好，容量没有限度
可用作内存队列或者栈
有程序性

你第一步应该做什么呢？对，没错，看下 LinkedList 的源码脉络：

第一张图中，你能够看到只有三个成员遍历 size、fisrt、last。除了 size，其余两个变量都是 Node 类型，能够猜想 Node 应该是它一个外部类。剩下的就是咱们罕用的构造函数、add、get、set、remove 等办法了，最初还有一些 toArray、addAll、indexOf 等办法和 ArrayList 的 API 很像。

第二张图如下：

这张图外面，能够看到有一些 pop、push、poll、offer 这些办法，如果你相熟数据结构的话，这些办法名字很像是队列数据结构入队，出队和栈构造的入栈、出栈罕用的办法名。接着就是 ListItr、Node 两个外部类了。

当你看过 LinkeList 源码的脉络后，接下来是不是应该简略写一个 Demo，从它的入口开始，看下他的外围源码呢？

你应该记得之前咱们提到过，看外围源码个别是从入口开始，也就常说的自顶而下。

首先你要有个代码 Demo。当你应用 LinkedList 的时候，个别是不是先创立，之后会调用 add 办法呢？来看下如下代码清单：

import java.util.LinkedList;

public class LinkedListDemo {public static void main(String[] args) {LinkedList<String> hostList = new LinkedList<>();

  hostList.add("host1");

  hostList.add("host2");

  hostList.add("host3");
}
}

这个很简略的代码，入口是 main 函数，第一行就是创立了一个 LinkedList，外面的元素都是 String 类型，应用默认无参的构造函数，你点击构造函数，进入源码来看看：

/**

* Constructs an empty list.

*/

public LinkedList() {}

什么都没干，从正文上看进去，结构了一个空的 LinkedList。之前你可能会留神到有一个 size 变量，你能够猜到，其实 LinkedList 没有大小限度，实践上内存足够，能够有限链接上来。下面的代码执行实现后，之前温习过 LinkedList 是一个双向链表，所以会造成如下的图：

接着 main 函数执行下一行，执行 add 办法：

public boolean add(E e) {linkLast(e);

   return true;

}

间接调用了 linkLast 办法，之后返回 true 了。

所以须要看下 linkLast 办法源码。终于，看到了重点，这个办法的脉络，有两个 last 和 first 成员变量，先弄了一个 newNode，之后有一个 if-else 判断，之后 size++ 就返回了。看上去如同很简略。

transient Node<E> first;

transient Node<E> last;

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;

   else

     l.next = newNode;

  size++;

  modCount++;

}

然而这个 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;

   }

}

你能够画一个图来了解下：原来 Node 就是一个外部类，有一个 item 元素，Node 类自身有一个 next 和 prev 是 Node 对象。

这个构造有没有很相熟？如果你对数据结构比拟相熟的话，或者你晓得 LinkedList 的底层数据是双向链表，你就能够 连蒙带猜 的想到，这个应该就是 LinkedList 底层代表双向链表的封装类。

prev 和 next 是两个指针，指向了前一个节点和后一个节点。item 是一个泛型，应该是寄存对应的数据元素的。心愿这个数据结构你没有还给大学老师。

你晓得了 Node 是什么后，再来看下 linkLast 办法的源码, 可能一开始不好间接了解。

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;

   else

      l.next = newNode;

   size++;

   modCount++;

}

首先执行第一行时，看上去还是不太好了解是什么意思，所以你是不是须要祭出一个办法：画图！通过画图来梳理下这个办法的脉络。如下所示：

从图中可清晰的看出 final Node<E> l = last; 这句话就是让 l 指向了 last 的地位，然而因为 last 为 null，所以 l 变量也就是 null。

接着执行第二行：final Node<E> newNode = new Node<>(l, e, null);

如图上图所示，创立了一个 Node 对象叫 newNode，item 元素的值是”host1”,newNode 的 prev 指针和 l 指向了一个地址，l 指向的地址是 last，是 null，所以 prev 也是 null。

再接着执行下一行，last = newNode, 这个很简略，就是 last 指向了 newNode 节点，如下图所示：

再接着，你能够看到会进入进入 if-else 判断, 如下图所示：

理论是让 first 指向了 newNode。最初进行了 size++，linkLast 办法就返回了。最终后果是不是就如下图所示：

通过这五步图，你是不是就了解了 LinkedList 的 add 办法了？次要做了以下三件事件：

应用长期指针 l 记录原最初一元素的地位
创立新元素，新元素的 prev 指针指向原最初一元素
last 指针指向新元素，如果是第一次增加元素 fisrt 指针也会指向新元素

大家能够设想下，再增加一个元素是不是就还是这个思路呢？记住这个思路，你能够试试本人画画图来感触下！

你就会失去如下的图：

其实你要害要记住的是辅助指针的思路，这样对你前面如果想首先一个链表，或者翻转一个单向链表会提供很好的思路。在汇合篇的结尾会让大家感触到的。

除了明天常识，技能的成长，给大家带来一个金句甜点，完结我明天的分享：置信比晓得更重要。

我给大家讲个故事，从前在东方，有一个牧师，他传教十分胜利，为什么呢？因为他百分之百的置信上帝，所以他传教的时候，总是这么说“上帝说……”，他的信徒越来越多。有一天他忽然发现，这些人都没有见过上帝，都是我跟他们讲“上帝说，上帝说…”。那我为什么要讲上帝说, 从此以后他就改成了“我本人说…我说…”。所以之后他传教时候就变成了“我说……，后果信徒越来越少，最初只剩他本人一个人。这个故事你能够学到什么？置信的力量有多大。

其实很多时候咱们置信事件会好起来，病会好起来。很多情理，事件，你不能只是晓得，而是要置信。置信和晓得的区别有多大？就比方晓得就像你头上的帽子，风一吹可能就刮走了，而置信就像是你头上的头发，风怎么吹都不会掉的。置信就是积重难返，一种信念，会逐步造成你的观点，成为了你本人的价值观。所以很多时候不要只是晓得，每天学习成长记会让本人晋升，会让本人变好，而是你要置信每天看看成长记，肯定会让本人成长，变得越来越好。记住置信比晓得更重要。

最初，你能够浏览完源码后，在茶余饭后的时候问问共事或同学，你也能够分享下，讲给他听听。

欢送大家在评论区留言和我交换。

本文由博客一文多发平台 OpenWrite 公布！

关于java:JDK成长记5LinkedList初探

LinkedList 初探

LinkedList 基本原理以及优缺点

初探 LinkedList 的脉络

从 add 办法开始摸索 LinkedList

金句甜点