on
Array vs Linked List
Array
最も基本的な資料構造であるArray資料構造は、論理的保存順序と物理的保存順序が一致する。
したがって、インデックス(index)で当該元素(element)にアクセスすることができる。
そのため、探したい元素のインデックス値を知っていれば、Big-O(1)に当該元素にアクセスすることができる。
つまり、random access が可能であるという長所があるのだ。
しかし、削除または挿入の過程では、該当元素に接近して作業を完了した後(O(1))、もう1つの作業を追加しなければならないため、さらに時間がかかる。
もし配列の元素のいずれかの元素を削除したといったとき、配列の連続的な特徴が破られることになる。
つまり、空きができるのだ。 したがって、削除した元素より大きなインデックスを持つ元素をシフトしなければならないコスト(cost)が発生し、この場合の時間複雑度はO(n)となる。
そのため、Array資料構造における削除機能に対するtime complexityのworst caseはO(n)になる。
挿入の場合も同様である。 もし、最初の席に新しい元素を追加したいなら、すべての元素のインデックスを1つずつシフトしなければならないので、この場合もO(n)の時間を要求することになる。
Linked List
この部分に対する問題点を解決するための資料構造がlinked listである。
それぞれの元素は自分自身の後でどんな元素なのかを覚えている。
したがって、この部分だけ他の値に変えれば、削除と挿入をO(1)で解決できるのだ。
しかし、Linked Listも一つ問題がある。
必要な位置に挿入したい場合は、必要な位置をSearch過程において最初の元素からすべて確認しなければならないということだ。
Arrayとは違って論理的保存順序と物理的保存順序が一致しないためだ。 これはまず挿入して整列するのと同じだ。
この過程のため、ある元素を削除または追加しようとするとき、その元素を探すためにO(n)の時間が追加的に発生することになる。
結局、linked list 資料構造はsearch にも O(n) の time complexity を持ち、挿入、削除に対しても O(n) の time complexity を持つ。
だからといって、とても無駄な資料構造ではないため、我々が学習するのだ。
このLinked ListはTree 構造の根幹となる資料構造であり、Tree で使用されたときにその有用性が明らかになる。