Более эффективно удалить элементы из ArrayList или LinkedList?
-
10-07-2019 - |
Вопрос
Теоретически, эффективнее ли удалять элементы из ArrayList
или LinkedList
?
Решение
Это "проще" (то есть более эффективно) удалить их из LinkedList
, потому что удаление из ArrayList
требует перемещения всех последующих элементов на новую позицию в списке - всех последующих элементов массиву должно быть присвоено новое значение. В случае связанного списка необходимо переназначить только один указатель (или два с двусвязным списком).
Другие советы
Ну, удаление элемента из списка (с двойной связью) - это O (1). Но удаление из массива потребует, чтобы оставшиеся элементы были сдвинуты на одну позицию в массиве, что равно O (n).
Тем не менее, получение определенного элемента в списке по индексу - это O (n), в то время как получение определенного элемента в массиве по индексу - это O (1).
Итак, для реального удаления LinkedList будет лучше. Более подробную информацию о списках Array и LinkedList можно найти здесь .