[初心者向け] イメージで覚えるデータ構造：static vs dynamic array編

シリーズものです．前回は配列のデータ構造について説明しましたが，実は配列には静的static，動的dynamicの2種類がありメモリの使い方が少し違います．

この記事ではそれの違いをイメージで説明しようと思います．

Big O

method	static	dynamic
push (to the end)	O(1)	O(1), or O(n)
memory size	O(n)	O(2n)

違いは要素を最後尾に追加するBig Oだけです．Arrayの詳しいBigOについては前回の記事で説明しています．

ではなぜこのような表になるのか見ていきましょう．

static arrayのメモリ

静的配列では配列を作る前にその大きさを指定します．何も特別なことではないと感じるかもしれませんが，この場合要素を追加したい時に配列の最後尾の次のメモリが空いている保証はありませんよね．もし既に使われている場合は要素を追加することができなくなってしまいます．

これは配列がメモリを連続で使う，という縛りがあるからです．

myStaticArray[3]; // defining size of the static array
myStaticArray[3] = { "a", "b", "c" };

myStaticArray.append('d') // ?

参考：Dynamic vs static array in c [closed]

dynamic arrayのメモリ

動的配列では配列を編集しようとした際にメモリが他に既に使われてしまっている場合，全く別の，連続で配列の倍の数のメモリが空いているところにコピーして編集します．

こうすることでメモリを連続で使う，という縛りを受けつつ新しい要素の追加などにも対応できるということですね．

ただし配列全体を動かす必要があるのでO(n)Timeかかってしまいます．これは毎回起こるわけではなく，新たにメモリを見つけないと処理できない場合のみに起こるのでdynamic arrayで要素を追加するBigOは，ほとんどの場合O(1)Timeだけど，配列を動かす必要のある場合のみO(n)Timeとなるわけですね．

まとめると：

• dynamic
  • メモリを動的に多め（2倍）に確保する
    • Good：配列のサイズを定義していなくても要素を自由に追加できる
    • Bad：メモリ消費が倍
    • 処理によっては配列全体を動かす必要がある
• static
  • メモリは配列のサイズを最初に定義した分だけ確保
    • Good：メモリ消費量が少なくて済む
    • Bad：初期サイズを超えるような処理ができない

次はHash Tableについて記事を書こうと思います．