リストの概要
- データとして順序を保持
- 可変長
- データそのものとその次のデータを指し示すデータ(ポインタ)が1セット
操作
参照
先頭から順々に走査する必要がある
-> O(n)
(n: list の要素数)
挿入・削除
前後の要素のポインタに対して新たに追加される要素へ変更すれば良い
-> O(1)
以上から、配列はアクセス(特にランダムアクセス)が頻繁に行われるようなユースケースに適している。
一方、挿入・削除の操作が頻繁に行われるユースケースには適さない。
メモリ
可変長となっているので必要な分だけ確保して利用可能
Code