動態集合中的後繼和前代最壞情況運行時間

Question

以下動態集合運算的漸近最差情況運行時間是多少？

後續（L，X）爲未分選的單獨&雙向鏈表

前身（L，X）爲未排序雙向鏈表

L：列表中，x：指針的條目

（其實這是本書第10-1題的一部分：「算法導論，第三版」，我搜索了答案，答案是O（n），但我找不到任何解釋）

Answer 1

隨着「前輩」和「succ essor「，我想你的意思是按照排序順序。

確實是O（n），因爲您需要查看列表中的每個元素才能找到它。