Java LinkedListノードの操作

Question

JavaでAaron WilliamのMultiset Permutation反復アルゴリズムを実装したいと考えています。 Algorithm Whitepaper。重要なのは、アルゴリズムがマルチリストを表すためにリンクリストを使用し、さまざまなリンクされたリストノードへのいくつかのポインタを保持し、ヘッドノードを追跡し、ポインタから次のノードを取得することです。

私は、組み込みのLinkedList実装ではこれらの機能を提供していないことを理解しています。私はまた、自分自身のリンクリストの実装をロールバックすることは、この作業では些細なことだと認識しています。しかし、Listインターフェースを尊重するためのすべての定型コードを書くのは簡単ではありません - 私はLists.Sortで自分のリストをソートしたいと言っています！また、別のリスト実装を格納するコレクションの入力から何らかのレベルのストレージ重複が発生することも私にはわかります。

私の質問：があります別のこれらの機能を提供するネイティブJavaデータ構造ですか？確かに私の目標は、独自のリンクリストの実装を必要とするのには程遠いです。

Answer 1

Java LinkedListノードのエントリは公開されていないため、一部のユースケースでは適切ではありません。特定の位置の特定の要素の検索、削除、または追加は高価です。私は、アイテムを効率的に削除してリストの一番上にプッシュするためにノードアクセスが必要な同様の問題を抱えていました。

私は、特殊な二重リンクリストの実装を考え出しました。私はノード構造を要素に直接格納する。すなわち、要素はノードから導出される。これには、リストを操作するためにメモリを割り当てる必要がないという利点があります。しかし、要素が1つのリストにしか含まれないという欠点があります。あなただけの要素を保持しているラッパーノードクラスを作成し、あなたの要素にノードを保存したくない場合は...

実装：DoubleLinkedList とテスト： DoubleLinkedListTest