位置：首页>> 软件编程>> java编程>> Java数据结构之双向链表的实现

Java数据结构之双向链表的实现

作者：兴趣使然黄小黄　　发布时间：2023-09-17 16:21:45　

标签：Java,数据结构,双向链表

1 双向链表

1.1 双向链表介绍

相较单链表，双向链表除了data与next域，还多了一个pre域用于表示每个节点的前一个元素。这样做给双向链表带来了很多优势：

单向链表查找的方向只能是一个方向，而双向链表可以向前或者向后查找；

单链表如果想要实现删除操作，需要找到待删除节点的前一个节点。而双向链表可以实现自我删除。

双向链表结构示意图如下：

1.2 双向链表实现思路

与单链表实现类似，交集部分不再赘述，详情可参考文章：Java数据结构：单链表的实现与面试题汇总

遍历：

与单链表遍历方式一样，同时，双向链表可以支持向前和向后两种查找方式

添加：

添加到末尾

先找到双向链表最后一个节点
cur.next = newNode；
newNode.pre = cur；

按照no顺序添加

先判断该链表是否为空，如果为空则直接添加
如果不为空则继续处理
根据no遍历链表，找到合适的位置
newNode.next = cur.next;
cur.next = newNode;
newNode.pre = cur;

修改操作与单链表实现步骤一致

删除操作：

双向链表可以实现自我删除
直接找到待删除的节点
cur.pre.next = cur.next;
cur.next.pre = cur.pre;
需要特别注意是否为最后一个元素，如果为最后一个元素，cur.next为null，此时使用cur.next.pre会出现空指针异常，所以，如果为最后一个元素，则该步骤可以省略，cur.next为null即可。

以删除红色的2号节点为例：

2 双向链表实现完整代码

2.1 节点类 Student.java

/**
* @author 兴趣使然黄小黄
* @version 1.0
* 学生类节点
*/
public class StudentNode {
public String no; //学号
public String name; //姓名
public int age; //年龄
public StudentNode pre; //指向前一个节点
public StudentNode next; //指向下一个节点

//构造器
public StudentNode(String no, String name, int age ){
this.no = no;
this.name = name;
this.age = age;
}

//为了显示方便
@Override
public String toString() {
return "StudentNode{" +
"no='" + no + '\'' +
", name='" + name + '\'' +
", age=" + age +
'}';
}
}

2.2 双向链表实现类 StudentDoubleLinkedList.java

/**
* @author 兴趣使然黄小黄
* @version 1.0
* 学生双向链表的具体实现
*/
public class StudentDoubleLinkedList {
//定义头节点
private StudentNode head = new StudentNode("", "", 0);

//获取头节点
public StudentNode getHead(){
return head;
}

//遍历双向链表的方法
public void showList(){
//判断链表是否为空
if (head.next == null){
System.out.println("当前链表为空");
return;
}
//遍历使用辅助指针
StudentNode temp = head;
while (temp != null){
//更新指针
temp = temp.next;
if (temp.next == null){
System.out.print(temp);
break;
}
System.out.print(temp + "--->");
}
}

//添加节点的方法
//添加到尾部
public void add(StudentNode newNode){
//先找到最后一个节点
StudentNode cur = head;
while (true){
//到达最后退出循环
if (cur.next == null){
break;
}
//更新指针
cur = cur.next;
}
//添加操作
newNode.next = cur.next; //也可以省略，因为恒为null
cur.next = newNode;
newNode.pre = cur;
}

//添加节点的方法
//根据学号顺序添加
public void addByOrder(StudentNode newNode){
//如果当前链表为空，则直接添加
if (head.next == null){
head.next = newNode;
newNode.pre = head;
return;
}
//按照学号找到对应位置
StudentNode cur = head;
boolean flag = false; //标识待添加的no是否存在
while (true){
if (cur.next == null){
//已经到达链表的尾部
break;
} else if (Integer.parseInt(cur.next.no) == Integer.parseInt(newNode.no)){
//已经存在
flag = true;
break;
}else if (Integer.parseInt(cur.next.no) > Integer.parseInt(newNode.no)){
//位置找到
break;
}
cur = cur.next;
}
if (flag){
System.out.println("当前no已经存在，无法添加!");
}else {
//添加操作
newNode.next = cur.next;
cur.next = newNode;
newNode.pre = cur;
}
}

//根据no学号修改学生信息
public void update(StudentNode studentNode){
if (head.next == null){
System.out.println("当前链表为空, 无法修改");
return;
}
StudentNode temp = head.next;
boolean flag = false; //表示是否找到节点
while (true){
if (temp == null){
break;
}
if (temp.no == studentNode.no){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
temp.name = studentNode.name;
temp.age = studentNode.age;
System.out.println("更新成功!");
}else {
System.out.println("没有找到");
}
}

//从双向链表中删除节点
public void delete(String no){
//直接找到对应no的节点直接删除
StudentNode cur = head.next;
boolean flag = false; //标记是否找到
while (true){
if (cur == null){
break;
}
if (cur.no.equals(no)){
flag = true; //找到了
break;
}
cur = cur.next;
}
if (flag){
//删除操作
//注意考虑最后一个节点后一个为空的情况
if (cur.next != null) {
cur.next.pre = cur.pre;
}
cur.pre.next = cur.next;
System.out.println("删除成功!");
}else {
System.out.println( no + "节点不存在，无法删除！");
}
}
}

2.3 测试类 StudentDoubleLinkedListDemo.java

/**
* @author 兴趣使然黄小黄
* @version 1.0
* 双向链表测试类
*/
public class DoubleLinkedListDemo {
public static void main(String[] args) {
StudentDoubleLinkedList doubleLinkedList = new StudentDoubleLinkedList();
doubleLinkedList.addByOrder(new StudentNode("1", "黄小黄", 20));
doubleLinkedList.addByOrder(new StudentNode("3", "懒羊羊", 20));
doubleLinkedList.addByOrder(new StudentNode("2", "沸羊羊", 25));
doubleLinkedList.addByOrder(new StudentNode("4", "美羊羊", 15));
System.out.println("遍历:");
doubleLinkedList.showList();

//测试更新方法
System.out.println("\n更新编号为4的信息后:");
doubleLinkedList.update(new StudentNode("4", "祢豆子", 14));
doubleLinkedList.showList();

//测试删除方法
System.out.println("\n删除第一个和最后一个:");
doubleLinkedList.delete("1");
doubleLinkedList.delete("4");
doubleLinkedList.showList();
}
}

2.4 结果

遍历:
StudentNode{no='1', name='黄小黄', age=20}--->StudentNode{no='2', name='沸羊羊', age=25}--->StudentNode{no='3', name='懒羊羊', age=20}--->StudentNode{no='4', name='美羊羊', age=15}
更新编号为4的信息后:
更新成功!
StudentNode{no='1', name='黄小黄', age=20}--->StudentNode{no='2', name='沸羊羊', age=25}--->StudentNode{no='3', name='懒羊羊', age=20}--->StudentNode{no='4', name='祢豆子', age=14}
删除第一个和最后一个:
删除成功!
删除成功!
StudentNode{no='2', name='沸羊羊', age=25}--->StudentNode{no='3', name='懒羊羊', age=20}
Process finished with exit code 0

3 双向链表小结

单向链表查找的方向只能为一个方向，双向链表解决了这个缺点，可以实现双向查找；

单链表进行删除操作必须找到待删除元素的前一个元素，才能完成删除操作。而双向链表就简单多了，只需要找到待删除的节点，进行自我删除；

本节介绍了双向链表的遍历、添加、按顺序添加、更新、删除方法的实现，可以尝试像单链表篇一样，尝试求有效节点数量，以及如何逆序输出双向链表加强练习！

来源：https://blog.csdn.net/m0_60353039/article/details/127494841

投稿