JDK成长记5:LinkedList初探

JDK成长记5:LinkedList初探

JDK成长记5:LinkedList初探

LinkedList初探

LinkedList初探

作为Java工程师,LinkedList你可能用的不多,大多你总是在new ArrayList。面试很多时候总是拿LinkedList和ArrayList的做对比。总会问你ArrayList 和 LinkedList 的区别是什么?它俩是不是线程安全的?等等。很多时候你的习惯了使用ArrayList,都很少考虑使用LinkedList。你可能都不知道他可以用作内存队列或者栈。再接下来的几节中,你就可以学习到LinkedList的底层各种源码的原理,练习之前学习到方法分析源码。

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

LinkedList基本原理以及优缺点

LinkedList基本原理以及优缺点

1)LinkedList基本原理

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

2)LinkedList优缺点

缺点:

  1. 随机访问性能差

优点:

  1. 频繁插入和删除元素性能很好,容量没有限制
  2. 可用作内存队列或者栈
  3. 有顺序性

初探LinkedList的脉络

初探LinkedList的脉络

你第一步应该做什么呢?对,没错,看下LinkedList的源码脉络:

JDK成长记5:LinkedList初探

第一张图中,你可以看到只有三个成员遍历size、fisrt、last。除了size,其他两个变量都是Node类型,可以猜测Node应该是它一个内部类。剩下的就是我们常用的构造函数、add、get、set、remove等方法了,最后还有一些toArray、addAll、indexOf等方法和ArrayList的API很像。

第二张图如下:

JDK成长记5:LinkedList初探

这张图里面,可以看到有一些pop、push、poll、offer这些方法,如果你熟悉数据结构的话,这些方法名字很像是队列数据结构入队,出队和栈结构的入栈、出栈常用的方法名。接着就是ListItr、Node两个内部类了。

当你看过LinkeList源码的脉络后,接下来是不是应该简单写一个Demo,从它的入口开始,看下他的核心源码呢?

从add方法开始探索LinkedList

从add方法开始探索LinkedList

你应该记得之前我们提到过,看核心源码一般是从入口开始,也就常说的自顶而下。

首先你要有个代码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是一个双向链表,所以会形成如下的图:

JDK成长记5:LinkedList初探

接着main函数执行下一行,执行 add方法:

public boolean add(E e) {

   linkLast(e);

   return true;

}

直接调用了linkLast方法,之后返回true了。

JDK成长记5:LinkedList初探

所以需要看下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是一个泛型,应该是存放对应的数据元素的。希望这个数据结构你没有还给大学老师。

JDK成长记5:LinkedList初探

你知道了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++;

}

首先执行第一行时,看上去还是不太好理解是什么意思,所以你是不是需要祭出一个方法:画图!通过画图来梳理下这个方法的脉络。如下所示:

JDK成长记5:LinkedList初探

从图中可清晰的看出final Node l = last;这句话就是让l指向了last的位置,但是由于last为null,所以l变量也就是null。

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

JDK成长记5:LinkedList初探

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

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

JDK成长记5:LinkedList初探

再接着,你可以看到会进入进入if-else判断,如下图所示:

JDK成长记5:LinkedList初探

实际是让first指向了newNode。最后进行了size++,linkLast方法就返回了。最终结果是不是就如下图所示:

JDK成长记5:LinkedList初探

经过这五步图,你是不是就理解了LinkedList的add方法了?主要做了以下三件事情:

  1. 使用临时指针l记录原最后一元素的位置
  2. 创建新元素,新元素的prev指针指向原最后一元素
  3. last指针指向新元素,如果是第一次添加元素fisrt指针也会指向新元素

大家可以想象下,再添加一个元素是不是就还是这个思路呢?记住这个思路,你可以试试自己画画图来感受下!

你就会得到如下的图:

JDK成长记5:LinkedList初探

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

金句甜点

金句甜点

除了今天知识,技能的成长,给大家带来一个金句甜点,结束我今天的分享:相信比知道更重要。

我给大家讲个故事,从前在西方,有一个牧师,他传教非常成功,为什么呢?因为他百分之百的相信上帝,所以他传教的时候,总是这么说“上帝说……”,他的信徒越来越多。有一天他突然发现,这些人都没有见过上帝,都是我跟他们讲“上帝说,上帝说…”。那我为什么要讲上帝说,从此以后他就改成了 “我自己说…我说…”。所以之后他传教时候就变成了“我说……,结果信徒越来越少,最后只剩他自己一个人。这个故事你可以学到什么?相信的力量有多大。

其实很多时候我们相信事情会好起来,病会好起来。很多道理,事情,你不能只是知道,而是要相信。相信和知道的区别有多大?就比如知道就像你头上的帽子,风一吹可能就刮走了,而相信就像是你头上的头发,风怎么吹都不会掉的。相信就是根深蒂固,一种信念,会逐渐形成你的观念,成为了你自己的价值观。所以很多时候不要只是知道,每天学习成长记会让自己提升,会让自己变好,而是你要相信每天看看成长记,一定会让自己成长,变得越来越好。记住相信比知道更重要。

最后,你可以阅读完源码后,在茶余饭后的时候问问同事或同学, 你也可以分享下,讲给他听听。

欢迎大家在评论区留言和我交流。

本文由博客群发一文多发等运营工具平台 OpenWrite 发布

上一篇:一篇解双链表(0基础看)(C语言)《数据结构与算法》


下一篇:漫画|有趣的了解一下赋值、深浅拷贝