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.