c - 展开链表比链表好在哪里？

Question

我正在学习“数据结构和算法变得简单”这本书，但是在学习“比较链表和展开链表”时我感到困惑......

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

Answer 1

开销是所有不属于您要存储的数据的内容。就像指向下一个和上一个元素的指针。

阻止列表是一个数组列表。每个数组包含多个元素。原则上，您的整个列表可以由一个 block 节点和一个包含所有元素的数组组成。开销更少。

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