1. 概要

このチュートリアルでは、動的データ構造：リンクリストについて説明します。

そのさまざまなバリエーションについて説明し、いくつかの実用的なアプリケーションで二重にリンクされたリストを詳細に示します。

2. リンクリストの紹介

プログラミングは、特定のタスクを実行するために一連の命令を定義するプロセスです。 プログラミングの重要なコンポーネントの1つは、さまざまな形式で情報をメモリに格納できるデータ構造です。

配列は有名なデータ構造の1つです。 これにより、一連のデータを保存し、それらを操作および操作できます。 ただし、配列のサイズは静的であり、宣言時に定義されます。これは、サイズの配列が必要な場合でもそれ以上のデータを格納できないことを意味します。

さらに、それを正しく宣言するために、プログラムはメモリ内で使用可能なブロックを並べて見つける必要があります。 リンクリストのデータ構造は、配列のすべての問題を克服できます。

リンクリストは、メモリ内のデータを整理するのに役立つ動的な構造です。ポインターを使用してデータをリンクすることにより、データのセットを組み立てることで構成されます。

各要素は、変数と、リンクリスト内の次の要素へのポインタで構成されています。

したがって、プログラムでリンクリスト構造を構築するには、リストの1つの要素を含む新しい構造を宣言します。これは、変数であり、この構造自体へのポインターです。

define structure Element {
    variable,
    Element *next,
}

リンクリストの要素を制御するための別の構造を宣言します。 リンクリストの最初のポインタです。

define structure L1 {
    Element *first,
}

次に、リンクリストの一般的な構造を見てみましょう。

ご覧のとおり、リストの最後の要素はを指しています。 その結果、リンクリストに新しい要素を簡単に追加できます。

このメモリ構成により、必要に応じて中央に新しい要素を追加できます。 また、リンクリストの任意の位置から要素を削除できます。

3. リンクリストの基本操作

リンクリストには、トラバーサル、挿入、削除、更新の4つの主要な操作があります。リンクリストは、検索、並べ替え、マージなどの操作もサポートします。

最初の操作はトラバーサルです。 すべてのノードまたは要素を次々にトラバースするために使用します。 ポインタをアイテムから次のアイテムに移動することでそれを行うことができます。

リストに要素を挿入する場合は、挿入操作を使用する必要があります。新しいアイテムは必ずしもリストの最後に挿入されるとは限りません。 任意の位置にアイテムを追加できます。

次の重要な操作は削除です。 ここでは、任意の位置から要素を削除できます。 アイテムを削除する必要があるリンクリストでの削除の例を見てみましょう。

リンクリストは動的なデータ構造であるため、大量のデータを格納できます。 必要なアイテムまたは要素を検索する場合は、リンクリストで使用可能な検索操作を使用できます。この操作は、ブール値を出力として返します。

リンクリストは、並べ替え機能を介して、ユーザーが必要とする特定の順序で要素を配置することも容易にします。

マージ操作を使用して、2つのリンクリストをマージできます。

4. バリエーション

リンクリストには、主に3つのタイプがあります。単一、循環、二重リンクリストです。

単一リンクリストは、これまでに説明したものと同じです。 リンクリストの他のバリエーションよりも必要なメモリが少なくて済みます。もう1つの利点は、アイテムの挿入、削除、およびアクセスが容易になることです。

単一リンクリストには順方向トラバーサルしかないため、前のノードにアクセスできません。 リストを解析する必要があるため、特定の要素にアクセスするのにより多くの時間がかかります。

最後の要素がnullではなく最初の要素を指す場合、循環リンクリストを形成します。リストの最後の要素が最初の要素を指す場合、リストを循環させ、閉じたリングになります。 したがって、任意の要素を開始点にすることができます。これは、キューの実装に非常に役立ちます。

循環リンクリストの主な欠点の1つは、実装がより複雑で、無限ループを簡単に作成できることです。

この記事の後半で、二重リンクリストについて説明します。

5. リンクリストの適用

スタック、キューなどの他のデータ構造を実装する際にリンクリストを使用できます。 コンピュータでは、グラフを表すために隣接リストをよく使用します。 隣接リストは、グラフの頂点を格納するためにリンクリストのデータ構造を利用します。

数論、数値解析などの分野で大規模なアプリケーションを計算するために、スパース行列を使用します。 スパース行列を表すために、リンクリストを利用します。

ハッシュマップでは、データの衝突を防ぐために、リンクリストを利用できます。リンクリストのその他の重要な用途には、メモリの動的な割り当て、ディレクトリからの名前の管理、多項式の操作などがあります。

実際のアプリケーションについて話しましょう。 音楽プレーヤーはリンクリストのプロパティを表示します。音楽プレーヤーでは、各曲が次の曲にリンクされます。

同様に、画像ビューアはすべての画像を相互にリンクします。 次と前のボタンを使用してすべての画像を表示できます。

6. 二重リンクリスト

二重リンクリスト（DLL）は、各要素が次の項目だけでなく前例も指すリンクリストのバリエーションです。

DLLの要素の追加または削除は、トラバーサル中に前の要素を追跡する必要がないため、単一リンクリストよりも効率的です。

DLLは順方向と逆方向の両方で解析できるため、特定のアプリケーションでDLLを採用しています。 ユーザーが未知の回数で複数の操作を元に戻すプログラムを作成する例を取り上げることができます。 システムは操作をDLLに保存するため、簡単に前後に移動できます。

プログラムでDLL構造を構築するには、変数と2つのポインターで構成されるリストの1つの要素を表す新しい構造を宣言する必要があります。 1つのポインターは次のアイテム用で、もう1つは前の要素用です。

define structure Element {
    variable,
    Element *next,
    Element *previous,
}

要素を制御するために名前が付けられた別の構造を宣言します。 二重にリンクされたリストの最初のポインタです。

define structure L2 {
    Element *first,
}

7. 二重リンクリストの適用

Webブラウザーは、二重にリンクされたリストのデータ構造を利用します。具体的には、DLLは順方向および逆方向の機能を容易にします。

コンピューターでは、DLLは元に戻す機能とやり直し機能を実装します。オペレーティングシステムでキャッシュ置換ポリシーとプロセススケジューリングを実行するためにも使用されます。

二重リンクリストは、バイナリツリー、スタック、ハッシュテーブルなどの一般的なデータ構造を実装できます。

8. 結論

このチュートリアルでは、リンクリストのデータ構造とそのバリエーションについて説明しました。 それぞれのバリエーションの長所と短所を紹介しました。

最後に、いくつかの実用的なアプリケーションを使用して、二重リンクリストについて詳しく説明しました。