რისი უკეთესია გამოყენება: ArrayList თუ LinkedList, თუ მე მინდა შუა სიის ელემენტის წაშლა?

ArrayList.

სიტყვების შუაში ამოღებისას:

• ArrayList: საჭიროებს ყველა შემდგომი ელემენტის გადატანას, რაც ყველაზე უარესი შემთხვევაში (პირველი ელემენტის ამოღებისას) დროით $O(n)$, სადაც $n$ — ელემენტების რაოდენობა. საშუალოდ, ოპერაცია რჩება $O(n)$-ში, რადგან მხოლოდ ნახევარი ელემენტი უნდა გადაიტანოს. ფაქტიური შესრულება ხშირად უკეთესია მონაცემების უკეთესი ლოკალიზაციის გამო.
• LinkedList: საჭიროებს გავლას ელემენტების მეშვეობით, სანამ არ იპოვის საჭირო კვანძს ($O(n)$ ყველაზე უარესი შემთხვევა, თუ იწყება დასაწყისიდან ან დასასრულიდან). კვანძის პოვნის შემდეგ, ამოღება $O(1)$.

მიუხედავად იმისა, რომ თავად კვანძის ამოღება LinkedList-ში სწრაფია, კვანძის ძებნა ამ ოპერაციის წინ საშუალოდ უფრო ნელი ხდება, ვიდრე 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; // სია ზომა
        int removeIndex = size / 2; // ამოღების ინდექსი (შუა)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // შუიდან ამოღება
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("ArrayList-დან ამოღების დრო: " + durationArrayList + " ნანოსექუნდა");

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

        long startTimeLinkedList = System.nanoTime();
        linkedList.remove(removeIndex); // შუიდან ამოღება
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("LinkedList-დან ამოღების დრო: " + durationLinkedList + " ნანოსექუნდა");
    }
}

შედეგები აჩვენებს, რომ თუ იცით ინდექსი, ArrayList ხშირად უკეთესია, რადგან უფრო სწრაფად ახდენს ინდექსით წვდომას, რაც კომპენსირებს გადატანის ხარჯებს.

// ArrayList - წვდომა ინდექსით O(1), ამოღება O(n) (გადატანა)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // "B" ამოღება - გადატანა "C"

// LinkedList - წვდომა ინდექსით O(n), ამოღება O(1) (ნაკლის შემდეგ)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // "B" ამოღება - ჯერ უნდა იპოვოს "B" (O(n)), შემდეგ ამოიღოს (O(1))

საერთო ჯამში, თუ იცით ინდექსი, ArrayList ხშირად უკეთესია, რადგან უფრო სწრაფად ახდენს ინდექსით წვდომას, რაც კომპენსირებს გადატანის ხარჯებს.