展开链表如何比链表更好？

Question

我正在学习“数据结构和算法变得容易”一书，但我在学习“比较链接列表和展开链接列表”时感到困惑。

什么是头顶？为什么他只为100个元素数组声明8个字节的开销？

​

​

Answer 1

我认为这本书在struct LinkedBlock的定义上有一个严重的错误。让我们稍后再讨论这个问题，首先是：

什么是头顶？

struct ListNode是为存储一个整数而设计的，但是除了这个整数之外，每个节点都有两个指针。因此，对于每个节点，需要分配1个整数+2个指针。让我们假设4字节整数和4字节指针。因此，每个节点都需要4+ 2x4 = 12字节。因此，为了存储实际数据的1项(又名1整数)，您需要分配12个字节。您在指针上浪费了8个字节。这8个“浪费”的字节称为开销。它们只用于簿记，而不是用于数据。

但更糟的是.在分配动态内存时(在使用链接列表时通常会这样做)，会有一些额外的开销。分配器可能需要为每个malloc添加一些额外的内存来存储有关malloc的信息。另一个问题是，malloc ed内存可能与某些固定块大小(例如16或32字节)对齐，因此如果分配20字节，就无法使用其余的12字节--它们被浪费了。这就是书中所说的“分配开销”。“分配开销”与系统有关，但书中假设每个malloc需要额外的8个开销字节。

因此，现在每个malloc 'ed struct ListNode都使用：

整数的4个字节

2个指针的8个字节

分配开销的8个字节

总共20个字节，其中4个字节是您的数据，16个字节是开销。因此，对于您需要存储的每个整数，您需要20个字节。如果您想要存储1000个整数，则最终会在开销上浪费16 4kb，以便存储4kb的数据。

现在回到struct LinkedBlock。在这本书里，看起来是这样的：

struct LinkedBlock {
    struct LinkedBlock *next;
    struct LinkedNode *head;
    int nodeCount;
};

我很肯定这本书有一个错误，它应该是这样的：

struct LinkedBlock {
    struct LinkedBlock *next;
    int *dataArray;
    int nodeCount;
};

使用它的方法如下：

struct LinkedBlock pNode = malloc(sizeof(struct LinkedBlock));
pNode->dataArray = malloc( 100 * sizeof(int) );

第一个malloc需要4+4+4+8=20个字节。(指针、指针、int、分配开销)

第二个malloc需要4* 100 +8= 408字节。(100 int，分配间接费用)

总共428字节。

然而，由于malloc'ed数据可以容纳100个整数(对应于400个字节)，您的开销仅为28个字节。换句话说，平均每个整数使用4.28字节。将其与第一种方法进行比较，即每个整数需要20个字节。

为什么他只为100个元素数组声明8个字节的开销？

这是因为数组是在一个调用中分配的，并且假定每个malloc调用都有8个字节的分配开销。

Answer 2

开销是不属于您想要存储的数据的所有内容。类似于指向下一个和前一个元素的指针。

块列表是数组的列表。每个数组包含许多元素。原则上，整个列表可以由一个块节点和一个包含所有元素的数组组成。所以头顶上少了些。

LinkedBlock中的head指向一个ListNode有点让人困惑--它应该指向任何数据(没有prev和下一个指针)。

Answer 3

在普通链表中，一个节点有一个元素和两个指针(8个字节)，2个指针是开销，因为它不是你的数据。在展开链表中，一个节点有100个元素和2个指针(8个字节)，因此100个元素的开销为8个字节。