Чем отличается время выполнения операции удаления первого элемента в ArrayList от LinkedList?

LinkedList выполняет операцию удаления первого элемента быстрее, чем ArrayList.

ArrayList реализован на основе массива, в котором все элементы имеют фиксированный размер. vk.com Чтобы удалить элемент, необходимо избавиться от освободившегося места путём смещения всех элементов справа на одну позицию влево. vk.com Время выполнения этой операции зависит от количества элементов и составляет O(n). vk.com

LinkedList основан на двусвязном списке, где каждый элемент содержит ссылку на последующий и предыдущий (исключение первый и последний элементы). vk.com Чтобы удалить элемент, нужно просто перебросить ссылки так, чтобы элементы, стоящие по бокам от удаляемого, ссылались друг на друга. vk.com Время выполнения этой операции — O(1). github.com

Таким образом, LinkedList более эффективен при выполнении операций удаления, особенно в начале списка, где нужно просмотреть относительно немного элементов. stackoverflow.com ArrayList же быстрее работает, когда операция происходит ближе к концу списка, так как нужно изменить только несколько оставшихся элементов, которые следуют за ним. stackoverflow.com