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

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


java arraylist linked-list
person Johanna    schedule 23.06.2009    source источник
comment
Это действительно следует изменить. Что-то вроде. Эффективнее ли удалять элементы из ArrayList или LinkedList? Теория не имеет к этому отношения, и «проще» вводит в заблуждение.   -  person AgileJon    schedule 24.06.2009
comment
Джоанна, определите, пожалуйста, что вы имеете в виду под словом "проще". Проще для программиста или эффективнее для ЦП?   -  person Steve Kuo    schedule 24.06.2009

Ответы (3)


arrow_upward
10
arrow_downward

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

person erickson    schedule 23.06.2009

arrow_upward
5
arrow_downward

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

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

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

person GManNickG    schedule 23.06.2009
comment
Обратите внимание, что linkedList.remove(100) - это O (n). - person sulai; 08.03.2013

arrow_upward
2
arrow_downward

ArrayList внутренне использует динамический массив для хранения элементов, поэтому манипуляции с ArrayList происходят медленно, поскольку он внутренне использует массив.

Если какой-либо элемент удаляется из массива, все биты сдвигаются в памяти, в то время как LinkedList внутренне использует двусвязный список для хранения элементов.

Работа с LinkedList выполняется быстрее, чем с ArrayList, поскольку в нем используется двусвязный список, поэтому сдвиг битов в памяти не требуется.

person Ayman Amjad    schedule 12.10.2019