配列

array

メモリ領域に、要素を一列に並べて管理する

固定長なので、宣言時に要素数を決めてメモリを確保する

添字を使って要素にアクセスする

メモリアドレスを直接指定しているのでアクセスが速い

生成後に途中に要素を挿入する処理は、それ以降の要素を全てズラして起き直さないといけないのでコストがかかる

要素を追加するときにコストがかかる

n番目に要素を追加した場合、n+1番目以降のものは全てコピーされる

例えば10000要素の配列の先頭に要素を追加すれば、10000回のコピーが必要になる

n番目の要素を見つけるときはO(1)

並べて入っているので、要素数がわかれば一瞬で見に行ける

例

Goのmap?

Pythonのarray

Ruby

Java

参考