読者です 読者をやめる 読者になる 読者になる

配列とリスト

Algorithm

学部時代にやった記憶はあるがアタマから飛んでる、というか理解あまりしてなかった...
ので、基礎的すぎるが整理をしたい。

配列

同じ型(int, long, double, etc)のデータを連続したアドレスで確保する。
整数添字で各要素にアクセスするので、参照はO(1)に、挿入/削除はO(n)になる。

リスト

抽象的な概念で、実装には双方向/循環など様々ある。基本的なアイデアは、各要素が次の要素のアドレスを保持することで、動的に要素を連結する、というものである。要素をすべて舐める必要があるので、参照はO(n)で、末尾への追加/末尾からの削除はO(1)になる。

言語によるが型は等価(Javaなら同じInterfaceを実装)であればよい。