自调整列表和常规链表之间的主要区别
Key Differences between Self-Adjusting Lists and Regular Linked List
我在学习数据结构class（基于 C++），我必须诚实地说，我的老师并没有教我们太多关于自调整列表的知识。尽管如此，我还是被分配了一个项目，需要实现这样的 class.
我的导师为这个项目留下的关于自我调整列表的唯一注释是：
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.
我不明白的是为什么所有插入都必须在列表的前面执行。考虑到插入的数据已被零次访问，最后插入不是更好吗？
此外，还有其他我应该注意的关键差异吗？我似乎无法在网上找到深入探讨该主题的良好资源。
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
虽然理论上这种列表的平均访问时间和最差访问时间与普通列表（随机节点）相同，但实际上，平均access/search时间要快得多。
如果节点数量增长到非常大的数量，自平衡 BST（例如红黑树）或哈希将提供更好的访问时间。
还有许多其他方案可用于保持列表的自我调整：
例如：
- 最近用在头上（如您所说）
- 保持列表按访问计数排序（最近访问的节点可能不一定排在前面）
- 访问非头节点时，与前一个节点交换
策略的确切选择取决于您的要求，在目标环境中进行分析是选择一种策略的最佳方式。
我在学习数据结构class（基于 C++），我必须诚实地说，我的老师并没有教我们太多关于自调整列表的知识。尽管如此，我还是被分配了一个项目，需要实现这样的 class.
我的导师为这个项目留下的关于自我调整列表的唯一注释是：
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.
我不明白的是为什么所有插入都必须在列表的前面执行。考虑到插入的数据已被零次访问，最后插入不是更好吗？
此外，还有其他我应该注意的关键差异吗？我似乎无法在网上找到深入探讨该主题的良好资源。
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
虽然理论上这种列表的平均访问时间和最差访问时间与普通列表（随机节点）相同，但实际上，平均access/search时间要快得多。
如果节点数量增长到非常大的数量，自平衡 BST（例如红黑树）或哈希将提供更好的访问时间。
还有许多其他方案可用于保持列表的自我调整： 例如：
- 最近用在头上（如您所说）
- 保持列表按访问计数排序（最近访问的节点可能不一定排在前面）
- 访问非头节点时，与前一个节点交换
策略的确切选择取决于您的要求，在目标环境中进行分析是选择一种策略的最佳方式。