循環リンクリストの最後にノードを挿入するのに時間の複雑さ？

Question

N個の要素を含む循環単一リンクリストの最後にノードを挿入する時間の複雑さ？最初のノードへのポインタがあるとします。

---

私は、次のフィールドを変更するために新しいノードの前にノードにLLを解析する必要があるので、O（N）だと思います。

私はそれを正しく持っていますか？

Answer 1

円の単一リンクリストの末尾に追加するには、O（1）時間で実行できます。

1. 新しいノードを作成し、ヘッドノードの後に​​挿入します。
2. データをヘッドからこの新しいノードにコピーします。
3. 新しいヘッドノードに新しいデータを追加します。
4. 頭を再割り当てします。

これらはすべて定数時間演算であるため、この手順はO（1）です。