二重リンクリストとPython 3でそれらを実装する方法

リンクリストは、データを格納する線形の方法です。これは、データを含むノードと、次のデータへのアクセス方法を示すポインターで構成されます。ノードをチェーンのメンバーと考えてください。強い絆を保つために、各チェーンは互いに依存しています。たとえば、中間リンクにすべてが欠けている場合、その後は失敗します。もはや完全なチェーンではありません!これはどのようにリンクリストに変換されますか?ポインターの1つが欠落しているか、正しくない場合、残りのデータは読み取れなくなります。

有効なチェーンではありません!これはリンクリストを壊します!

ただし、この記事のトピックは、リンクリストのより汎用性の高いバージョン、つまり二重リンクリストに関するものです。通常の(または単独の)リンクリストと比較して、二重リンクリストには、previousという別のポインターが含まれています。ご想像のとおり、これによりノードは前のノードの場所を知ることができます。それに比べて、単一リンクリストは、同じポイントに到達するために、リスト全体を前のポイントまで再度トラバースする必要があります。

単一リンクリストの詳細については、クラスメートの記事をご覧ください。

前述のように、ノードはメモリ内の他の場所を指します。どういう意味ですか?まあ、連続した場所に格納されている配列とは異なり、リンクリストには単にポインターがあります。下の図では、メモリの各ブロック(赤)を指す2つのポインターがあります。次のポインター(黒)を見て、その情報にアクセスします。前のブロックを見つけたい場合は、前のポインター(白)を確認します。

では、二重リンクリストをどのように実装するのでしょうか? PythonPython 3の方法

Nodeクラスに.prevを追加するだけです。これで実装を開始する準備が整いました!

利点— Python 3コード付き!

二重にリンクされたリストが単一にリンクされたリストよりも優れている点は何ですか?二重にリンクされたリストを使用すると、ノード間を前後に移動できます。これにより、挿入などが非常に簡単になります。二重リンクリストを使用すると、リンクリストから目的のノードまで移動し、前のノードを呼び出すだけです。

短所

リンクリストには優れた点がありますが、万能のソリューションではありません。多くのデータ構造およびアルゴリズムと同様に、これは武器庫のツールである必要があります。単一リンクリストの欠点の1つは、二重リンクリストの各リンクがその前のポインターを追跡する必要があるため、メモリ消費量が増えることです。また、上記のポインタを追跡することは困難です。

私は実際にそれらの実装を実践している最中です。これは、この記事の執筆時点(2019年4月)で2回目の成功した実装です。毎回少しずつ簡単になりますが、以前のポインターが他のすべての機能とどのように相互作用するかを図で表す必要があります。

しかし、これは何のために使用されますか?

聞いてますね前と次を見たときはいつでも考えてください。それらを実装できるいくつかの明白で微妙な方法があります。

ソース:https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

音楽プレーヤーのような場合はどうですか?非常に明示的な「次へ」および「前へ」ボタンがあります。二重にリンクされたリストを使用して、これらの2つの曲を切り替えることができます。

それともブラウザはどうですか?これらには、アクセスしたWebページ間を前後に移動する明示的な方法もあります。

次に、選択したワードプロセッシングソフトウェアまたはフォトエディターについて考えます。間違えたときはいつでも、Ctrl(Macの場合はCMD)+ Zを押して、最後のアクションを取り消すことができます。同様に、元に戻したものをCTRL(Macの場合はCMD)+ Yでやり直すことができます。なぜこの音が馴染みのあるのでしょうか?二重にリンクされたリストで実装することもできます!前のポインターは、行われたアクションを指しますが、あまりにも多くの操作を元に戻すとアクションをやり直すことができます。

ソース:https://gfycat.com/brilliantbeautifuldassieソース:https://www.solitairecardgames.com/how-to-play-solitaire

私が考えたあまり明白ではない実装は、ゲームソリティアでした。側には、私の要点を説明するのに役立つソリティア用語のイメージがあります。

このゲームは、前か次のカードがタブローであろうと廃棄物であろうと常に表示できるようにする必要がある輝かしい例です。廃棄物の山からタブローにカードをプレイすると、廃棄物の山はそれ以前のカードで更新されます。

二重リンクリストの使用に関するより活発な議論については、stackoverflowに関するこの議論をご覧になることをお勧めします。

次回リンクリストを実装するときは、二重リンクリストを試してみませんか?リンクリストの上にあるコードはそれほど多くないため、大きなメリットがあります。

追加のリソース

二重リンクリストのPython 3実装への完全なリンクは、Githubリポジトリにあります。

二重リンクリストの3D印刷可能なチェーンが必要な場合は、Thingiverseにアップロードしました。

https://www.geeksforgeeks.org/doubly-linked-list/

https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm

https://www.youtube.com/watch?v=JdQeNxWCguQ