Python には配列はビルトインとしては存在しません。
配列ではなく、同一の型でなければならないという配列の制約を取り払った「リスト」と言われるデータ構造が使われます。
少しややこしいですが、Python のリストは一般的な “Linked List” ではなく、型の制約のない「配列」です。
CPythonでは、リストの最後への要素の追加は\( O (1) \)、リストの途中への要素の挿入は\( O (N) \)、リストの最後の値の削除は\( O (1) \) 、 リストの途中の要素の削除は\( O (N) \)と、配列と同じように実装されています。
ちなみに、型の制約のある配列を使いたいときは、array というモジュールを使うことができます。
または、numpy を用いることもできます。
リスト
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) \)である連想配列を使うことができます。
