連結清單的設計--單連結清單逆序開始

這個問題僅僅可以考察人們對c語言特别是指針的熟悉程度，在實際程式設計中沒有任何的意義，單連結清單逆序無論如何都要花費大量的時間，如果非要這麼做為何不用空間來換時間，比如用雙連結清單，然而如果你使用了雙連結清單的話，逆序就更是一個沒有意義的操作了，不管怎麼說，單連結清單逆序這件事還是要做的，方法有二，一個是遞推，另一個是遞歸，遞歸法可以省去一個中間變量，而遞推法則必須使用三個變量：一個表頭，一個臨時節點指針，一個臨時節點的下一個節點的指針，為何需要這些額外的變量呢？因為一旦将一個節點從連結清單摘除，那麼它就會徹底孤立，再也與原來的連結清單節點聯系不起來，是以需要在将一個節點摘除之前儲存它的下一個節點，因為交換後序指針需要兩個節點參與，是以還需要儲存目前節點和目前節點的前一個節點，是以最終需要三個額外的變量，有了這三個變量，程式算法就簡單了：

資料結構定義如下：

struct PS_list_head{

PS_list_head * next;

};

初始化如下：

PS_list_head * list_curr = head; //初始化為頭節點

PS_list_head * list_prev = NULL; //初始化時頭結點沒有前序指針

PS_list_head * list_next = head->next; //後序指針為頭結點的next字段

接着每一步做以下工作：

list_curr->next = list_prev?list_prev:NULL;

list_prev = list_curr;

list_curr = list_next;

list_next = list_curr->Next;

一直到最終。

現在看一下遞歸的方式，遞歸可以節省一個額外的變量，其實上面的操作最關鍵的一個步驟就是list_curr->next = list_prev?list_prev:NULL其餘的操作都是為這個操作做準備的，那麼既然通過定義額外變量加上遞推的方式能幫助程式完美實作這關鍵的一步，換一種方式十有八九也一定可以，于是嘗試一下遞歸，之是以在遞推中儲存目前節點的下一個節點指針是因為一旦目前節點脫離連結清單就再也找不到了，畢竟後面的還沒有被處理，而遞歸算法可以節省一個額外的變量，因為遞歸保證後面的節點都已經被處理過了：

struct PS_list_head * list_reverse( struct PS_list_head* head )

{

struct PS_list_head * list_next=head->next;

if( likely(list_next) ) //likely優化，參見linux核心源碼

struct PS_list_head * list_tail=reverse(list_next); //保證後面的都被處理

list_next->next=head; //關鍵的一步

return list_tail;

}

else

return head;

遞歸有遞歸的缺點，一旦深度過大就會導緻棧溢出，空間開銷過大，僅僅為了節省一個變量不值得。以上就是單連結清單的逆序的全部内容，關于單連結清單還有很多問題，比如判斷有無環路，比如一次周遊找到倒數特定索引活着特定總長度比例處的元素，其實這兩個問題是一個問題，既然限制了周遊的次數，那麼隻好在這僅有的一次周遊中多動用一些資源，典型的就是指針，對于特定索引典型的解法就是定義兩個指針，一個先開始周遊，等到達這個倒數特定索引的數值步長的時候第二個指針開始周遊，然後當第一個指針完畢之後第二個指針就到了，單連結清單的特點就是在一次單指針周遊中，中間狀态很難得到儲存，過了就丢了，全部儲存呢開銷過于大，是以必須動用第二個指針，求特定索引的節點其實就是等差問題，隻需要一個內插補點，而另一個問題，求總長度特定比例節點的問題就不是等差問題，而是等速度比問題，比如讓一個指針的速度是另一個的兩倍，那麼當一個指針到尾部時，另一個正好到中間，這其實和國小時學的相遇問題和相離問題十分類似要麼就是施工隊問題，看來程式設計的問題都不難，很多都是國小知識。

以上就是這個最無趣的問題，linux核心當然不會這麼無趣了，是以我在核心中沒有找到單連結清單的上述操作，list_head用的是最多的了，雖然是雙連結清單，多了一個指針，但是來了很多友善，可以線速的在任何一個節點的前或者後添加或者删除一個節點，連結清單的兩個方向是對稱的，總體來看，list_head根本就沒有方向，也沒有表頭和表尾。為了适應通用類型，核心中沒有使用STL的泛型之類的機制，而是使用了OO的思想，将資料和操作分離，連結清單結構中不再有資料，也就是list_head中隻是代表了連結清單本身，沒有資料，也沒有任何泛型，泛型展現了同一個層次上的通用資料結構的算法，可以泛型的類型必須屬于同一個層次，并且泛型主要友善了通用算法的使用上，泛型的算法是相同的，隻是資料不同，而繼承卻不是這樣，或者說恰恰相反，繼承指的是參與計算的資料操作相同，但是操作的算法不同，繼承更加适合于擴充新操作算法而不是重用已有的操作算法。我們來看一下list_head的設計，首先為了統一的使用雙向連結清單的操作，核心抽象出了list_head資料結構，它剝離了資料，僅僅留下來了一個資料結構，既然沒有了資料那麼就不存在不同的資料類型，是以泛型已經被pass掉了，剩餘的東西仔細一看，其實就是繼承，list_head就是一個基類，當然你也可以了解成是包含，總之list_head是抽象的結果，展現了OO的思想。

緊接着問題又來了，考慮哈希連結清單，一個哈希桶由于碰撞難免要攜帶一個連結清單，該連結清單完全可以用list_head表示，但是不同于list_head的其它使用場合，哈希表總是不希望特别長的，因為好的雜湊演算法總是試圖擴充寬度而不是增加每一條沖突哈希連結清單的長度，是以雜湊演算法越好，各個連結清單的長度越均勻，實際上的結果就是沒有特别長的連結清單，是以list_head的一些優勢，比如快速周遊，随機插入，删除等就不再那麼明顯了，畢竟連結清單不會很長的，但是卻很多。很多的話就要考慮是否占用了太多的空間以及在此基礎上能否優化空間開銷了，是以就設計出了hlist_head資料結構同時更改了list_head資料結構使之成為一個新的資料結構hlist_node:

/*

* Double linked lists with a single pointer list head.

* Mostly useful for hash tables where the two pointer list head is

* too wasteful.

* You lose the ability to access the tail in O(1).

*/

struct hlist_head {

struct hlist_node *first;

struct hlist_node {

struct hlist_node *next, **pprev;

hlist_head是哈希連結清單的頭，注意hlist和list_head不同，後者沒有頭和尾，但是hlist的頭并不和尾相連接配接，直接的後果就是你無法通過連結清單頭直接得到連結清單尾，看一下以上的hlist_node結構，它本質上還是一個雙向連結清單結構，但是pprev卻不再是hlist_node類型的指針，而是其指針的指針，這又當何解呢？hlist的設計過程是很有趣的，首先要說明的是僅僅是查找的話，hlist設計成單連結清單就可以，但是由于涉及到随機的删除和插入(删除是真的随機的，但是插入一般都是往前面或者往後面插入的)，如果是單連結清單的話，沒有目前節點上一個節點的資訊就會很麻煩，對于删除而言，由于要修改上一個節點的next字段，是以必須周遊單連結清單才能找到上一個元素，這是很不和諧的，于是最終還是要用雙向連結清單；接下來的問題就是對于哈希沖突連結清單來講，在哈希桶很大的時候，這種連結清單會很多而不像list_head那樣數量确定，比如有一條task_struct連結清單，一條檔案系統的連結清單等等，哈希沖突連結清單的數量越多對記憶體的消耗就越大嗎？不，不是這樣的，雜湊演算法好的話，連結清單會很多，但是每一條都會很短，總的算下來開銷還是很雜湊演算法不好的那種連結清單很少但很長的情況一樣，但是問題是進入核心的雜湊演算法一般都不賴，最起碼都在朝着好的方向發展，是以哈希沖突連結清單在朝着短而多的方向發展，是以減少一條連結清單的開銷顯得有意義而重要，對，鑽的就是這個空子，核心開發就是這樣，有空子就鑽，隻要能優化。連結清單頭的優化是個好主意，可以将連結清單頭的prev指針優化掉，如此一來類似于list_head那樣的循環連結清單豈不是斷掉了嗎？是的，斷掉了，但是首尾相連有什麼好處呢？既然沒有好處那麼斷掉可以節約一個指針又何嘗不可呢？作為一個例子，我們看一下核心中對tcp-bind的處理資料結構：

struct tcp_bind_bucket {

unsigned short port;

signed short fastreuse;

struct hlist_node node; //該結構是另外一個更上層結構的節點

struct hlist_head owners; //該結構保有一個hash連結清單，該連結清單的内容是sock

struct tcp_bind_hashbucket {

spinlock_t lock;

struct hlist_head chain; //tcp_bind_bucket的node字段連入的連結清單

struct tcp_bind_bucket *tcp_bucket_create(struct tcp_bind_hashbucket *head, unsigned short snum)

struct tcp_bind_bucket *tb = kmem_cache_alloc(tcp_bucket_cachep, SLAB_ATOMIC);

if (tb) {

tb->port = snum;

tb->fastreuse = 0;

INIT_HLIST_HEAD(&tb->owners);

hlist_add_head(&tb->node, &head->chain);

return tb;

void tcp_bind_hash(struct sock *sk, struct tcp_bind_bucket *tb, unsigned short snum)

inet_sk(sk)->num = snum;

sk_add_bind_node(sk, &tb->owners); //将sk的hlist_node加入到tb的owners

tcp_sk(sk)->bind_hash = tb;

hlist的操作幾乎和list_head一樣，如果哪個結構需要挂接在一個哈希連結清單中，那麼就加入一個hlist_node的結構體指針，一切很簡單，實際上在核心中很少有地方用到hlist_add_before/after的，并且可以看出，真的就是沒有用到首尾相接這一個特性，現在可以看到優化方案的重要了，每個連結清單頭去掉prev指針，後面的不去掉，還保持雙向連結的特性以保證删除和随機插入的高效性，但是等等，為何要将prev指針換成pprev，原因很簡單，prev不能用了，為何不能用了呢？其實不是不能用，而是不好用，現在已經明白hlist連結清單不是循環連結清單了，那麼頭指針的prev就是NULL了，那麼在删除和插入時必須判斷目前的節點是不是頭結點，如果是要做一番處理，比如将其prev設定成NULL等等，這将導緻大量的if判斷，還要傳入儲存的hlist_head的資訊，否則就沒有辦法找到hlist_head進而更新它的first字段，但是并不是每次都删除表頭，删除表頭的占少數，為了這少數而多傳入一個參數值得嗎？而在程式設計中判斷總不是什麼好事，特别是在基于長流水線的分支預測的機器中更是這樣的。最好是能通過一個統一的方式來進行操作，就像list_head那樣，省略掉不必要的分支判斷。于是pprev就被設計出來了，再次看一下hlist_node資料結構，第一個字段同樣也是一個hlist_node的指針，看的好像AT&T的記憶體管理算法中的mem的設計，其實原理是一樣的，如果是prev的話，那麼prev指向的是前一個節點所在的位址，而如果是pprev的話，懂指針的人就會認為是前一個節點的位址的位址，其實不然，正确的解釋應該是前一個節點的next的位址，巧就巧在hlist_node的設計，第一個字段是一個同類型的指針。真的是這樣嗎？真的是這樣，不過前面的說法也沒有錯啊，難道它不是位址的位址嗎？實際上前面的說法也是正确的，兩種方式的解釋正是表達了兩種行為，這正包容了連結清單頭的特殊性，之是以設計pprev就是為了統一的表示不同的行為，而恰恰pprev可以有上述兩種解釋，我們先看一下普通位置的插入：

static __inline__ void hlist_add_before(struct hlist_node *n, struct hlist_node *next)

n->pprev = next->pprev;

n->next = next; //n->next本身就是一個指針，後面取&就是指針的指針

next->pprev = &n->next; //此場景中，pprev的解釋就是前一個節點的next字段的位址

*(n->pprev) = n; //直接修改指針指向的值，不必像list_head那樣得到原先next的prev字段指向的值

再看看在連結清單頭插入：

static __inline__ void hlist_add_head(struct hlist_node *n, struct hlist_head *h)

struct hlist_node *first = h->first;

n->next = first;

if (first)

first->pprev = &n->next;

h->first = n;

n->pprev = &h->first; //這裡解釋為位址的位址，因為h->first本身就是一個指針代表位址，再加上&就是位址的位址

删除節點的函數很簡潔：

static __inline__ void __hlist_del(struct hlist_node *n)

struct hlist_node *next = n->next;

struct hlist_node **pprev = n->pprev;

*pprev = next;

if (next)

next->pprev = pprev;

如果是list_head的非循環版本的話，就是下面的實作了：

static __inline__ void __hlist_del_v2(struct list_head *n)

if(n->prev ==NULL) //删除頭結點

n->next->prev = NULL;

//接下來我要如何找到hlist_head并且更改它的first字段呢？

...

看看hlist的設計總流程吧，首先意識到大哈希表時連結清單會很多，每個哈希桶中放一條list_head看一下效果，然後果斷的将表頭的prev去掉，并且為了和後面的正式節點區分，将表頭更名為hlist_head，後面的删除遇到了麻煩，于是将prev改為了pprev，利用了其雙重含義，最終hlist被設計完成。有人會問，哈希連結清單的第一個元素是hlist_head本身還是其first字段訓示的呢？看一下list_head就知道了：

static inline int list_empty(const struct list_head *head)

return head->next == head;

如果隻有一個list_head的話，那麼就是空表，是以在list_head中，起初的這個list_head就相當于hlist中的hlist_head，是以僅有一個head它隻是一個樁子，第一個元素是它的first指向的節點元素。

連結清單其實是很複雜的資料結構，設計得好的連結清單效率會非常高，畢竟它的操作很單一，如果有很多資料就要想想怎樣将這些資料組織到連結清單，是一個表還是多個表，另外就是長連結清單的處理問題，很多時候會将長連結清單分解為多個短連結清單，但是會帶來管理開銷，不如直接管理一個長連結清單，效率的高低就看管理算法了，最簡單的就是每次記住結束處理的索引，下次從這裡開始而不是從頭開始，比如一個系統的lru連結清單很長，一次記憶體回收操作僅僅周遊到其長度的三分之一處，那麼下次周遊如果從頭開始的話就會引起抖動或者類似饑餓的現象是以下次周遊就從三分之一後面開始。還有一種算法就是每次取連結清單長度内的随機數作為開始處理的節點，這樣在統計意義上會比較公平。最複雜的就是自适應的管理算法了，我還沒有做出來，這裡就不說了。

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1274005