Šta je bolje koristiti: ArrayList ili LinkedList, ako…

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 + " 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 је често бољи избор због брже операције приступа по индексу, што компензује трошкове преноса.

Šta je bolje koristiti: ArrayList ili LinkedList, ako želim da uklonim element iz sredine liste?