線形リスト - suto3の大福帳

線形リスト

線形リストには、片方向リストと双方向リストがあり、どちらも任意の位置でデータの追加・削除が$ O(1)時間でできるのが特長である。

しかし、ソートされた配列や木構造と違い、データの検索は$ O(n)時間かかってしまうという欠点がある

（ソートされていない配列は線形リストと同じ$ O(n)の検索時間である）。