Более эффективно удалить элементы из ArrayList или LinkedList?

Question

Теоретически, эффективнее ли удалять элементы из ArrayList или LinkedList ?

Answer 1

Это "проще" (то есть более эффективно) удалить их из LinkedList , потому что удаление из ArrayList требует перемещения всех последующих элементов на новую позицию в списке - всех последующих элементов массиву должно быть присвоено новое значение. В случае связанного списка необходимо переназначить только один указатель (или два с двусвязным списком).

Answer 2

Ну, удаление элемента из списка (с двойной связью) - это O (1). Но удаление из массива потребует, чтобы оставшиеся элементы были сдвинуты на одну позицию в массиве, что равно O (n).

Тем не менее, получение определенного элемента в списке по индексу - это O (n), в то время как получение определенного элемента в массиве по индексу - это O (1).

Итак, для реального удаления LinkedList будет лучше. Более подробную информацию о списках Array и LinkedList можно найти здесь .