为什么std::listC++ 标准库中的类的反向函数具有线性运行时？我认为对于双向链表，反向函数应该是 O(1)。
std::list
反转双向链表应该只涉及切换头指针和尾指针。
假设，reverse可能是 O(1) 。（再次假设地）可能有一个布尔列表成员，指示链接列表的方向当前是否与创建列表的原始方向相同或相反。
reverse
不幸的是，这将降低基本上任何其他操作的性能（尽管不改变渐近运行时）。在每个操作中，需要参考一个布尔值来考虑是否跟随链接的“下一个”或“上一个”指针。
由于这可能被认为是相对不频繁的操作，因此标准（不规定实现，仅规定复杂性）指定复杂性可以是线性的。这允许“下一个”指针始终明确地表示相同的方向，从而加快常见情况的操作。
