Ro'yxatning o'rtasidan elementni o'chirishni…

ArrayList.

Listaning o‘rtasidan elementni olib tashlash:

ArrayList: Barcha keyingi elementlarni siljitishni talab qiladi, bu eng yomon holatda (birinchi elementni olib tashlashda) $O(n)$ vaqt oladi, bu yerda $n$ elementlar soni. Biroq, o‘rtacha holatda, operatsiya $O(n)$ qoladi, chunki faqat yarmi elementlarni siljitish kerak bo‘ladi. Haqiqiy ishlash ko‘rsatkichi odatda yaxshiroq bo‘ladi, chunki ma’lumotlarning yaxshiroq lokalizatsiyasi mavjud.
LinkedList: Kerakli tugunni topish uchun elementlar bo‘ylab iteratsiya qilishni talab qiladi ($O(n)$ eng yomon holatda, agar iteratsiya boshidan yoki oxiridan boshlansa). Tugunni topgach, uni olib tashlash $O(1)$.

LinkedListda tugunni o‘zi olib tashlash tezroq bo‘lsa-da, uni topish uchun qidiruv o‘rtacha holatda ArrayListga qaraganda sekinroq bo‘ladi.

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

public class ListRemovalComparison {

    public static void main(String[] args) {
        int size = 100000; // Ro‘yxat hajmi
        int removeIndex = size / 2; // Olib tashlash indeksi (o‘rtacha)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // O‘rtacha joydan olib tashlash
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("ArrayListdan olib tashlash vaqti: " + 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); // O‘rtacha joydan olib tashlash
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("LinkedListdan olib tashlash vaqti: " + durationLinkedList + " ns");
    }
}

Benchmark natijalari shuni ko‘rsatadiki, o‘rtadagi elementni olib tashlash uchun, ArrayList odatda tezroq bo‘ladi, nazariy siljitish murakkabligiga qaramay. Bu, LinkedListda indeks bo‘yicha qidiruv ($O(n)$) ArrayListdagi siljitishdan sekinroq bo‘lishidan kelib chiqadi.

// ArrayList - indeks bo‘yicha kirish O(1), olib tashlash O(n) (siljitish)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // "B" ni olib tashlash - "C" ni siljitish talab qilinadi

// LinkedList - indeks bo‘yicha kirish O(n), olib tashlash O(1) (tug‘unni topgach)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // "B" ni olib tashlash - avval "B" tug‘unni topish (O(n)), keyin olib tashlash (O(1))

Xulosa qilib aytganda, o‘rtadagi elementni olib tashlash operatsiyasi uchun, indeksni bilsangiz, ArrayList odatda, indeks bo‘yicha kirish operatsiyasining tezligi bilan afzalroq, bu siljitish xarajatlarini qoplaydi.

Ro'yxatning o'rtasidan elementni o'chirishni istasangiz, ArrayList yoki LinkedList dan qaysi biri yaxshiroq?