[データ構造] Pythonでの配列

Python には配列はビルトインとしては存在しません。

配列ではなく、同一の型でなければならないという配列の制約を取り払った「リスト」と言われるデータ構造が使われます。

少しややこしいですが、Python のリストは一般的な “Linked List” ではなく、型の制約のない「配列」です。

CPythonでは、リストの最後への要素の追加は\( O (1) \)、リストの途中への要素の挿入は\( O (N) \)、リストの最後の値の削除は\( O (1) \) 、 リストの途中の要素の削除は\( O (N) \)と、配列と同じように実装されています。

Python list implementation

ちなみに、型の制約のある配列を使いたいときは、array というモジュールを使うことができます。

array — 効率のよい数値アレイ

または、numpy を用いることもできます。

Array creation

リスト

リスト型 (list)

Python のリストを使ってみます。

以下のようなリストを作成します。

>>> nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> nums
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

それぞれの要素にはインデックス（添え字）を用いて\( O (1) \) でランダムアクセスできます。

>>> nums[0]
0
>>> nums[1]
1
>>> nums[5]
5
>>> nums[2] = 20
>>> nums
[0, 1, 20, 3, 4, 5, 6, 7, 8, 9]

Python の配列（リスト）は、一般的な配列と異なり型の制約がないので、同一配列内に異なる型の値を持つことができます。

>>> nums[2] = '二十'
>>> nums
[0, 1, '二十', 3, 4, 5, 6, 7, 8, 9]
>>>

リストでループを回します。

>>> nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> 
>>> for num in nums:
...     print(num)
... 
0
1
2
3
4
5
6
7
8
9

range を使い、インデックスでループを回します。

>>> nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> 
>>> for index in range(len(nums)):
...     print(nums[index])
... 
0
1
2
3
4
5
6
7
8
9

スライスを使い、配列の一部にアクセスできます。

>>> nums[:2]
[0, 1]
>>> nums[2:7]
[2, 3, 4, 5, 6]
>>> nums[3:-1]
[3, 4, 5, 6, 7, 8]
>>> nums[:]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

ループを使い、配列の最大値を取得します。

>>> nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> max_num = nums[0]
>>> for num in nums:
...     if num > max_num:
...         max_num = num
... 
>>> max_num
9

このように、配列では、インデックスが分からない要素を探索する場合、最初から最後まで全ての要素を確認する必要がり、計算量は\( O (N) \) になります。

よって、値の探索を多く行う時は、データ構造は配列と比較して複雑になりますが、探索の計算量が\( O ( \log N)\)である2分探索や \( O (1) \)である連想配列を使うことができます。