Javaのデータ構造におけるリンクリストの概念と構造は何ですか?

1. リンク リストの概念

概念: リンク リストは、物理ストレージ構造における非連続かつ非順次のストレージ構造であり、データ要素の論理的順序が実現されます。 ’s

1. リンク リストは一連のノードで構成されます (リンク リストの各要素はノードと呼ばれます)。

2. ノードは実行時に動的に生成 (malloc) できます。

3. 各ノードには 2 つの部分が含まれており、1 つはデータ要素を格納するデータ フィールド、もう 1 つは次のノードのアドレスを格納するポインタ フィールドです (詳細については、「1.2 ノード」セクションを参照)。

4. 線形リストのシーケンス構造に比べて、連結リスト演算は複雑です。ただし、リンク リストは順序どおりに格納する必要がないため、挿入時に O(1) の複雑さを実現でき、シーケンシャル リストよりもはるかに高速ですが、ノードの検索や特定の番号を持つノードへのアクセスには、 O(n) 時間、シーケンス リストは O(1)

2 のみ必要です。ノード

リンク リストはノードで構成され、各ノードは構造体の形式になっています。構造体の最初の変数は必要に応じて指定されます。最後の変数はこの構造体タイプのポインタで、次のノードの最初のアドレスを格納するために使用されます‘

リンク リスト ノードは 2 つのフィールドに分割されます
データフィールド : さまざまな実際のデータを格納します
ポインタフィールド : 次のノードのアドレスを格納します

(図はセンチネルヘッダノードを含むリンクリストを示しています) )

3. リンク リストの使用シナリオ

線形テーブルは、データ要素を頻繁に挿入または削除する必要がある場合に、リンク ストレージ構造を使用するのに適しています。

リンク リストの場合、データの挿入または削除には、ノードの作成、データの入力、ノードをリンク リスト内の特定の位置に接続するポインタの変更のみが必要であり、シーケンシャル リストの場合はデータの挿入が必要なためです。他のデータに移動する必要がある場合がありますが、これは非常に複雑です。

4. リンクリストの分類とよく使われる構造

リンクリストは全部で8種類ありますが、実際に最も一般的に使用されるのは、ヘッドレス一方向非巡回リンク リストとヘッド付き双方向巡回リンク リストです。

1. ヘッドレス一方向非循環リンク リスト: 一般に「単一リンク リスト」として知られています。構造は単純なので、通常はデータのみを保存するためには使用されません。実際、これは他のデータ構造 (ハッシュ バケット、グラフ隣接リスト、スタック チェーン構造など) の下部構造のようなものです。

2. 見出し付き双方向循環リンク リスト: 一般的に最も複雑な構造です。 used データを個別に保存します。実際に使用されるリンクリストの多くは、見出し付き双方向循環リンクリストである。構造は最も複雑ですが、この構造には多くの利点があります。

5. シーケンシャル リストとの比較

リンク リスト: リンク リストは、ノードを介して離散データをテーブルにリンクし、操作を通じてノードの挿入と削除を行います。データ。

シーケンス テーブル: シーケンス テーブルは、連続メモリを開くことによってデータを格納します (配列または malloc を直接使用してから、realloc 拡張を使用します)。

ただし、realloc 拡張は、その場での拡張とオフサイト拡張に分かれているため、前者は低コストですが、後者はデータをコピーするだけでなく、古い領域を解放する必要があります。拡大する。また、拡張する場合、通常は元の容量の 2 倍まで拡張されますが、拡張しすぎると容量を無駄に使いやすくなります。リンク リスト、メンバーとノード データ型には、標準の C 型またはユーザー定義の構造体型を使用できます。

#比較オブジェクト #シーケンス リスト ストレージスペース連続データの移動が必要になる場合があります。複雑さ O (n)ダイナミック シーケンス テーブル: 十分なスペースがないため、拡張する必要があります頻繁なアクセスが必要です

#リンク リスト
不連続		データの挿入または削除
ポインタを変更するだけです		push
「容量」の概念はなく、プッシュ時に新しいノードを直接割り当てます		アプリケーション
頻繁なアクセスが必要ですデータの挿入と削除

以上がJavaのデータ構造におけるリンクリストの概念と構造は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。