data-structures - 動的セットでの後続および先行の最悪の場合の実行時間

Question

次の動的集合操作の漸近的な最悪の場合の実行時間は?

ソートされていない一重および二重にリンクされたリストの場合、Successor(L,x)

ソートされていない二重連結リストの Predecessor(L,x)

L: リスト、x: エントリへのポインタ

（実際には、これは本の質問10-1の一部です：「アルゴリズム入門、第3版」、私は答えを探しました、答えはO（n）ですが、私はそれについての説明を見つけることができませんでした）

Answer 1

「前任者」と「後任者」とは、ソート順を意味していると思います。

それを見つけるには、リストの各要素を調べる必要があるため、実際には O(n) です。