В какую структуру данных вставлять элемент быстрее чем в массив?

Быстрый вставка элемента: альтернативы массиву

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

Связные списки (Linked Lists)

Связный список — структура, где каждый элемент (node) содержит значение и ссылку на следующий элемент. Вставка нового элемента в любую позицию требует лишь создания нового узла и изменения ссылок соседних узлов, без перемещения остальных данных.

class ListNode<T> {
    var value: T
    var next: ListNode?
    
    init(value: T, next: ListNode? = nil) {
        self.value = value
        self.next = next
    }
}

// Вставка в середину списка (пример):
func insertAfter(node: ListNode<T>, newValue: T) {
    let newNode = ListNode(value: newValue, next: node.next)
    node.next = newNode
    // Операция выполняется за O(1) — константное время
}

Преимущества для вставки:

• Вставка в начало (head) — O(1).
• Вставка после известного узла — O(1).
• Не требует перемещения памяти — только изменение ссылок.

Недостатки:

• Доступ по индексу — O(n) (нужен последовательный traversal).
• Больше памяти на хранение ссылок (next).

Деревья (Trees)

Бинарные деревья поиска (BST) или их оптимизированные версии (AVL, красно-черные) также обеспечивают эффективную вставку — O(log n) при сохранении порядка.

class TreeNode<T: Comparable> {
    var value: T
    var left: TreeNode?
    var right: TreeNode?
    
    init(value: T) {
        self.value = value
    }
}

func insert(root: TreeNode<T>?, value: T) -> TreeNode<T> {
    // Рекурсивная вставка с поиском места — O(log n) в сбалансированном дереве
}

Преимущества для вставки:

• Сбалансированные деревья обеспечивают O(log n) вставку.
• Поддержка порядка элементов без полного перестроения.

Хэш-таблицы (Hash Tables)

Для вставки без учёта порядка хэш-таблица (Dictionary в Swift) даёт почти константное время O(1) в среднем случае (при хорошей хэш-функции и отсутствии коллизий).

var dictionary = [String: Int]()
dictionary["newKey"] = 42 // Вставка за O(1)

Преимущества для вставки:

• Максимальная скорость при добавлении по ключу.
• Не зависит от размера коллекции в идеальном случае.

Вывод: что выбрать для быстрой вставки?

1. Если нужна вставка в начало/середину без индексации — используйте связный список (можно реализовать или взять готовую библиотеку).
2. Если нужен порядок и быстрая вставка/поиск — сбалансированные деревья (AVL, B-деревья).
3. Если порядок не важен, нужен быстрый доступ по ключу — хэш-таблица (Dictionary).
4. Если вставка только в конец — массив (Array) в Swift тоже эффективен (амортизированное O(1)) благодаря резервированию capacity.

В Swift для большинства задач Dictionary и специализированные деревья (через сторонние библиотеки) предпочтительнее связных списков из-за лучшей производительности в реальных сценариях и удобства API. Однако для алгоритмических задач (например, реализации очереди или стека с частыми вставками в начало) связный список остается теоретически оптимальной структурой.