Q

不同类型的链接列表！

2010-03-05 80 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

相关问题