Linus: 这样写是不懂指针
你好,我是雨乐!
但凡刷过leetcode或者参加面试,大抵都遇到过如下这种问题:删除单链表中value为给定值的所有节点。
假设链表节点定义如下:
struct ListNode {
int value;
ListNode* next;
};
那么,为了实现该功能,我们需要从头到尾遍历链表,同时删除value等于给定值的节点,显然,我们会像如下这样写:
void Remove(ListNode *head, int to_remove) {
ListNode *entry = head;
ListNode *prev = NULL;
while (entry) {
if (entry->val == to_remove) {
if (prev)
prev->next = entry->next;
else
head = entry->next;} else {
prev = entry; }
entry = entry->next;
}
}
代码实现中,我们所做的是遍历列表,直到entry
为 NULL(第5行)。当我们遇到要删除的节点时(第 6 行),我们将当前next
指针的值分配给前一个,进而从当前链表中摘除当前元素(第 8 行)。
上述这种写法,相对来说简单、易理解,但 Linus Torvalds
却不这么认为,其曾经评价这种写法:
At the opposite end of the spectrum, I actually wish more people understood the really core low-level kind of coding. Not big, complex stuff like the lockless name lookup, but simply good use of pointers-to-pointers etc. For example, I’ve seen too many people who delete a singly-linked list entry by keeping track of the “prev” entry, and then to delete the entry, doing something like
if (prev) prev->next = entry->next; else list_head = entry->next;
and whenever I see code like that, I just go “This person doesn’t understand pointers”. And it’s sadly quite common. People who understand pointers just use a “pointer to the entry pointer”, and initialize that with the address of the list_head. And then as they traverse the list, they can remove the entry without using any conditionals, by just doing a “*pp = entry->next”
其大概意思就是,对于写出本文一开始那种代码的评价就是:***这个人不懂指针(This person doesn’t understand pointers)***。
那么,Linus推荐的写法又是什么样的呢?
void Remove(ListNode *head, int to_remove) {
ListNode **pp = &head;
ListNode *entry = head;
while (entry) {
if (entry->val == to_remove)
*pp = entry->next;
else
pp = &entry->next;
entry = entry->next;
}
}
这块代码看起来相对简洁,但是,如果第一次遇到这种实现,可能需要花一点时间进行理解~~
实际上刷过题的都知道,list相关问题首先在栈上声明一个dummy node
,能简化各种插入删除操作代码。使用dummy node
操作后,代码如下:
void Remove(ListNode *head, int to_remove) {
ListNode tmp;
tmp.next = head;
ListNode *pre = tmp;
while (pre->next) {
if (pre->next->val == to_remove) {
pre->next = pre->next->next;
} else {
pre = pre->next;
}
}
}
相比来说,较Linus的实现方式更为简洁,但明显的,需要生成一个dummy节点,最明显的,内存使用上并不是最优,尽管其更易于理解和实现。
链表属于LC中相对来说比较简单的部分,选择一种适合自己的方式,并不一定非要选择最优,选择一个适合自己的。至于Linus实现的这种,可以保留意见,且当其最优吧,毕竟:没有人比Linus更懂指针
,哈哈哈~
好了,今天的文章就到这,我们下期见!
相关文章
- 使用 NGINX ingress controller 和 Flagger 来实现 canary deployments
- IDEA激活码(2022idea最新激活码)
- NFT链游开发及存储技术
- 【一】知识图谱基础概念、开发流程以及落地策略
- 火遍外网的Keychron测评,带你入坑;ps马上5.20了送一个给你的心爱的她/他。
- 做知识图谱遇到的环境问题合集【spacy、gensim、keras_contrib等】
- 知识图谱项目实战(一):瑞金医院MMC人工智能辅助构建知识图谱--初赛实体识别【1】
- Jupyter Notebook 下 import 第三方库,显示 no module xxx 【本质是环境没有切换过来】
- 【一】ERNIE:飞桨开源开发套件,入门学习,看看行业顶尖持续学习语义理解框架,如何取得世界多个实战的SOTA效果?
- 总结一下强化学习在工业界应用,给大家扩展一下思路(简易科普)
- conda创建虚拟环境后文件夹中只有conda-meta文件夹,无法将环境添加到IDE中
- 百度飞桨:ERNIE 3.0 、通用信息抽取 UIE、paddleNLP的安装使用[一]
- PaddleHub--飞桨预训练模型应用工具{风格迁移模型、词法分析情感分析、Fine-tune API微调}【一】
- salesforce零基础学习(一百二十三)Transaction Security 浅入浅出
- Winforms Cefsharp应用通过Vs Installer安装,应用崩溃,缺少文件错误
- Winform Vs Installer之添加自定义安装流程
- 网页唤起Winform窗体通过非IE浏览器
- Java程序员除了做增删改查还能干嘛?
- PaddleHub实战篇{词法分析模型LAC、情感分类ERNIE Tiny}训练、部署【三】
- 百度地图使用记录