Java代码实战:通过手写一个单链表,告诉你学习编程的方法和捷径!
2020/2/20 17:01:50
本文主要是介绍Java代码实战:通过手写一个单链表,告诉你学习编程的方法和捷径!,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
读者朋友们,你们现在可以手写一个单链表吗?😄
截止到目前,我还经常收到一些读者的微信,他们向我抱怨道“为什么我看视频或者看书都能够看懂,就是写不出来代码呢?”
哈哈,这是不是就是我们一直说的“一看就会,一做就错”呢?别说你们,我相信每个初学编程的人都会遇到这样的问题,看书觉得自己看明白了,知道咋回事了,可是一到自己写代码,要么无从下手,要么bug百出,真的很打击信心啊。
对于编程的学习,很多人也会问我有没有什么捷径,我通常回答说“多看多练”,但是实际情况是很多人都是看的多,练的少,这其实是导致很多人,一看就懂,一做就错,时间长了就忘的罪魁祸首之一(还有很多自身因素),尤其代码这块,更加要多敲!
今天,我就以单链表为例来聊聊写代码这些事吧,我会一步步带大家写出一个简易的单链表,并且中间会不断的给大家讲解如何进行代码实战,这其中的一些思考方法也是很重要的。
知己知彼,方能百战不殆
首先就是关于写代码的第一步,那就是你得理解你要写什么代码,比如我们今天要用java去实现一个单链表,那么,你必须得知道啥是链表吧,这是前提啊,如果你连链表都不知道是个什么玩意,那你能写出个什么玩意呢?😂
而且,你不仅要了解,还要深入的了解,这样写起来相应的代码才会得心应手,就拿链表来说,也许你现在不知道啥是链表,但是嘞,你花个十来分钟,随便找一篇文章看看,也许对于链表就能知道个大概,但是即使如此,让你实现一个单链表,你很大可能还是写不出来。
简单的了解并不能让你轻松的写出代码来,你还需要对其中的一些关键性知识做深入理解,比如链表里面的指针,其实在java中没有指针这一说,取而代之的可以说是引用,但是写链表代码的时候我们一般都会说指针,什么next指针,所以啊,对于手写单链表,你不仅要理解啥是链表,更要理解其中指针的含义。
对于链表,我之前特意写过一篇文章,详细的聊了聊链表,建议对链表不熟悉的去看看再回过来看今天的实战部分:链表不会?看这个立马就懂!
心急吃不了热豆腐
对于手写单链表,在了解了链表相关的知识之后,我们就要分析一个单链表该如何实现了,我们初次在进行这样的操作的时候不要渴望自己一次就能写出完代码来,我觉得那是不可能的,刚开始我们可以写简单点,代码可以写的不那么优雅,不那么高效,但是要实现最起码的功能,然后把这些基本的简单的理解透了,再去不断迭代我们的代码。
要知道,好文章都是修改出来的,代码也是一样!
所以这次手写单链表,我们就实现一些简单的功能,比如最常用的增加一个新的节点,然后还可以删除一个节点,当然我们还可以看看这个链表保存的数据,也就是打印链表。
链表是个重要的知识点,我们要一步步的去攻克它,不要想着一口吃个胖子,一下子把链表相关的代码都烂熟于心。
这个节点该怎么定义
我想你已经知道了什么是链表了,那么我们首先要考虑的就是这个链表中的节点该怎么定义,还记得链表的结构吧,它长这个样子:(这里是单链表)
在链表中,都是由一个个的节点组成的,所以我们在实现单链表的时候,首先就是要定义一个节点,在Java中,万物皆对象啊,所以嘞,我们首先要想到把节点用一个类来表示,也就是一个节点类,那么这个类名称叫啥嘞,一般就是Node了,来来,写代码啦
class Node{ } 复制代码
这里定义一个Node嘞,链表中的一个节点是这样的:
包括两个部分,一个是真得数据,一个是保存下一个对象的next指针,其实就是下一个Node对象的引用,所以我们接着写代码:
class Node{ //真实数据 int data; //next指针,指向下一个节点对象 Node next; } 复制代码
这样就ok了吗?我们想下,链表归根到底是用来保存数据的,那么我们创建一个节点的时候是不是应该往里面塞数据啊,这个代码怎么来呢?很容易想到啊,可以通过构造函数啊,就是这样啦:
class Node{ //结点数据 int data; //结点指针 Node next; //无参构造函数 public Node(int data){ this.data = data; } } 复制代码
ok,这样一个节点我们就定义好了,现在有节点了,我们就开始写我们的单链表了,首先起个名字吧,就叫做MyLinkedList吧。
增加节点
接下来我们就实现第一个功能,那就是增加节点啊,这里其实涉及不少问题,什么哨兵节点,什么头插,什么尾插以及中间插入嘞,我们不搞那么麻烦,我们先设定一个场景前提:
本来没有链表,我们要创建一个出来,然后增加的话直接在尾部追加即可
这个很好理解吧,那么我们就开始写代码吧:
public class MyLinkedList { //定义一个头结点 Node head; //链表的长度 int size; } 复制代码
这里我们首先需要定义一个头结点,为啥要定义这个头结点嘞,因为一个链表,咋弄也得先有一个节点,然后一个连着一个的增加吧,所以只有有了头结点,也就是第一个节点,剩下的才顺理成章啊,对了,把我们定义的节点类也放进去,这时候是内部类的方式:
public class MyLinkedList { //定义一个头结点 Node head; //链表的长度 int size; //创建结点 class Node{ //结点数据 int data; //结点指针 Node next; //无参构造函数 public Node(int data){ this.data = data; } } } 复制代码
写我们的增加节点的方法:
//增加节点,顺序插入,也就是在尾部追加数据 public void addNode(int data){ } 复制代码
想想怎么写,我们首先想到的就是现在还没有链表嘞,我们增加第一个数据那就是增加的头结点啊,所以先对头结点进行处理:
//增加节点,顺序插入,也就是在尾部追加数据 public void addNode(int data){ //头结点的处理 if(head == null){ head = new Node(data); size++; return; } } 复制代码
这个逻辑简单,不用再多加解释吧,这其实就是第一次增加节点的时候也就是创建头结点的操作,如此一来,就有了一个头结点,接下来呢?这是增加头结点可以这么来,那接下里增加新的节点就是把新的节点跟在前一个节点的后面,一个个链接起来吧,那这个该怎么操作嘞?
//遍历到尾结点 Node temp = head; while (temp.next != null){ temp = temp.next; } //找到尾结点,赋值 temp.next = new Node(data); size++; 复制代码
代码就是上面这样的,就这些代码,第一次写链表代码的同学要好好理解并且要记住了,这里的核心就是遍历找到链表的尾结点,为啥,因为我们再次添加新节点,之前规定了就是在尾部追加啊,所以我们重点就是要找到这个尾部代码,接下来就是理解为啥要写这么一句代码:
Node temp = head; 复制代码
为啥要定义一个临时节点出来呢?首先你想啊,我们要遍历找到尾结点,肯定是从头结点遍历,但是现在我们又不知道这个尾结点是谁,头结点又是固定的,因此我们需要定义一个新的临时节点,从头结点开始,可以一次向后移动,移动到尾结点的时候把其复制成尾结点,这样一来就好表示了,仔细想想。
然后就是这个循环代码:
while (temp.next != null){ temp = temp.next; } 复制代码
显而易见啊,这个就是遍历找到尾结点啊,temp的next就是指的头结点后面的节点,如果不为空,说明头结点后面还有节点,那么就把这个临时节点继续后移,怎么后移嘞,现在这个temp指向头结点,对吧,这个知道吧,后移的的话也就是指向头结点的后一个节点,那不就是把头结点的后一个节点赋值给这个临时节点嘛,正是这样:
temp = temp.next; 复制代码
然后直到找到这个临时节点后面没有节点了,也就是为空了,执行这些代码:
//找到尾结点,赋值 temp.next = new Node(data); size++; 复制代码
此时这个临时节点temp指向的就是尾结点了,然后在气候追加新的节点,就是为其next赋值新节点。
如此一来,增加节点这个操作我们就完成了,整体代码如下:
/** * 增加节点,顺序插入,也就是在尾部追加数据 * @param data */ public void addNode(int data){ //头结点的处理 if(head == null){ head = new Node(data); size++; return; } //遍历到尾结点 Node temp = head; while (temp.next != null){ temp = temp.next; } //找到尾结点,赋值 temp.next = new Node(data); size++; } 复制代码
删除节点
知道如何新增节点了,接下来我们就要看看如何删除节点了,首先,我们看看如下的链表:
我们看这个链表,如果我们删除数据2的话,是不是就要把数据1的next指向数据3,也就是数据1.next = 数据3,脑海中要有这个概念。
接下来我们看看这个删除的代码该怎么写,写这个删除的话,我们得考虑依据什么来删除,我们之前定义了一个size来代表链表的长度,增加一个节点就加一,你想是不是可以看做这些链表节点根据加入的先后顺序被编号了,也就是有了索引,那么我们这里删除的时候就根据这个索引来删除。
然后我们得考虑了,有这么些特殊情况:
public Node deleteNode(int index){ //处理空链表 if (size == 0){ return null; } //处理异常索引 if (index < 1 || index > size){ return null; } //删除头结点 if (index == 1){ Node temp = head; head = head.next; size--; return temp; } } 复制代码
首先就是空链表,然后还有越界索引,这个我想都好理解,我就不多说了,我们写的这个删除节点的代码会返回被删除的这个节点,在处理头结点的时候,删除头结点要返回头结点该怎么返回嘞,我这里的鹅湖粗粒是定义一个临时节点指向最开始的这个头结点,更新了头结点之后把原先的返回,这些代码没什么复杂,就不多说了。
我们接下来看,出去这些特殊情况,我们删除后续节点该怎么操作,想想上面说的那三个节点数据删除数据2的操作,这个时候你得明确,我们根据索引去删除,再次删除的一定不是头结点了,因为头结点已经按照特殊情况去处理了,所以我们再次删除,就要看看这个索引是啥,我们需要遍历,找到这个索引对应的节点。
你想啊,此时我们遍历是不是就是从链表的第二个节点开始,所以我们先定义一个索引值int i = 2,知道为啥等于2吧,这就代表链表中的第二个节点,然后要删除的节点的索引是index,我们就需要找到这个i == index的情况就找到要删除的节点了。
然后,我们仔细看看下面这个图:
其实现在我们只知道头结点,然后要从头结点下一个节点去遍历,我们怎么表示这个遍历的起点呢?我们把这个当做当前节点,用cureNode来表示,这个其实也好表示,不说就是head.next嘛,而且此时这个当前节点的索引是2,这都好理解吧,假如说啊,这个index就是2,说明我们删除的节点就是头结点之后的这个节点,那么是不是就是把头结点的next指向当前节点的next所指的节点呢?代码表示就是:
head.next = cureNode.next; 复制代码
当然,这里不应删除的就是头结点之后的节点,所以统一来说:
如果我们要删除当前节点,就需要让当前节点的上一个节点的next指向当前节点的next所指向的对象
代码表示就是:
preNode.next = cureNode.next; 复制代码
那么思考下,这里的cureNode和preNode最初该怎么表示,想想,我们最初只知道头结点的,所以这个当前节点是不是就是:
Node cureNode = head.next; 复制代码
而这个preNode不就是头结点嘛:
Node preNode = head; 复制代码
所以啊,我们删除除特殊情况外的节点代码就可以这样写:
//删除非头结点 //从头结点的下一个节点开始遍历 Node cureNode = head.next; //记录当前循环的节点的上一个节点用于删除当前节点 Node preNode = head; int i = 2; while (cureNode != null){ if (i == index){ //要删除的就是此节点 preNode.next = cureNode.next; size--; break; }else { preNode = cureNode; cureNode = cureNode.next; i++; } } return cureNode; 复制代码
然后返回删除的当前节点,另外要注意的就是这段代码:
preNode = cureNode; cureNode = cureNode.next; i++; 复制代码
这个其实就是往下继续遍历,知道找到要删除的那个节点,把cureNde和preNode依次往后移动。
这么一来删除节点的代码就搞定了,整体代码如下:
/** * 删除节点,根据索引删除 * @param index * @return */ public Node deleteNode(int index){ //处理空链表 if (size == 0){ return null; } //处理异常索引 if (index < 1 || index > size){ return null; } //删除头结点 if (index == 1){ Node temp = head; head = head.next; size--; return temp; } //删除非头结点 //从头结点的下一个节点开始遍历 Node cureNode = head.next; //记录当前循环的节点的上一个节点用于删除当前节点 Node preNode = head; int i = 2; while (cureNode != null){ if (i == index){ //要删除的就是此节点 preNode.next = cureNode.next; size--; break; }else { preNode = cureNode; cureNode = cureNode.next; i++; } } return cureNode; } 复制代码
该怎么打印链表嘞?
一般的啊,我们还要搞一个打印链表的操作,这是为了看到链表的内容,方便做一些测试啊,那么该怎么打印链表啊,咋一看,一想好像摸不着头脑,再仔细一想,我擦,不就是从头结点开始遍历,然后分别打印出每个节点的data数据吗?
来来,直接上代码:
/** * 打印链表 */ public void printList(){ Node curNode = head; //循环遍历到尾结点 while (curNode != null){ System.out.print(curNode.data + " "); curNode = curNode.next; } System.out.println(); } 复制代码
经过上面新增节点和删除节点的剖析,这段代码不在话下吧,就不多说啦。
返回链表长度
这个其实我觉得还是很有必要的,虽然真的超级简单:
/** * 返回链表长度 */ public int getSize(){ return size; } 复制代码
差不多啦,测试一下
到这里我们就完成了最基本和最简单的增加,删除和打印链表,我们来测试下看看,先增加几个节点,然后打印看下链表长度:
MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addNode(10); myLinkedList.addNode(20); myLinkedList.addNode(30); myLinkedList.printList(); System.out.println("链表长度= " + myLinkedList.getSize()); 复制代码
测试结果如下:
吆西,像那么回事啊,删除一个试试(删除头结点):
//删除链表节点 MyLinkedList.Node node = myLinkedList.deleteNode(1); System.out.println("删除的节点数据是:" + node.data); myLinkedList.printList(); System.out.println("链表长度= " + myLinkedList.getSize()); 复制代码
测试结果是:
不赖啊,继续删除其他节点试试,比如删除最后一个:
MyLinkedList.Node node = myLinkedList.deleteNode(3); 复制代码
测试结果是:
阔以,是那么一回事😂
这就是渣渣代码
实话说,上面的代码实现真不怎么滴,可以优化的地方有很多,也有很多考虑不周的地方,但是这里不是为了要实现一个多美完美的单链表代码,而是通过实现一些简单的基本的功能,来告诉大家,多敲代码很重要,你不敲,你第一次真的写不出来,即使自己动手了,也不定写的出来,即使写出来了,bug也非常多。
但是还是那句话:好文章都是修改出来的,代码也是如此!
当你开始写的那一刻,你就迈出了一大步,你只会越来越好,代码写的越来越流畅,理解的也越来越深刻,代码能力就是这么提升上来的。
另外,很多人问,学编程有什么不二法门吗?
答案是有的,啥嘞,四个字“多看多练”,尤其多练!
朋友们,拿起你的键盘,敲起来吧!
感谢阅读
大学的时候选择了==自学Java==,工作了发现吃了==计算机基础不好==的亏,==学历不行==这是没办法的事,只能后天弥补,于是在==编码之外==开启了自己的逆袭之路,不断的学习Java核心知识,深入的研习计算机基础知识,所有心得全部书写成文,整理成有目录的PDF,持续原创,PDF在公众号持续更新,如果你也不甘平庸,那就与我一起在编码之外,不断成长吧!
其实这里不仅有技术,更有那些技术之外的东西,比如,如何做一个精致的程序员,而不是“屌丝”,==程序员本身就是高贵的一种存在啊,难道不是吗?==
非常欢迎你的加入,未来的日子,编码之外,有你有我,一起做一个==人不傻,钱很多,活得久==的快乐的程序员吧!
回复关键字“PDF”,获取技术文章合集,已整理好,带有目录,欢迎一起交流技术!
另外回复“庆哥”,看庆哥给你准备的惊喜大礼包,只给首次关注的你哦!
任何问题,可以加庆哥微信:H653836923,另外,我有个交流群,我会不定期在群里分享学习资源,不定时福利,感兴趣的可以说下我邀请你!
==对了,如果你是个Java小白的话,也可以加我微信,我相信你在学习的过程中一定遇到不少问题,或许我可以帮助你,毕竟我也是过来人了!==
感谢各位大大的阅读🥰
这篇关于Java代码实战:通过手写一个单链表,告诉你学习编程的方法和捷径!的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性