Orta listedeki bir öğeyi silmek istiyorsam, ArrayList…

ArrayList.

Liste ortasındaki bir öğeyi kaldırırken:

ArrayList: Tüm sonraki öğelerin kaydırılmasını gerektirir, bu en kötü durumda (ilk öğenin kaldırılması) $O(n)$ zaman alır, burada $n$ öğe sayısıdır. Ancak, ortalama olarak, işlem $O(n)$ kalır çünkü yalnızca yarısı kaydırılır. Gerçek performans, veri yerelleştirmesinin daha iyi olması nedeniyle genellikle daha yüksektir.
LinkedList: İstenen düğüme kadar öğeler üzerinde yineleme yapmayı gerektirir ($O(n)$ en kötü durumda, yineleme baştan veya sondan başlatılırsa). Düğüm bulunduğunda, kaldırma işlemi $O(1)$'dir.

LinkedList'te düğümün kendisini kaldırmak daha hızlı olsa da, kaldırmadan önce düğümün bulunması genel işlemi ortalamanın altında yavaşlatır, ArrayList'e göre.

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

public class ListRemovalComparison {

    public static void main(String[] args) {
        int size = 100000; // Liste boyutu
        int removeIndex = size / 2; // Kaldırma indeksi (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 kaldırma
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("ArrayList'ten kaldırma süresi: " + 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 kaldırma
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("LinkedList'ten kaldırma süresi: " + durationLinkedList + " ns");
    }
}

Benchmark sonuçları, ortadan bir öğe kaldırmak için, ArrayList'in genellikle daha hızlı olduğunu gösterir, teorik kaydırma karmaşıklığına rağmen. Bu, LinkedList'te indeks aramanın ($O(n)$) ArrayList'teki kaydırmadan daha yavaş olmasından kaynaklanır.

// ArrayList - indeks erişimi O(1), kaldırma O(n) (kaydırma)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // "B"'yi kaldırır - "C" kaydırılması gerekir

// LinkedList - indeks erişimi O(n), kaldırma O(1) (düğüm bulunursa)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // "B"'yi kaldırır - önce "B" düğümünü bulmak (O(n)), sonra kaldırmak (O(1))

Özetle, ortadan kaldırma işlemi için, indeks bildiğinizde, ArrayList genellikle daha hızlı erişim işlemi nedeniyle tercih edilir, bu da kaydırma maliyetini telafi eder.

Orta listedeki bir öğeyi silmek istiyorsam, ArrayList mi yoksa LinkedList mi kullanmak daha iyidir?