Java实现单向链表的基本功能详解
作者:Java3y 发布时间:2022-12-18 10:57:02
一、前言
最近在回顾数据结构与算法,有部分的算法题用到了栈的思想,说起栈又不得不说链表了。数组和链表都是线性存储结构的基础,栈和队列都是线性存储结构的应用~
本文主要讲解单链表的基础知识点,做一个简单的入门~如果有错的地方请指正
二、回顾与知新
说起链表,我们先提一下数组吧,跟数组比较一下就很理解链表这种存储结构了。
2.1回顾数组
数组我们无论是C、Java都会学过:
数组是一种连续存储线性结构,元素类型相同,大小相等
数组的优点:
存取速度快
数组的缺点:
事先必须知道数组的长度
插入删除元素很慢
空间通常是有限制的
需要大块连续的内存块
插入删除元素的效率很低
2.2链表说明
看完了数组,回到我们的链表:
链表是离散存储线性结构
n个节点离散分配,彼此通过指针相连,每个节点只有一个前驱节点,每个节点只有一个后续节点,首节点没有前驱节点,尾节点没有后续节点。
链表优点:
空间没有限制
插入删除元素很快
链表缺点:
存取速度很慢
链表相关术语介绍,我还是通过上面那个图来说明吧:
确定一个链表我们只需要头指针,通过头指针就可以把整个链表都能推导出来了~
链表又分了好几类:
1、单向链表
一个节点指向下一个节点
2、双向链表
一个节点有两个指针域
3、循环链表
能通过任何一个节点找到其他所有的节点,将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环
操作链表要时刻记住的是:
节点中指针域指向的就是一个节点了!
三、Java实现链表
算法:
遍历
查找
清空
销毁
求长度
排序
删除节点
插入节点
首先,我们定义一个类作为节点
数据域
指针域
为了操作方便我就直接定义成public了。
public class Node {
//数据域
public int data;
//指针域,指向下一个节点
public Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
3.1创建链表(增加节点)
向链表中插入数据:
找到尾节点进行插入
即使头节点.next为null,不走while循环,也是将头节点与新节点连接的(我已经将head节点初始化过了,因此没必要判断头节点是否为null)~
/**
* 向链表添加数据
*
* @param value 要添加的数据
*/
public static void addData(int value) {
//初始化要加入的节点
Node newNode = new Node(value);
//临时节点
Node temp = head;
// 找到尾节点
while (temp.next != null) {
temp = temp.next;
}
// 已经包括了头节点.next为null的情况了~
temp.next = newNode;
}
3.2遍历链表
上面我们已经编写了增加方法,现在遍历一下看一下是否正确~~~
从首节点开始,不断往后面找,直到后面的节点没有数据:
/**
* 遍历链表
*
* @param head 头节点
*/
public static void traverse(Node head) {
//临时节点,从首节点开始
Node temp = head.next;
while (temp != null) {
System.out.println("关注公众号Java3y:" + temp.data);
//继续下一个
temp = temp.next;
}
}
结果:
3.3插入节点
插入一个节点到链表中,首先得判断这个位置是否是合法的,才能进行插入~
找到想要插入的位置的上一个节点就可以了~
/**
* 插入节点
*
* @param head 头指针
* @param index 要插入的位置
* @param value 要插入的值
*/
public static void insertNode(Node head, int index, int value) {
//首先需要判断指定位置是否合法,
if (index < 1 || index > linkListLength(head) + 1) {
System.out.println("插入位置不合法。");
return;
}
//临时节点,从头节点开始
Node temp = head;
//记录遍历的当前位置
int currentPos = 0;
//初始化要插入的节点
Node insertNode = new Node(value);
while (temp.next != null) {
//找到上一个节点的位置了
if ((index - 1) == currentPos) {
//temp表示的是上一个节点
//将原本由上一个节点的指向交由插入的节点来指向
insertNode.next = temp.next;
//将上一个节点的指针域指向要插入的节点
temp.next = insertNode;
return;
}
currentPos++;
temp = temp.next;
}
}
3.4获取链表的长度
获取链表的长度就很简单了,遍历一下,每得到一个节点+1即可~
/**
* 获取链表的长度
* @param head 头指针
*/
public static int linkListLength(Node head) {
int length = 0;
//临时节点,从首节点开始
Node temp = head.next;
// 找到尾节点
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
3.5删除节点
删除某个位置上的节点其实是和插入节点很像的, 同样都要找到上一个节点。将上一个节点的指针域改变一下,就可以删除了~
/**
* 根据位置删除节点
*
* @param head 头指针
* @param index 要删除的位置
*/
public static void deleteNode(Node head, int index) {
//首先需要判断指定位置是否合法,
if (index < 1 || index > linkListLength(head) + 1) {
System.out.println("删除位置不合法。");
return;
}
//临时节点,从头节点开始
Node temp = head;
//记录遍历的当前位置
int currentPos = 0;
while (temp.next != null) {
//找到上一个节点的位置了
if ((index - 1) == currentPos) {
//temp表示的是上一个节点
//temp.next表示的是想要删除的节点
//将想要删除的节点存储一下
Node deleteNode = temp.next;
//想要删除节点的下一个节点交由上一个节点来控制
temp.next = deleteNode.next;
//Java会回收它,设置不设置为null应该没多大意义了(个人觉得,如果不对请指出哦~)
deleteNode = null;
return;
}
currentPos++;
temp = temp.next;
}
}
3.6对链表进行排序
前面已经讲过了8种的排序算法了【八种排序算法总结】,这次挑简单的冒泡排序吧(其实我是想写快速排序的,尝试了一下感觉有点难.....)
/**
* 对链表进行排序
*
* @param head
*
*/
public static void sortLinkList(Node head) {
Node currentNode;
Node nextNode;
for (currentNode = head.next; currentNode.next != null; currentNode = currentNode.next) {
for (nextNode = head.next; nextNode.next != null; nextNode = nextNode.next) {
if (nextNode.data > nextNode.next.data) {
int temp = nextNode.data;
nextNode.data = nextNode.next.data;
nextNode.next.data = temp;
}
}
}
}
3.7找到链表中倒数第k个节点
这个算法挺有趣的:设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点
/**
* 找到链表中倒数第k个节点(设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点
*
* @param head
* @param k 倒数第k个节点
*/
public static Node findKNode(Node head, int k) {
if (k < 1 || k > linkListLength(head))
return null;
Node p1 = head;
Node p2 = head;
// p2比怕p1快k个节点
for (int i = 0; i < k - 1; i++)
p2 = p2.next;
// 只要p2为null,那么p1就是倒数第k个节点了
while (p2.next != null) {
p2 = p2.next;
p1 = p1.next;
}
return p1;
}
3.8删除链表重复数据
跟冒泡排序差不多,只要它相等,就能删除了~
/**
* 删除链表重复数据(跟冒泡差不多,等于删除就是了)
*
* @param head 头节点
*/
public static void deleteDuplecate(Node head) {
//临时节点,(从首节点开始-->真正有数据的节点)
Node temp = head.next;
//当前节点(首节点)的下一个节点
Node nextNode = temp.next;
while (temp.next != null) {
while (nextNode.next != null) {
if (nextNode.next.data == nextNode.data) {
//将下一个节点删除(当前节点指向下下个节点)
nextNode.next = nextNode.next.next;
} else {
//继续下一个
nextNode = nextNode.next;
}
}
//下一轮比较
temp = temp.next;
}
}
3.9查询链表的中间节点
这个算法也挺有趣的:一个每次走1步,一个每次走两步,走两步的遍历完,然后走一步的指针,那就是中间节点
/**
* 查询单链表的中间节点
*/
public static Node searchMid(Node head) {
Node p1 = head;
Node p2 = head;
// 一个走一步,一个走两步,直到为null,走一步的到达的就是中间节点
while (p2 != null && p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
return p1;
}
3.10通过递归从尾到头输出单链表
/**
* 通过递归从尾到头输出单链表
*
* @param head 头节点
*/
public static void printListReversely(Node head) {
if (head != null) {
printListReversely(head.next);
System.out.println(head.data);
}
}
3.11反转链表
/**
* 实现链表的反转
*
* @param node 链表的头节点
*/
public static Node reverseLinkList(Node node) {
Node prev ;
if (node == null || node.next == null) {
prev = node;
} else {
Node tmp = reverseLinkList(node.next);
node.next.next = node;
node.next = null;
prev = tmp;
}
return prev;
}
反转链表参考自:https://www.jb51.net/article/136185.htm
四、最后
理解链表本身并不难,但做相关的操作就弄得头疼,head.next next next next ....(算法这方面我还是薄弱啊..脑子不够用了.....)写了两天就写了这么点东西...
操作一个链表只需要知道它的头指针就可以做任何操作了
1、添加数据到链表中
遍历找到尾节点,插入即可(只要while(temp.next != null),退出循环就会找到尾节点)
2、遍历链表
从首节点(有效节点)开始,只要不为null,就输出
3、给定位置插入节点到链表中
首先判断该位置是否有效(在链表长度的范围内)
找到想要插入位置的上一个节点
将原本由上一个节点的指向交由插入的节点来指向
上一个节点指针域指向想要插入的节点
4、获取链表的长度
每访问一次节点,变量++操作即可
5、删除给定位置的节点
首先判断该位置是否有效(在链表长度的范围内)
找到想要插入位置的上一个节点
将原本由上一个节点的指向后面一个节点
6、对链表进行排序
使用冒泡算法对其进行排序
7、找到链表中倒数第k个节点
设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点
8、删除链表重复数据
操作跟冒泡排序差不多,只要它相等,就能删除了~
9、查询链表的中间节点
这个算法也挺有趣的:一个每次走1步,一个每次走两步,走两步的遍历完,然后走一步的指针,那就是中间节点
10、递归从尾到头输出单链表
只要下面还有数据,那就往下找,递归是从最后往前翻。
11、反转链表
有递归和非递归两种方式,我觉得是挺难的。可以到我给出的链接上查阅~
PS:每个人的实现都会不一样,所以一些小细节难免会有些变动,也没有固定的写法,能够实现对应的功能即可~
总结
参考资料:
http://www.cnblogs.com/whgk/p/6589920.html
https://www.cnblogs.com/bywallance/p/6726251.html
来源:https://segmentfault.com/a/1190000014045776
猜你喜欢
- 什么是“异步调用”?“异步调用”对应的是“同步调用”,同步调用指程序按照定义顺序依次执行,每一行程序都必须等待上一行程序执行完成之后才能执行
- public class CrossSum{ public static void main(String args[]){
- 类和对象的关系类就是一类对象的统称。对象就是这一类具体化的一个实例。 (对象是类的实例化)对象是什么?此对象非彼对象!!!😂说到对象就要提到
- @Autowired加到接口上但获取的是实现类问题Spring的@Autowired加到接口上但获取的是实现类? &
- 文章来源:csdn 作者:wangfengsdu经常听到回调函数(callback function)这个概念, 所谓回调函数,就是指这个函
- Mybatis @Select、foreachforeach属性属性描述item循环体中的具体对象。支持属性的点路径访问,如item.age
- 本文实例讲述了Java数组的定义、初始化、及二维数组用法。分享给大家供大家参考,具体如下:数组的定义1.数组是有序数据的集合,数组中的每个元
- 前言如果你了解过 Liunx ,了解过 Liunx 的中管道命令 | ,那么你会发现,其实 Java 8 的 stream 和 Liunx
- 本实例使用用户和订单的例子做说明: 一个用户可以有多个订单, 一个订单只对应一个用户。(其中应用到注释)1.代码的结构2. 建表语
- 目录一.数组的基本概念二.数组的声明三.数组的创建及初始化1.数组的创建2.数组的初始化四.访问数组元素五.for each 循环六.数组的
- eclipse导入Spring配置文件约束 Windows-Preference-XML-XMLCatalog点 Add 选Fil
- 一、 通过JDK网络类Java.net.HttpURLConnection1.java.net包下的原生java api提供的http请求使
- 前言消息队列中间件是分布式系统中重要的组件,主要解决应用耦合、异步消息、流量削锋等问题,实现高性能、高可用、可伸缩和最终一致性架构,是大型分
- 1. 启动入口本系列RocketMQ4.8注释github地址,希望对大家有所帮助,要是觉得可以的话麻烦给点一下Star哈前面我们已经分析完
- Java 8支持动态语言,看到了很酷的Lambda表达式,对一直以静态类型语言自居的Java,让人看到了Java虚拟机可以支持动态语言的目标
- 编写一个 Java 应用程序,实现图形界面多人聊天室(多线程实现),要求聊天室窗口标题是 “欢迎使用 XXX 聊天室应用
- Java synchronized 关键字 可以将一个代码块或一个方法标记为同步代码块。同步代码块是指同一时间只能有一个线程执行的代码,并且
- protected bool IsChineseLetter(string input,int index){int code = 0;in
- C#之继承继承、封装和多态是面向对象编程的重要特性。其成员被继承的类叫基类也称父类,继承其成员的类叫派生类也称子类。派生类隐式获得基类的除构
- 要想使Java运行,我们可以设计一个面向Java语言特性的虚拟机,并通过编译器将Java程序转换为它可以识别的指令序列,也称为Java字节码