LinkedList运营成本

Question

在链表中查找元素的成本是多少？我知道在一个平衡的二叉树中找到一个元素的成本是O(log )，但是链表呢？

Answer 1

如果您对链表中的元素一无所知，并且没有指向链表的指针，则在链表中搜索元素的成本在最好的情况下为O(1)，在最坏的情况下为O(n)。在最好的情况下，您在最前面找到元素，而在最坏的情况下，您必须查看所有元素，然后才能确定您要搜索的元素不在那里。

在最坏的情况下，这比平衡二叉搜索树慢得多，因此在链表上有一些变种，旨在加快访问速度。例如，skip list使用多个并行链表来“跳过”列表中的元素。这要求按排序顺序存储元素，但它确实将查找时间减少到预期的O(log )。

希望这能有所帮助！