Какая сложность операции удаления в LinkedList?

Какая сложность операции удаления в LinkedList

Время сложность (Time Complexity) операции удаления в LinkedList зависит от того, удаляем ли мы элемент по индексу или по значению.

Сценарии удаления

1. Удаление элемента по значению: O(n)

Время сложность: O(n) — линейная

Почему именно O(n):

• Нужно пройти по всем элементам с начала до того, как найдём нужный
• В худшем случае элемент находится в конце списка (n операций)
• В среднем случае — n/2 операций

val list: LinkedList<String> = linkedListOf("a", "b", "c", "d")
list.remove("c")  // O(n) — нужно найти элемент с индексом 2

2. Удаление элемента по индексу: O(n)

Время сложность: O(n) — линейная

Почему:

• LinkedList не может напрямую обратиться к элементу по индексу
• Нужно пройти по цепочке от начала до элемента с индексом k
• В худшем случае k = n (последний элемент)

val list: LinkedList<String> = linkedListOf("a", "b", "c", "d")
list.removeAt(2)  // O(n) — нужно пройти 2 узла до удаления

3. Удаление первого элемента (head): O(1)

Время сложность: O(1) — константная

Почему это быстрая операция:

• LinkedList хранит ссылку на первый узел (head)
• Просто перенаправляем head на следующий узел
• Не нужно обходить список

val list: LinkedList<String> = linkedListOf("a", "b", "c", "d")
list.removeFirst()  // O(1) — просто изменяем head ссылку
list.remove()       // O(1) — синоним removeFirst()

4. Удаление последнего элемента (tail): O(n)

Время сложность: O(n) — линейная

Почему так медленно:

• Нужно найти элемент перед последним
• Чтобы обновить его next ссылку
• Приходится обходить весь список

val list: LinkedList<String> = linkedListOf("a", "b", "c", "d")
list.removeLast()   // O(n) — нужно найти элемент перед tail
list.pop()          // O(n) — синоним removeLast()

Сравнение с ArrayList

Реальная реализация

// Упрощенная реализация LinkedList удаления
class LinkedList<T> {
    private var head: Node<T>? = null
    
    fun remove(value: T): Boolean {
        var current = head
        var prev: Node<T>? = null
        
        // O(n) цикл — ищем элемент
        while (current != null) {
            if (current.data == value) {
                if (prev == null) {
                    head = current.next  // Удаляем head
                } else {
                    prev.next = current.next  // Обновляем ссылку
                }
                return true
            }
            prev = current
            current = current.next
        }
        return false
    }
    
    fun removeFirst(): T? {
        val data = head?.data
        head = head?.next  // O(1) — просто переводим указатель
        return data
    }
}

Когда использовать LinkedList

Хорошо для:

• Частые insertions/deletions в начало списка
• Когда вы часто вызываете removeFirst()/removeLast()
• Нет необходимости в random access по индексу

Плохо для:

• Частый поиск по значению
• Удаление в середине или конце списка
• Доступ по индексу

Вывод

В большинстве случаев удаление в LinkedList — это O(n) операция, потому что требует поиска элемента. Исключение — удаление первого элемента, которое работает за O(1). В современных Android приложениях рекомендуется использовать ArrayList, так как операции с памятью и кешем работают быстрее, чем дополнительные операции разыменования указателей в LinkedList.