配列とリスト

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

配列

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

リスト

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

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