C++ 標準ライブラリのクラスの逆関数のstd::list実行時間が線形なのはなぜでしょうか? 二重リンク リストの場合、逆関数は O(1) になるはずだと思います。
二重リンクリストを逆にするには、ヘッドとテールのポインタを切り替えるだけです。
ベストアンサー1
reverse仮に、オー(1)（これも仮定の話ですが）リンク リストの方向が、リストが作成された元の方向と現在同じか反対かを示すブール リスト メンバーが存在する可能性があります。
残念ながら、これによって基本的に他のすべての操作のパフォーマンスが低下します (ただし、漸近的な実行時間は変わりません)。各操作では、リンクの「次」ポインタに従うか「前」ポインタに従うかを検討するためにブール値を参照する必要があります。
これはおそらく比較的まれな操作であると考えられていたため、標準 (実装を規定するのではなく、複雑さのみを規定) では複雑さが線形になる可能性があると指定されました。これにより、「次の」ポインタは常に明確に同じ方向を意味するようになり、一般的な操作が高速化されます。