Aké sú hlavné rozdiely medzi LinkedList a ArrayList v Jave?

Hlavné rozdiely medzi LinkedList a ArrayList spočívajú v ich vnútornej dátovej štruktúre a následne v výkonnosti rôznych operácií:

Vnútorná štruktúra:

• ArrayList používa dynamický pole na ukladanie prvkov.
• LinkedList používa dvojito prepojený zoznam, kde každý uzol obsahuje údaje a odkazy na predchádzajúci a nasledujúci uzol.

Výkon operácií:

Operácia	ArrayList	LinkedList	Dôvod
Pridanie na koniec	O(1)	O(1)	V ArrayList je zvyčajne miesto, v LinkedList ľahko pridáme nový koniec.
Pridanie na začiatok alebo do stredu	O(n)	O(1)	V ArrayList je potrebné posunúť prvky. V LinkedList je potrebné zmeniť niekoľko odkazov.
Odstránenie z konca	O(1)	O(1)	V ArrayList sa neposúvajú prvky. V LinkedList je ľahké odstrániť koniec.
Odstránenie zo začiatku alebo zo stredu	O(n)	O(1)	V ArrayList je potrebné posunúť prvky. V LinkedList je potrebné zmeniť niekoľko odkazov.
Získanie prvku podľa indexu	O(1)	O(n)	V ArrayList priame prístup k prvkom podľa indexu. V LinkedList je potrebné prejsť zoznam.
Vyhľadávanie prvku	O(n)	O(n)	Je potrebné prehľadávať celý zoznam v oboch prípadoch.

Využitie pamäti:

• LinkedList zvyčajne spotrebúva viac pamäti kvôli uloženiu ďalších odkazov na predchádzajúci a nasledujúci uzol.

Použitie:

• ArrayList je vhodnejší, keď sú časté operácie prístupu k prvkom podľa indexu a pridávanie/odstraňovanie na konci.
• LinkedList je vhodnejší, keď sú časté operácie pridávania a odstraňovania prvkov z začiatku alebo stredu zoznamu.

Príklad: Pridanie na začiatok

// ArrayList
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add(0, "First"); // O(n) - posun existujúcich prvkov

// LinkedList
LinkedList<String> linkedList = new LinkedList<>();
linkedList.addFirst("First"); // O(1) - len zmena odkazov