c++ - 自调整列表和常规链表之间的主要区别

Question

我在上一门数据结构课(基于 C++)，老实说，我的老师并没有教我们太多关于自调整列表的知识。尽管如此，我被分配了一个需要实现这样一个类的项目。

我的导师为这个项目留下的关于 self 调整列表的唯一注释是:

A self-adjusting list is like a regular list, except that all insertions are performed at the front, and when an element is accessed by a search, it is moved to the front of the list, without changing the relative order of the other items. The elements with highest access probability are expected to be close to the front.

我不明白的是为什么所有插入都必须在列表的前面执行。考虑到插入的数据已被零次访问，在最后插入不是更好吗？

此外，还有其他我应该注意的关键差异吗？我似乎无法在网上找到深入探讨该主题的良好资源。

Answer 1

What I do not get about this is why all insertions must be performed at the front of the list. Wouldn't it be better to insert at the end considering that the data being inserted has been accessed zero times?

通常最近添加的项目更有可能成为访问对象。而且开头插入是常数时间运算。

例如，如果您购买书籍并将最新的书籍放在顶部，以便最容易访问。如果您从一堆旧书中搜索和阅读一本旧书，它会被放在最上面。

当然，您想将最新购买的书放在最前面，尽管您从未读过它。

Also, are there any more key differences I should look out for? I cannot seem to find a good source online that goes in-depth about this topic

虽然理论上这种列表的平均访问时间和最差访问时间与普通列表(随机节点)相同，但在实践中，平均访问/搜索时间要快得多。

---

如果节点数量增长到非常大的数量，自平衡 BST(例如红黑树)或哈希将提供更好的访问时间。

还有许多其他方案用于保持列表自调整: 例如:

• 最近用在头上(如您所说)
• 保持列表按访问计数排序(最近访问的节点可能不一定排在前面)
• 当访问一个非头节点的节点时，将其与前一个节点交换。

策略的确切选择取决于您的要求，在目标环境中进行分析是选择一种策略而不是另一种策略的最佳方式。