リスト
linked list
要素数が可変
メモリ上では各要素はバラバラの場所に置かれることも出来る
要素の前後にポインタを置き、それでアクセスする
各要素は、次の要素や、前の要素のポインタも持っている必要があるため、メモリ的には少しコストがある
要素にアクセスする場合は先頭からポインタを辿っていく必要があるためコストがかかる
途中に要素を挿入したり、削除したりはポインタを書き換えるだけで住むので少コスト
全要素アクセス可能？
どこからでも追加可能？
要素を追加するときにO(1)で済む
n番目の要素を見つけるときはO(n)かかる
前から辿っていくから。
結合
命令形データ構造では$ O(1)
元のリストは使えない
関数型データ構造では$ O(n)
元のリストは使える、一つはコピー、一つは共有
元のデータと新しいデータの一部が共有されているのが割と味噌
例
Goのslice?
Lisp
Scheme
Pythonのlist
HaskellのList
Haskellでは要素に添え字アクセスすることはほとんどないのでデメリットの影響は小さそう
関連
catenable list
参考
LinkedListをRustで実装するチュートリアル