数据结构与算法学习笔记之写链表代码的正确姿势(下)

前言

想成功你就得有决心,并有方法和技巧的付出精力。

正文

如何优雅的写出链表代码?

一、理解指针或引用的含义

1.含义:

将某个变量(对象)赋值给指针(引用),实际上就是就是将这个变量(对象)的地址赋值给指针(引用)。

指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量

2.示例

p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。 p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址。

二、警惕指针丢失和内存泄漏(单链表)

在插入和删除结点时,要注意先持有后面的结点再操作,否者一旦后面结点的前继指针被断开,就无法再访问,导致内存泄漏。

1.插入节点

在节点a和节点b之间插入节点x,b是a的下一节点,,p指针指向节点a,则造成指针丢失和内存泄漏的代码:p—>next = x;x—>next = p—>next; 显然这会导致x节点的后继指针指向自身。 正确的写法是2句代码交换顺序,即:x—>next = p—>next; p—>next = x;

2.删除节点

在节点a和节点b之间删除节点b,b是a的下一节点,p指针指向节点a:p—>next = p—>next—>next

三、利用“哨兵”简化实现难度

1.什么是“哨兵”?

链表中的“哨兵”节点是解决边界问题的,不参与业务逻辑。如果我们引入“哨兵”节点,则不管链表是否为空,head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表,相反,没有“哨兵”节点的链表就称为不带头链表。

2.未引入“哨兵”的情况

如果在p节点后插入一个节点,只需2行代码即可搞定: new_node—>next = p—>next; p—>next = new_node; 但,若向空链表中插入一个节点,则代码如下: if(head == null){ head = new_node; } 如果要删除节点p的后继节点,只需1行代码即可搞定: p—>next = p—>next—>next; 但,若是删除链表的最有一个节点(链表中只剩下这个节点),则代码如下: if(head—>next == null){ head = null; } 从上面的情况可以看出,针对链表的插入、删除操作,需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐,所以引入“哨兵”节点来解决这个问题。

3.引入“哨兵”的情况

“哨兵”节点不存储数据,无论链表是否为空,head指针都会指向它,作为链表的头结点始终存在。这样,插入第一个节点和插入其他节点,删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。

4.“哨兵”还有哪些应用场景?

这个知识有限,暂时想不出来呀!但总结起来,哨兵最大的作用就是简化边界条件的处理。

四、重点留意边界条件处理

经常用来检查链表是否正确的边界4个边界条件: 1.如果链表为空时,代码是否能正常工作? 2.如果链表只包含一个节点时,代码是否能正常工作? 3.如果链表只包含两个节点时,代码是否能正常工作? 4.代码逻辑在处理头尾节点时是否能正常工作?

五、举例画图,辅助思考

核心思想:释放脑容量,留更多的给逻辑思考,这样就会感觉到思路清晰很多。

六、多写多练,没有捷径

5个常见的链表操作:

1.单链表反转 2.链表中环的检测 3.两个有序链表合并 4.删除链表倒数第n个节点 5.求链表的中间节点

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

三个技巧,将Docker镜像体积减小90%【面试+工作】

在构建Docker容器时,应该尽量想办法获得体积更小的镜像,因为传输和部署体积较小的镜像速度更快。

19410
来自专栏新智元

天才女孩!12岁小学生写出冯·诺依曼提出的元胞自动机

这名叫Liam Ilan的12岁小女孩在Hackernews上低调写了一句话,仅数小时,便惊呆了一路众人:

17520
来自专栏AI科技大本营的专栏

汉语转拼音工具、新华字典API——两个支持Python的中文资源

【导读】平常为大家推荐的资源中,以英语语言占据大多数。今天 AI科技大本营特别要为大家推荐两个跟中文相关的资源工具。先简单介绍下这两个资源工具都是什么。第一个,...

28230
来自专栏编程微刊

本地运行github上的vue2.0仿饿了么webapp项目

在vue刚刚开始流行的时候,大多数人学习大概都见到过这样的一个项目吧,可以作为学习此框架的一个模板了

53730
来自专栏IT米粉

hexo——轻量、简易、高逼格的博客

写blog虽然经历了N多不同时代的产品,恒久不变的始终是自己无人问津的网站。虽然没几个人看,还是隔断时间就要折腾一下。从最开始的wordpress,到tale,...

43420
来自专栏编程微刊

基于promise用于浏览器和node.js的http客户端的axios

axios 是一个基于Promise 用于浏览器和 nodejs 的 HTTP 客户端,它本身具有以下特征:

14620
来自专栏西二旗一哥

Ghost - Birth of my blog

如果出现以上文字,那么恭喜你,进入服务器成功。 + 3.2 安装 Node.js 依次在终端上输入以下命令,注释除外(如果怕打错请全部复制粘贴):

25380
来自专栏Java架构沉思录

Node.js 三大特点你都懂了吗

在Java、PHP或者.net等服务器端语言中,会为每一个客户端连接创建一个新的线程。而每个线程需要耗费大约2MB内存。也就是说,理论上,一个8GB内存的服务器...

14330
来自专栏云计算教程系列

如何在Ubuntu 16.04上使用PM2和Nginx开发Node.js TCP服务器应用程序

Node.js是一个流行的开源JavaScript运行时环境,它基于Chrome的V8 Javascript引擎构建。Node.js用于构建服务器端和网络应用程...

29030
来自专栏云计算教程系列

如何在Ubuntu 14.04上使用Hexo创建博客

Hexo是一个基于Node.js的静态博客框架。使用Hexo,您可以以博客文章的形式发布Markdown文档。博客帖子和内容被处理并转换为HTML / CSS,...

20700

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励