不同类型的链表！

Question

常用的链表类型有哪些？

我知道并使用过以下链表类型：

1. 单向链表
2. 双向链表
3. 循环链表

你或你所知道的其他链表类型是什么？

- Jay

---

循环链表可以是单向链表或双向链表，因此，“选项”实际上与链接方向无关，而不是单独的选项。 - Tronic

Answer 1

跳表！虽然不是真正的链表类型，但它和链表有关系，并且非常酷。

好吧，根据分类方式，它要么是一种链表类型，要么是一组链表，但它具有 O(log N) 的插入/选择效率，这对于链表来说相当不错。

- Jimmy

---

跳表实际上是一种链表，或者至少是多个链表的混合和融合，具体取决于您的观察方式。 - Quinn Taylor

我一直认为跳表是一种奇怪的半树/半列表混合结构。数据结构的本体论不是我的强项。 - Jimmy

Answer 2

1. 展开链表

在计算机编程中，展开链表是链表的一种变体，它在每个节点中存储多个元素。它可以显著提高缓存性能，同时减少存储列表元数据（例如引用）所需的内存开销。它与B树相关。- 维基百科

2. XOR链表

XOR链表是计算机编程中使用的一种数据结构。它利用位异或运算（⊕）来减少双向链表的存储需求。- 维基百科

- Pratik Deoghare

Answer 3

还有一种多重链接列表。

在多重链接列表中，每个节点包含两个或更多的链接字段，每个字段用于按不同顺序连接相同数据记录集合（例如，按名称、按部门、按出生日期等）。 （虽然双向链表可以看作是多重链接列表的特殊情况，但两个顺序互为相反的事实导致了更简单和更有效的算法，因此它们通常被视为一个单独的情况。）

- codaddict

---

只是好奇，有没有未链接列表（Unlinked List）？哈哈 ;) +1 - Pratik Deoghare

@The Machine Charmer：它们被称为数组 :) - Jimmy

@Charmer，是的，在Java中有一个ArrayList。 - P Shved

难以置信！你们这些人把它看得如此认真！ - Pratik Deoghare

@Charmer：在极客圈子里，技术笑话可不是闹着玩的 :) - Caleb Hattingh

Answer 4

堆栈和队列通常使用链表实现，并仅限制支持的操作类型。堆栈和队列都是如此。一个展开链表是一种链表，其中每个节点包含一个数据值数组。这导致了更好的缓存性能，因为更多的列表元素在内存中是连续的，并且减少了内存开销，因为需要为列表的每个元素存储较少的元数据。

- Vijay Mathew

Answer 5

我可以想象出一些情境，其中随时能够从列表中的任何元素链接到第一个和最后一个元素将会非常有用。如果没有其他人纠正我，我断言这被称为 高性能标记列表。

- High Performance Mark

---

我认为每个节点维护1或2个额外链接是一个非常糟糕的想法。特别是因为可以轻松地在列表节点外部存储对第一个和最后一个元素的指针，并且只需在一个位置更新它们。即使在C语言中（而不是面向对象的语言），我也会选择存储两个额外变量，而不是使链表节点携带冗余数据。 - Quinn Taylor

根据定义，您始终可以指向第一个节点（头部）。保持指向最后一个节点（尾部）的指针也是常见的编程实践。这种数据结构称为“头尾链接列表”。基于这样的列表可以实现双端队列，因此有时将这些术语视为同义词。http://en.wikipedia.org/wiki/Double-ended_queue - Wildcat

可悲的是，“高性能标记列表”并不是一个高性能列表。叹气。 - High Performance Mark