Siyahının ortasından element silmək istəyirəmsə…

ArrayList.

Listənin ortasından elementin silinməsi:

ArrayList: Bütün ardıcıl elementlərin hərəkət etdirilməsini tələb edir ki, bu da ən pis halda ($O(n)$) vaxt alır, burada $n$ elementlərin sayıdır. Ancaq orta hesabla, əməliyyat $O(n)$ qalır, çünki yalnız yarım elementin hərəkət etdirilməsi lazımdır. Faktiki performans daha yaxşı olur, çünki məlumatların daha yaxşı lokalizasiyası var.
LinkedList: İstənilən düyünü tapmaq üçün elementlər üzərində iterasiya etməyi tələb edir ($O(n)$ ən pis halda, əgər iterasiya başlanğıc və ya sonundan başlayırsa). Düyü tapıldıqdan sonra, silinmə $O(1)$-dir.

LinkedList-də düyünü özünü silmək daha sürətlidir, ancaq silməzdən əvvəl düyünü tapmaq ümumi əməliyyatı orta hesabla daha yavaş edir, ArrayList-ə nisbətən.

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

public class ListRemovalComparison {

    public static void main(String[] args) {
        int size = 100000; // Siyahının ölçüsü
        int removeIndex = size / 2; // Silmək üçün indeks (orta)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Ortadan silinmə
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("ArrayList-dən silmə vaxtı: " + 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); // Ortadan silinmə
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("LinkedList-dən silmə vaxtı: " + durationLinkedList + " ns");
    }
}

Benchmark nəticələri göstərir ki, orta elementin silinməsi üçün, ArrayList ümumiyyətlə daha sürətlidir, nəzəri silmə mürəkkəbliyinə baxmayaraq. Bu, LinkedList-də indeks axtarışının ($O(n)$) ArrayList-dəki silmədən daha yavaş olmasından irəli gəlir.

// ArrayList - indeksə görə giriş O(1), silmə O(n) (kənarlaşdırma)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // "B"-ni sil - "C"-ni hərəkət etdirmək tələb olunur

// LinkedList - indeksə görə giriş O(n), silmə O(1) (düyünü tapdıqdan sonra)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // "B"-ni sil - əvvəlcə "B" düyünü tapmaq (O(n)), sonra silmək (O(1))

Qısaca, orta elementin silinməsi əməliyyatı üçün, indeks bilirsinizsə, ArrayList daha çox üstünlük təşkil edir, çünki indeksə görə daha sürətli giriş əməliyyatı ilə, silmə xərclərini kompensasiya edir.

Siyahının ortasından element silmək istəyirəmsə, ArrayList və ya LinkedList-dən hansı daha yaxşıdır?