专栏首页重归混沌双向链表的三种实现

双向链表的三种实现

这篇文章,其实很像是“茴字的四种写法”。这让人不由的想起来孔乙己。在我印象中,大多数人对孔乙己是持嘲讽态度的。

但是从技术上讲,我觉得”茴字的四种写法”在满足需求的前提下,有助于我们简化实现。

在我的历史经验中,我一共写过三种双向链表。

在最开始实现时,就是按算法导论最朴素的实现。

  1. //算法1
  2. struct node {
  3. struct node *prev;
  4. struct node *next;
  5. }
  6. struct node *head = NULL;
  7. void insert(struct node *n) {
  8. n->prev = NULL;
  9. n->next = head;
  10. if (head != NULL)
  11. head->prev = n;
  12. head = n;
  13. }
  14. void remove(struct node *n) {
  15. if (n->prev != NULL)
  16. n->prev->next = n->next;
  17. else
  18. head = n;
  19. if (n->next != NULL)
  20. n-next->prev = n->prev;
  21. }

写了几次之后,我觉得每次修正head指针,心智负担有点重而且极易出错,于是浪费了一点点空间改进了一下。

  1. //算法2
  2. struct node {
  3. struct node *prev;
  4. struct node *next;
  5. }
  6. struct node head = {NULL, NULL}
  7. void insert(struct node *n) {
  8. n->next = head.next;
  9. if (n->next != NULL)
  10. n->next->prev = n;
  11. head.next = n;
  12. n->prev = &head;
  13. }
  14. void remove(struct node *n) {
  15. n->prev->next = n->next;
  16. if (n->next != NULL)
  17. n->next->prev = n->prev;
  18. }

但是这样做有一个弊端,struct node是一个结构体而不是一个指针,在某些情况下不便于存储。

因此这些年,我几乎都是两种算法换着用。但是每次使用算法1时,总是要停下来仔细思考一下,才敢下手。

最近在Review几年前的代码时,发现之前使用算法1写的双向链表有bug.

这再次使我想对双向链表的算法2进行改进,我仔细思考了一下双向链表的特性。

双向链表主要有两个功能:

  1. 提供反向遍历
  2. 以O(1)的时间复杂度删除某个节点

但是到目前为止, 我从来没有使用过双向链表的特性1.

我使用双向链表的惟一原因就是要快速删除某一个节点。

即然如此,根据“这个世界是平衡的”原则,如果我去掉某个特性,就一定能简化部分实现,只是简化多少的问题。

我仔细研究了算法2,想从中找到某种启发。

最终我发现,在整个逻辑中,prev指针的惟一用处就是用来访问或修改前置节点的next变量。

而head的prev变量同样是多余的。

那么,如果将prev的含义修改为指向前置节点的next变量,关于prev的循环不变式同样成立。

优化后的代码如下:

  1. //算法3
  2. struct node {
  3. struct node **prev;
  4. struct node *next;
  5. }
  6. struct node *head = NULL;
  7. void insert(struct node *n) {
  8. n->prev = &head;
  9. n->next = head;
  10. if (head != NULL)
  11. head->prev = &n->next;
  12. head = n;
  13. }
  14. void remove(struct node *n) {
  15. *n->prev = n->next;
  16. if (n->next != NULL)
  17. n->next->prev = n->prev;
  18. }

由此,终于可以在享有算法2逻辑复杂度的同时,而不必要承担一个head结构体。

BTW,在写本文的前一天,我无意间发现Lua源码中也是这样做的 :D

本文分享自微信公众号 - 重归混沌(findstrx),作者:重归混沌

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-31

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 三角形光栅化时遇到的坑

    前一段时间打算写一个完整的游戏, 客户采用Unity3D引擎, 服务端则采用我自己的Silly网络框架。

    重归混沌
  • 一次性能优化经历

    自从上次修改backlog之后, Silly的IO能力,就一直以少量(约4~6K)的差距落后于redis,却一直找不到原因。

    重归混沌
  • 移动平台native代码遭遇的坑

    最近客户端终于开始运行在移动平台上了,之前在PC平台上完全没问题的代码,开始出现一些诡异的问题。

    重归混沌
  • AAAI 2019评审惹争议!“好论文”遭退稿?程序主席回应

    人工智能“The”顶会之一的AAAI 2019论文录取结果昨日公布,16.2%,可以说是AAAI录取率最低的年份之一,更何况今年的投稿数量高达7745篇,比去年...

    昱良
  • AAAI 2019评审惹争议!“好论文”遭退稿?程序主席回应

    人工智能“The”顶会之一的AAAI 2019论文录取结果昨日公布,16.2%,可以说是AAAI录取率最低的年份之一,更何况今年的投稿数量高达7745篇,比去年...

    新智元
  • R-概率统计与模拟(五)彩票连号、归纳法以及二项分布

    由于微信公众号不支持Markdown,所以我们会将文章先发表在支持Markdown的csdn博客上,然后从公众号跳转到csdn博客。从本文开始,会尝试一段时间看...

    一只羊
  • 世界旅游城市联合会香山旅游峰会9月在赫尔辛基召开

    ? “旅游让城市生活更美好” 九月的赫尔辛基 将以一场盛会为契机 为这份美好带来全新活力 9月2日至4日,由世界旅游城市联合会和芬兰赫尔辛基市共同主办的20...

    腾讯文旅
  • 记一次逆向 Android 的经历

    戳上面的蓝字关注我们哦! 作者:王不哈 链接:https://www.jianshu.com/p/d0732c9319b2 声明:本文是 王不哈 原创,转发等请...

    用户1269200
  • Node-RED | 无需一行代码,快速在浏览器中构建你的可视化 IoT Web App

    Node-RED是一种编程工具,通过在浏览器中拖拽的方式将硬件设备、API和在线服务连接在一起,构成数据流,使用户可以快速的创建出自己的Web应用。

    Mculover666
  • Android自定义控件实现带文字提示的SeekBar

    SeekBar控件在开发中还是比较常见的,比如音视频进度、音量调节等,但是原生控件有时还不能满足我们的需求,今天就来学习一下如何自定义SeekBar控件,本文主...

    砸漏

扫码关注云+社区

领取腾讯云代金券