linked-list - 根据搜索频率在链表中搜索

Question

假设内存中有一个未排序的链表。建议一个合适的搜索过程，其中经常搜索的元素会以较少的比较次数找到。（如果您愿意，可以修改数据结构。）

这该怎么做？

标签： linked-list

Answer 1

实现这一目标的一种方法是

• 在未排序的链表中搜索需要的元素（线性搜索）
• 如果找到，则从那里删除该节点并使其成为头节点（删除和插入操作）
• 所以下次需要较少的比较来找到该节点。
• 所有已经搜索过的元素都将出现在头部附近，因此它的检索将是有效的。