真的很快跳到双链表的中间

Question

是否有任何方法可以快速跳转到双向链接列表的中间元素,而不是这样做

for(int i = 0; i <= numOfElements/2; i++){
element = element.next;
}

这在我的代码中需要这么多时间,如果我会优化它,那真的很酷:)

Answer 1

链接(或双重链接)列表的要点是随机访问很慢(O(n)).

您需要使用其他类型的列表,例如跳过列表.

Answer 2

链表的重点是无法做到这一点.但是,存在(间接)允许该操作的其他数据结构.一个这样的数据结构是跳过列表,其名称来源于它可以精确地执行以下操作:跳过项目.

此数据结构不能直接应用于您的情况,因为跳过列表实现了字典,不允许直接访问索引项.但是,可以相应地调整一般结构.