Q

不同類型的鏈接列表！

2010-03-05 111 views 8 likes

8

常用的鏈接列表有哪些不同的類型？不同類型的鏈接列表！

我知道並使用了以下內容：

單鏈表
雙向鏈表
循環列表

什麼是已經使用的其他類型的列表你還是知道你？

2010-03-05 Jay

+4

圓形列表可以單獨鏈接或雙向鏈接，以便「選項」與鏈接方向性真正正交，而不是單獨的選項。 – Tronic 2010-03-05 08:57:02

A

回答

5

Unrolled Linked List

在計算機編程，一個展開鏈表是存儲在每個節點的多個元素鏈表上的變化。它可以顯着提高緩存性能，同時減少與存儲列表元數據（如引用）相關的內存開銷。它與B樹有關。 - 維基百科

XOR Linked List

XOR鏈表是在計算機編程中使用的數據結構。它們利用在這裏用⊕表示的按位排列（XOR）操作到降低雙存儲列表的存儲需求。 - 維基百科

2010-03-05 09:04:59

5

Skip lists！ ~~不是一種真正的鏈接列表，而是相關的，和漂亮的neato。~~

好吧，它可能是一種鏈表或一組鏈表，這取決於你如何對事物進行分類，但它具有O（log N）插入/選擇功能，這對於鏈表來說非常好。

2010-03-05 08:55:59 Jimmy

+0

實際跳過列表* *是一種鏈接列表，或者至少是多個鏈接列表的混合和混搭，具體取決於您如何查看它。 – 2010-03-05 09:10:32

+0

mmmmm，我一直認爲跳過列表是一些奇怪的半樹/半列表突變結構。數據結構的本體並不是我的專長。 – Jimmy 2010-03-05 09:14:43

0

我大概可以想象一下，從列表中的任何元素鏈接到第一個元素和最後一個元素都是有用的。如果沒有人糾正我，我斷言這稱爲高性能標記清單。

2010-03-05 08:58:23

+2

我會說從每個節點維護1或2個額外的鏈接是一個非常糟糕的主意。特別是因爲很容易將指針存儲到列表節點外的第一個和最後一個元素，並且只需要在一個位置更新它們。即使是直接C語言（與面嚮對象語言相反），我也會選擇存儲兩個額外的變量，而不是用冗餘數據來阻塞鏈表節點。 – 2010-03-05 09:09:20

+0

您始終可以根據定義指向第一個節點（頭）。這也是常見的編程習慣，也是保持指向最後一個節點（尾部）的指針。這種數據結構被稱爲「頭尾鏈表」。雙端隊列可以基於這樣的列表來實現，所以有時候這個術語被稱爲同義詞。 http://en.wikipedia.org/wiki/Double-ended_queue – Wildcat 2010-03-05 09:14:34

+1

不幸的是，高性能標記清單證明不是一個高性能清單。 Sigghhh。 – 2010-03-05 09:31:44

3

stacks和queues通常都使用鏈表來實現，並且只是限制了支持的操作類型。 unrolled linked list是一個鏈接列表，其中每個節點包含一組數據值。這導致改進的緩存性能，因爲更多的列表元素在內存中是連續的，並且減少了內存開銷，因爲需要爲列表的每個元素存儲更少的元數據。

2010-03-05 09:03:13

4

還有一個multiply-linked list。

在乘法運算鏈表，每個節點包含兩個或多個環節領域，正在使用的每個字段例如，按名稱，按部門，按日期同一組數據記錄連接以不同的順序（出生等）。（雖然雙向鏈表可以看作是多鏈表的特例，但兩個命令彼此相反的事實導致更簡單和更高效的算法，因此它們通常被視爲單獨的情況。）

2010-03-05 09:04:52 codaddict

+2

只是好奇是否有任何'Unlinked List'？哈哈;）+1 – 2010-03-05 09:09:49

+1

@ The Machine Charmer：它們被稱爲數組:) :) – Jimmy 2010-03-05 09:19:15

+0

@Charmer，是的，Java中有一個'ArrayList'。 – 2010-03-05 09:21:30

相關問題