java数据结构基础:单链表与双向链表
作者:去吧猫头夜鹰 时间:2023-03-02 09:21:59
单链表:
每个数据是以节点的形式存在的
每个节点分为数据域和指针域
数据域中保存该节点的数据
指针域中保存指向下一个节点的指针
实现思路:
节点类SingleNode中保存数据和指向下一个节点的指针
单链表类SingleLinkedList中保存链表的头节点,实现相关链表方法
对于链表方法,涉及到位置查找,如在指定位置增加、删除节点,需要使用一个临时变量temp从头节点开始遍历,直至找到对应的位置。
对于节点的增加删除,只需要修改相关结点的指针指向即可
代码实现:
节点类SingleNode:
public class SingleNode {
public int data;
public SingleNode next;
public SingleNode(int data) {
this.data = data;
}
@Override
public String toString() {
return "SingleNode{" + "data=" + data + '}';
}
}
单链表类SingleLinkedList:
public class SingleLinkedList {
private SingleNode head = new SingleNode(0);
//获取头结点
public SingleNode getHead(){
return head;
}
//添加节点
public void add(SingleNode singleNode) {
SingleNode temp = head;
//找到链表最后一个节点
while (temp.next != null) {
temp = temp.next;
}
temp.next = singleNode;
}
//按顺序添加节点
public void addByOrder(SingleNode singleNode) {
SingleNode temp = head;
while (true) {
if (temp.next == null) {
//已经遍历到链表最后了
break;
} else if (temp.next.data > singleNode.data) {
//找到应插入的位置
break;
}
temp = temp.next;
}
singleNode.next = temp.next;
temp.next = singleNode;
}
//删除节点
public void delete(int data) {
SingleNode temp = head;
boolean flag = false; //标志是否找到待删除节点的前一个节点
while (true) {
if (temp.next == null) {
//已经遍历到链表最后了
break;
} else if (temp.next.data == data) {
//找到待删除节点的前一个节点
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
} else {
System.out.println("要删除的节点不存在");
}
}
//输出链表
public void show() {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
SingleNode temp = head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
}
双向链表:
每个节点中除了保存了指向后一个节点的指针外,还保存了指向前一个节点的指针
实现思路:
相关方法实现与单链表类似,不同点在于需要增加对指向前一个节点的指针的更改
代码实现:
节点类DoubleNode:
public class DoubleNode {
public int data;
public DoubleNode next;
public DoubleNode pre;
public DoubleNode(int data) {
this.data = data;
}
@Override
public String toString() {
return "DoubleNode{" + "data=" + data + '}';
}
}
双向链表类DoubleLinkedList:
public class DoubleLinkedList {
public DoubleNode head = new DoubleNode(0);
//获取头结点
public DoubleNode getHead() {
return head;
}
//添加节点
public void add(DoubleNode doubleNode) {
DoubleNode temp = head;
//找到链表最后一个节点
while (temp.next != null) {
temp = temp.next;
}
temp.next = doubleNode;
doubleNode.pre = temp;
}
//删除节点
public void delete(int data) {
DoubleNode temp = head.next;
boolean flag = false; //标志是否找到待删除节点的前一个节点
while (true) {
if (temp == null) {
//已经遍历到链表最后了
break;
} else if (temp.data == data) {
//找到待删除节点
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.pre.next = temp.next;
if (temp.next != null) {
//若删除节点不为最后一个节点
temp.next.pre = temp.pre;
}
} else {
System.out.println("要删除的节点不存在");
}
}
//输出链表
public void show() {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
DoubleNode temp = head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
}
来源:https://blog.csdn.net/qq_25274377/article/details/119246506
标签:java,单链表,双向链表,基础
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
心动吗?正大光明的免费使用IntelliJ IDEA商业版
2023-11-25 04:29:48
![](https://img.aspxhome.com/file/2023/6/59976_0s.jpg)
C#过滤DataTable中空数据和重复数据的示例代码
2022-03-15 19:33:45
Java RandomAccessFile 指定位置实现文件读取与写入
2023-06-05 17:06:25
idea启动springmvc项目时报找不到类的解决方法
2023-11-09 16:51:04
![](https://img.aspxhome.com/file/2023/6/59416_0s.png)
Mybatis查询多条记录并返回List集合的方法
2023-08-08 05:16:48
一篇文章带你了解Maven的生命周期
2022-04-22 10:40:22
![](https://img.aspxhome.com/file/2023/0/75440_0s.png)
最值得Java开发者收藏的网站
2022-03-09 15:57:08
java使用淘宝API读写json实现手机归属地查询功能代码
2021-05-31 03:27:38
java虚拟机中多线程总结
2022-09-01 22:55:48
![](https://img.aspxhome.com/file/2023/6/79956_0s.png)
SpringBoot注册Filter的两种实现方式
2023-01-01 10:26:05
![](https://img.aspxhome.com/file/2023/0/79230_0s.jpg)
springboot整合通用Mapper简化单表操作详解
2022-08-19 19:24:19
JSON各种转换问题(json转List,json转对象等)
2021-09-28 08:53:45
使用SpringBoot获取resources文件路径
2022-10-12 15:29:56
![](https://img.aspxhome.com/file/2023/9/66639_0s.png)
SpringCloud Nacos + Ribbon 调用服务的实现方式(两种)
2023-11-18 09:30:38
![](https://img.aspxhome.com/file/2023/5/86035_0s.png)
深入理解C#之枚举
2023-01-02 14:08:33
C#实现char字符数组与字符串相互转换的方法
2022-01-18 05:28:52
springboot 在idea中实现热部署的方法
2022-10-24 22:27:19
![](https://img.aspxhome.com/file/2023/8/70518_0s.png)
C# dump系统lsass内存和sam注册表详细
2021-06-26 12:19:53
![](https://img.aspxhome.com/file/2023/9/70429_0s.jpg)
详解Spring中的@PropertySource注解使用
2023-05-05 06:40:15
Java日常练习题,每天进步一点点(7)
2023-11-27 00:34:58
![](https://img.aspxhome.com/file/2023/8/59978_0s.png)