Список структур данных

Материал из Википедии — свободной энциклопедии

Это — список структур данных. Для более широкого списка см. список терминов, относящихся к алгоритмам и структурам данных.

• Линейные структуры данных (Linear data structures)
  • Список (List)
    • Массив (Array)
      • Битовые поля (Bitmaps)
        • Изображения (Images)
        • Поля высот (Heightfields)
      • Параллельный массив (Parallel array)
      • Дерево отрезков
    • Связанный список (Linked list)
      • Список с пропусками (Skip list)
      • Развёрнутый связанный список (Unrolled linked list)
      • Xor-связанный список (Xor linked list)
    • V-список (VList)
  • Ассоциативный массив (Associative array a.k.a. dictionary or map) — также известен как словарь или карта
  • Хеш-таблица (Hash table)
  • Стек (Stack a.k.a. LIFO Last in, first out) — также известен как ЛИФО
  • Очередь (Queue a.k.a. FIFO First in, first out) — также известен как ФИФО
    • Приоритетная очередь (Priority queue) — иногда выполняется в виде кучи, см. ниже
  • Дек (Deque) — двусвязная очередь
  • Буферное окно (Buffer gap)
• Граф (Graph)
  • Список рёбер (Adjacency list)
  • Представление графа в разорванном виде (Disjoint-set data structure)
  • Представление графа в виде стеков (Graph-structured stack)
  • Сценограф (Scene graph)
  • Деревья
    • M-Way Tree
      • B-дерево
    • Двоичное дерево поиска (Binary search tree)
      • Самобалансирующееся дерево поиска (Self-balancing binary search tree)
        • АВЛ-дерево (AVL tree)
        • Красно-чёрное дерево (Red-black tree)
        • Дерево со штрафами (Scapegoat tree)
        • Косое дерево (Splay tree)
        • Дерево ван Емде Боаса (van Emde Boas tree)
      • Дерево остатков (Radix tree)
      • Интервальное дерево (Interval tree)
    • Куча (Heap)
      • Двоичная куча (Binary heap)
      • Биномиальная куча (Binomial heap)
      • Фибоначчиевская куча (Fibonacci heap)
      • 2-3-куча (2-3 heap)
      • Мягкая куча (Soft heap)
    • Дерево разбора (Parse tree)
    • Квад-дерево (Quadtree) и Окт-дерево (Octree)
    • Дерево суффиксов (Suffix tree)
    • Бор Префиксное дерево (Trie)
      • Бор (Patricia trie)
• Другие структуры данных
  • Помеченное объединение (Tagged union)
  • Объединение (Union)
  • Таблица (Table)

Попытка классификации некоторых из них на основании особенностей:

Структура	Упорядоченная	Уникальная	Данных на вершину
Сумка	нет	нет	1
Множество	нет	да	1
Список	да	нет	1
Ассоциативный массив	нет	да	2

«Упорядоченная» не означает — отсортированная, только то, что исходный порядок «сохранён». Другие структуры, такие как «связанный список» и «стек» не могут легко быть определены таким образом, потому что существуют специальные операции ассоциирующиеся с ними.