リンクリスト、連結リスト、などとも言う

線形リストも同じ？

要素数が可変

メモリ上では各要素はバラバラの場所に置かれることも出来る

要素の前後にポインタを置き、それでアクセスする

各要素は、次の要素や、前の要素のポインタも持っている必要があるため、メモリ的には少しコストがある

要素にアクセスする場合は先頭からポインタを辿っていく必要があるためコストがかかる

途中に要素を挿入したり、削除したりはポインタを書き換えるだけで住むので少コスト

スタックみたいなもの？

全要素アクセス可能？

どこからでも追加可能？

要素を追加するときにO(1)で済む

n番目の要素を見つけるときはO(n)かかる

前から辿っていくから。

結合

命令形データ構造ではO(1)

元のリストは使えない

関数型データ構造ではO(n)

元のリストは使える、一つはコピー、一つは共有

元のデータと新しいデータの一部が共有されているのが割と味噌

例

Goのslice?

Lisp

Scheme

Pythonのlist

HaskellのList

Haskellでは要素に添え字アクセスすることはほとんどないのでデメリットの影響は小さそう

関連

catenable list

参考

LinkedListをRustで実装するチュートリアル