I know that a std::vector supplies an O(1) random access function but only has an O(N) insertion/removal function due to having to shift elements to make new space or fill up old space.
On the other hand, a linked list data structure has an O(1) insertion/removal function due to its use of pointers, but an O(N) random access function because we have to traverse from the first element to access any other.
Is there any data structure that can combine the two benefits given by each of the above data structures, to produce a structure with constant lookup, insertion, and deletion times?
Aucun commentaire:
Enregistrer un commentaire