展开链表数组与节点

Question

我正在阅读有关展开链表的文章，并找到了两种不同的制作方法。我的书是这样实现的：

// Node
typedef struct node {
    int data;
    struct node *next;
} Node;

// Block of nodes
typedef struct linkedblock {
    struct linkedblock *next;
    Node *head;
    int nodeCount;
} LinkedBlock;

但是维基百科显示，LinkedBlock 没有指向 Node 的指针，它有一个数组。我认为这可能是因为内存是连续的并且与缓存效率有关？这样做还有其他好处吗？我这本书实现的方式是不是少了optimized/worse？是否碰巧有一种常见或首选的方式？

我正在尝试实现一个展开的链表，这样我就可以了解它们是如何工作的，而且以防万一我将来需要使用它（奇怪的是，我在 [=20= 上找不到任何 C 实现] 或其他地方）。基本上我想知道这两种方式中的哪一种更有可能用于实际应用程序。这也是我不应该浪费太多时间学习的数据结构吗？因为在我的其他算法书 (CLRS) 中我什至没有看到它被提及。

Answer 1

这本书的实现似乎没有多大用处，因为它实际上比标准链表使用更多内存（用于存储那些 LinkedBlock 结构). 展开链表的主要优点之一是与普通链表相比，每个节点可以存储更多数据。这是数组和链表之间的平衡，数组只使用一个额外的 space 整数来存储大小（space 高效），链表在给定指向某些数据（时间）的指针的情况下具有高效的插入和删除高效）。

至于了解它们的价值：它们具有与普通链表相似的算法特性。制作展开链表的大部分好处是，如果您有一个需要加速或使用过多内存的现有应用程序，因为它们将具有与常规链表相同的接口。如果您了解渐近分析（CLRS 中也有讨论），那么您可能能够认识到展开链表的内存使用和时间效率仅相差一个常数因子，因此渐近地它们是相同的。

我的建议是：注意它们的存在并且它们可以提高实际应用程序的性能，但除非您有一个特定的应用程序要尝试加速，否则不要太担心他们。

展开链表数组与节点

Unrolled linked list arrays vs. nodes

c

linked-list

data-structures

unroll