Linked list

リンクリストとは?

ArrayListとは異なり、EllistとEllistの間の接続を利用してリストを実現することを意味する.接続リストでは、セグメントをノードまたは頂点と呼びます.
接続リストは、データと次のノードアドレスを含むノードを1行に接続するリニアデータ方式のデータ構造である.Linked listの最大折りたたみは、データの挿入と削除が容易であることです.逆に、チェーンテーブルで特定の位置のデータを検索するには、最初のノードからナビゲートする必要があります.その時間長はO(n)であるため,配列やツリー構造よりもナビゲーションが遅い.

ノードは少なくとも2つの情報を知らなければならない。

ノード値

次ノード

ノードの基本構造を表示すると、よりよく理解できます.

ノードの基本構造:

ヘッド

ヘッドは建物の出入り口のようです.linklistを使用するには、headが指す最初のノードを見つける必要があります.どうしたんですか.linklistは特定の場所のデータが見つかりません.最初のノードから探索するからです.つまり、headを見つけることはとても自然で重要です!

ノード(データフィールド、リンクフィールド)-

に接続されています.
データフィールドにはvalueという変数が使用され、リンクフィールドにはnext変数が使用されます.valueはノード値を格納し、nextは次のノードのポインタまたは参照値を格納してノードをノードに関連付けます.

データの追加

先頭に追加

新規ノード

を作成

新しいノードの次のノード(次のノード)は、第1のノード

を指す.
headの値を変更して、新しく作成したノードを最初のノード

にします.

中間に追加

これはarrayリストと最も異なる部分です.配列の中間に追加すると、削除時にそのセグメントの後ろのすべてのセグメントの位置を移動する必要がありますが、linklistでは、追加/削除するセグメントの今回、以降のノードの参照値(next)を変更するだけなので、速度が速いです.
2番目の場所に追加するとします.
1.headを参照して最初のノードを検索する必要があります
2.最初のノードの次のノード(2番目)を変数に保存
3.2番目のノードの次の参照値も変数に格納
4.新規ノードの作成
5.最初のノードの次の参照値に新しいノードを割り当てる
6.新しいノードに次の参照値として2番目のノードを割り当てる
自然に:

첫번째 노드 -> 새로운 노드 -> 두번째 노드

データの削除

データを追加する方法と似ています.
3番目の場所を削除するとします.
1.headを参照して最初のノードを検索
2.2番目のノードに移動
3.3番目のノードを見つける
4.2番目のノードの次の参照値(next)を4番目のノード(.next.next)に変更
5.3番目のノードを削除する(delete)

索引によるデータの問合せ

linked listの場合、headが示すノードから順にノードを検索する必要があります.ただしarrayリストは、対応する別名に直接アクセスできます.

リンクリストのタイプ

Singly linked list

Doubly linked list

Circular linked list

リンクリストの章と欠点

長所

データ挿入、

削除しやすい

挿入と削除操作O(1)で

を完了する.

チェーンテーブル長

を動的に調整可能

🔥🔥🔥 メモリ管理が簡単

短所

特定のノードに直接アクセスできない(インデックスによるアクセス時間が長い)

.

O(N)(head to tail)

にナビゲート

は、次のノードの位置

を格納するために追加の空間を必要とする.

(キャッシュ位置を用いる)近接データ

をキャッシュに予め格納することが困難である.

チェーンテーブル

を逆閲覧することが困難である.
Reference:
https://opentutorials.org/module/1335/8821
https://underflow101.tistory.com/3
https://daimhada.tistory.com/72