1

我正在阅读有关展开链表的信息，并找到了两种不同的制作方法。我拥有的这本书实现了这样的一个：

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

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

但是 Wikipedia 显示，它LinkedBlock没有指向 a 的指针Node，而是有一个数组。我认为这可能是因为内存是连续的并且与缓存效率有关？这样做还有其他好处吗？我的书实现它的方式是否优化/更差？是否有一种常见或首选的方式？

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

4

1 回答 1

3

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

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

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

于 2016-07-16T20:46:09.357 回答