day23_集合/15-尚硅谷-Java语言高级-LinkedList的源码分析

好，那么ear list这个源码分析呢，我们就说到这儿了，接下来呢，我们可以再看一个啊第三个点，那就提一下这个叫link list，哎，它的一个源码分析。啊，这个关于link list，它的源码分析呢，在我们七和八当中就没有什么大的差别了，哎，我们呢就可以直接来看一下咱们八当中的link list了，这个link list呢，咱们上午讲的时候呢，也提到过，它呢底层是用这个呃对链表进行存储的啊回头等我们把这个集合讲完以后呢，咱们稍微给大家呢介绍一下这个数据结构啊，哎，大家呢，有一个稍微清晰的一个整体脉络，那么在数据结构当中涉及到底层存储啊，有两个比较典型的或者叫基本的结构啊，其实一个呢就叫做嗯数组啊，它这样叫顺序表，那么另外一个呢，就是链表，对，这是最基本的两种数据的存储结构，那其他的一些像树啊，图啊等等，都是由咱们这些结构呢给它改造出来的。

啊，都是改造出来的，这是两个最基本的那沿，IG呢就是我们，而list和link link list呢就是一个选了一个啊，这个呢选的是顺序表中的数组，这个呢选的是我们的链表啊，目的呢就是区分出来，因为本身这两种结构呢，它们的特性呢不太一样啊，像这种呢，频繁的插入删除，我们用它要好一些。如果你要不是频繁的插入删除，仅仅呢，就是放进去。然后在某个位置呢，统一的又取出来，这个用哪个呀，用a list就行，为什么呢。因为这时候呢，其实它的效率要高一些了。怎么讲？嗯，你看我们这个list，我造完速度是不是就有通过角标直接就往里放就行了，而你这个link list是不是还得维护一对所谓的指针呢？一个元素是不是好几部分这个指指针指这，这个指针指这，你添一个元素是不是还得去老师维护这个指针，而我这呢，直接是不是就扔进去就完了，对的啊，同时的话呢，如果我们假设想找某个位置上元素，不涉及到这个是插入和删除啊，我就想找这个，比如说角标是十的这个元素，那你数组是不是直接就定位到这儿，那我类似呢。

你是第一个是不是找到第二个，第二个找到第三个，第三个找第四个找找找哦，这是第十个。他没有这个角标的这个说法呀，对吧？哎，所以他找起来呢，就会慢一些啊，那就是说对于咱们平时的一些便利啊，或者就是一些查找啊呃，添加呀，基本上不怎么会涉及到这个插入删除的时候呢，呃，你就是添加也是添加到末尾啊，别加到中间，加中间就成叉入了啊我们呢，其实还是建议用list的，那么link list呢，就是针对这种情况下我们才会去用啊，经常对它进行修改才会去用啊，它的好处呢，就是效率比较高一些，那么这个结构呢，我们也简单来看一下，那同样的道理，我们呢也是啊link list直接呢去做一个实例化，哎这样的方式好，我们这块呢，Ctrl c ctrl shift t啊看一下YouTube下的它，诶首先呢，咱们找一下它最初的这样一个结构定义啊。

声明。哎，在这呢，这呢叫link list，我们去看它这个源码的时候呢，它就嗯没有这个数组结构了，它有两个比较典型的结构呢，呃，就是这个属性哈，呃，Node类型的first node类型的last，这个node就是它的一个数据存储的基本单位啊，就是我们数据呢都存到这个node里了，就是咱们呢，通过link list这个对象呢，调艾的方法。这个方法放在这个数据实际上呢，就作为它这个整体对象的一部分啊，一部分这个node呢，咱们也上午稍微看了一下啊，你打开就找到这样的一个结构，这呢是一个内部类。

咱们前面讲面向对象的时候呢，说过内部类就是这个类呢，他在外边别人不用，就他自己用，那我们就定义到它的这个内幕，嗯，那这个node的话呢，我们会看到它的这个核心的结构。啊，我们呢，呃爱的方法，你添的这个数其实就是这个数啊这呢就是你添加的这个核心的数据了，那么这个呃我们填一个数据，相当于底层呢就造了一个node，那就把这个呢，核心的数据呢就放到这了，那另外呢，还有两个变量，一个呢叫啊previous，简称叫pre哈，哎，Next下一个就是我们去记录它的，哎这个当前这个元素。哎，当年这个元素呢，其实分成三部分，核心的数据，它的上一个是谁，下一个是谁，构成一个链条一样啊，就这样子啊，那我们还回到咱们刚开始说的这个位置上，又一个linked list啊，这呢是整个记录这个大肠的这个链条的头，这个头呢叫做first啊，那么当前的最后一个呢，它这个哎叫last来表示的。

因为呢，你要新添加的话呢，都得是从这儿呢去接着往后去添加，所以我得诶这个有一个变量，专门记录最后一个，或者叫当前这个是到哪了啊，那你要是想找某一个元素的话呢，我得从头这块呢，一个一个给你去往后找啊，我想找第五个元素啊，那我得从头开始去找，所以呢，我们对头上这个事情呢也比较关心，所以呢，定义两个属性啊放这儿了。那接下来我们的ctrl o调一下这个艾特方法，进来调下艾特方法，我们想往link的list当中添加一个元素，添加一个元素，我们就调了一下这个link last点进来做了这个事儿，看一下这个代码呢，不多。但是呢，还是有点思维量的，这其实就是相当一个小算法一样了。

这个last咱们刚才也看到了啊，就是咱们所谓的当前的最后一个元素，如果你要是首次调用at方法，这个呢，就是no，把这个给了我们这个node，接下来我们呢，新建一个node，新建一个node的话呢，这个呃，新建的就是这是你要添加的元素了，这是那个LL就是这个就是所谓的就是你目前最后的一个元素，这个node构造器，它呢，你看才放的这个元素的顺序哈，先放的是前一个中间的核心数据，它的下一个对有个印象啊，相当于我们现在要填的这个数据呢，是E，我这儿这儿呢就相当于是造完这个node了，把E呢就放到这儿，然后前边呢放了一个LL呢就是呃，前边如果你要是添加过的话呢，这是最后一个，相当于把这个L呢索引地址，就把你的这个元素地址给我，我是不是就相当于要指向你了。

那就这么着，但是你要这本身是第一个元素的话呢，这些是不是就其实你这个位置不就相当于这是个闹了嘛，对守元素的这个previous确实就是闹了，那接下来你这个新的这个元素，因为你目前要添加的啊，它呢就作为我们这个last出现了。嗯，然后这个呢，我不是记录成一个新的叫L了吗？它这个叫L了啊，嗯，再接着去看这的话就问一下说你这个，呃，一开始这个付给L了啊，说你L是no吗。啊，如果L是脑，那说明呢，你以前就没有添加过啊，那我们这时候这个你新添加这个元素呢，哎你呢，哎，你就是first。你是first啊，你这时候你也是last，因为就你自己。啊，就你自己啊，就像一个班就一个人，第一名是他，倒数第一也是他，哎，对就这个啊，哎，那如果你要是不是第一个元素不是这个元素呢，就是你就不是闹了哈，那这个时候呢，这不就呈现这样一个情况，我们刚才在这个位置，这不都把你指过来了，那这时候呢，就会涉及到，哎，我们这个L的next就是它了，因为你不是闹了吗？不是闹的话呢，你不是也有三部分，嗯，当初你你是最后一个的时候，你这个位置其实没有元素啊，你没有元素呢，现在我把你的这个next你指向我就行了，啊，现在我是最后一个了，这样这个链条呢，这就勾上了。

那这个位置呢，咱们不是附了个nor吗？哎，它就是个nor s加加一下，哎，这个大家先不用管啊，这个呢，就加了一个元素，我们就S加加，这不就把这个元素呢给它练起来了嘛。啊，就这样啊，那么类似的话呢，我们再可以去看我怎么去删除一个元素，这呢，我就不看这个源码了，其实这个逻辑呢，大家也能分析出来，比如我要添加一个，咱们上午也说过啊，哎，就是你这个网站值，这个网站值现在的话呢，诶，你指向它的这个值，你你别指了，你给了我给了我的这个next啊，我指向它，哎然后呢，你这个值呢，重新附一下，附成谁呢？把我付给你的next。这个逻辑都能想清楚，大家就能去写，然后接下来的话呢，就是呃这个下一个元素的它的呃指向前一个了，这个你别指它了，你把你指的这个值你给我，我指向它啊，然后你这个值呢，重新修改，改成谁呢？你改成我啊就你指成我，诶我们就插入了删除也类似的去修改就行，这呢就是咱们看到的这个叫诶link list它的一个源码分析啊诶这呢我们就简单写一下了，哎这里边呢去new了个，它其实里边呢没有做什么事情啊哎主要呢，大家就关注一下它内部，哎内部呢声明了啊一个呢叫node类型的，一个呢叫first，哎和我们这个哎last这样的一个属性吧，哎那么这个时候呢，默认值哎为now，哎这时候呢还没有值呢，哎当我们通过这个list呢，咱去调这个I的方法，往里边呢，去添加一个去体的对象。

哎，这个时候呢，我们说将将我们这个123呢，就封装到。

对，封装到咱们这个node这个当中，呃，相当于创建了这个node的一个对象，嗯，然后呢，就是有一些后续的，咱们看到这个核心的代码，我就不具体往这去写了啊这呢，我们主要关心的一下呢，就是其中，呃，咱们这个node定义为。哎，Note呢，定义为咱们刚才看到的这个源码。哎，它呢定义成这个样子，哎CTRLC这个呢，我就诶往这呢就诶稍微放一下啊，这个noe定义成这样子，哎放它的意义什么呢？通过这个结构呢，我们能够证明的事儿就是这个link的list呢，它确实是一个双向链表，咱们说叫双向。是不是就是通过这体会的呀，啊，一个有上一个，有个下一个啊，这叫双向链表，言外之意呢，就是我们像这个元素，我知道它的下一个，它的知道下一个，像这种呢，这叫单向链表，单向列表EID呢，就是我如果现在知道这个数据了，他能知道他上个是谁吗？

他不知道。他只知道他的下线是谁，像以前那个中共的地下党，基本上都是下线是吧，他都往下去对应，你想找他上线找不着，这样的比较安全。万一呢，某个人被。这个国民党反动派是吧？嗯，以前呢，这个一说国民党就是小时候啊，一说国民党后边呢，必须加个反动派啊，就感觉国民党就是这个跟这个恐怖分子一样是吧，那后来说啊，国民党其实分成这个也有好的哈，就是不是反动派的那那些是吧，嗯，比如说呢，现在就把这个这个我党这个地下人士给抓了是吧？哎，这个抓了以后呢，他顶多呢就把他的下线供出来。哎，把下边这个人就都抓了，但是他不知道他上个人是谁啊，上边这个人呢，就还是安全的，那这个人呢，就再再找个下线呗，是吧，就可以了啊哎，就是单线联系啊，这呢就是属于这个叫单向列表了，那你要是双向，这就就就就比较麻烦了啊双向的话呢，就是我知道我下线是谁，我也知道我上个是谁啊，那你要上个把这个人再抓，这个人还知道他上个是谁，这一条线就废了是吧，就一直抓到头了，就啊啊当然了，我党人士都是好人是吧，你就双向的，他也不会说的哈啊就是这是双向，就是你能知道下个谁也知道上个是谁，单向就不行了啊，那这呢就是我们叫双向列表啊体现了啊，我们叫link啊list。

啊，它呢就叫双向链表的一个说法，OK，那么关于这个link list的话呢，我们就看到这就可以了，它呢，因为也不涉及到扩容了，只有数组才会扩容啊，你又不是数组，你爱加几个你就加几个，哎，所以呢，它非常的灵活，哎，非常的灵活啊行，这呢就是关于link list的一个源码分析。