Mis on parem kasutada: ArrayList või LinkedList, kui…

ArrayList.

Elementi keskelt eemaldamisel:

ArrayList: Vajab kõikide järgnevate elementide nihutamist, mis halvimal juhul (kui eemaldatakse esimene element) võtab aega $O(n)$, kus $n$ on elementide arv. Keskmiselt jääb operatsioon $O(n)$-ks, kuna tuleb nihutada ainult pool elementidest. Tegelik jõudlus on sageli parem andmete parema paiknemise tõttu.
LinkedList: Vajab iteratsiooni elementide kaudu, kuni leitakse vajalik sõlm ($O(n)$ halvimal juhul, kui algusest või lõpust alustatakse). Pärast sõlme leidmist, eemaldamine võtab $O(1)$.

Kuigi sõlme ise eemaldamine LinkedListis on kiirem, sõlme otsimine enne eemaldamist muudab kogu operatsiooni keskmiselt aeglasemaks kui ArrayListis.

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

public class ListRemovalComparison {

    public static void main(String[] args) {
        int size = 100000; // Nimekirja suurus
        int removeIndex = size / 2; // Eemaldamise indeks (keskel)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Keskmine eemaldamine
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("ArrayList eemaldamise aeg: " + 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); // Keskmine eemaldamine
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("LinkedList eemaldamise aeg: " + durationLinkedList + " ns");
    }
}

Tulemused näitavad, et kui teate indeksit, on ArrayList tavaliselt parem valik, kuna see võimaldab kiiremat juurdepääsu indeksile, mis kompenseerib nihutamise kulud.

// ArrayList - juurdepääs indeksi järgi O(1), eemaldamine O(n) (nihutamine)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // "B" eemaldamine - nihutab "C"

// LinkedList - juurdepääs indeksi järgi O(n), eemaldamine O(1) (pärast sõlme leidmist)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // "B" eemaldamine - kõigepealt tuleb leida "B" sõlm (O(n)), siis eemaldada (O(1))

Kokkuvõttes, kui teate indeksit, on ArrayList sageli parem valik, kuna see võimaldab kiiremat juurdepääsu indeksile, mis kompenseerib nihutamise kulud.

Mis on parem kasutada: ArrayList või LinkedList, kui ma tahan eemaldada elemendi keskmest nimekirjas?