c++ - 双方向リンクリストを実装するには?

Question

クラスで単方向リストを実装する方法を学びました。私たちの教授は、私たちが二重連結リストをやっていると言いましたが、どうやらとても簡単なようで、その方法を詳しく説明していませんでした。私は片方向リストを扱うのがとても得意ですが、二重方向リストの作り方を誰か教えてくれませんか?

Answer 1

一重連結リストの適切な定義が既にある場合、二重連結リストは簡単です。

あなたがおそらく次のようなものを持っていた前に

struct link{
  struct link* next; //a pointer to the node that comes next
  int value;
}

これはに変更する必要があります

struct link{
  struct link* next; //a pointer to the node that comes next
  struct link* prev; //a pointer to the node that comes before
  int value;
}

これで、基本的に、リストをトラバースするときに next の代わりに previous を使用して逆の操作を行うことができます。

追加または削除するときに、物事が正しいものに向けられるように、「簿記」に注意する必要があることに注意してください。

私はいつも、関数を書くとき、リンクされたリストへの追加と削除のすべてのステップを描くように学生に言います。そして、削除されるまで、ポインターを介して図面内のすべてへの参照を常に保持するようにします。

Answer 2

@kratenko には素晴らしい点がありますが、ここでは簡単にアクセスできるように簡単に説明します。

単一リンクリストには、一方向に移動するポインターがあります。

HEAD*-> |データ| -> |データ| -> |データ| -> ヌル

双方向リンク リストの場合は、片方向リンク リストを両方向に実装します。

HEAD* <-> |データ| <-> |データ| <-> |データ| <-> しっぽ*

ここで、HEAD* と TAIL* は両方とも、それらを指す node* メンバーを持つノードです (DoublyLinkedList クラス内)。

Answer 3

頭と尻尾に「ダミーノード」を追加する必要があります。これにより、追加と削除の方法が簡素化されます（頭と尾への追加と削除を考慮する必要はなく、「中間の状況」と考えるだけです）。

プログラムを終了する前に、ダミーノードをNULLに置き換えることを忘れないでください。