Ответ
Связный список (Linked List) обеспечивает более быструю вставку элементов в начало или середину по сравнению с массивом.
Сравнение сложности операций:
| Операция | Массив (Array) | Связный список |
|---|---|---|
| Вставка в начало | O(n) | O(1) |
| Вставка в середину | O(n) | O(1) (при известном узле) |
| Вставка в конец | O(1) (амортизированно) | O(n) или O(1) с tail-указателем |
| Доступ по индексу | O(1) | O(n) |
Пример реализации на Swift:
class ListNode<T> {
var value: T
var next: ListNode?
init(_ value: T) {
self.value = value
}
}
// Вставка в начало связного списка — O(1)
func insertAtBeginning<T>(_ value: T, into list: inout ListNode<T>?) {
let newNode = ListNode(value)
newNode.next = list
list = newNode
}
// Вставка в массив в начало — O(n)
var array = [1, 2, 3, 4, 5]
array.insert(0, at: 0) // Требует сдвига всех элементовПрактические рекомендации:
- Используйте связные списки, когда частые вставки/удаления в середине структуры
- Выбирайте массивы, когда нужен быстрый доступ по индексу и последовательное хранение
- В Swift
Arrayсильно оптимизирован, поэтому для большинства случаев он предпочтительнее