【データ構造】配列 (Array)とは?基本的な使い方を解説

スポンサーリンク
配列とは データ構造

配列 (Array)とは

配列 (Array)とは、

同じデータ型の値の集まりを1つにまとめたデータ構造

です。

 

配列には同じ型の複数のデータを入れ、添え字でアクセスします。

配列の概要

 

配列のデータはメモリ上の連続した領域に格納されます。

そのため、メモリのアドレスは添え字を使って計算でき、各データにランダムアクセスすることができます。

 

まとめると、配列は以下の特徴があります。

配列の特徴
  • 同じデータ型
     配列に格納できる値は全て同じデータ型でなければなりません
    (整数、浮動小数点数、文字列など)。
  • 連続したメモリ領域
    配列の要素は連続したメモリ上に格納されています。
    そのため、任意の要素にランダムアクセスが可能です。
  • インデックスによるアクセス
    配列の各要素にはインデックス番号(通常は0から始まる)が割り当てられており、そのインデックスを指定して要素にアクセスします。

 

配列 (Array)の計算量

配列(Array)における各操作の計算量は以下のようになります。

配列(list)の計算量
list
要素の参照 list[k] O(1)
先頭に追加
insert O(n)
末尾に追加 append O(1)
要素の削除 remove O(n)
ソート sort O(n log n)

 

配列に要素を追加する場合、追加したい場所以降の要素をずらす必要があります。

配列への要素の追加

 

実装方法

正確には配列とは異なりますが、pythonではListを使うことが一般的なためそちらの実装方法を記載しておきます。

listオブジェクトは配列と似たもので、要素の型が異なっていても格納できるなど、より高機能になっています。

mylist = ["apple", "orange"]
mylist.append("banana")
mylist.insert(0, "grape")
print(mylist) # ['grape', 'apple', 'orange', 'banana']
print(mylist[1]) #  apple

 

同じ型のみを格納したい場合は、標準でarrayモジュールをimportして使うこともできます。

import array

myarray = array.array('i', [1, 2, 3])
myarray.append(4)
myarray.insert(0, 0)
print(myarray)

 

参考文献

競技プログラミングの鉄則
created by Rinker

5. データ構造 — Python 3.12.3 ドキュメント

array — Efficient arrays of numeric values — Python 3.12.3 ドキュメント

TimeComplexity – Python Wiki

コメント

タイトルとURLをコピーしました