data-structures - 动态集合中的后继和前继最坏情况运行时间

Question

以下动态集操作的渐近最坏情况运行时间是多少？

Successor(L,x) 用于未排序的单链和双链表

Predecessor(L,x) 用于未排序的双向链表

L：列表，x：指向条目的指针

（实际上这是本书问题10-1的一部分：“算法简介，第三版”，我搜索了答案，答案是O（n）但我找不到任何解释）

Answer 1

对于“前任”和“继任者”，我想您的意思是按排序顺序。

这确实是 O(n)，因为您需要查看列表的每个元素才能找到它。