Kas geriau naudoti: ArrayList ar LinkedList, jei…

ArrayList.

Pašalinti elementą iš vidurio sąrašo:

ArrayList: Reikalauja visų vėlesnių elementų perkėlimo, kas blogiausiu atveju (pašalinus pirmą elementą) užtrunka $O(n)$ laiką, kur $n$ yra elementų skaičius. Tačiau vidutiniškai operacija lieka $O(n)$, nes reikia perkelti tik pusę elementų. Faktinis našumas dažnai būna geresnis dėl geresnės duomenų lokalizacijos.
LinkedList: Reikalauja pereiti per elementus iki reikalingo mazgo ($O(n)$ blogiausiu atveju, jei pradžia arba pabaiga). Po mazgo radimo, pašalinimas užtrunka $O(1)$.

Nors pats mazgo pašalinimas LinkedList yra greitesnis, mazgo paieška prieš pašalinimą daro bendrą operaciją vidutiniškai lėtesnę nei ArrayList.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListRemovalComparison {

    public static void main(String[] args) {
        int size = 100000; // Sąrašo dydis
        int removeIndex = size / 2; // Pašalinimo indeksas (vidurys)

        // ArrayList
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
        }

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Vidurio pašalinimas
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("ArrayList pašalinimo laikas: " + durationArrayList + " ns");

        // LinkedList
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            linkedList.add(i);
        }

        long startTimeLinkedList = System.nanoTime();
        linkedList.remove(removeIndex); // Vidurio pašalinimas
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("LinkedList pašalinimo laikas: " + durationLinkedList + " ns");
    }
}

Rezultatai rodo, kad jei žinote indeksą, ArrayList dažniausiai yra geresnis pasirinkimas dėl greitesnio prieigos laiko, kuris kompensuoja perkėlimo išlaidas.

// ArrayList - prieiga pagal indeksą O(1), pašalinimas O(n) (perkėlimas)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // "B" pašalinimas - perkeliama "C"

// LinkedList - prieiga pagal indeksą O(n), pašalinimas O(1) (po mazgo radimo)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // "B" pašalinimas - pirmiausia reikia rasti "B" mazgą (O(n)), tada pašalinti (O(1))

Apibendrinant, jei žinote indeksą, ArrayList dažnai yra geresnis pasirinkimas dėl greitesnio prieigos laiko, kuris kompensuoja perkėlimo išlaidas.

Kas geriau naudoti: ArrayList ar LinkedList, jei noriu ištrinti elementą iš vidurio sąrašo?