Какая алгоритмическая сложность операции очистки коллекции от nil-элементов?

Операция очистки коллекции от nil-элементов (или null-значений) — это фильтрация, которая удаляет все элементы, равные nil. Её алгоритмическая сложность (временная сложность) определяется тем, как организована коллекция и какой алгоритм используется для удаления.

Структуры данных и их влияние на сложность

Рассмотрим две распространённые структуры:

• Массив (Array, List, Slice): элементы хранятся в непрерывной области памяти. Прямое удаление элемента из середины требует сдвига всех последующих элементов, чтобы заполнить образовавшуюся "дыру". Если удалять каждый nil по мере обхода, это приведёт к квадратичной сложности O(n²), потому что для каждого из k nil-элементов (где k ≤ n) мы сдвигаем в среднем O(n) элементов.
• Связный список (LinkedList): каждый элемент хранит ссылку на следующий (и, возможно, предыдущий). Удаление элемента требует только обновления ссылок у соседних узлов, что делается за O(1), если у нас есть указатель на удаляемый узел. Поэтому полный обход списка с удалением nil выполняется за O(n).

Оптимизация для массивов

Для массивов можно применить алгоритм с двумя указателями (или индексами), который работает за O(n) и на месте (in-place), если допустимо изменять исходный массив. Один указатель (write) отмечает позицию, куда будет записан следующий ненулевой элемент, другой (read) проходит по всем элементам. В конце длина массива усекается до позиции write.

// Псевдокод для массива arr
write = 0
for read = 0 to arr.length - 1:
    if arr[read] != nil:
        arr[write] = arr[read]
        write++
arr.resize(write) // обрезаем массив

Этот подход использует O(1) дополнительной памяти (если не считать память под сам массив) и выполняется за O(n).

Пример на Python

В Python списки (list) являются динамическими массивами. Простой способ — использовать list comprehension, который создаёт новый список:

original = [1, None, 2, None, 3]
filtered = [x for x in original if x is not None]
# filtered = [1, 2, 3]

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

Где применяется

Очистка от nil часто нужна при обработке данных, полученных из внешних источников (например, из API, файлов), где некоторые поля могут отсутствовать или быть пустыми. Также это полезно при подготовке данных для дальнейших операций, которые не допускают nil (например, математические вычисления, построение графиков).

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