1.配列

に関連付けられたデータからなる連続構造の資料構造.

javascript配列の長さは、いつでも増加または減少することができ、連続的に格納することができ、その密集性は保証されない.

要素には

インデックスでアクセスでき、整数でなければなりません.

角カッコ構文または属性アクセス者を使用する場合、配列内の要素ではなくArrayオブジェクトに関連する変数が参照されます.

const arr = [1, 2, 3, 4];

console.log(arr[1]); // 2
console.log(arr["length"]); // 4
console.log(arr["1"]); // undefined

に必要な要素のインデックスが分かれば、O(1)で要素を検索できます.

一般的な意味での配列は、メモリ領域を連続的に使用する.

1-1)JavaScript配列内のメモリ

※一般的な配列

一般に、配列とは、同じ大きさのメモリ空間がシームレスに連続して配列された資料構造を指す.アレイ内の要素は1つのタイプに統一され、互いに連続的に隣接しています. 密集アレイと呼ばれます.

※JavaScriptの並び

JavaScriptの配列は、配列内の要素に同じメモリ領域を割り当てる必要はなく、連続したメモリ領域も必要ありません.配列内の要素が不連続な配列. 疎アレイと呼ばれます.

JavaScriptの配列は、通常の配列動作を模したハッシュテーブルによって実現されるオブジェクトである.

インデックスを使用してアレイ要素にアクセスすると、通常のアレイよりもパフォーマンスが低下します.

は、特定の要素を参照または挿入または削除する際に、従来のアレイよりも高速なパフォーマンスを期待することができる.

1-2)アレイ要素の追加、除去

配列内の要素を追加、削除するには、次の手順に従います.

追加

1)追加するindexから、indexの後ろにあるすべての要素を1つ後ろに押します.
2)インデックスに空の場所があるため、その場所に要素を追加します.

削除

1)削除するインデックス要素を削除します.
2)インデックスが空です.(JavaScriptでnullまたはundefined)
3)indexから、後ろのすべての要素を1つ前に引く.

の手順に従って、配列要素の追加、削除に要する総時間はO(n)である.

1～3）配列要素の検索

配列要素検索は、線形検索とバイナリ検索に分けられます.

せんけいたんさく

の最初の要素から、順番に検索する要素と同じ要素があるかどうかを確認します.

すべての要素

をチェックします.したがって、ソートされていない配列でも使用できます.

O(n)時間複雑度を持つ.

バイナリサーチ

分割征服アルゴリズムの規則に従い,中間の要素から比較を開始する.

配列を分割し、検索する要素と同じ要素があるかどうかを確認します.

は配列されている必要があります.

O(lognlognlogn)時間複雑度を有する.

2.接続リスト

は、各要素をポインタで接続して管理するリニアデータ構造である.

各要素はノードと呼ばれ、データ|ポインタ領域からなる.

ポインタが一方向にのみ存在する場合はシングルリンクリスト(Sivey Linked List)と呼ばれ、ポインタが両方向に存在する場合はダブルリンクリスト(Doubly Linked List)と呼ばれる.

メモリが許可されている限り、要素を無限に追加できます.

ナビゲーションはO(n)時間複雑度を有する.

元素を添加し、O(1)時間の複雑さを解消した.

接続リストはポインタで接続されているため、メモリはハッシュされています.

2-1)接続リスト要素の追加、削除

追加

1)新しいノードポインタを追加するノードを指すノード.
2)追加するノードへのポインタを、新しいノードへのポインタに変更します.

削除

1)削除するノードの前のノードから削除するノードへのポインタを変更します.
2)削除するノードのポインタを削除します.

の上の手順に従って、接続リストの要素を追加、削除するのに要する総時間はO(1)である.

2-2)接続リスト要素の検索

の最初のノードのデータ領域から、ポインタ領域によって順次検索が行われる.

要素のインデックスを知っているか知らないかにかかわらず,要素を探索するのに要する時間はO(n)である.

3.整理

これまでjavascriptの配列も従来の配列(密集配列)の特徴を有すると誤って考えられてきた.
その結果,JavaScriptの配列は一般的な意味での配列ではなく,ハッシュテーブルによって実現される特殊なオブジェクトであり,メモリが不連続である可能性があることが分かった.
次回はスケジュールを整理した方が良いと思います

リファレンス

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array
https://poiemaweb.com/js-array-is-not-arrray
https://levelup.gitconnected.com/array-vs-linked-list-data-structure-c5c0ff405f16