在已排序的链接列表中插入节点的时间复杂度

Question

在Java中的排序链接列表中插入节点的时间复杂度是多少？有没有一种算法的复杂度小于O（n）？

Answer 1

如果您拥有的只是一个链接链接，并且您从头开始，最糟糕的情况是您必须遍历整个列表才能找到插入点。这给了O（n）最坏情况的时间。

类似于skiplist可能会给O（log n）插入。然而，这与你所询问的数据结构不同（树木等）。