LinkedList初探

在前面的文章里，我们讲了数组和ArrayList，在现实中，不管什么系统，如果不考虑性能的话，用其中的一个就可以完成所有工作，那为什么不用它们来进行所有的数据存储呢？

在数组/ArrayList中读取和存储(get/set)的性能非常高，为O(1)，但插入(add(int index, E element))和删除(remove(int index))却花费了O(N)时间，效率并不高。

今天我们来看Java中的另一种List即LinkedList，LinkedList是基于双向链表来实现的，关于链表的知识我们Java数据结构之线性表 - 知乎专栏一文中有过介绍，HashMap和链表也有关系，所以我们要先讲它，话不多说，上代码。

这段代码和我们之前的往ArrayList添加元素的代码基本上是一模一样的，只是修改了红框的内容为LinkedList，这时候再往里添加元素，调用的就是LinkedList里面的add方法了。在之前的面向对象一文中我们已经说过了，这是多态的体现，利用好多态，在编码过程中，我们可以少修改很多东西，忘记了的朋友可以回过头去看一下。一看到new这个关键字，我们脑海里应该是，这货在堆内存中开辟了一块空间，我们先从构造函数入手吧。

满怀希望的打开构造函数，好伤心，里面没有任何逻辑，只能从成员变量入手。

发现三个成员变量，size就不多说了，大家猜一下就知道是LinkedList的逻辑长度，初始化为0，并持有两个Node引用，first看名字一猜就是第一个，last看名字就是最后一个，我们先来画一画

初始化完了，在堆内存中就是这个样子，size为0。引用类型的成员变量初始化为null，再来看一看这个Node是什么东东

这是一个内部静态私有类，该类只能在LinkedList中访问，先记住它，debug看一下

和我们图中一致，我们继续执行码里的add方法，看源码

很普通，e是我们往里添加的Person对象“张三”，继续跟踪linkLast方法：

第一次往LinkedList里添加元素，我们看上图11-1就知道，first为null，last也为null，把我们的Person对象“张三”传给了Node的构造函数，再看Node的构造函数：

用Person张三为入参构造了一个Node对象，好了，又到了画图的时候

老规矩，debug一下：

和我们图中所画的一致，我们继续添加“李四”这个Person对象，再打开源码分析一下。

张三这个Node指向新new出来的Node对象，再看Node是怎么创建的

创建Node对象，新new出来的Node对象的prev引用指向包含Person张三的Node对象。item引用指向Person李四对象，继续画图：

看上图，原来的next引用指向新new出来的Node，同时新new出来的Node的prev引用指向原来的Node对象，item指向新new出来的Person李四这个对象，同时perList这个LinkedList对象的last引用指向新new出来的这个Node，再debug看一下

好的，继续添加“王五”，“赵六”

很简单，没有了底层数组，新增加了一个Node对象，记录了Person的内容，每个Node对象都持有next引用(下一个)和prev引用(上一个)，其实就是之前Java数据结构之线性表 - 知乎专栏一文里介绍的双向链表，这个图看起来有点乱，多年前我在读这段代码的时候，差点晕过去了，又是next，prew，first，last，容易乱，因此大家在学习源码的过程中，有不明白的地方，找张纸和笔画一画，就清晰了。放张简化版的图，方便大家理解。

大家有什么看不明白的地方，可以在评论区留言，本文在写作过程中如果有什么勘误，还希望细心的读者提出来，下一篇我们研究LinkedList的查找、插入与删除，并引入时间复杂度来分析。

转载出自：https://zhuanlan.zhihu.com/p/28101975