Τι είναι καλύτερο να χρησιμοποιήσετε: ArrayList ή LinkedList, αν θέλετε να διαγράψετε ένα στοιχείο από το μέσο της λίστας;

ArrayList.

When removing an element from the middle of the list:

• ArrayList: Requires shifting all subsequent elements, which in the worst case (removing the first element) takes $O(n)$ time, where $n$ is the number of elements. However, on average, the operation remains $O(n)$, as only half of the elements need to be shifted. The actual performance is often better due to better data locality.
• LinkedList: Requires iterating through the elements to find the desired node ($O(n)$ in the worst case, if iteration starts from the beginning or the end). After finding the node, removal takes $O(1)$.

Although removing the node itself in LinkedList is faster, searching for the node before removal makes the overall operation slower on average than in 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; // List size
        int removeIndex = size / 2; // Index to remove (middle)

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

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Remove from middle
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("Time to remove from 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); // Remove from middle
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("Time to remove from LinkedList: " + durationLinkedList + " ns");
    }
}

Benchmark results show that, for removing an element from the middle, ArrayList is generally faster, despite the theoretical complexity of shifting. This is because index-based search in LinkedList ($O(n)$) is slower than shifting in ArrayList.

// ArrayList - index access O(1), removal O(n) (shifting)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // Remove "B" - requires shifting "C"

// LinkedList - index access O(n), removal O(1) (after finding the node)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // Remove "B" - first need to find node "B" (O(n)), then remove (O(1))

In summary, for the operation of removing from the middle, if you know the index, ArrayList is often the more preferred choice due to faster index access, which compensates for the cost of shifting.