mercredi 24 février 2016

Why std::list::reverse has O(n) complexity?

Does anyone know why the reverse function for the std::list class in the C++ standard library has 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.

Aucun commentaire:

Enregistrer un commentaire