写在前面
今天写代码的时候,发现我居然被Java的ListNode的输入卡了半天,所以就打算写一篇博客来整理一下ListNode。
链表的定义
首先ListNode就是链表,它的基本结构如下:
及一个包含数据,和指针的结构,我们将一个节点的指针的节点指向下一个节点,这样就形成了一串链式结构,并称之为:链表。
所以对于链表的定义如下:
/**
* Java ListNode 链表的各种定义方法
*
* @作者(yequan17)
* @版本(2021.12.6)
*/
public class JListNode
{
/**
* 基本结构
*/
class ListNodeBasicStructure{ //类名:Java类就是一种自定义的数据结构。
int val; //数据:节点数据。
ListNodeBasicStructure next; //对象:引用下一个节点对象。在Java中没有指针的概念,Java中的引用和C语言的指针类似。
}
/**
* 添加构造方法方便初始化
*/
class ListNodeConstructor{ //类名:Java类就是一种自定义的数据结构。
int val; //数据:节点数据。
ListNodeConstructor next; //对象:引用下一个节点对象。在Java中没有指针的概念,Java中的引用和C语言的指针类似。
ListNodeConstructor(int val){ //构造方法:构造方法和类名相同
this.val=val; //把接收的参数赋值给当前类的val变量
}
}
/**
* 范型写法:使用范型可以兼容不同的数据类型
*/
class ListNodeParadigm<E>{ //类名:Java类就是一种自定义的数据结构。
E val; //数据:节点数据。
ListNodeParadigm<E> next; //对象:引用下一个节点对象。在Java中没有指针的概念,Java中的引用和C语言的指针类似。
ListNodeParadigm(E val){ //构造方法:构造方法和类名相同
this.val=val; //把接收的参数赋值给当前类的val变量
}
}
}
我们逐个来看:
/**
* 基本结构
*/
class ListNode{ //类名:Java类就是一种自定义的数据结构。
int val; //数据:节点数据。
ListNode next; //对象:引用下一个节点对象。在Java中没有指针的概念,Java中的引用和C语言的指针类似。
}
这是最基本的链表结构,即一个数据一个指向下一个节点的指针或者说是指向下一个节点对象的引用。
但是这不并能满足我们的需要,因为我们在使用一个对象前必须对其进行初始化,如果不初始化,Java也会对其进行初始化。
所以我们将其修改为:
/**
* 添加构造方法方便初始化
*/
class ListNode{ //类名:Java类就是一种自定义的数据结构。
int val; //数据:节点数据。
ListNode next; //对象:引用下一个节点对象。在Java中没有指针的概念,Java中的引用和C语言的指针类似。
ListNode(int val){ //构造方法:构造方法和类名相同
this.val=val; //把接收的参数赋值给当前类的val变量
}
}
这就足够了吗?当然不是,有时候我们需要的可能并不是一个包含整型数据的链表,它也可能是浮点型,甚至是一个一个对象,所以就有了范型下链表的表示:
/**
* 范型写法:使用范型可以兼容不同的数据类型
*/
class ListNode{ //类名:Java类就是一种自定义的数据结构。
E val; //数据:节点数据。
ListNode<E> next; //对象:引用下一个节点对象。在Java中没有指针的概念,Java中的引用和C语言的指针类似。
ListNode(E val){ //构造方法:构造方法和类名相同
this.val=val; //把接收的参数赋值给当前类的val变量
}
}
链表的基本操作
好的在上面我们已经知道了链表是如何定义的,那么接下来,我们就来对链表进行一些最基本的在操作吧,它包括遍历链表、插入一个新的节点、置换一个节点和删除一个节点。
我们先来看链表的遍历。
再看一遍链表的结构,遍历链表就像遍历数组一样,从头到尾一个一个走就行,和数组不一样的是,我们遍历数组是根据数组的下标从零开始,依次前进。那么如何遍历链表呢?
我们发现,现在有两个问题摆在我们的面前:
- 怎么找到链表的头部,或者说,遍历应该从哪里开始呢?
- 怎么找到链表的尾部,或者说,遍历何时结束呢?
这个问题其实很好解决。
我们只需要将链表的第一个节点定义为head,头节点,然后将它后面的节点定义为head.next,再后面的就是head,next.next,当然我们并不需要怎么写,我们可以定义一个中间节点nextNode用来表示当前节点,然后每一次将nextNode.next指向nextNode。这么说可能有些抽象,我们不妨来看一下图解:
首先,我们定义一个nextNode,并让它指向head,即nextNode=head
接着我们生成一个新的节点node,并让nextNode.next指向这个node,即nextNode.next=node
再让nextNode=nextNode.next,即将当前节点的位置向后移动一个,便得到了:
依次类推,便可以向后遍历链表了,那么如何结束呢?
其实也很简单,因为,最后一个节点的下一个节点为空,这就是一个判断结束的标志,即nextNode.next==null时,就遍历结束。
接下来,我们来看一个创建链表、为其赋值,再将其输出的例子:
/**
* Java ListNode 链表的创建与遍历
*
* @作者(yequan17)
* @版本(2021.12.6)
*/
public class JListNodeTraverse
{
/**
* 定义链表
*/
static class ListNode{ //类名:Java类就是一种自定义的数据结构。
int val; //数据:节点数据。
ListNode next; //对象:引用下一个节点对象。在Java中没有指针的概念,Java中的引用和C语言的指针类似。
ListNode(int val){ //构造方法:构造方法和类名相同
this.val=val; //把接收的参数赋值给当前类的val变量
}
}
/**
* 创建链表及遍历链表
*/
public static void main(String[] args){
ListNode head=new ListNode(0); //创建头节点
ListNode nextNode; //声明一个变量用来在移动过程中指向当前节点
nextNode=head; //指向头节点
//创建链表
for(int i=1;i<10;i++){
ListNode node=new ListNode(i);//生成新的节点
nextNode.next=node; //把节点连起来
nextNode=nextNode.next; //把当前节点往后移动
}//当for循环完成之后,nextNode指向最后一个节点
nextNode=head;//重现赋值让它指向头节点
print(nextNode);//打印输出
}
static void print(ListNode listNode){
//创建链表节点
while(listNode!=null){
System.out.println("节点:"+listNode.val);
listNode=listNode.next;
}
System.out.println();
}
}
好看完了遍历,我们来看一下链表的一个很重要的方法,插入节点。
如何在这样的一个链表中插入节点呢?
直观的理解就是:
所以,如果我们需要在nextNode后面插入一个新的节点newnode,那么我们需要做的第一件事就是将nextNode的下一个节点保存下来,为什么要这么做呢?
因为,单链表中,我们只能根据前一个节点来找到它的下一个节点,而不能更具一个节点找到它前面的节点。
所以,我们需要先将nextNode.next保存下来,可以记为node。
接着让nextNode.next指向newnode,即nextNode.next=newnode,这样我们就在nextNode后面加上了一个新的节点,但这还没完,我们还需要将整个链表剩下的部分接回来,所以,我们可以让newnode指向我们之前保存的node,即newnode.next=node,而对于node,它后面的节点没有发生变化,所以就有了一条新的链表。
代码如下:
/**
* Java ListNode 链表的创建与插入节点
*
* @作者(yequan17)
* @版本(2021.12.6)
*/
public class JListNodeInsert
{
/**
* 定义链表
*/
static class ListNode{ //类名:Java类就是一种自定义的数据结构。
int val; //数据:节点数据。
ListNode next; //对象:引用下一个节点对象。在Java中没有指针的概念,Java中的引用和C语言的指针类似。
ListNode(int val){ //构造方法:构造方法和类名相同
this.val=val; //把接收的参数赋值给当前类的val变量
}
}
/**
* 创建链表及在链表特定位置插入新的节点
*/
public static void main(String[] args){
ListNode head=new ListNode(0); //创建头节点
ListNode nextNode; //声明一个变量用来在移动过程中指向当前节点
nextNode=head; //指向头节点
//创建链表
for(int i=1;i<10;i++){
ListNode node=new ListNode(i);//生成新的节点
nextNode.next=node; //把节点连起来
nextNode=nextNode.next; //把当前节点往后移动
}//当for循环完成之后,nextNode指向最后一个节点
nextNode=head;//重现赋值让它指向头节点
print(nextNode);//打印输出
while(nextNode!=null){
if(nextNode.val==5){
ListNode newnode=new ListNode(99);//生成新的节点
ListNode node=nextNode.next;//先保存下一个节点
nextNode.next=newnode;//插入新节点
newnode.next=node;//新节点的下一个节点指向之前保存的节点
}
nextNode=nextNode.next;
}//循环完成之后,nextNode指向最后一个节点
nextNode=head;//重新赋值让它指向头节点
print(nextNode);//打印输出
}
static void print(ListNode listNode){
//创建链表节点
while(listNode!=null){
System.out.println("节点:"+listNode.val);
listNode=listNode.next;
}
System.out.println();
}
}
好,看完了插入,我们来看一下如何替换一个节点呢?
思路同上,我们同样要先保存链表的后半截,但这个后半截是从要被替换节点的后面开始的,即从node.next开始,所以,我们可以直接定义node为要被替换节点的下一个节点,套用上面插入的操作就是,node=nextNode.next.next,然后同上面一样操作,当然也要注意一点,我们是在进行替换操作,所以应该将被替换节点从整个链表中取出,或者说删除,那么很简单,我们只需要在最开始就让nextNode.next.next指向空就行,即nextNode.next.next=null。
所以代码如下:
/**
* Java ListNode 链表的创建与替换节点
*
* @作者(yequan17)
* @版本(2021.12.6)
*/
public class JListNodeChange
{
/**
* 定义链表
*/
static class ListNode{ //类名:Java类就是一种自定义的数据结构。
int val; //数据:节点数据。
ListNode next; //对象:引用下一个节点对象。在Java中没有指针的概念,Java中的引用和C语言的指针类似。
ListNode(int val){ //构造方法:构造方法和类名相同
this.val=val; //把接收的参数赋值给当前类的val变量
}
}
/**
* 创建链表及在链表特定位置插入新的节点
*/
public static void main(String[] args){
ListNode head=new ListNode(0); //创建头节点
ListNode nextNode; //声明一个变量用来在移动过程中指向当前节点
nextNode=head; //指向头节点
//创建链表
for(int i=1;i<10;i++){
ListNode node=new ListNode(i);//生成新的节点
nextNode.next=node; //把节点连起来
nextNode=nextNode.next; //把当前节点往后移动
}//当for循环完成之后,nextNode指向最后一个节点
nextNode=head;//重现赋值让它指向头节点
print(nextNode);//打印输出
while(nextNode!=null){
if(nextNode.val==5){
ListNode newnode=new ListNode(99);//生成新的节点
ListNode node=nextNode.next.next;//先保存要替换节点的下一个节点
nextNode.next.next=null;//被替换节点指向为空,等待Java垃圾回收
nextNode.next=newnode;//插入新节点
newnode.next=node;//新节点的下一个节点指向之前保存的节点
}
nextNode=nextNode.next;
}//循环完成之后,nextNode指向最后一个节点
nextNode=head;//重新赋值让它指向头节点
print(nextNode);//打印输出
}
static void print(ListNode listNode){
//创建链表节点
while(listNode!=null){
System.out.println("节点:"+listNode.val);
listNode=listNode.next;
}
System.out.println();
}
}
通过上面的操作,我们对链表已经很熟悉了,因此,删除某一个节点的操作其实就是将当前节点nextNode直接指向后面的后面的节点,我们定义即nextNode后面的后面的节点为listnode,即listnode=nextNode.next.next,然后删除中间节点,那么nextNode.next=listnode。
代码如下:
/**
* Java ListNode 链表的创建与删除节点
*
* @作者(yequan17)
* @版本(2021.12.6)
*/
public class JListNodeDelete
{
/**
* 定义链表
*/
static class ListNode{ //类名:Java类就是一种自定义的数据结构。
int val; //数据:节点数据。
ListNode next; //对象:引用下一个节点对象。在Java中没有指针的概念,Java中的引用和C语言的指针类似。
ListNode(int val){ //构造方法:构造方法和类名相同
this.val=val; //把接收的参数赋值给当前类的val变量
}
}
/**
* 创建链表及在链表特定位置插入新的节点
*/
public static void main(String[] args){
ListNode head=new ListNode(0); //创建头节点
ListNode nextNode; //声明一个变量用来在移动过程中指向当前节点
nextNode=head; //指向头节点
//创建链表
for(int i=1;i<10;i++){
ListNode node=new ListNode(i);//生成新的节点
nextNode.next=node; //把节点连起来
nextNode=nextNode.next; //把当前节点往后移动
}//当for循环完成之后,nextNode指向最后一个节点
nextNode=head;//重现赋值让它指向头节点
print(nextNode);//打印输出
while(nextNode!=null){
if(nextNode.val==5){
ListNode listnode=nextNode.next.next;//先保存要删除节点的下一个节点
nextNode.next.next=null;//被替换节点指向为空,等待Java垃圾回收
nextNode.next=listnode;//指向被删除节点的下一个节点
}
nextNode=nextNode.next;
}//循环完成之后,nextNode指向最后一个节点
nextNode=head;//重新赋值让它指向头节点
print(nextNode);//打印输出
}
static void print(ListNode listNode){
//创建链表节点
while(listNode!=null){
System.out.println("节点:"+listNode.val);
listNode=listNode.next;
}
System.out.println();
}
}
总结
ListNode虽然看起来不想数组那么简约,但其实它的原理也很简单,只需要多加练习,就能熟练掌握这项数据结构,而在整个操作过程中,我们可以发现,我们让某一个节点指向空的之后,并没有对其释放,这是为什么呢,这便是Java的一个强大的功能,垃圾回收,当没有任何地方引用这个对象时,Java就会将其回收。