array
Фиксированный набор данных одного типа в виде непрерывного ряда. Простая базовая статическая структура данных с последовательным распределением элементов в памяти с прямым или произвольным доступом (одномерный массив – вектор, двухмерный – матрица).
Операции:
- Получить элемент по индексу
О(1) - Записать элемент
О(1) - Поиск элемента в несортированном массиве
О(n), в сортированном —O(log(n))
Плюсы:
- Доступ за постоянное время
- Память тратится только на данные
Минусы:
- Статичная, неизменяемая структура
associative array, map, symbol table, dictionary
An associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection. Operations associated with this data type allow:
- the addition of pairs to the collection
- the removal of pairs from the collection
- the modification of the values of existing pairs
- the lookup of the value associated with a particular key
Ассоциативный массив еще называют нагруженным множеством (data + info), где data – ключ, а нагрузка – значение ключа. Ассоциативный массив — это абстракция и может быть реализован не только хеш-таблицей. Другие варианты:
- сбалансированное дерево (Red-Black, AVL) → O(log n)
- B-tree (часто в базах данных)
- Trie (если ключи — строки)
hash table, hash map
Ассоциативный массив, хранит пары в виде связанного списка (open hash, closed address) или массива пар (closed hash, open address). Индекс элемента равен хеш-функции от ключа i = hash(key). Разбиение множества на подмножества происходит с помощью хеш функции (пример: телефонная книга).
/// Простая реализация хеш-таблицы с цепочками (chaining)
struct HashTable<Key: Hashable, Value> {
private typealias Element = (key: Key, value: Value)
private var buckets: [[Element]]
private(set) var count = 0
private let capacity: Int
init(capacity: Int = 16) {
self.capacity = max(1, capacity)
self.buckets = Array(repeating: [], count: capacity)
}
/// Хеш-функция: берем `hashValue`, берем по модулю размер массива
private func index(for key: Key) -> Int {
return abs(key.hashValue) % capacity
}
/// Вставка или обновление значения
mutating func insert(_ value: Value, for key: Key) {
let i = index(for: key)
// Проверка: существует ли уже такой ключ — обновляем
if let indexInBucket = buckets[i].firstIndex(where: { $0.key == key }) {
buckets[i][indexInBucket].value = value
} else {
// Иначе добавляем
buckets[i].append((key, value))
count += 1
}
}
/// Получение значения по ключу
func get(_ key: Key) -> Value? {
let i = index(for: key)
return buckets[i].first(where: { $0.key == key })?.value
}
/// Проверка наличия ключа
func contains(_ key: Key) -> Bool {
return get(key) != nil
}
/// Удаление значения по ключу
mutating func remove(_ key: Key) {
let i = index(for: key)
if let indexInBucket = buckets[i].firstIndex(where: { $0.key == key }) {
buckets[i].remove(at: indexInBucket)
count -= 1
}
}
}• Хеш-функция: используем стандартный hashValue и берем по модулю capacity.
• Коллизии (если два ключа попали в одно и то же “ведро”) разрешаются цепочками — массивом кортежей.
• Все ключи уникальны, как в словаре (Dictionary).
Производительность:
• Средняя: O(1) для вставки, поиска, удаления.
• Худшая (все в одном bucket): O(n).
set
A set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set. Some set data structures are designed for static or frozen sets that do not change after they are constructed. Static sets allow only query operations on their elements — such as checking whether a given value is in the set, or enumerating the values in some arbitrary order. Other variants, called dynamic or mutable sets, allow also the insertion and deletion of elements from the set.
list
Простейшая динамическая структура, упорядоченное множество с переменным числом элементов.
linked list
doubly linked list
circular Linked list
Плюсы
- Движение в обе стороны
- Добавление элемента за
O(1)время - Удаление за
O(1)время
Минусы
- На указатели тратится дополнительная память
- Поиск только последовательный путем перебора за
O(n)
Отличие списка от массива:
Массив имеет фиксированное время перехода по индексу, но нуждается в монолитном секторе памяти, обладает нефиксированным временем вставки и удаления.
Список более требователен к памяти, дольше переход по индексу, но значительно быстрее вставка и удаление за O(1).
queue
Абстрактный тип данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, first-in-first-out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
stack
Стек – реализация очереди LIFO (last-in-first-out) и является структурированной областью памяти, в отличие от кучи. Последовательный список с переменной длинной, включение и исключение только из вершины стека. Состоит из последовательности фреймов. Пример: после вызова метода из стека выделяется запрошенная область памяти – фрейм, который хранит значения объявленных переменных.
Операции:
- Включение
- Исключение
- Определение размера
- Очистка
- Неразрушающее чтение
Функция стека – сохранить работу, невыполненную до конца, с возможностью переключения на другую работу.
/// Простая реализация стека (LIFO — последний пришёл, первый ушёл)
struct Stack<T> {
private var elements: [T] = []
/// Добавляет элемент на вершину стека
mutating func push(_ value: T) {
elements.append(value)
}
/// Удаляет и возвращает верхний элемент (если он есть)
mutating func pop() -> T? {
return elements.popLast()
}
/// Возвращает верхний элемент, не удаляя его
func peek() -> T? {
return elements.last
}
/// Проверяет, пуст ли стек
var isEmpty: Bool {
return elements.isEmpty
}
/// Количество элементов в стеке
var count: Int {
return elements.count
}
/// Очистка стека
mutating func clear() {
elements.removeAll()
}
}
double ended queue, dequeue
Очередь с двумя концами, включение и исключение из любого конца (левого или правого).
heap
Куча как структура данных представляет собой дерево, где родитель A >= ребенка B => A – корень кучи. Max куча, Min куча.
Операции:
- Найти max или min
- Удалить max или min
- Увеличить ключи или уменьшить
- Добавить
- Слияние
Куча как область памяти – реализация динамически распределяемой памяти, в которой хранятся все объекты (вызов alloc в Objective-C выделяет из кучи требуемую область памяти).
graph
Фигура, состоящая из вершин и ребер, соединяющих вершины. Направленный и ненаправленный.
tree
Связанный граф без циклов. Выделена одна вершина – корень. Остальные – сыновья. Если нет ребенка – терминальная вершина
binary search tree
Состоит из узлов (записей) вида data, left, right, где
key[left[x]] < key[x] <= key[right[x]]
Ключ данных родительского узла больше левого сына и нестрого меньше правого.
red-black tree, rb-tree
Одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».
- Узел либо красный, либо чёрный.
- Корень — чёрный. (В других определениях это правило иногда опускается. Это правило слабо влияет на анализ, так как корень всегда может быть изменен с красного на чёрный, но не обязательно наоборот).
- Все листья (NIL) — черные.
- Оба потомка каждого красного узла — черные.
- Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.
