Why does std::list::reverse have O(n) complexity?
<p>Why does the reverse function for the <code>std::list</code> 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).  </p>

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