数据结构系列之链表

  • 3
  • 2,132次阅读
  • A+
所属分类:数据结构

链表 不是一块连续的空间,它是通过“指针”将一组零散的内存块串联起来使用。

我们来看看链表与数组的差异

数据结构系列之链表

很明显,数组在内存中是一连串相邻的区域组成的,而链表则是由不连续的指针而组成的。

链表的分类

链表分为最常见的三种类型:单链表、循环链表和双向链表。

单链表

数据结构系列之链表

单链表如图所示,除了data中存储数据结构以外,还有一个next元素,为指向下一个节点内存地址的后继指针。单链表有两个特殊节点,一个是头节点,一般可以使用头节点循环遍历整个单链表。一个是尾节点,尾节点属于单链表的最后一个节点,所以一般为null。

单链表的插入和删除

数组在插入与删除操作时(由于是一连串的内存地址)需要进行一些列的搬迁工作,所以效率很低,时间复杂度为O(n)但是链表的插入和操作,只需要更改相邻节点的指针,时间复杂度为O(1),所以很高效。

数据结构系列之链表

循环链表

循环链表其实是一个特殊的单链表,它与单链表的区别就是尾节点,我们知道单链表的尾节点为null,而循环链表的尾节点对应链表的头节点,形成了一个循环的状态,所以称为循环链表。

数据结构系列之链表

双向链表

它有两个方向的指针,分别是前驱指针指向前一个节点,与后继指针指向后面一个节点。

数据结构系列之链表

双向链表由于多一个指针用来指向前一个节点,所以势必会在空间上比单链表占用更多内存,但是双向链表可以支持在O(1)复杂度下找到前驱节点,所以在某种情况下,删除与插入比单链表更加高效,简单。

双向循环链表

顾名思义就是双向链表的循环版本,尾节点的next指针指向头节点的data元素,头节点的前驱节点prev指向尾节点的data元素。

数据结构系列之链表

链表与数组的性能对比

数据结构系列之链表

如上图

数组由于是一连串的内存空间,所以在进行元素插入和删除时,往往会进行数据搬移工作,这样就会造成性能上的损耗,所以时间复杂度为O(n),而数组在访问某一个元素时,可以通过下标位置访问元素单元,不需要进行循环查找,所以时间复杂度为O(1)。

链表在是一连串不连续的内存空,在元素插入和删除时,可以通过元素的前驱节点或者后继节点直接查询到元素的所在位置,可以通过更改元素的前驱节点或者后续节点的指针指向,所以时间消耗几乎很小,对性能影响微乎其微,所以时间复杂度为O(1),而在查找元素时恰恰与数组相反,链表需要通过头节点,依次遍历所有节点查找元素,故时间复杂度为O(n)。

所以,在项目中,要根据场景的不同,择优选择是使用数组还是链表。

如何写好正确的链表代码?

一 、理解指针或引用

将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量。

例如: p -> next = q 这段代码的意思就是 p节点中的next指针存储了q节点的内存地址。
p -> next = p -> next -> next 这段代码的意思就是 p节点的next指针存储了p节点的下下一个节点的内存地址。

二、警惕指针丢失和泄露

插入节点时,要注意操作的顺序

删除节点时,要手动释放内存空间

三、利用哨兵简化难度

哨兵节点,在任何时候,不管链表是不是空,head指针都会一直指向这个哨兵节点,把这种带有哨兵节点的链表叫做带头链表。相反,没有哨兵节点的链表叫做不带头链表

数据结构系列之链表

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

在写链表代码时一定要注意边界问题,如果不处理边界问题可能引起程序抛出空指针异常甚至崩溃。此处总结几点需要注意的地方

  • 如果链表为空时,代码是否能正常工作
  • 如果链表只包含一个节点时,代码是否能正常工作
  • 如果链表只包含两个节点时,代码是否能正常工作
  • 代码在处理头节点和尾节点时,是否能正常工作

五、举例画图,辅助思考

六、多写多练,反复思考

5个常见链表操作

单链表反转

链表中环的检测

两个有序的链表合并

删除链表倒数第 n 个结点

求链表的中间结点

  • 我的微信
  • 加好友一起交流!
  • weinxin
  • 微信公众号
  • 关注公众号获取分享资源!
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:3   其中:访客  2   博主  1

    • 小小名 小小名 1

      good good study, day day up…

      • 小小名 小小名 1

        good good study, day day up

        • 柳梦溪 柳梦溪 Admin

          @小小名 加油!