java - 単一リンク リストに対する双方向反復

Question

私は現在、データ構造試験の勉強をしていて、反復に関する質問に遭遇しました。

一方向にリンクされたリストに双方向イテレータを実装することは可能ですか? もしそうなら、それをどのように実装しますか？

最初にリンクされたリストを順方向にトラバースし、ノードを逆方向に保持する一時的なリンクされたリストを保存するというアイデアがありました。しかし、この一時リストをトラバースすると、逆方向のトラバースしかできないイテレータになります。

Answer 1

この回答は、リストが常に単一リンクのままである必要があることを前提としています。

最初の要素へのポインターと現在の要素へのポインターのみが必要です。

前方に反復するときは、カウンターをインクリメントして、反復した回数を確認します。(挿入はイテレータを無効にするかもしれません!)。この変数を呼び出しましょうcount

ここで、現在の要素から値を逆方向に反復したい場合kは、最初の要素から FORWARDS を反復する必要があることがわかりますcount - k。

編集: もちろん、効率を向上させることができます。この答えは、一種のブルートフォースアプローチです。

言及されたコメントの 1 つとして、前方に反復するときにポインターをスタックにプッシュし、後方に反復するときにそれらをポップすることができます。

リストが常に単一リンクのままである必要がない場合は、前方に反復するときに後方リンクを追加し、後方に反復する場合はそれらのリンクを削除できます (理由はわかりませんが)。

Answer 2

現在のノードを追跡する変数をいつでも使用できます。前方にトラバースしたい場合は、通常どおりに行ってください。逆方向に移動したい場合は、最初のノードから始めて、次のノードが現在のノードと等しくなるまで移動を続けます。