前書き

データ構造ってたくさんあって覚えるの大変ですよね．僕も勉強した直後はいいんですがある程度日数が経つと忘れてしまい -> また勉強し直す，の繰り返しでした．

その過程のうち効果的だったのが，タイトルにもある通り絵や図で特徴を覚える方法でした．

データ構造ってかなり抽象的な内容だと思います．コンピューターのメモリの中身を実際に見る機会なんて少ないので学んだデータ構造が本当にどのように振る舞っているのかなかなか確認しづらいのが，定着率が低い原因だと思いました．

そこで，この記事では簡単かつ具体的な図で各構造を表す（つもり）ことで大学で情報工学専攻じゃ無い人も，プログラミング初心者でも事前知識無しでデータ構造の特徴を覚えることができるのでは，と期待しつつ，自分へのメモ書きも含めて記事を書きました．

データ構造を学ぶ目的としては完全に構造を暗記するのではなく，それぞれの構造の良いところと欠点を知ることで，自分の開発目的にあった効率の良い構造を選べるようになることだと思います．というわけでこの記事の内容も丸暗記するというよりは，配列ってこんな良いところ，欠点があるよねって話せるようになるキッカケになれば，と思っています．

Big O

各データ構造を比べるには，その性能を定量的に測る仕組みが必要ですよね．データ構造の性能を測るものさしとしてよく使われる考え方がBig Oです．以下にその定義を示しますが少し複雑に感じるかもしれません．

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann,[1] Edmund Landau,[2] and others, collectively called Bachmann–Landau notation or asymptotic notation.

(wikipedia)

僕はBig Oはデータの要素がたくさん増えたとき，その処理時間（Time Complexiy），とメモリ消費量（Space Complexiy）がどれくらい増えやすいかを表す指標，と考えると理解しやすかったです．以降では時間に関するBig OはO()Time，メモリ消費に関してはO()Spaceと表記します．

BigOが大きいほど処理時間やメモリ消費が増えてしまうのでよくない，という感じです．

以下によく使うBig Oの表記とその意味を示しておきます．

O(1): どれだけデータが増えても（nが大きくなっても）関係なしに一瞬で動作が終わる状態．超早い！これを目指そう！
O(log n): ループ処理などで，各ループで要素の半分を切り捨てることができる状態．要素全てを見なくてもOKなので，かなり良い状態！
O(n): データが増えた量だけ（nの増加分だけ）処理が比例して増える状態．普通．

特によく使うのは上の3つです．もっと詳しくBig Oについて知りたい人はBig-O Cheat Sheetなどが参考になると思いますし，Google画像検索をしても良いイメージが掴めるかと思います．

Big-O Cheat Sheetより

特にO(1), O(log n) が早いことが分かりますね

ArrayのBigOまとめ

復習しやすいように配列，ArrayのBig Oを表にまとめました．この記事を読んだ後にまた見返して下さい．

目標はなぜArrayがこの表の特性を持つのか，そしてどのような場合に使うべきかを説明できるようになることです．

methods	time
lookup	O(1)
insert	O(n)
delete	O(n)
push (to the end)	O(1) / sometime O(n)
memory use	continues
loop every element	O(n)

ただしnは配列の要素数を示します

ではなぜこのような特性になるのか詳しく見ていきましょう．

Arrayの構造

memory use

Arrayはメモリを連続に使っていきます．これによって配列を簡単にループできます．でも配列を作成するには連続で空いているメモリを見つける必要がある，とも言えますね．

const myArray = ['apple', 'blueberry', 'chocolate']

lookup: O(1)

何番目の要素か知っている場合はアクセスするのは一瞬です．これは配列がメモリを連続で使う，という縛りがあるからですね．

// lookup: O(1)Time
myArray[2] // chocolate

insert to the end (push): O(1)

新しい要素をArrayの最後に追加するのも一瞬です．

Arrayのメモリでの状況をイメージできていれば予想できますね．

// add item to the end (push): O(1)Time
myArray.push('donut')

console.log(myArray) // [ 'apple', 'blueberry', 'chocolate', 'donut' ]

insert: O(n)

要素を配列の真ん中に挿入のは遅いです．挿入する場所以降の要素を一つずらす必要があるからですね．先頭に追加する場合が最悪（全要素をずらす必要がある），最後から2番目への挿入は1つしか要素をずらさずに済みます．

// insert item to the middle or the bigining: O(n)Time
myArray.splice(2, 0, 'cookie')

console.log(myArray) // [ 'apple', 'blueberry', 'cookie', 'chocolate', 'donut' ]

delete: O(n)

要素を削除するのも挿入と同じように，処理後の配列がメモリを順番に使う状態を保つため幾つかの要素をずらす必要があります．これが原因で遅くなってしまうのですね．

せっかく削除したい要素を見つける（lookup）は早いのに，なんだかもったいない気がしますね．

// delete: O(n)Time
myArray.splice(1, 1) 

console.log(myArray) // [ 'apple', 'cookie', 'chocolate', 'donut' ]

最後の要素を削除するBig Oはどうなると思いますか？

答えはO(1)Timeです．最後の要素を消した後に配列を調整する必要がないからですね．これもイメージできていれば簡単に導けますね．

後書き

図を作って説明するのって結構大変なので省略しがちですが，図を書くのが大変な抽象的な内容ほど必要なことだと思います，逆に図で説明できないということは理解していない証拠ですね．

もう一度ArrayのBigOまとめの表を見て下さい．Arrayの構造をイメージできていれば左の内容から右のBigOを導けるはずです．ポイントは表を丸暗記するのではなく，構造のイメージを掴み，長所，短所を導き出せることです．

この図で説明する記事が特にプログラミング初学者に役立つことを期待して，次はHash Tableについて記事を書こうと思います．