数据结构与算法(三)链表

什么是链表

链表是通过指针将一些零散的内存块串起来使用的一种数据结构,支持数据的查找、插入、删除操作。

因为链表在内存中是不连续的,所以无法像数组那样可以根据首地址和下标通过寻址公式直接计算出第 K 个元素,而是需要遍历所有的节点通过计数获取。

数组与链表在内存中的结构对比

三种类型的链表

单链表

单链表

结点

我们把链表中每一个内存块称为结点,链表中的第一个结点称为头结点,最后一个结点称为尾结点,它的指针批向空地址 NULL

后继指针 Next

为了将所有的结点串起来,每个链表的结点除了要存储数据之外,还需要记录当前结点的下一个结点的地址,称为后继指针 Next

循环链表

循环链表就是一种特殊的单链表,它的尾结点指针指向头节点,而不是 NULL

循环链表相比于单链表的优势就是:从链尾到链头方便,所以当我们要处理的数据具有环形结构的特征时,适合使用循环链表来解决,如:约瑟夫问题

双向链表

双向链表支持两个方向,每个结点不止有一个后继指针 Next 指向后面的结点,还有一个前驱指针 Prev 指向前面的结点

双向链表

LRU 缓存淘汰算法

Redis 的缓存淘汰机制就基于 LRU(Least Recently Used) 缓存淘汰算法,即『最近最少使用』算法,正是依赖于单链表这种数据结构。

LRU 算法的基本实现思路如下:

  • 使用头结点存储最新数据,尾结点为最少使用的数据。
  • 如果数据之前已经被缓存的链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  • 如果数据没有被缓存在链表中,分两种情况:
    • 如果缓存未满:将此结点直接插入到链表头部。
    • 如果缓存已满:将链表尾结点删除,将新的数据结点插入到链表头部。

写出正确链表代码的技巧

理解指针的含义

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

警惕指针丢失和内存泄漏

  • 向链表中插入新的结点时,注意操作顺序。
  • 删除节点时,释放内存空间,避免内存泄漏。

利用哨兵简化实现难度

针对链表的插入、删除操作,需要对插入第一个节点删除最后一个节点的情况进行特殊处理,这样就会在实现代码中添加不必要的判断,为了解决这个问题,引入哨兵的概念。

哨兵其实就是不存储数据的头节点,有了它的存在,就算链表是空链表时,链表头的指针依然指向哨兵结点,这个时候哨兵结点其实就充当了头结点的作用,但是它不存储数据,有种生活中『用一件物品占座』的感觉。

重占留意边界条件处理

为了尽量避免代码 BUG,可以用以下边界条件检查代码:

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

用画图来辅助思考

多写多练,没有捷径。

五个常见的链表操作

以下是五个常见的链表操作,可以用来在使用代码实现链表的时候刻意练习。

  • 单链表反转
  • 链表中环的检测
  • 两个有序链表合并
  • 删除链表倒数第 N 个结点
  • 求链表的中间结点

 上一篇
The Fucking Github The Fucking Github
The Fucking Github 是一个 Chrome 浏览器的扩展插件,可以用来很方便地查看、整理、搜索你已经 Star 过的项目和搜索 Github 上的项目。 能干啥你是否在 Github 上有很多 star 过的项目并且经常需
2019-04-14
下一篇 
数据结构与算法(一):复杂度分析 数据结构与算法(一):复杂度分析
什么是数据结构与算法数据结构是指数据在内存中存储的结构,算法是操作数据的方法。 它们之间相辅相成,数据结构为算法提供服务,而算法依赖于特定的数据结构。 复杂度分析评估一段代码的指标有两点: 执行效率如何 占用内存空间情况如何 评估这两点
2019-03-23
  目录