Агар ман хоҳам, ки унсури дар маркази рӯйхатро тоза…

ArrayList.

Дар вақти хориҷ кардани ун element аз маркази рӯйхат:

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 + " 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 истифода кунам?