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

31次阅读

共计 7658 个字符，预计需要花费 20 分钟才能阅读完成。

<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 的基础知识。

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

1）LinkedList 基本原理

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

2）LinkedList 优缺点

毛病：

随机拜访性能差

长处：

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

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

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

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

第二张图如下：

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

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

<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;”> 从 add 办法开始摸索 LinkedList</span></h3></div>

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

首先你要有个代码 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 指针也会指向新元素

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

你就会失去如下的图：

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

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

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

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

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

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