Java-----Java实现双向链表

双向链表

1.双向链表简介

双向链表和单向链表略微有些区别,  需要将每个节点划分为3个部分, 一个部分存储数据, 一个部分存储前一个节点的地址, 一个数据存储后面的节点位置

 

2.双向链表的算法实现

创建一个类Node, 用于描述每个节点, Node中表示数据的为data(Object)类型, 表示前一个简单的为pre(Node类型), 后一个节点为next(Node类型)

 

2.1 add()方法

2.1.1 尾节点和尾指针

(1) 尾节点

和单向链表一样, 在往里面添加数据的时候, 通过Node将数据进行封装, 所以每次新添加一个节点就要创建一个Node对象, 然后要将这个节点和该链表中的其它链表产生关联, 在之前的单向链表中, 提到了一个首节点的概念, 有了首节点, 能够很方便的对整个链表进行操作,但是这例要普及另一个概念-----尾节点.

尾节点和首节点的概念相似, 首节点是链表中的第一个节点, 而尾节点就是链表中的最后一个节点

 

如上图所示, Last为尾节点, 因为是非循环链表, 所以尾节点的next指向尾null

(2) 尾指针

尾指针是指向尾节点的一个指针, 但是Java中并没有指针的概念, 但是可以定义一个Node类型变量

l(字母L, 不是1), 用作记录最后一个节点的位置

 

2.1.2 算法分析

有了尾节点和尾指针, 添加操作就会非常的简单, 因为尾节点的next指向是null的, 所以只需要判断这个Node节点的next指向是否为null, 如果为null, 那么就让该节点的next指向每次添加时新new的Node节点

 

2.1.3 代码实现

首先定义头节点和尾节点

 

然后定义尾指针l, 指向end尾节点

 

每次add()时, 都要创建一个新的Node节点, 新的Node节点的pre为添加之前的尾节点, 新节点将作为尾节点, 所以next为null,

 

接下来在添加节点的时候,  要先判断尾指针是否为null, 因为在进行添加操作时, 首先做的操作时将尾节点赋值给了尾指针(Node l = end), 然后将新的Node节点newNode赋值给了尾节点end, 这证明了如果l尾指针为null, 那么证明Node节点没有被new过, 所以此时头节点head和尾节点end都不存在, 这个时候就将新的Node节点newNode, 赋值给head节点, 这样才方便链表的后续操作

 

当尾指针存在的情况下, 就将尾指针的next指向这个newNode

2.2 size()和get()方法

2.1已经实现了add()方法, 但是数据到底有没有存入进去, 需要遍历一下链表查看,

遍历的时候需要使用size()方法和get()方法, 所以接下来实现这两个方法

 

2.2.1 size()方法

size方法实现比较简单, 只需要定义一个全局的计数变量size

 

每次add()时将计数自增1, 每次remove()时计数器自减1即可.

 

先暂时执行自增, 当后面实现remove()方法时,再进行自减

 

2.2.2 get()方法

get()方法是获取链表中某个节点数据的方法, 一般情况下通过下标来获取, 所以这个方法需要一个返回值为Object, 一个参数为index

因为后续还要会有set和remove方法, 都要通过下标找到相应的节点, 所以这里可以先封装两个方法, 分别是下标越界的检查 和 Node节点的查找

 

有了以上两个方法, 那么在get方法中, 只需要检查一下标是否越界, 然后再将下标index传入到node()方法中获取到Node节点, 最后将该节点的data数据返回即可

 

2.2.3 node()方法的实现

(1) 算法分析

单向链表由于每个Node节点只知道后面的Node节点是谁而不知道前面的Node节点是谁, 所以只能从头到尾逐次遍历查找, 但是双向链表的特点就是每个Node节点不仅知道下一个Node节点是谁,还知道前面一个Node节点是谁, 所以在查找的时候就可以根据需要查找的下标index的大小决定从前开始遍历还是从后开始遍历

 

(3) 代码实现

 

此时size()和get()方法已经实现, 进行方法测试

 

 

2.3 set()方法

2.3.1 方法设计

   set()方法能够根据下标index修改Node节点中的data数据为新数据newData, 并且将修改之前的结果返回, 所以set()方法的需要两个参数, 一个参数是需要修改的Node节点的下标, 另一个参数是新数据newData, 返回值类型为data的类型Object

 

2.3.2方法分析

如果要修改某个节点的数据, 首先要找到这个Node节点, 然后将这个节点中的data数据替换为newData

 

2.3.3 代码实现

 

2.4 remove()方法

2.4.1 方法设计

删除方法需要知道要删除的Node节点的索引, 所以需要一个参数为下标index, 删除后返回所删除的节点中的data, 所以需要一个Object类型的返回值

 

 

2.4.2 算法分析

在链表的删除操作中, 首节点head和尾节点end是一定要存在,

所以有以下几种情况

当删除head时, 就要让head的next所指向的Node节点作为head,

当删除end时, 就要让end的pre所指向的节点为end

当删除的不是head和node时, 只要将当前节点的pre所指向的Node的next指向当前节点的next所指向的节点即可

 

2.4.3 方法实现

 

3. 将数据类型改为泛型

在Java中常使用的集合, 数据的类型都是泛型, 所以这里将所有数据类型改为泛型

首先定义泛型T

 

然后全局将Object替换为T

 

Node前加上泛型, Node<T>

 

此时再往里面添加非泛型定义的数据时, 就会报错

 

其实, 以上就是Java中LinkedList的部分源码!!!