Video在线视频

这一节我们来介绍一下

java集合框架当中的LinkedList类

中文简称为列表

LinkedList

它是把List接口中的列表

这个形式来实现的

那它实现了所有可选的一些列表操作

并且允许有空元素的存在

那LinkedList

它也实现了Deque接口

为add poll提供了一种

先进先出的队列操作

以及其他堆栈和双端队列的操作

那链表的话它本身是非线程安全

也就是说它不是那个（英文）的

那这是什么意思呢

也就是说我们在编程序过程当中

如果你用到这个链表

那并且是多线程

去访问这个链表的时候

你自己要去加（英文）

那对于LinkedList

也就是说链表这个类

它本身自己不做这个

同步与互斥来控制

而需要你自己写程序

来去控制这些事情

那链表的话它有一个特点

也就是说它比较适合于增或者删

但是比较弱的一项

就是说去查它或者改它

那它的这个特点

正好和我们上一节介绍的

ArrayList是相反的

那我们看看它为什么是这个特点

这是链表的数据结构

那第一行是这个

用这个数据结构Entry E

来表示的一个链表的头叫header

那header等于new Entry E

然后三个空

那这三个空什么含义我们往下看

第二行private

static class Entry E

那这个Entry

就是我们一个链表当中的节点

那这个节点里面包含什么呢

往下看 E element

这个节点当中这个E element

来表示说我这个节点

它本身的值是什么

Entry E next

而next表示说我当前这个节点

它的下一个节点是哪一个节点

Entry E previous

那只是说我这个节点

它的前序节点是谁

那我们通过这个

它的三个成员变量可以看出

对Entry这样一个数据结构来说

它实际上表示了

我们一个链表当中的一个节点

那这个节点的前面一个

和后面一个是谁都指明了

以及这个节点本身

它的值是什么也都指明了

那再往下我们看一下这个构造方法

Entry然后括号E param E

Entry E paramEntry1

Entry E paramEntry2

那这个paramEntry1

和paramEntry2分别什么意思呢

也就是说我们要把

我们的第一个参数

我们的目标对象param E

放到这个paramEntry1之前

且在paramEntry2之后

那这个构造方法

就相当于我们把的这个目标元素

插入到链表当中

那我们看构造一个方法里面

都是怎么实现的

thil.element等于param E

那就是把我们这个节点的值

它的这个成员变量的值

设置为param E

然后this.next等于paramEntry1

也就是说这个节点的下一个节点

就是指向paramEntry1

this.prevlous等于paramEntry2

这个节点的前序节点

之前的节点指向paramEntry2

那我们可以看一下这页PPT最下面

实际上它是一个双向的一个队列

我现在蓝色标出的是Entry

就是我们这个链表当中的

某一个节点

那这个节点它有next指向了说

它下一个后续的这个节点是谁

然后它同时还有一个

这个prevlous的

这么一个类似指针的东西

指向了它之前前面的那个节点是谁

所以大家可以想象

如果我们有两个 三个 四个

这样的节点

实际上它就会构成一个

这个双向的这么一个链表

下面我们看一下在链表这个类里面

到底有哪些方法

我们先看一下第一个方法叫Entry

那这个方法的目的

就是说我们给定一个

这个链表当中节点的序号

int paramInt

然后返回这个节点的值

那我们看一下这个方法怎么实现的

if paramInt小于0

或者paramInt大于等于this.size

那这什么意思呢

也就是说你给出的这个参数

它是小于0

或者是超出了整个链表的长度

那说明这个节点的这个值

它是属于数组下标越界

所以在下一行我们就能看到

throw new

IndexOutOfBoundsExceptionl

产生了一个数组下标越界的异常类

异常对象 然后把它抛出去

那如果都没问题我们往下看

Entry localEntry

等于this.header

好了 我们先要找这个

想要的这个节点的话

就从这个链表的头部开始找

那从头部开始找的时候

其实有一个选择

因为其实我们的链表是个双向环

那从头部开始找的时候

你看从往左找更近呢

还是往右找更近

那这时候就要做一个判断了

那我们要判断一下

所给提供的参数paramInt

它到底是比我们这个

列表长度的一半小

还是比列表长度一半大

我们看一下paramInt

小于this.size右移移位

this.size右移移位的话

相当于把我们的长度除以2

那如果我们这个参数paramInt

小于我们长度值的一半

那就说明我们要找的这个节点

在整个链表的前一半

所以我们就开始逐一往下找

怎么找呢 for i等于0

i小于等于paramInl i++

然后是localEntry

等于localEntry.next

也就是一个一个的往下找

好了 那else else是什么意思呢

就是说如果我们输入的

这个参数paramInt

它是比我们的这个长度一半还要大

那就说明我们要找的这个节点

它在我们整个链表的后一部分

那后一部分我们可以

从我们的头往尾部开始找

那怎么找呢

for i等于this.size

i大于paramInt i--

这个时候localEntry

等于localEntry.previous

也就是从尾部开始往前找

那找到最后是肯定能找着

紧接着我们return localEntry

那这个就是我们这个

Entry方法的实现过程

那我们再看另外一个方法

我们另外一个方法叫addBefore

addBefore意思就是说

我要在某一个节点之前

去增加我某一个这个元素

那我们看一下

private Entry E addBefore

然后第一个参数是E paramE

第二个参数是

Entry E paramEntry

那实际上这两个参数

第一个参数指明说是

我要添加的这个对象是谁

第二就是说我要插到谁之前

我要插到这个

Entry E paramEntry之前

那我们往里面看一下怎么实现呢

然后我们是Entry localEntry

等于new Entry 然后param E

这是什么意思呢

就是说我是要实例化新的一个节点

这个Entry这个结构

把我们要添加这个元素值

param E放进去

然后这个时候必须指定说

我要放在哪 对了

我放在哪呢

我放在param Entry这个对象

就这个节点之前

然后放在哪个节点之后呢

就要放在paramEntry.previous

也就是说paramEntry

它之前一个节点

那我要把我新增的这节点

加在这中间 插入到这中间

那插入到中间了以后

我们紧接着要指定了localEntry

localEntry它是一个节点的数据结构

它除了本身自己的值之外

它还要指明说

它的前一个节点是谁

它的后一个节点又是谁

那我们先看一下

怎么指明它的前一个节点

那就localEntry.previous.next

这个东西看起来有点绕

怎么又有previous 又有next呢

实际上是这样的

就localEntry.previous

那就是我们当前

已经插入了这个节点它的前序

那前序也是一个Entry

我们把它前序的这个Entry的节点

它的next 就是全新的

它的往下走指向谁呢

指向我这个localEntry

也就是指向我这个

刚刚插进去的这个节点

也就是这个感觉就像是

我们去食堂里排队的时候

当你站入

插入到前面某一个位置的时候

你主动告诉你身前那个人说

你后面是我 就是这个意思

告诉身前的人说

那个他后面这个人就是你自己

好 我们再往下一行

localEntry.next.previous

这个看起来也有点绕

又有next 又有previous

那localEntry.next

就是说localEntry

假如是我们去排队

假如说我自己我的下一个

那就是next

然后他的previous

告诉他previous就是我

那还是我们排队的时候

你这个就想你去食堂排队

你已经插队成功了 那插队成功了

你要告诉你身后的人说

我已经站在你前面了

所以我们这行代码就是告诉说

就是达到这个目的

刚才上一个代码是告诉你

前面的人说我站在你后面了

就起这么一个作用

然后再往下就是this.size+1

加等于1就是加1

然后this.modCount+=1

也就是说我们修改的次数加1

最后retum localEntry

然后就是把这个

已经插入的这个节点返回

那大家看到这个addBefore

这个方法它在添加

也就是这个元素的时候

还是蛮方便的

首先它需不需要进行元素的拷贝

大家回想上一节我们讲到ArrayList

也就是数组列表的时候

它要加入元素

是要把后面这些元素

都要往后拷贝一下

在我们这里面没有拷贝

只需要在我们这个节点结构

Entry里指明说我的前面是谁

我的后面是谁就可以了

所以说这个LinkedList

也就是链表它的插入操作

速度是比较快的

那我们再看一下

另外一个这个插入操作

也就是说我们要在指定的

某一个位置上面

去添加某一个元素

public void add

然后位置是int index

然后元素就E element

那这时候我们就会调用

addBefore element

然后在什么位置呢

就是说我们需要判断一下

到底它这个位置有没有

一些非常奇特或者特殊的位置

index==size？

header：entry index

什么意思呢

也就是说如果我们正好

要在我们链表的最后

去添加这个元素的话

那实际上相当于是

要在我们这个链表的头部之前

去加我们这个元素

那否则就是正常的

就在Entry index

在某一个这个节点上

也就是中间的

就这个链表的中间

去添加一个元素

所以这就是add这个方法

那我们再看另外一个方法

public void addFirst

E paramE

那其实它就想说我在一开头

我要添加 这个队首添加元素

那就直接调用addBefore

paramE this.header.next

就是在我们header的后面去添加

当然header这个结构的话

它是在链表当中

它也是符合我们Entry

这个节点的结构

然后再往下就是我们队尾添加元素

public void addLast

然后参数是E paramE

那也就是说我们在最后最后

来去添加 队尾去添加元素

那就header paramE

this.header

那其实在队尾添加这个元素

那实际上就是相当于

加到我们的队头前面

就是header加在我们的

整个链表的header前面

那我们再看一下

这个链表当中怎么实现删除的

private Eremove Entry E e

就是我们要删除某一个节点

那if e==header

也就是说你要删除的是这个头部

头节点的话

那它就会抛出说没有这样的元素

这样的异常

那好了 如果你不是想删除

这个头节点

删除其中的普通的节点

那我们看怎么做

E result等于e.element

那我们先得到这个

你要删除的这个结果

它的元素值是什么

然后保存到到result当中

我们再看一下它怎么删除

e.previous.next=e.next

这句话看起来又有点绕

好了 现在实际上我们是想把e

它这个节点给删除了

它其实删除是怎么删除的

e.previous

就是说我这个要被删除的节点的

前一个节点

然后前一个节点我把它的next

就告诉前面那个人说next

就是他的下一个节点是我的什么呢

是e.next 是我的后一个人

好了 其实这有点像

我们刚刚有举那个例子

我们到食堂去排队

这时候有人插队

插队完后被大家说要赶出去了

那这时候这个人要赶出去之前

他就会对站在他前面的人

我已经不站在你身后了

你身后的人是我现在身后的那个人

就是这个意思

然后再往下e.next.previous

等于e.previous

那e.next.previous指的是谁呢

就是说我的下一个

e.next是我的后面这个人

然后我的后面的人.previous

我告诉后面的人

说你的前面的人不是我了

是谁呢 是e.previous

就是我身前的人

那这行意思就是说

我告诉我身后那个人

说你前面的人不是我了

是我前面那个人

那经过这么一些结构处理

实际上相当于把自己

从这个链表当中删除掉了

然后间接着往下

e.next等于e.brevious等于空

也就是由于要把我自己

这个要删除掉的话

我把我的前序和我的后序

都设置为空

说都不知道指向谁了

间接着e.element等于空

也就是我本身这个节点的元素

本身的值也设为空

间接着size--

也就是说我们的整个链表的长度减1

modCount++

这个修改次数加1

return result

也就是说最后把我这个节点它的值

刚才已经保留下来了 返回

做一个返回去返回

所以这个删除过程大家可以看到

它的删除速度也是蛮快的

它只需要把被删除那个节点

它的前一个和后一个

之间的这些内容

做一个相应的这个调整就可以了

不影响到其它的这个节点

但是如果大家回想一下

你们在上一节当中学到的ArrayList

就是这个数组列表当中

你要做一个删除操作的话

那你从中间删除某一个元素

你得把后面的那些所有的元素

都要往前挪一位

那这样的情况下肯定是动作比较大的

而相比之下我们链表的操作

删除操作会速度比较快

那我们再看看这个删除

还有哪些方法

这个public E remove

remove相当于就是

删除掉第一个元素

然后public E remove int index

那就是我们要删除掉

某个下标的节点

那直接就

return remove entry index可以了

那再往下实际上是实现了那个

第三个方法是实现了remove First

remove First

实际上它就是调用了

remove的那个header.next

就是说头部的下一个

再往下是public remove Last

删除最后一个

删除最后一个

实际上它是通过删除

header.previous

也就是说把头部

它的前一个进行了这个删除

所以header这样这么一个结构

在我们的链表当中

它首先就是一个Entry

是符合我们节点结构

但是它的这个所表达

也是专门来指出它就是头部的

有它特殊的作用

那我们可以看到这个list这个接口

我们已经介绍了有两个类

一个叫ArrayList

一个叫LinkedList

那这两个类它的内部实现的机制

包括它的方法的实现过程

我们这两节都已经介绍到了

那它们有各自适用范围

是ArrayList适用于

对数据查询修改

大于数据增删的场合

也就是说当你的本身

写的java程序的

对于数据的处理

它如果里面对于数据

查询修改的需求

多过增加或删除的这种需求的话

在这种情况下你用ArrayList

比较合适 比较高效

那如果你的写程序的

这个应用过程当中

它对于数据的增加

和删除的需求比较大

大过这个对于数据查询的

这种这个需求的话

那这个时候你用ArrayList

效率就比较高

这一节的内容就介绍到这里