What is better to use: ArrayList or LinkedList if I…

ArrayList.

When removing an element from the middle of a 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)$ because only half of the elements need to be shifted. Actual performance is often better due to better data locality.
LinkedList: Requires iteration through elements to find the desired node ($O(n)$ in the worst case, if iteration starts from the beginning or end). After finding the node, removal takes $O(1)$.

Although removing the node itself in a LinkedList is faster, the search 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 for removal (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 shift complexity. This is because index-based access in LinkedList ($O(n)$) is slower than shifting in ArrayList.

// ArrayList - index access O(1), removal O(n) (shift)
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 the node "B" (O(n)), then delete (O(1))

In conclusion, for the operation of removing from the middle when you know the index, ArrayList is often the preferred choice due to faster index access, which offsets the cost of shifting.

What is better to use: ArrayList or LinkedList if I want to delete an element from the middle of the list?