👋

データ構造①　配列 (Arrays)

2024/03/17に公開

array

配列とは

配列とは、複数の同じ型のデータを連続的に並べたデータ構造のこと。
添字を用いることで、各データ(要素)にアクセスすることができる。
また、各データはメモリが隣接した状態で確保される。

// 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の講座を参考にしています。

配列とは

実装

それぞれの操作の計算量

静的配列と動的配列について

参考webサイト

Discussion