Vlákno názorů k článku Datové kolekce v programovacím jazyku Rust od ebik - To srovnání operací je trochu nefér k linked-listům....

To srovnání operací je trochu nefér k linked-listům. Divil bych se, kdyby neexistovala operace insert a remove které dostávají iterátor a ne celočíselný index. Potom mají takové operace složitost O(1), a popravdě je to jeden z hlavních důvodů proč používat linked listy.

A u deque a vectoru je potřeba vědět jak probíhá realokace v případě překročení kapacity. Jestli se používá klasický exponenciální růst, tak to znamená, že takový kontejner má nejvýše dvojnásobnou kapacitu (pokud se z něho nemazalo) protože se při překročení zvýší kapacita na dvojnásobek. To má výhodu, že každý prvek se v průměru bude přesouvat z důvodu realokace jen dvakrát, tedy amortizovaná složitost push() je O(1). Jen se musí počítat s tím, že jednou za "n" kroků může být ta složitost "n".