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 – ключ, а нагрузка – значение ключа.
hash table, hash map
Ассоциативный массив, хранит пары в виде связанного списка (open hash, closed address) или массива пар (closed hash, open address). Индекс элемента равен хеш-функции от ключа i = hash(key). Разбиение множества на подмножества происходит с помощью хеш функции (пример: телефонная книга).
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) и является структурированной областью памяти, в отличие от кучи. Последовательный список с переменной длинной, включение и исключение только из вершины стека. Состоит из последовательности фреймов. Пример: после вызова метода из стека выделяется запрошенная область памяти – фрейм, который хранит значения объявленных переменных.
Операции:
- Включение
- Исключение
- Определение размера
- Очистка
- Неразрушающее чтение
Функция стека – сохранить работу, невыполненную до конца, с возможностью переключения на другую работу.
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) — черные.
- Оба потомка каждого красного узла — черные.
- Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.