[TIL]Data Structure 02)Linked list

🤔 linklistを知る前に知っておくべきことは?🙋

データ構造の中で最も重要な部品とターゲットメモリ!

> data structure의 미션은, '메모리의 효율적 사용'에 있기 때문!

コンピュータの中で最も重要な3つの方面

CPU:思考と計算を行う.
データの演算速度が最も速い.

Memory:
価格↑、容量↓、電源オフ後データ消失.
メモリ>ストレージ(Memory>Storage)(相対速度)

メモリ(HDD/SDD/フロッピーディスク...):ファイルなどのデータを格納する場所.
価格↓、容量↑は、電源が切れてもデータが保存されます.

❗メモリからcpuではなくcpuにデータを直接インポートした場合?
:ストレージ内のデータのインポート速度が遅いため、メモリからデータをインポートする必要があります.

                  그림 01. array list 와 linked list의 데이터 구조 비교

array vs link listの構造比較

array:同じ要素がメモリに連続的に付着します.

チェーンテーブル:各要素はランダムにメモリに散らばっていますが、つながっています!

メモリと建物のオフィスを比較します.
どのオフィスにもオフィスの湖があるはずですが、メモリで計算すると住所です.
各メモリアドレスが指すオフィス、すなわち空間にデータが格納されています.

array listの利点:スペースの数が限られているため、特定のオフィスにアクセスするときに速度が速くなります.
効果的に探索できる.

array listの欠点:すべてのオフィスの人員がいっぱいになると、スペースを増やすことができません.
新しい建物に引っ越したり、もっと大きな空間に引っ越したりするしかありません.
メモリの特徴は、各アドレスにアクセスするのに要する時間が同じであることです.

linklistの利点:1棟のビルに会社が借りたオフィスが分かれていて、
従業員が増えたとしても、空いているオフィスに勝手に入ればいいので、あまり心配することはありません.

linked listの欠点:オフィスにアクセスする必要がある場合は、まず最初の矢印が示すオフィスにアクセスする必要があります.
そして次のオフィスに聞いて、探しているオフィスを探して、効率↓.

                  그림 02. linked list의 데이터 연결 구조

この形式のメモリをランダムアクセスメモリ(RAM)と呼ぶ.
これらのメモリの特性を理解すれば、作成するアプリケーションは非常に速くなります.
これらのメモリ特性を十分に活用したデータ構造をリンクリストと呼ぶ.

Linked list

:動的なデータ構造.複数のノード接続からなるデータ構造.

は、新しいデータを追加し、データをナビゲートし、削除する場所を必要とします.

データ処理の時間的複雑さ

linked list:任意の場所でデータを追加または削除する場合:O(1)(一定時間)の時間複雑度.

接続リストの各ノードにはインデックスがありません.
したがって、接続リストから特定のデータを検索する場合は、
「最初から接続リスト全体を順番に並べなければなりません.」
これはO(n)(線形時間)の複雑さを必要とする.

자료구조       가져오기  추가하기  삭제하기
linked list    O(n)      O(1)    O(1)

vs
Array:O(n)(線形時間)の複雑さを持つ追加と削除.

node

:資料構造を構成する要素.

			      그림 03. 노드의 구성
                  

			      그림 04. 연결리스트의 구조

Javaなどのオブジェクト向け言語を使用する場合、
オブジェクトにデータフィールドとリンクフィールドを作成します.

データフィールド(DATAフィールド)
:通常、valueという変数が使用されます.ノードの値を格納します.

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

HEAD
:listを建物として表すと、「出入り口」に相当するのがheadです.つまり.
linklistを使用するには、headが指す最初のノードを見つけなければなりません.👀

はい。

1>2>3>4>5という名前の接続リストがある場合、1,2,3,4,5はvalue、>next、すなわちアドレスです.
[1,2,3,4,5]配列はデータの位置を表し、1,2,3,4,5はデータを表し、array[0]、array[1]はデータの位置を表す.
また,配列はarrayである.push()を使用してデータを追加できます.
array.splice()を使用してデータを削除できます.
ただし,接続リストを実装するには配列を簡単に使用すると学習できない.
オブジェクトを利用して実現したほうがいい.
すなわち,接続リストを用いて配列を実現すると考えられる.
参照元
1. リンクリストコンセプト1-概要-データ構造(生活符号化ビデオ)
2. リンクリスト(ブログ)