FreeBASIC TutLinkedLists

連結リスト　左にメニュー・フレームが表示されていない場合は、ここをクリックして下さい

---

連結リストは、最も基本的なデータ構造の1つで、容易に拡張可能な構造です。
連結リストは、配列とは違い、構成要素数がいくつ分からないときに、非常に役に立つでしょう。
連結リストの背後にある概念は、それぞれのノード構造が、その直前と直後のノード構造を参照するポインタを持っている、ということです。
2つの異なったノードにリンクするとき、これは二重連結リストと呼ばれます。
構造にポインタを使うので、直前か直後のノードがなければ、ヌルポインタを指定できます。また、ポインタがメモリアドレスを格納するので、格納できるノードの量は、メモリによる制限だけになります。

連結リストを使う唯一の欠点は、たとえば整数を格納するために、その整数だけでなく、整数へのポインターと周囲のノードへのポインターを含む構造体にも、スペースを割り当てなければならない点です。
しかし、これは、何百万ものノードを格納する場合でなければ、今日のコンピュータでは大した違いになりません。

連結リストの基本構造は、ノード(結節点)です。

宣言はこれです:

補足として、このスクリプトにアクセスできる人が FreeBASIC に新しいキーワード（Ptr など）を含むように更新したい場合は、誰でもお気軽にどうぞ :)
また、LIST は FB キーワードではないと思います（私が間違っているなら修正してください）。

この構造は、3つのポインタを含んでいます。
1番目は、何でもへのポインタ (Any Ptr) です。これは、文字列、整数、文字、ユーザ定義型、および組合さえ格納できることを、意味します。
しかし、これは、また、あなたがポインタを渡さなければならないことを意味します。
Allocate(または、CAllocate)関数を使って、ポインタを入手できます。

次の2個のポインタは、listnodes へのポインタです。これで、技術的に、下のようになります:

Print node -> pNext -> pNext -> pNext -> pNext -> pNext...

以後、各ノードは、別のノードへのポインタを含みます。
上の構文の問題は、アクセスできるノード数に制限があることと、コードが理解しにくいことです。
この目的で ListGetNext 関数を使い、While ループで繰返し処理できます。

これ以上先に行く前に、連結リストを使うためのすべての宣言を見ましょう。

全ての関数に、"List" の接頭語を付けてあることに、注意してください。

編集: ふむ、私は、関数の中で "Rem" を使うのが好きでないように、みえるでしょう。 けれども、こうすると、うまくコンパイルされます。

内容は、連結リストを作成する関数、項目を加える関数、様々なノードを得る関数、データを得る関数、ノードを取り除く関数です。

ここで、ListCreate 関数に焦点を合わせます。
ListCreate 関数は、パラメタを取らないで、listnode ポインタを返します。
ListCreate 関数が作成する構成には、データを全く書き込みません。
全ての構成はヌルですが、それでも、これは構成です。
ノードを追加すると、pNext メンバーは変更されて新しい項目を指すようにな、nullノードのままになることはありません。その目的がないためです。
ただし、ListCreate によって返される値にはデータが格納されていません。前のノードもありません。

ListCreate 関数は、下のようになります:


私は、関数から値を返すのに Return 指示を使うことを好みます。しかし、FUNCTION = pTemp や、 ListCreate = pTemp を使ってもかまいません。これらを使うと、すぐに、関数を出ることはなくなりますが。

この関数のポイントは見やすいことです。ノードが割り当てられて、返されます。
コメントでは、CAllocate 関数 は、自動的にメモリをゼロに合わせる、と言っています。
Allocate 関数 を使うと、メモリは自動的にゼロに合わせられません。あなたは自分でそれをしなければなりません。

次の関数、ListAdd と ListAddHead は、ノードをリストに追加します。
ListAdd は、リストの最後(尾部)にノードを追加します。一方、ListAddHead は、最初(頭部)にノードを置きます。


あなたは、ListAdd が、まだ説明していない関数 ListGetLast を参照しているのを見つけるでしょう。
ここで、知っておくべきことは、ListGetLast は、リストの最後のノードへのポインタを返す、ということです。
詳しいことは、後で説明します。

ListAdd は、最後のノードを検索して、新しい listnode 構成に、pNext ポインタを設定します。
これはメモリ喪失を引き起こさないでしょう。 最後のノードは、何もそれに続かないので、ヌル pNext 値を持っているからです。
ノードがいったん加えられると、-> 演算子 を使って、それにアクセスできます。
行
pTemp->pNext->pPrev = pTemp
は、連結リストの全体の基礎で、リンクの部分です。
これが示すことは、私たちはノードの参照を持つ、ということです。
そのノードは、次のノードがどこにあるかを知っており、今度は、次の次のノードに、前のノードがあることを伝えています。
これは、最初は、少し冗長に見えるかもしれません。しかし、コンパイラは、ノードがどこか、あなたがそれを設定するまで知りません。
あなたがいったん設定すると、あなたは連結リストを通して、たどることができます。

ListAddHead 関数は、もう少し複雑です。ListCreate から、私たちが、実際に、ノードを、現在の最初のノードと、ヌル・ノードの間に、挿入しているからです。
ListAddHead 関数がする基本的なことは、現在の最初のノードを保持するためのスペースを割り当てます。そして、そこで新しいノードを作成して、それらをお互いにリンクします。
あなたは、これを少し研究すると、もっと明確に分かるでしょう。
最後の If 命令文は、存在しないメモリに、アクセスしようとしないことを、まさしく確実にします。 (NULL->pPrev)
pTemp が、実際、ゼロと等しくないなら、pPrev メンバーは代入されます。
Otherwise, there is no reason to worry about it.
さもなければ、それを心配する理由が全くありません。

次の関数は、ListGetFirst と ListGetLast です。
ListGetLast が、先の関数で参照をつけられたので、私は、次に、これらを実装しました。


最初の関数は、たぶん、最も短く、最も理解しやすい簡単な関数です。それは、ListCreate によって返されたノードに、ポインターを固定している、という事実に依存しますが。
あなたが、ポインターを固定しないなら、ListGetFirst は、なにか無作為のノードを返すでしょう。
ListGetFirst がすることは、最初のノード、またはヌル・ノードの直後に来るノードへの、ポインタを返すことです。

2番目の関数、ListGetLast は、ヌル・ノードを見つけるまで、リストを通して繰返します。
私が、 pTemp = 0 の代わりに、 if pTemp->pNext = 0 をチェックしている理由は、私がゼロを返したくないからです。
私は、最後のノードを返したいと思います。それは、pNext の値をゼロに設定するノードです。
いったんそのノードが見つかると、ListGetLast はそれを返します。

次の 3つの関数は、ただヘルパー関数で、コードの 1行で、容易に達成されるかもしれません。
私が書いていない元の実装には ListGetNext 関数があったため、それは本当に存在します。



最初の関数 ListGetNext は ListGetFirst とまったく同じですが、違いはユーザーの視点にあります。
この実装では、ノード値で ListGetFirst を使用できます。しかし、他の実装では最初のノードを見つけるためにリストの先頭でループする場合があるため、使うことは賢明ではありません。 その場合、無限ループで、動かなくなるでしょう。

ListGetPrev 関数は、もう少し複雑です。ヌル・ノードを返したくないからです。
コードの1番目と3番目の行(コメントでない)は、実際に必要なものです。しかし、2番目の行は、ヌル・メモリにアクセスしていないことを確実にするための、コードです。
3行目は、2つのノードが null の場合、ゼロを返す必要があることを示しています。
つまり、最上位ノード（nullノードではない）にいる場合、何もできる前のノードは有りません。前のノードは存在するので、ゼロを返す必要があります。
最後の行は、デフォルトの場合を扱います。デフォルトでは、実際に、直前のノードがあって、直前のノードを返します。

ListGetData 関数は、ListGetFirst 関数、ListGetNext 関数と同じくらい簡単で、同じくらい簡潔です。
ListGetData 関数は、ただノードのデータへのポインタを返します。

最後の 2つの関数が、リストからノードを取り除きます。


ListRemove 関数には、2つの仕事があります:
あなたが指定したノードを取り除くことと、その両側の 2つのノードを結びつけること、の 2つの仕事です。
ListRemove 関数が、これをするために、直前と直後のポインタを格納することを、見ることができます。
オプションのパラメータ (bDelete) は、データ項目を削除すべきかどうか、を指定します。
整数、またはポインターのない構造体だけを保存している場合、このパラメーターに1を渡すと、アイテムが削除されます。
しかし、その中にポインターを持った構成の場合、最良の考えは、全てのデータは、あなた自身が削除します。そして、ListRemove には、メモリ喪失がないことを保証するために、リスト部分のみを扱わせることです。
listnode ポインタは、あなたが、データを削除するように、ListRemove に言ったかどうかにかかわらず「割り当て解除」されます。

ListRemoveAll は、ノードを削除するために、ListRemove 関数を当てにします。
ListRemoveAll は、単純に、While ループを使ってリストを通して繰返して、全てのノードを削除します。
元のコードは、For ループを使いました。しか、FB は、私が下のようにするのを、好まないようです。

For node = list To 0 Step ListRemove (node)

それで、While ループに変えました。

これで終わりです。ここに、これらの使い方に関する、全体のファイルがあります。最初の部分にサンプルも含めています。
これは、私が書く初めてのチュートリアルです。なので、遠慮なく、改善できる方法についてコメントを残してください。
また、私のコードでバグが見つかったら、私にお知らせください。
また、ご自由に編集して、バグを除いて下さい。ただ、私も、それについて知りたいと思っています。


既に気付いているでしょうが、ListAdd と ListAddHead は、入力したデータに、ポインタを返します。
サンプルコード(上を参照)は、この機能性の使い方を示しています。
ListRemove は、次のノードに、ポインタを返します。
それは、ListRemoveAll が、ノードを取り除く方法です。
ListRemoveAll は、唯一何も返さない手続きです。このため、ListRemoveAll だけ、Function 手続きではなく、Sub 手続きを使っています。
ListRemoveAll を呼んだ後、リスト全体が空になるから、戻り値は、必要ありません。