Melyik adatszerkezetben gyorsabb az új elem beszúrása: a LinkedList-ben vagy az ArrayList-ben?

A LinkedList-be való új elem beszúrása általában gyorsabb, mint az ArrayList-be, különösen akkor, ha a beszúrás nem a lista végén történik.

Ennek oka, hogy a LinkedList egy kétszintű láncolt lista, ahol minden elem tartalmaz hivatkozásokat az előző és a következő elemre. A beszúráshoz elegendő néhány hivatkozást módosítani, ami O(1) időt vesz igénybe, ha a pozíció ismert.

Az ArrayList-ben az adatok egy tömbben vannak tárolva. A tömb közepén vagy elején történő beszúráskor minden következő elemet el kell tolni, ami O(n) időt vesz igénybe.

Azonban, ha a beszúrás a végén történik:

• Az ArrayList amortizált O(1) idő alatt beszúrja az elemet (ha nem szükséges a tömb bővítése).
• A LinkedList szintén O(1) idő alatt beszúr, ha van hivatkozás az utolsó elemre.

Ezért, véletlenszerű pozícióba történő beszúrás esetén a LinkedList gyorsabb, a végére történő beszúrásnál pedig körülbelül ugyanaz a teljesítmény.