循環リストは、リスト全体を何度も繰り返すループと組み合わせて、適切なリスト (終了マーカー付き) によってシミュレートできるという直感があります。私の感覚では、制御ロジック (ループ) が構造に組み込まれているため、循環リストの方がすっきりしています。一方、制御ロジックを構造から切り離すことは、関心の分離のように思われ、状況によっては好まれるかもしれません。よくわからないのは、それぞれがどのような状況で役立つかです。また、シミュレーションが常に可能かどうかはよくわかりません。そうでない場合は、反例を教えてください。
2 に答える
3
はい、いつでも可能です。
長所：
- 循環リストがあります。これはおそらくプロです。そうでなければ、あなたはそれをしていません。
短所：
- なんらかの理由で、最初に循環リストを作成する代わりに、通常のリストの周りにラッパーを実装するのに時間を無駄にしました。
FWIW、私は何年も前に、すべてのリストは循環するべきだという結論に達しました。これにより、リスト内の (概念的な)最後の要素への単一のポインターを使用できますが、O(1) 時間でリストの先頭と末尾の両方に簡単に挿入できます。さらに、リストを循環させると、リスト操作コードの特殊なケースの数が減ります (次のポインターには常に有効なノードが存在します)。
于 2014-02-26T15:55:14.613 に答える
1
はい、シミュレートできます。ただし、リストを制御するには 2 つのポインタが必要です。現在の要素にアクセスするための 1 つのポインターと、最初の要素を保持するための 1 つのポインター。「現在の要素ポインター」がリストの境界外にあることを検出し、それを最初の要素に移動するロジックを作成する必要があります。
于 2014-02-26T15:55:20.447 に答える