Как реализовать функцию вставки и удаления элементов в структуре данных

Что проверяют

Знаете ли вы стоимость операций в стандартных коллекциях Swift и умеете ли выбрать структуру под сценарий. Первым делом уточните, какая структура нужна и важен ли порядок элементов. Следом просят оценить сложность или написать связный список вручную.

Как отвечать

Назовите сложность по основным вариантам:

• Array: append за амортизированное O(1), insert(_:at:) и remove(at:) за O(n), потому что элементы сдвигаются. removeLast() за O(1). Удаление по значению требует поиска через firstIndex(of:), это ещё O(n);
• удаление без сохранения порядка: swapAt с последним элементом и removeLast(), после нахождения индекса это O(1);
• Set и Dictionary: вставка, удаление и проверка наличия в среднем за O(1). Элементы должны быть Hashable, порядок не гарантирован;
• связный список: вставка и удаление за O(1), если узел уже на руках, но поиск O(n) и плохая локальность памяти. На практике массив часто быстрее даже там, где по учебнику выигрывает список;
• очередь: removeFirst() у массива стоит O(n). Для очереди берут Deque из пакета swift-collections, в стандартной библиотеке его нет.

Реализацию оформляйте как struct Container<Element: Equatable> с mutating func insert(_:) и mutating func remove(_:) -> Bool. Метод удаления стоит пометить @discardableResult, иначе каждый вызов без проверки результата даёт предупреждение компилятора. Массив внутри структуры уже копируется при записи, так что семантика значения достаётся бесплатно.

Где спотыкаются

Считают вставку в массив всегда дешёвой. O(1) даёт только добавление в конец, а insert(_:at: 0) сдвигает все элементы.

Пишут двусвязный список на классах с сильными ссылками в обе стороны. Получается цикл удержания, и узлы не освобождаются: ссылку на предыдущий узел делают weak. Вторая ловушка: длинный список при освобождении рекурсивно вызывает deinit узлов и может переполнить стек, поэтому цепочку разбирают циклом.

Удаляют элементы в цикле по индексам. После remove(at:) индексы сдвигаются, элемент пропускается или получается выход за границы массива. Для фильтрации есть removeAll(where:), он проходит за O(n).