Java——数据结构之双向链表
Java——数据结构之双向链表
Java——数据结构之双向链表
在之前的学习中，我们主要了解了很多 Java 的 基本语法，但是 在之后的 Java学习中，了解 基础 数据结构的知识 非常重要，数据结构的思想 可以帮助我们更加清晰 明白的了解 Java 的解题思路等等。
今天我们就来开始学习 实现一个 Java 基础的 不带头双向非循环链表。
1.单链表的实现
（1）定义一个节点类型
我们创建一个 ListNode 的类作为节点类型，那么我们如何定义成员属性呢？
通过上面的结构分析，我们需要定义两个成员变量 val --作为该节点的存储的数值， next – 保存下一个节点的地址/引用， prev - 保存上一个节点的地址/引用
同时定义之后，他们的默认值为 0 ，null ，null，所以要想赋予这个节点数值，要写一个构造方法去首先保存数值。
这里我们提供了两个构造方法，一个是实现提供数值的节点，另一个是没有提供数值的节点，方便我们之后使用。
作为双向链表，可以从头节点遍历到尾节点，同时也可以从尾节点遍历到头节点，所以我们要定义两个节点—— head头节点，last尾节点
public ListNode head;
public ListNode last;之后我们在 LinkedList 的类中实现单链表的各种方法。
（2）头插法
以上述结构为例，这个单链表没有专门的傀儡节点来充当头节点，首个节点就定义为头节点，所以头插法，就是我们定义一个节点，插在这个链表的最前面，作为新的 head。
思路：
这里分两种情况：
第一次插入
不是第一次插入
代码展示：
（3）尾插法
和头插法类似，同样插入一个节点，在链表的最后。
代码展示：
（4）根据下标插入节点
第一个数据节点为0号下标，任意位置插入节点。
还以上面的链表为例，我们想将新的节点插入到2 号位置
思路：
1.先判断传入的 index 下标位置是否合法
2.如果传入的index==0，头插法
3.如果传入的index==sizeof(),尾插法
4.插入中间节点时，改变cur前后节点的属性
代码展示：
（5）查找关键字
以上面的链表为例，我们现在要查找这个链表中是否出现 val=20 的节点，如果存在，那么返回true，如果不存在，则返回 false.
遍历链表，走过每一个节点，如果 cur.val == key，则 return ture ，遍历完后还未找到 key，那么return false.
思路：
代码展示：
（6）删除第一次出现的关键字
思路：
代码展示：
（7）删除所有出现的关键字key
思路：
删除的思路与上一个方法一致，不过上面第一次遇到关键字删除后，直接return了，要想删除所有关键字，将return 改为 cur = cur.next; 继续向后进行遍历。
特殊情况：节点全部出现关键字
代码展示：
（8）节点的回收
节点的回收有两种方式：
1.暴力法
直接将head、last 置空
2. 挨个置空
遍历单链表，将每一个节点的next、prev都置为 null.
思路：
代码展示：
（9）链表打印展示
2.完整代码展示
好了今天的知识就分享到这里，希望大家多多练习，谢谢大家的欣赏与关注！！
感谢支持！！！