リンクされたリスト は線形データ構造であり、要素は連続した場所に格納されるのではなく、ポインターを使用してリンクされます。リンク リストは一連の接続されたノードを形成し、各ノードにはデータと次のノードのアドレスが格納されます。
ノード構造: リンク リスト内のノードは通常、次の 2 つのコンポーネントで構成されます。
データ： これは、ノードに関連付けられた実際の値またはデータを保持します。
次のポインタ: シーケンス内の次のノードのメモリ アドレス (参照) を格納します。
頭と尾: リンクされたリストには、リストの最初のノードを指すヘッド ノードを介してアクセスされます。リストの最後のノードは NULL または nullptr を指し、リストの終わりを示します。このノードは末尾ノードとして知られています。
なぜリンクリストデータ構造が必要なのでしょうか?
以下にリンク リストの利点をいくつか示します。なぜリンク リストを知る必要があるのかを理解するのに役立ちます。
- 動的データ構造: メモリのサイズは、操作の挿入または削除に基づいて、実行時に割り当てまたは割り当て解除できます。
- 挿入/削除の容易さ: 要素の挿入と削除は、挿入と削除後に要素をシフトする必要がなく、アドレスのみを更新する必要があるため、配列よりも簡単です。
- 効率的なメモリ使用: ご存知のとおり、リンク リストは動的データ構造であり、要件に応じてサイズが増減するため、メモリの無駄が回避されます。
- 実装： スタック、キュー、グラフ、ハッシュ マップなどのリンク リストを使用して、さまざまな高度なデータ構造を実装できます。
例：
システムでは、ID の並べ替えられたリストを配列 id[] = [1000, 1010, 1050, 2000, 2040] で維持するとします。
新しい ID 1005 を挿入する場合、並べ替え順序を維持するには、1000 以降のすべての要素 (1000 を除く) を移動する必要があります。
特別なテクニックを使用しない限り、配列の削除にもコストがかかります。たとえば、id[] の 1010 を削除するには、コードの効率に影響を与える非常に多くの作業が行われるため、1010 以降のすべてを移動する必要があります。
リンクリストの種類 :
リンク リストには主に 3 つのタイプがあります。
- 単一リンクリスト
- 二重リンクリスト
- 循環リンクリスト
1. 単一リンクリスト :
単一リンクリストでは、各ノードにシーケンス内の次のノードへの参照が含まれます。単一リンクされたリストの走査は、順方向に行われます。
単一リンクリスト
2. 二重リンクリスト :
二重リンクリストでは、各ノードに次のノードと前のノードの両方への参照が含まれます。これにより、前方と後方の両方の方向へのトラバースが可能になりますが、後方参照用に追加のメモリが必要になります。
二重リンクリスト
3. 循環リンクリスト :
循環リンク リストでは、最後のノードが先頭ノードを指し、循環構造が作成されます。単一リンクまたは二重リンクのいずれかにすることができます。
文字列Javaで分割
循環リンクリスト
リンクされたリストの操作
- 挿入 : 新しいノードをリンク リストに追加するには、既存のノードのポインタを調整して適切なシーケンスを維持する必要があります。挿入はリスト内の先頭、末尾、または任意の位置に実行できます。
- 削除 : リンク リストからノードを削除するには、削除されたノードによって残されたギャップを埋めるために隣接するノードのポインタを調整する必要があります。削除はリスト内の先頭、末尾、または任意の位置で実行できます。
- 検索中 : リンク リスト内の特定の値を検索するには、値が見つかるかリストの末尾に到達するまで、ヘッド ノードからリストを走査する必要があります。
リンクリストの複雑さの分析 :
- 時間計算量: O(n)
- 補助スペース: O(n)
リンクリストの利点
- ダイナミックサイズ: メモリ割り当ては実行時に行われるため、リンク リストは動的に拡大または縮小できます。
- 挿入と削除: リンクされたリストへの要素の追加または削除は、特に大きなリストの場合に効率的です。
- 柔軟性: リンクされたリストは、連続したメモリ ブロックを必要とせずに、簡単に再編成および変更できます。
リンクされたリストの欠点
- ランダムアクセス： 配列とは異なり、リンク リストではインデックスによって要素に直接アクセスできません。特定のノードに到達するにはトラバーサルが必要です。
- 追加メモリ: リンク リストは、配列と比較して、ポインターを格納するために追加のメモリを必要とします。
結論：
リンク リストは、動的なメモリ割り当てと効率的な挿入および削除操作を提供する多用途のデータ構造です。リンク リストの基本を理解することは、プログラマーやコンピューター サイエンスの愛好家にとって不可欠です。この知識があれば、リンク リストを実装してさまざまな問題を解決し、データ構造とアルゴリズムについての理解を深めることができます。