Linus slashdot: ? ?https://meta.slashdot.org/story/12/10/11/0030249

原文： https://coolshell.cn/articles/8990.html

Linus大嬸在slashdot上回答一些編程愛好者的提問，其中一個人問他什么樣的代碼是他所喜好的，大嬸表述了自己一些觀點之后，舉了一個指針的例子，解釋了什么才是core low-level coding。

下面是Linus的教學(xué)原文及翻譯——

“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。（在這段話的最后，我實際上希望更多的人了解什么是真正的核心底層代碼。這并不像無鎖文件名查詢（注：可能是git源碼里的設(shè)計）那樣龐大、復(fù)雜，只是僅僅像諸如使用二級指針那樣簡單的技術(shù)。例如，我見過很多人在刪除一個單項鏈表的時候，維護了一個”prev”表項指針，然后刪除當(dāng)前表項，就像這樣）”

if (prev)prev->next = entry->next;
elselist_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.（當(dāng)我看到這樣的代碼時，我就會想“這個人不了解指針”。令人難過的是這太常見了。）

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”. （了解指針的人會使用鏈表頭的地址來初始化一個“指向節(jié)點指針的指針”。當(dāng)遍歷鏈表的時候，可以不用任何條件判斷（注：指prev是否為鏈表頭）就能移除某個節(jié)點，只要寫)

*pp = entry->next

So there’s lots of pride in doing the small details right. It may not be big and important code, but I do like seeing code where people really thought about the details, and clearly also were thinking about the compiler being able to generate efficient code (rather than hoping that the compiler is so smart that it can make efficient code *despite* the state of the original source code). （糾正細節(jié)是令人自豪的事。也許這段代碼并非龐大和重要，但我喜歡看那些注重代碼細節(jié)的人寫的代碼，也就是清楚地了解如何才能編譯出有效代碼（而不是寄望于聰明的編譯器來產(chǎn)生有效代碼，即使是那些原始的匯編代碼））。

Linus舉了一個單向鏈表的例子，但給出的代碼太短了，一般的人很難搞明白這兩個代碼后面的含義。正好，有個編程愛好者閱讀了這段話，并給出了一個比較完整的代碼。他的話我就不翻譯了，下面給出代碼說明。

如果我們需要寫一個remove_if(link*, rm_cond_func*)的函數(shù)，也就是傳入一個單向鏈表，和一個自定義的是否刪除的函數(shù)，然后返回處理后的鏈接。

這個代碼不難，基本上所有的教科書都會提供下面的代碼示例，而這種寫法也是大公司的面試題標(biāo)準模板：

typedef struct node
{struct node * next;....
} node;typedef bool (* remove_fn)(node const * v);// Remove all nodes from the supplied list for which the
// supplied remove function returns true.
// Returns the new head of the list.
node * remove_if(node * head, remove_fn rm)
{for (node * prev = NULL, * curr = head; curr != NULL; ){node * const next = curr->next;if (rm(curr)){if (prev)prev->next = next;elsehead = next;free(curr);}elseprev = curr;curr = next;}return head;
}

這里remove_fn由調(diào)用查提供的一個是否刪除當(dāng)前實體結(jié)點的函數(shù)指針，其會判斷刪除條件是否成立。這段代碼維護了兩個節(jié)點指針prev和curr，標(biāo)準的教科書寫法——刪除當(dāng)前結(jié)點時，需要一個previous的指針，并且還要這里還需要做一個邊界條件的判斷——curr是否為鏈表頭。于是，要刪除一個節(jié)點（不是表頭），只要將前一個節(jié)點的next指向當(dāng)前節(jié)點的next指向的對象，即下一個節(jié)點（即：prev->next = curr->next），然后釋放當(dāng)前節(jié)點。

但在Linus看來，這是不懂指針的人的做法。那么，什么是core low-level coding呢？那就是有效地利用二級指針，將其作為管理和操作鏈表的首要選項。代碼如下：

void remove_if(node ** head, remove_fn rm)
{for (node** curr = head; *curr; ){node * entry = *curr;if (rm(entry)){*curr = entry->next;free(entry);}elsecurr = &entry->next;}
}

同上一段代碼有何改進呢？我們看到：不需要prev指針了，也不需要再去判斷是否為鏈表頭了，但是，curr變成了一個指向指針的指針。這正是這段程序的精妙之處。（注意，我所highlight的那三行代碼）

讓我們來人肉跑一下這個代碼，對于——

• 刪除節(jié)點是表頭的情況，輸入?yún)?shù)中傳入head的二級指針，在for循環(huán)里將其初始化curr，然后entry就是*head(*curr)，我們馬上刪除它，那么第8行就等效于*head = (*head)->next，就是刪除表頭的實現(xiàn)。

• 刪除節(jié)點不是表頭的情況，對于上面的代碼，我們可以看到——

1）（第12行）如果不刪除當(dāng)前結(jié)點 —— curr保存的是當(dāng)前結(jié)點next指針的地址。

2）（第5行）?entry 保存了 *curr?——?這意味著在下一次循環(huán)：entry就是prev->next指針?biāo)赶虻膬?nèi)存。

3）（第8行）刪除結(jié)點：*curr = entry->next; —— 于是：prev->next 指向了 entry -> next;

是不是很巧妙？我們可以只用一個二級指針來操作鏈表，對所有節(jié)點都一樣。

如果你對上面的代碼和描述理解上有困難的話，你可以看看下圖的示意：

總結(jié)

以上是生活随笔為你收集整理的二维指针删除单向链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。