在已排序的鏈接列表中插入節點的時間複雜度

Question

在Java中的排序鏈接列表中插入節點的時間複雜度是多少？有沒有一種算法的複雜度小於O（n）？

Answer 1

如果您擁有的只是一個鏈接鏈接，並且您從頭開始，最糟糕的情況是您必須遍歷整個列表才能找到插入點。這給了O（n）最壞情況的時間。

類似於skiplist可能會給O（log n）插入。然而，這與你所詢問的數據結構不同（樹木等）。