Как удалить элемент из слайса за O(1), если порядок элементов не важен?

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

Решение для удаления первого элемента:

Если нужно удалить именно первый элемент (i=0), как в вопросе:

s := []int{1, 2, 3, 4, 5}

// 1. Копируем значение последнего элемента на место первого
s[0] = s[len(s)-1]

// 2. Укорачиваем слайс, отбрасывая последний элемент
s = s[:len(s)-1]

// Результат: s = []int{5, 2, 3, 4} (порядок нарушен)

Эта операция имеет сложность O(1), так как она не зависит от размера слайса. Происходит только одно копирование значения и изменение заголовка слайса (его длины), а не перемещение всех элементов.

Обобщенная функция для удаления по индексу i:

Этот подход легко обобщить для удаления элемента по любому индексу i.

func removeUnordered[T any](slice []T, i int) []T {
    // Заменяем элемент по индексу i последним элементом
    slice[i] = slice[len(slice)-1]
    // Возвращаем слайс без последнего элемента
    return slice[:len(slice)-1]
}

s := []int{10, 20, 30, 40, 50}
s = removeUnordered(s, 2) // Удаляем элемент с индексом 2 (значение 30)
// Результат: s = []int{10, 20, 50, 40}

Важное замечание о памяти

Если слайс содержит указатели или структуры с указателями, то после удаления старый последний элемент все еще будет доступен в базовом массиве, и на него будет сохраняться ссылка, что может привести к утечке памяти. Чтобы этого избежать, нужно явно обнулить значение последнего элемента перед укорачиванием слайса.

func removeUnorderedWithGC[T any](slice []*T, i int) []*T {
    // Заменяем удаляемый элемент последним
    slice[i] = slice[len(slice)-1]
    // Обнуляем ссылку на старый последний элемент для сборщика мусора
    slice[len(slice)-1] = nil
    // Укорачиваем слайс
    return slice[:len(slice)-1]
}

Для сравнения: удаление с сохранением порядка

Если порядок важен, используется append, что приводит к сдвигу элементов и имеет сложность O(N):

i := 2
s = append(s[:i], s[i+1:]...)
// Результат: s = []int{10, 20, 40, 50} (порядок сохранен)