Тизмедеги ортосундагы элементти өчүргүм келсе…

ArrayList.

Элементти ортоңкудан алып салуу үчүн:

ArrayList: Бардык кийинки элементтерди жылдыруу талап кылынат, эң жаман учурларда (биринчи элементти алып салганда) убакыт $O(n)$ болот, анда $n$ — элементтердин саны. Орто эсеп менен, операция $O(n)$ бойдон калат, анткени тек гана жарымын жылдыруу керек. Чындыкта, иштетүү көбүнчө жакшыраак, анткени маалыматтардын жайгашуусу жакшыраак.
LinkedList: Элементтер аркылуу өтүү керек, керек болгон түйүндү табуу үчүн ($O(n)$ эң жаман учурларда, эгер ал баштан же аягынан башталса). Түйүндү тапкандан кийин, алып салуу $O(1)$.

LinkedList ичинде түйүндү табуу жана андан кийин алып салуу операциясы орто эсеп менен ArrayListке караганда узак болот, анткени табуу $O(n)$, ал эми жылдыруу 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 + " ns");

        // 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 + " ns");
    }
}

Жыйынтык көрсөтүп турат, эгер сиз индексин билсеңиз, 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 көбүнчө жакшыраак тандоо, анткени ал тезирээк жетүү операциясын камсыз кылат, бул жылдыруу чыгымдарын жабат.

Тизмедеги ортосундагы элементти өчүргүм келсе, ArrayList же LinkedList колдонсумбы?