Какой лучший алгоритм из этих 2 (в Java) для удаления определенных значений в списке?

Question

Каков наилучший алгоритм из этих 2 (в Java) для удаления определенных значений в списке?
1: использование массива
2: использование связного списка

for (int i = arraylist.size()-1; i >= 0; i--) {
        if(arraylist.get(i).getValue() < 20)
            list.remove(i);
    }

или

for (int i = linkedlist.size()-1; i >= 0; i--) {
        if(linkedlist.get(i).getValue() < 20)
            list.remove(i);
    }

Кроме того, в чем сложность этих двух алгоритмов? (если в течение цикла)? Я думаю, что это O (N), но я не уверен ...

Answer 1

LinkedList

Вы не должны никогда, никогда перебирать связанный список путем индексации в нем.Индексирование в связанный список - это операция O(n).Вот пример:

1. Вы перебираете размер списка: n steps => O(n) операция.
2. Вы индексируете его, чтобы получить сохраненное значение: O(n) операция.
3. Вы индексируете в нем, чтобы удалить сохраненное значение: O(n) операция.

На каждом шаге итерации из 1. выше, вы выполняетеO (n) операция в два раза.Это 2n * O(n), что эквивалентно O(n^2).

Чтобы удалить из связанного списка за O(n) время, вам нужно использовать его внутренний механизм итератора, чтобы перебрать его и iterator.remove() элементовиз него, если они соответствуют вашим критериям.

ArarayList

Для списка на основе массива проблема заключается в том, что операция удаления является операцией O(n): элементы справа отудаленный элемент необходимо переместить влево.Переход с правой стороны ничего не решает , потому что сохраненные значения все еще нужно переместить влево, если вы удалите что-то в дальнем левом углу массива.Разбивка:

1. Вы перебираете размер списка: n steps => O(n) операция.
2. Вы индексируете его, чтобы получить сохраненное значение: O(1)операция.
3. Вы удалили сохраненное значение: O(n) операция.

Что дает вам O(n^2) производительность.

Вы не можете Удалять элементы из ArrayList без такой производительности из-за операции удаления, равной O(n) (если только массив не отсортирован и копирование части массива не считается операцией O(n)).

Answer 2

Если sortedList является экземпляром LinkedList, то второй алгоритм имеет O(n^2) сложность, поскольку linkedlist.get(i) имеет сложность O(n).