链表代码书写技巧 | 极客时间《数据结构与算法之美-王争》链表(下)总结


很多面试官都喜欢让人现场手写代码,以考验一个人逻辑思维能力。因为链表代码中到处都是指针的操作、边界条件处理等,稍有不慎就容易产生Bug。所以链表代码写的好坏最可以看出一个人写代码是否足够细心,考虑问题是否全面,思维是否缜密。
极客时间课程《数据结构与算法之美》中,王争根据他的学习经历和工作经验,分享了六个写链表代码的技巧。

技巧一:理解指针或引用的含义

事实上,看懂链表的结构并不是很难,但是要把它和指针混在一起就很容易让人摸不着头脑。所以,要想写对链表代码,首先要理解好指针。
在C语言中,有指针的概念,而在JAVA、Python等语言中,取而代之的是“引用”的概念,不管是“引用”还是“指针”,本质上他们是一样的,都是用于存储所指对象的内存地址
关于指针的概念,用一句话来辅助理解一下:

  1. 将某个变量赋值给指针,实际上是将这个变量的地址赋值给了这个指针
  2. 或者可以反过来说,被赋值的指针中,存储了这个变量的内存地址,通过指针可以找到这个变量。

技巧二:警惕指针丢失或者内存泄漏

常见的指针丢失实例:
我们希望在一个单链表的结点a和结点b之间插入结点x,一定要先用结点x指向结点b,然后再用结点a指向结点x,如果修改指向的顺序写反了,就会造成指针丢失。
内存泄漏:是指程序中已动态分配的堆内存由于某种原因程序未释放或无法释放,造成系统内存的浪费,导致程序运行速度减慢甚至系统崩溃等严重后果。
在有些语言中,比如C语言,内存管理由程序员负责,如果没有手动释放结点对应的内存,就会造成内存泄漏。如果插入结点时指针丢失,或者删除结点时未手动释放内存空间,都会造成内存泄漏。

技巧三:利用哨兵简化实现难度

在链表的头部和尾部进行插入、删除等操作时,一般需要特殊处理,实现起来往往会比较繁琐,不简洁,而且也容易出错。引入不直接参与业务逻辑的“哨兵”结点,可以很好的解决边界问题。
哨兵结点,放置在链表的最前端,在任何时候,不管链表是否为空,head指针都会一直指向这个哨兵结点。我们把这种有哨兵结点的链表称为带头链表,相反,没有哨兵结点的链表称为不带头链表
带头链表示意图

技巧四:重点留意边界条件处理

软件开发中,代码在一些边界或者极端情况下最容易产生BUG。要实现没有BUG的链表代码,对于边界情况一定要重点考虑。
几个常见的边界特殊情况:

  1. 链表为空
  2. 链表只含一个结点
  3. 链表只含两个结点
  4. 头结点和尾结点

技巧五:举例画图,辅助思考

链表操作中的指针跳转,是一个挺复杂的事情,单靠脑袋思考,很容易被绕晕。所以可以用举例法画图法来辅助思考,避免脑容量不够。

技巧六:多写多练,没有捷径

以上只是总结出来的思维技巧,真正想把链表相关的问题做透,还是需要多做练习题,熟能生巧!
列举五个常见的链表操作:

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

本文发表于2018年10月25日 19:36
阅读 33 讨论 0 喜欢 0

讨论

周娱

君子和而不同
按照自己的方式,去度过人生

4601 1243912
抢先体验

扫码体验
趣味小程序
文字表情生成器

加入组织

扫码添加周娱微信
备注“加入组织”
邀请进开发群

闪念胶囊

不积跬步无以至千里,越焦虑越要扎实干。

不要试图鹤立鸡群,趁早离开那群鸡!

程序员过节需要的不是美女、不是美食、不是不加班!他们需要的是写代码,一群人写、往死里写、通宵写!!那种暗流涌动的狂欢,远比虚无庸俗的食色更让他们振奋!! by芋头

面试的时候,常常会问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。 实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。 所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

找一个bug就好比从一泡烂泥里找一条泥鳅,写一个bug就好比往一泡烂泥里丢一条泥鳅进去

数据结构在某种程度上和设计模式类似,都是前辈的武功套路。不同的是,设计模式是近几十年的卓越程序员的智慧结晶,而数据结构是几百上千年的无数科学家、数学家的智慧沉淀,更加具有深厚的背景。

18年元旦立下的flag要集中突击一下了.....

人生是一场马拉松,起跑的优劣对于整段路途而言并没有那么重要,笑到最后的都是一直在跑的人,也就是一辈子都在学习的人。

角色是谁并不重要,重要的是会不会抢戏~

Copyright © 2016 - 2018 Cion.
All Rights Reserved.
备案:鲁ICP备16007319号.