👋
データ構造① 配列 (Arrays)
配列とは
配列とは、複数の同じ型のデータを連続的に並べたデータ構造のこと。
添字を用いることで、各データ(要素)にアクセスすることができる。
また、各データはメモリが隣接した状態で確保される。
// int型のデータ配列とstring型のデータの配列
const numbers = [0, 1, 2];
const fruits = ['apple', 'banana', 'grape'];
// 以下のように、添字で各要素にアクセスが可能
console.log(numbers[0]); // 0
console.log(numbers[1]); // 1
console.log(fruits[0]); // 'apple'
console.log(fruits[1]); // 'banana'
実装
以下のようにして、実装が可能。(ただし、動的配列)
class MyArray {
// 配列の初期化
constructor() {
this.length = 0;
this.data = {};
}
// ある添字の要素の取得
get(index) {
return this.data[index];
}
// 配列の末尾にデータを追加
push(item) {
this.data[this.length] = item;
this.length++;
}
// 配列の末尾のデータを取得、削除
pop() {
const item = this.data[this.length-1];
delete this.data[this.length-1];
this.length--;
return item;
}
// ある添字の要素を削除
delete(index) {
for (let i = index; i < this.length-1; i++) {
this.data[i] = this.data[i+1];
}
delete this.data[this.length-1];
this.length--;
}
}
それぞれの操作の計算量
それぞれの操作にかかる計算量は以下。
ただし、lookupは特定のデータを検索する操作。
lookupやpushは効率的に行うことが可能だが、insertやdeleteはそれぞれの要素をシフトさせて配列を整える必要があるため、非効率。
| 操作 | 計算量 |
|---|---|
| lookup | O(1) |
| push* | O(1) |
| insert | O(n) |
| delete | O(n) |
*動的配列の場合、メモリを再確保する場合は元データをコピーする必要があるため、O(n)の計算量がかかる。
静的配列と動的配列について
静的配列は、宣言時に要素数を指定しするため、サイズが固定された配列。
動的配列は、宣言時に要素数を指定しないため、サイズに柔軟性がある配列。(javascriptやpythonにおける配列)
動的配列では要素の追加が可能だが、最初に確保したメモリの容量を超える要素数を追加する場合は、通常その容量の2倍の容量のメモリが新たな領域に再確保され、元のデータがその領域にコピーされる。これが起こった場合、計算に少し時間がかかってしまう。
参考webサイト
このUdemyの講座を参考にしています。
Discussion