這兩種不同的實現雙鏈表的方式有什麼區別？

我遇到過兩種方式來實現雙向鏈表：這兩種不同的實現雙鏈表的方式有什麼區別？

#define LIST_ENTRY(type)      \ 
    struct {        \ 
     struct type *le_next; /* next element */   \ 
     struct type **le_prev; /* address of previous next element */ \ 
}

這種方式是在FreeBSD的queue.h，我想知道爲什麼它採用指針的指針le_prev？

struct list_head { 
    struct list_head *next, *prev; 
};

這種方式是在linux list.h，它只是使用兩個簡單的指針。

有什麼區別？哪個更好，只需使用一個簡單的指針和一個指向指針的指針或兩個簡單的指針？

來源

2014-11-14 karllo

它依賴於語義。單指針將指向前一個或下一個節點或元素另一方面可以使用雙指針，其中指針將再次指向包含其他節點的鏈接列表。 –

你確定雙指針是用於「上一個下一個元素」嗎？ –

http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/sys/queue.h?rev=1.30 –

該列表並非「雙向鏈接」，因爲該列表在兩個方向都不可穿過。給出雙指針，以便下一個指針可以快速更改。

另外，在c中，結構元素總是連續存儲。所以給定下一個指針的地址，你可以計算出前一個節點的地址。但是這隻會增加代碼的複雜性，並且需要您計算結構中所有元素的大小。這是不值得的麻煩。（你不應該假設這一點，並說這是一個雙向遍歷的鏈表）

哪個更好？

用兩個簡單的指針實現通常更好。可能會出現雙指針實現可能更好的特殊情況。

來源

2014-11-14 09:13:38

「因此，考慮到下一個指針的地址，你可以計算出前一個節點的地址。」您是否假設列表中的元素存儲在數組中？ –

下一個指針指向下一個元素（在結構中）。我不是說鏈表的下一個節點 –

這兩種不同的實現雙鏈表的方式有什麼區別？

回答

相關問題