手写单链表基础之增,删,查!附赠一道链表题

​一,文章简介

大家好,该文章是本人的公众号第一篇文章,是想通过最基础的数据结构来延伸出后面的算法题目。想必大家都知道算法和数据结构一直是程序员的必修课,但是我发现一味的刷题未必就会有好的效果,毕竟题目都是百变的。也正因为如此,个人想出一个方法先去熟悉下最基础的知识,比如该篇的单链表结构。在掌握基础原理知识后,再去刷题多少就会感觉知其然而知其所以然。好了,话不多说请看文章。

二,单链表简介

单链表(Singly Linked List)一种常见的数据结构,又名单向链表/线性表,单链表是以节点的方式存储,也就是链式存储。
单链表的每个节点会包含Data域和Next域,Next域是指向下个节点,
单链表是需要一个头指针来指向头节点的,需要声明的是头指针和头节点是不一样的,头指针是指向第一个头节点的,而头节点是单链表中的第一个节点。那么回过头来再看我们上面说的一个节点是包括Data域和Next域的,如下图所示:

使用头指针指向头节点,每个节点之间的链接,如下图所示:

通过上面简单的介绍帮助大家回顾下单链表的结构,接下来就和大家分享编写模拟一个单链表的实现。

三,初始化单链表

3.1 定义节点结构

我们定义一个节点属性包括城市编号(仅以用作标示),城市名称。

初始化好节点后接着还需要创建一个头指针节点

3.2 添加节点(尾插法)

新增节点大致分为2步,
第一步:定义一个辅助指针,用来指引下一个节点。
第二步:循环遍历节点,直到遍历到最后一个节点时,将该节点的next指向新插入的节点。如下图所示:

为方便我们验证添加节点的方法,再来一个遍历的单链表的方法。单链表的遍历与新增节点的第二步类似,同样使用辅助指针移动,如果next不为空,则直接打印出来,为了图省事就在CityNode中直接重写了toString方法(QAQ)。

接着来个main方法测试一下:

测试结果:

3.3 添加指定节点(按照编号插入)

按照顺序插入节点其实就相当于在指定位置插入,大致的思路是,先获取到要插入节点的位置,如果该节点不是最后一个节点,那么需要将该节点前面节点的next指向该新增节点。而新增节点的next就需要指向原节点的下个节点,以插入进单链表中。

第一步:同样定义辅助指针,用来遍历需要插入节点的位置

第二步:当获取到要插入节点位置后,更改新增节点的next位置,如图所示:

第三步:更改插入位置的next指针,将其指向新增的节点,如图所示:

3.4 删除节点

按照上述案例,通过城市编号删除一个指定节点。那么按照上面的套路,毫无疑问是同样需要一个辅助指针的。但是删除节点有个小小的细节,也就是我们定义的辅助指针是不能直接指向要删除的节点,如图:

如果辅助指针直接指向要删除的节点,这样是无法正常删除的,因此我们是需要将辅助指针指向要删除节点的上一个节点,通过更改next的指引来删除,如图:

四,小试牛刀(237)

先来分析一波题目,题中给出了链表的节点数据和要指定删除的节点。诶,等下~~~咋没有头节点???

好吧,其实这道题不仅要考察链表的结构,还要考察脑智商~

如果按照文章的描述,这道题就没法做了,因为给的信息是不全的。但换种思路去思考的话,题目中指定删除的节点为【5】,假设我们定义一个辅助变量指针的话,如图:

那么问题来了,辅助指针指向要删除的节点,是无法直接删除该节点。但如果我们把节点【5】的下一个节点【1】将节点【5】替换调。

按照当前思路的话,节点【5】已经不存在了,但是多处了节点【1】,那我们那只需要将节点【1】删除一个即可。按照删除节点的套路,可以这样写。

// 1,将删除节点的下个节点复制替换 node.data = node.next.data;
// 2,将节点【1】的指针直接指向节点【9】 node.next = node.next.next;

五,总结

上述篇幅中,介绍了单链表的尾插法和指定位置插入及删除,当亲自写一遍后其实发现并不难。当我们理解单链表的基础原理后,我们再来看看关于链表的题目。

看到这些题目有没有什么感触呢?
但是不急,关于链表的算法题会在后续的文章中与大家分享出来,每道题都分析出原理知识。

本篇文章是个人的第一篇,有很多纰漏之处还请包含。后期的文章个人会更注重文章的质量,包括排版给读者一个更清晰的视觉。才疏学浅,有错误之处还请多多指教。

相关推荐

发表评论

路人甲

网友评论(0)