Why does std::list::reverse have O(n) complexity?

Why does the reverse function for the std::list class in the C++ standard library have linear runtime? I would think that for doubly-linked lists the reverse function should have been O(1).

Reversing a doubly-linked list should just involve switching the head and the tail pointers.

7 Answers

Leave a Comment