Какие основные структуры данных вы знаете и в чем их особенности?

Основные структуры данных и их характеристики:

1. Массив (Array)

   • Описание: Упорядоченная коллекция элементов с доступом по индексу.
   • Сложность операций:
     • Доступ по индексу: O(1)
     • Поиск по значению: O(n)
     • Вставка/удаление в конце: O(1) (амортизированно)
     • Вставка/удаление в середину: O(n)
   • Пример (Swift):

     var numbers = [1, 2, 3]
     numbers.append(4) // [1, 2, 3, 4]
     let firstElement = numbers[0] // 1

2. Словарь (Dictionary)

   • Описание: Хранит пары «ключ-значение». Ключи уникальны.
   • Сложность операций: В среднем O(1) для вставки, удаления и поиска по ключу.
   • Пример (Swift):

     var userAges = ["Alice": 25, "Bob": 30]
     userAges["Charlie"] = 35 // Добавление
     let age = userAges["Alice"] // 25 (Optional<Int>)

3. Множество (Set)

   • Описание: Хранит уникальные неупорядоченные элементы.
   • Сложность операций: В среднем O(1) для проверки принадлежности, вставки и удаления.
   • Пример (Swift):

     var uniqueTags: Set<String> = ["Swift", "iOS", "Swift"]
     // uniqueTags == ["Swift", "iOS"]
     print(uniqueTags.contains("iOS")) // true

4. Стек (Stack) – LIFO

   • Описание: «Последним пришел – первым ушел». Основные операции: push (добавить) и pop (удалить).
   • Сложность операций: O(1) для push и pop.
   • Пример (Swift):

     var stack = [Int]()
     stack.append(1) // push
     stack.append(2)
     let last = stack.popLast() // pop, возвращает 2

5. Очередь (Queue) – FIFO

   • Описание: «Первым пришел – первым ушел». Основные операции: enqueue (поставить в очередь) и dequeue (взять из очереди).
   • Сложность операций: Эффективная реализация обеспечивает O(1) для обеих операций.
   • Пример (Swift):

     struct Queue<T> {
         private var elements = [T]()
         mutating func enqueue(_ value: T) {
             elements.append(value)
         }
         mutating func dequeue() -> T? {
             return elements.isEmpty ? nil : elements.removeFirst() // O(n) для массива
         }
     }
     // На практике используют два стека или кольцевой буфер для O(1).

6. Связный список (Linked List)

   • Описание: Элементы (узлы) хранят значение и ссылку на следующий узел.
   • Сложность операций:
     • Вставка/удаление в начало: O(1)
     • Поиск по индексу/значению: O(n)
   • Применение: Когда важны частые вставки/удаления в начале списка.

7. Дерево (Tree), например, Бинарное дерево поиска (BST)

   • Описание: Иерархическая структура. В BST для каждого узла: левые потомки меньше, правые – больше.
   • Сложность операций: В среднем O(log n) для поиска, вставки, удаления (в сбалансированном дереве).

8. Граф (Graph)

   • Описание: Набор вершин (узлов) и ребер (связей). Бывают направленные и ненаправленные.
   • Основные алгоритмы: Поиск в ширину (BFS), поиск в глубину (DFS), Дейкстра (кратчайший путь).

Выбор структуры зависит от операций, которые будут выполняться чаще всего (чтение, запись, поиск).