Kura datu struktūrā jauna elementa ievietošana ir ātrāka: LinkedList vai ArrayList?

LinkedList jauna elementa ievietošana parasti ir ātrāka nekā ArrayList, īpaši, ja ievietošana nenotiek listes beigās.

Iemesls ir tas, ka LinkedList ir divvirzienu saistīts saraksts, kur katrs elements satur atsauces uz iepriekšējo un nākamo elementu. Lai ievietotu, pietiek mainīt dažas atsauces, kas aizņem O(1) laiku, ja pozīcija ir zināma.

ArrayList dati tiek glabāti masīvā. Ievietojot vidū vai sākumā, ir nepieciešams pārvietot visus sekojošos elementus, kas aizņem O(n) laiku.

Tomēr, ja ievietošana notiek beigās:

• ArrayList ievieto elementu amortizētā O(1) laikā (ja nav nepieciešama masīva paplašināšana).
• LinkedList arī ievieto O(1), ja ir atsauce uz pēdējo elementu.

Tādēļ, ievietojot jebkurā pozīcijā, LinkedList ir ātrāka, bet, ievietojot beigās — aptuveni vienāda.