資料構造:1-1.接続リスト

1.概要

A国は人口5万の小さな国です.A国の大統領選挙は10個の選挙箱で処理できる.
しかし、ある瞬間、移民が急増し、人口は10万人に増えた.
これならまだ10個の選挙箱が必要だが、A国は選挙箱を輸入しなければならない.
「選挙委員長はそう思っている」「既存の選挙箱を改造し、選挙箱を美術バケツのように柔軟に増やせばいいのではないか」.

そうですね.既存の方式は「配列」であり、選挙箱を改造する方式は「接続リスト」である.
配列は、プログラマが宣言するスペースのみを占有します.
より多くのデータストレージが必要な場合、接続リストは、スペースを宣言することなく、柔軟にスペースを追加できます.
1つの選挙箱に5000人の投票紙しか入っていない場合、新しい方法で5000人以上の投票紙を収容することができます.

このように、入力されたデータ量が不確定である場合に、データを柔軟に記憶するために作成されるデータ構造が接続リストである.
接続リストは、次のノードのアドレスを現在のノードの次の一意の領域に格納するため、2つのデータの物理的な位置が異なります.
互いにつながっていることがわかります.

2.接続リストVSシナリオ

案


前述したように、レイアウトは、プログラマが早期に宣言したスペースを占有することができる.
利点は、論理記憶順序が物理記憶順序と一致することである.したがって、インデックスを使用できます.
特定の要素に直接アクセスできます.
つまり、7番目の要素を探すためには、最初から一つ一つ探索する必要はありません.
したがって探索に要する時間はO(1)である.ただし挿入と削除の際、O(N)の時間
必要です.これは、特定の場所で要素を挿入または削除するには、セルを後ろまたは前に移動する必要があるためです.
移動します.そのため、出費が大きいと言えます.
また、不要なスペースが発生し、メモリが浪費される可能性があります.

int[] arr = new int[10];
arr[1] = 10;
arr[2] = 30;
//남은 공간 낭비됨.

開発者がアレイのサイズを10と宣言し、そのうち2つのデータしかない場合は?
これは資源の浪費だ.

接続リスト

接続リストの物理的な格納順序が論理的な格納順序と一致しません.

アレイ宣言後、メモリ内の特定の領域が連続的に使用されます.
接続リストには、スペースを使用してデータと次のデータのアドレスが格納されます.
したがって、1つのノード
接続できる構造は、次のノードのアドレス情報のみです.複雑に見えますが、ストレージスペース
柔軟に増減できる.しかし、非順序的に近づくことはできない.
インデックスがないため、特定の要素を検索するときは、最初のノードからアクセスする必要があります.
したがって探索時間はO(N)を消費する.
ただし、一番前または一番後ろの要素を挿入または削除する場合はO(1)となります.探求する必要がないからです.
ただし,中間のノードを挿入・削除すると,O(N)の時間が消費される可能性がある.
探求が必要だからです.
ただし、挿入と削除では、配列よりも大きな利点があり、ストレージスペースを再割り当てする必要がないということです.
配列は、挿入および削除時に1つのセルを前後に移動する必要があります.
接続リストには必要ありません.
利点は多いが、接続リストにも致命的な欠点がある.
「断片化」の話題です.各ノードのメモリ領域は非順序で割り当てられます.新しいプロセスがメモリにアクセスしようとすると、十分なスペースがあっても、データの割り当てが一致しないため、押し出し可能なスペースがありません.

3.実行時間の比較

Array

ナビゲーションO(1)

挿入O(n)

削除

O(n)

LinkedList

ナビゲーションO(n)

挿入[一番前または一番後ろに挿入]O(1)、[閲覧による中間挿入]O(N)

削除

[前削除または後削除]O(1)、[参照による中間ノードの削除]O(N)

.