Pythonで動的配列を実装する方法を徹底解説

動的配列（Dynamic Array）とは

Pythonにおいて、リスト（list）・セット（set）・辞書（dict）はミュータブル（変更可能）なオブジェクトです。一方、数値・文字列・タプルはイミュータブル（変更不可能）なオブジェクトです。

ミュータブルなオブジェクトとは、リストやセット、辞書に対して要素の追加や削除が自由に行えるという意味です。しかし、タプルや文字列のようなイミュータブルなオブジェクトでは、これはできません。

Pythonではリストがまさに動的配列として機能します。実際に動的なリストを作成してみましょう。

>>> # 空のリスト list1 を作成
>>> list1 = []
>>> type(list1)
<class 'list'>

作成した空のリスト list1 に要素を追加してみます。

>>> # 要素を追加
>>> list1 = [2, 4, 6]
>>> list1
[2, 4, 6]
>>> # appendメソッドを使った別の追加方法
>>> list1.append('Tutorialspoint')
>>> list1
[2, 4, 6, 'Tutorialspoint']

次に、リストから要素を削除してみましょう。

>>> # リストから要素を削除
>>> list1.pop()
'Tutorialspoint'
>>> list1
[2, 4, 6]

この結果から分かるように、リストは実質的に配列の拡張版であり、サイズを自由に増減させることができます。上記の例では、サイズ「0」のリストから始めて、「4」つの要素を追加しました。

動的配列実装の基本原理

ここで、リスト list1 の容量がいっぱいになった状態で要素を追加（append）するケースを考えてみます。このサイズ制限の問題を克服するために、以下の手順を実行します。これこそが動的配列実装の基礎です。

• より大きな容量を持つ新しい配列 list2 を確保する
• i = 0, 1, ..., n-1 について list2[i] = list1[i] を設定する（nは現在の要素数）
• list1 = list2 とし、list2への参照をlist1に引き継ぐ
• その後、新しい要素をリスト（list1）に挿入（append）する

それでは、Pythonプログラミングでこの動的配列の概念をどのように実装するか、シンプルなコードを作成してみましょう。Pythonの組み込みライブラリである ctypes を使用し、生の配列として扱うことで、独自の動的配列クラスを作成します。

dynamicArray.py の実装コード

import ctypes

class DynamicArray(object):
    # 初期化
    def __init__(self):
        # 3つの属性を持つ
        self.n = 0                # デフォルトの要素数
        self.capacity = 1         # デフォルトの容量
        self.A = self.make_array(self.capacity)  # make_arrayは後で定義

    # 長さを返すメソッド
    def __len__(self):
        # 配列内の要素数を返す
        return self.n

    def __getitem__(self, k):
        # インデックスkの要素を返す
        if not 0 <= k < self.n:
            return IndexError('k is out of bounds')
        return self.A[k]

    def append(self, element):
        # 容量のチェック
        if self.n == self.capacity:
            # 新しい配列の容量を2倍にする
            self._resize(2 * self.capacity)  # _resizeは後で定義されるメソッド
        # 配列Aのn番目のインデックスに要素を設定
        self.A[self.n] = element
        self.n += 1

    def _resize(self, new_cap):  # new_capは新しい容量
        # 配列Bを宣言
        B = self.make_array(new_cap)
        for k in range(self.n):
            B[k] = self.A[k]  # 配列Aの要素をBに参照コピー
        self.A = B            # Aは現在Bを参照
        self.capacity = new_cap  # 容量をリセット

    # ctypesを使ってmake_arrayメソッドを作成
    def make_array(self, new_cap):
        return (new_cap * ctypes.py_object)()

arr = DynamicArray()

これで独自の動的配列クラスが完成しました。早速使ってみましょう。

>>> len(arr)
0
>>> arr.append(1)
>>> # 1つ目の要素を追加
>>> len(arr)
1
>>> arr.append('Tutorialspoint')
>>> # 2つ目の要素を追加
>>> len(arr)
2
>>> arr[1]
'Tutorialspoint'

以上で完了です。独自の動的配列を作成することができました。このように、Pythonのリストは内部的にサイズを自動的に拡張できる動的配列として動作しています。