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>作为Java工程师，LinkedList你可能用的不多，大多你总是在new ArrayList。面试很多时候总是拿LinkedList和ArrayList的做对比。总会问你ArrayList 和 LinkedList 的区别是什么？它俩是不是线程安全的？等等。很多时候你的习惯了使用ArrayList，都很少考虑使用LinkedList。你可能都不知道他可以用作内存队列或者栈。再接下来的几节中，你就可以学习到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优缺点缺点：随机访问性能差优点：频繁插入和删除元素性能很好，容量没有限制可用作内存队列或者栈有顺序性初探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，从它的入口开始，看下他的核心源码呢？从add方法开始探索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;">从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指针也会指向新元素大家可以想象下，再添加一个元素是不是就还是这个思路呢？记住这个思路，你可以试试自己画画图来感受下！你就会得到如下的图：其实你关键要记住的是辅助指针的思路，这样对你后面如果想首先一个链表，或者翻转一个单向链表会提供很好的思路。在集合篇的结尾会让大家感受到的。金句甜点<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;">金句甜点</span></h3></div>除了今天知识，技能的成长，给大家带来一个金句甜点，结束我今天的分享：相信比知道更重要。我给大家讲个故事，从前在西方，有一个牧师，他传教非常成功，为什么呢？因为他百分之百的相信上帝，所以他传教的时候，总是这么说“上帝说……”，他的信徒越来越多。有一天他突然发现，这些人都没有见过上帝，都是我跟他们讲“上帝说，上帝说…”。那我为什么要讲上帝说,从此以后他就改成了 “我自己说…我说…”。所以之后他传教时候就变成了“我说……，结果信徒越来越少，最后只剩他自己一个人。这个故事你可以学到什么？相信的力量有多大。其实很多时候我们相信事情会好起来，病会好起来。很多道理，事情，你不能只是知道，而是要相信。相信和知道的区别有多大？就比如知道就像你头上的帽子，风一吹可能就刮走了，而相信就像是你头上的头发，风怎么吹都不会掉的。相信就是根深蒂固，一种信念，会逐渐形成你的观念，成为了你自己的价值观。所以很多时候不要只是知道，每天学习成长记会让自己提升，会让自己变好，而是你要相信每天看看成长记，一定会让自己成长，变得越来越好。记住相信比知道更重要。最后，你可以阅读完源码后，在茶余饭后的时候问问同事或同学， 你也可以分享下，讲给他听听。欢迎大家在评论区留言和我交流。本文由博客一文多发平台 OpenWrite 发布！
