V ktorej dátovej štruktúre je vkladanie nového prvku rýchlejšie: v LinkedList alebo v ArrayList?

Vloženie nového prvku do LinkedList je zvyčajne rýchlejšie ako do ArrayList, najmä ak sa vloženie ne vykonáva na konci zoznamu.

Dôvodom je, že LinkedList predstavuje dvojitý prepojený zoznam, kde každý prvok obsahuje odkazy na predchádzajúci a nasledujúci prvok. Na vloženie stačí zmeniť niekoľko odkazov, čo trvá O(1) času, ak je pozícia známa.

V ArrayList sú údaje uložené v poli. Pri vkladaní do stredu alebo na začiatku poľa je potrebné posunúť všetky nasledujúce prvky, čo trvá O(n) času.

Avšak, ak sa vloženie vykonáva na konci:

• ArrayList vloží prvok v amortizovanom čase O(1) (ak nie je potrebné rozšírenie poľa).
• LinkedList tiež vloží v O(1), ak existuje odkaz na posledný prvok.

Preto je pri vkladaní na ľubovoľnú pozíciu LinkedList rýchlejšia, pri vkladaní na koniec — približne rovnaká.